长乐国庆集训Day1 - c++编程基础

TOP

长乐国庆集训Day1(二)

2019-10-09 19:57:16 【大中小】浏览:80次

(v[x]) continue; v[x]=1; for(int i=head[x];i;i=next[i]) { int y=ver[i],z=edge[i]; if(d[y]>d[x]+z) { d[y]=d[x]+z; q.push(make_pair(-d[y],y)); } } } for(int i=1;i<=tot;i++) { int x=from[i],y=ver[i],z=edge[i]; if(d[x]+z==d[y]) deg[y]++; } for(int i=1;i<=n;i++) if(deg[i]) ans=(1LL*ans*deg[i])%mod; } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; add(x,y,z); add(y,x,z); } dijkstra(); cout<<ans; return 0; } View Code

T3 开根号

题目

【题目描述】

【输入格式】

输入包含多组数据。每组数据包含一行两个正整数L,R。

文件以0 0结尾（结尾不需要输出）。

【输出格式】

对于每组数据，输出一行表示答案。保证答案在[0,2⁶³)范围内。

【样例输入】

2 10
248832 248832
0 0

【样例输出】

13
5

【数据规模】

解析

可怕的数论题~~~

先把区间求和用前缀和表示，所以只需求[1,n]的答案。

依次求每个数的f(i)很麻烦，考虑求[1,n]中f(i)=k的个数，其个数用g(k)表示。

用p(k)表示[1,n]中开k次方还是正整数的数的个数，可以得到p(k)=n^1/k(向下取整)。

则。

所以用递推推出答案就可以了。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps=1e-10;
long long l,r,f[100];
long long solve(long long x)
{
    if(x<2) return 1;
    int num=0;
    for(int i=63;i>=2;i--)
    {
        f[i]=(long long)(pow(x,(double)1.0/i)+eps)-1;
        for(int j=i+i;j<=63;j+=i) f[i]-=f[j];
        num+=f[i]*(i-1); 
    }
    return num+x;
}
int main()
{
    cin>>l>>r;
    while(l!=0&&r!=0)
    {
        cout<<solve(r)-solve(l-1)<<endl;
        cin>>l>>r;
    }
    return 0;
}

View Code

T4 旅行

题目

【题目描述】

【输入格式】

第一行包含两个非负整数n,k，含义如【题目描述】所述。

接下来n-1行，每行三个正整数u,v,w，表示u,v之间有一条边权为w的边。

【输出格式】

输出一行一个整数，表示答案。保证存在合法解。

【输入样例】

【输出样例】

【数据规模】

解析

不难发现：

dis(u,v)=dis(u,1)+dis(v,1)。
如果经过的边数为奇数，那么必定有一个点的深度为奇数，另一个点的深度为偶数。

所以将所有点按深度的奇偶来分类，于是就有了两个序列a，b，只需求a_i+b_i的第k小值即可。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
const int N=100010;
struct node
{
    long long v;
    int p;
    node(long long a,int b):v(a),p(b){}
    bool operator < (const node &a) const
    {
        return v>a.v;
    }
};
priority_queue<node> q;
int head[N],ver[N<<1],edge[N<<1],next[N<<1],tot;
long long dis[N],deep[N],a[N],b[N],cnta,cntb;
void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z,next[tot]=head[x],head[x]=tot;
}
void dfs(int x,int fa)
{
    for(int i=head[x];i;i=next[i])
    {
        int y=ver[i],z=edge[i];
        if(y==fa) continue;
        dis[y]=-dis[x]+z,deep[y]=deep[x]+1;
        dfs(y,x);
    }
}
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n-1;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
        if(deep[i]&1) a[++cnta]=dis[i];
        else b[++cntb]=dis[i];
    sort(b+1,b+cntb+1);
    for(int i=1;i<=cnta;i++) q.push(node(a[i]+b[1],i));
    for(int i=1;i<=cnta;i++) head[i]=1;    
    while(k>1)
    {
        node t=q.top();
        q.pop();
        if((++head[t.p])<=cntb) q.push(node(a[t.p]+b[head[t.p]],t.p));

首页上一页 1 2 3 下一页尾页 2/3/3
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：交换排序	下一篇：洛谷 P1079 Vigenère 密码