2017ccpc江苏省赛

自用笔记算法

2017ccpc江苏省赛

E

题意

有一些点 每个点只能被选作起点或终点一次
每次询问一个范围 若在l-r之间 结果加上l-r区间的和 l和r都不能再作为端点
求给定次数的询问后 最大的和是多少

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
#define LL long long
#define maxn 100050
using namespace std;
struct node{
    LL st,ed,sum;
}e[maxn];
LL sum[maxn];
int main(){
   // freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
      cin.tie(0);
    LL n,m,c;
    while(cin>>n>>m>>c){
        sum[0]=0;
        for(int i=1;i<=n;i++){
            LL x;
            cin>>x;
            sum[i]=sum[i-1]+x;
        }
         sort(sum,sum+n+1);
         LL ans=0,cnt=0;
         for(int i=0;i<n/2;i++){
            if(cnt==m) break;
            LL temp=abs(sum[n-i]-sum[i])-c;
            if(temp<0) break;
            ans+=temp;
            cnt++;
         }
       cout<<ans<<endl;
    }
    return 0;
}

思路&注意事项

对前n项和排序 每次用最大减去最小 得到的最大值加入到答案中
如果从某项开始已经小于0或者已经用完了询问次数 结束循环

I

题意

猜公式

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL gcd(LL a,LL b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(){
   // freopen("input.txt","r",stdin);
    LL n,m;
    while(cin>>n>>m){
        LL x=n/gcd(n,m)*m;
        cout<<"1/"<<2*x<<endl;
    }
    return 0;
}

H

题意

类似于最大生成树
每两个城市之间有一个权值
最后要求用n-1条道路联通 并要求权值最大

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
#define LL long long
#define maxn 100050
using namespace std;
struct node{
    int to,w;
    node(int to,int w):to(to),w(w){}
};
vector<node>e[maxn];
int n; 
int vis[maxn],deep[maxn],f[maxn],anc[maxn][25];
LL dis[maxn],temp[maxn];
void dfs(int x,int fa){
    anc[x][0]=f[x];
    for(int i=1;i<=20;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
    for(int i=0;i<e[x].size();i++){
        int next=e[x][i].to;
        if(next!=fa){
            f[next]=x;
            deep[next]=deep[x]+1;
            dfs(next,x);
        }
    }
}
int lca(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
    return f[x];
}
void dfs2(int id){
    for(int i=0;i<e[id].size();i++){
        int next=e[id][i].to,ww=e[id][i].w;
        if(vis[next]) continue;
        dis[next]=(LL)dis[id]+ww;
        vis[next]=1;
        dfs2(next);
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n){
        for(int i=0;i<=n;i++) e[i].clear();
        for(int i=1;i<n;i++){
            int u,v,w;
            cin>>u>>v>>w;
            e[u].push_back(node(v,w));
            e[v].push_back(node(u,w));
        }
        memset(f,0,sizeof(f));
        memset(anc,0,sizeof(anc));
        memset(deep,0,sizeof(deep));
        deep[1]=1;
        dfs(1,0);
        memset(dis,0,sizeof(dis));
        memset(vis,0,sizeof(vis));
        vis[1]=1;
        dfs2(1);
        int id1=0,id2=0;
        LL mx=0;
        for(int i=1;i<=n;i++){
            if(mx<dis[i]){
                mx=dis[i];
                id1=i;
            }
        }
        memcpy(temp,dis,sizeof(dis));
        memset(dis,0,sizeof(dis));
        memset(vis,0,sizeof(vis));
        vis[id1]=1;
        dfs2(id1);
        mx=0;
        for(int i=1;i<=n;i++){
            if(mx<dis[i]){
                mx=dis[i];
                id2=i;
            }
        }
        LL ans=-mx;
        for(int i=1;i<=n;i++){
            int f1=lca(i,id1);
            int f2=lca(i,id2);
            LL d1=temp[i]+temp[id1]-2*temp[f1];
            LL d2=temp[i]+temp[id2]-2*temp[f2];
            ans+=max(d1,d2);
        }
        cout<<ans<<endl;
    }
    return 0;
}

思路&注意事项

无根树转为有根树 默认1为根节点
用prim算法预处理出根结点1到所有点的最短距离
从结点1dfs一次找到直径的第一个端点 记录下他的id1
从id开始再进行一次dfs即可找到树的直径 记录下端点id2
把剩下的所有点加入该直径中 距离哪个端点的距离大则把该点加入
计算树中两个点的距离使用LCA

本文标题:2017ccpc江苏省赛

文章作者:Hippopmonkey

发布时间:2017-05-19, 08:01:44

最后更新:2017-10-27, 10:49:03

原始链接:http://xuboming8.github.io/2017/05/19/ccpc江苏省赛/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 2017ccpc江苏省赛
    1. 1.1. E
      1. 1.1.1. 题意
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路&注意事项
    2. 1.2. I
      1. 1.2.1. 题意
      2. 1.2.2. 参考AC代码
    3. 1.3. H
      1. 1.3.1. 题意
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路&注意事项
|