title : 2020CCPC 秦皇岛站 个人题解
date : 2022-11-21
tags : ACM,题解，练习记录
author : Linno
2020CCPC 秦皇岛站 个人题解
题目链接：https://codeforces.com/gym/102769
补题进度：5/12
A-A Greeting from Qinhuangdao
复制代码
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#include <bits/stdc++.h> using namespace std; long long n,r,b; long long gcd(long long a,long long b) { if (a%b==0) return b; else return gcd(b,a%b); } int main() { cin>>n; for (int i=1;i<=n;++i) { cin>>r>>b; if (r<1) cout<<"Case #"<<i<<": 0/1n"; else { long long p=1ll*r*(r-1); long long q=1ll*(r+b)*(r+b-1); long long g=gcd(p,q); cout<<"Case #"<<i<<": "<<p/g<<'/'<<q/g<<"n"; } } return 0; }
E-Exam Results
复制代码
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#include <bits/stdc++.h> #define int long long using namespace std; struct dat { int v,id; }c[2000005]; int T,ti,m,n,f[2000005],sum,ans,l,p,g[2000005]; bool cmp(dat a,dat b) { return a.v<b.v; } signed main() { cin>>T; while (T--) { ++ti; //cin>>n>>p; scanf("%lld%lld",&n,&p); m=0; for (int i=1;i<=n;++i) { ++m; scanf("%lld",&c[m].v); c[m].id=i; ++m; scanf("%lld",&c[m].v); c[m].id=i; } for (int i=1;i<=m;++i) g[i]=0,f[i]=0; sort(c+1,c+1+m,cmp); l=1; ans=0; sum=0; int cnt=0; //for (int i=1;i<=m;++i) cout<<c[i].v<<' '; cout<<"n"; for (int i=1;i<=m;++i) { f[c[i].id]++; if (f[c[i].id]==1) sum++; //ans=max(ans,sum); while (l<i&&c[l].v*100ll<c[i].v*p) { f[c[l].id]--; if (f[c[l].id]==0) sum--; l++; } g[c[i].id]++; if (g[c[i].id]==1) ++cnt; if (cnt>=n) ans=max(sum,ans); //cout<<i<<' '<<l<<"n"; } printf("Case #%lld: %lldn",ti,ans); } return 0; } /* 2 4 80 40 100 20 30 10 11 10 35 3 65 2 5 3 7 4 8 */
F-Friendly Group
缩点之后答案其实就变成了每一个强连通分量内部的对数减去分量大小之和了，直接计算贡献。
复制代码
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119#include<bits/stdc++.h> using namespace std; const int N=1e6+7; int read(){ int x=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x; } struct E{ int u,v,nxt; }e[N<<1]; int cnt=0,head[N]; inline void addedge(int u,int v){ e[++cnt]=(E){u,v,head[u]};head[u]=cnt; } int n,m,sz[N],eg[N]; int dfn[N],low[N],bel[N],stk[N],vis[N],top=0,idx=0; void tarjan(int x,int f){ dfn[x]=low[x]=++idx; stk[++top]=x; vis[x]=1; for(int i=head[x];i;i=e[i].nxt){ int to=e[i].v; if(!dfn[to]){ tarjan(to,x); low[x]=min(low[x],low[to]); }else if(vis[to]) low[x]=min(low[x],dfn[to]); } if(low[x]==dfn[x]){ int y; while(y=stk[top--]){ vis[y]=0; bel[y]=x; if(x==y) break; sz[x]+=sz[y]; } } } void solve(int t){ n=read();m=read(); top=0;cnt=0;idx=0; for(int i=1;i<=n;++i){ dfn[i]=low[i]=head[i]=vis[i]=eg[i]=0; bel[i]=i;sz[i]=1; } for(int i=1,u,v;i<=m;++i){ u=read();v=read(); addedge(u,v); addedge(v,u); } for(int i=1;i<=n;++i){ if(!dfn[i]){ tarjan(i,0); } } for(int i=1;i<=cnt;++i){ int fx=bel[e[i].u],fy=bel[e[i].v]; if(fx==fy){ ++eg[fx]; //记录连通分量中的边数 } } int ans=0; for(int i=1;i<=n;++i){ if(bel[i]==i){ //cout<<i<<" "<<sz[i]<<" "<<eg[i]<<"!!n"; eg[i]/=2; if(eg[i]>sz[i]) ans+=eg[i]-sz[i]; } } printf("Case #%d: %dn",t,ans); //cout<<"Case #"<<t<<": "<<ans<<"n"; } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T=1; T=read(); for(int i=1;i<=T;++i){ solve(i); } return 0; } /* 2 12 13 1 2 2 3 2 4 4 5 5 6 4 6 6 7 7 8 8 9 9 10 10 11 11 12 12 8 8 9 1 2 1 3 2 3 3 4 4 5 2 4 6 7 7 8 2 4 */
G-Good Number
复制代码
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#include<bits/stdc++.h> using namespace std; typedef long long ll; ll t; ll n,k; const ll mod=1e9+7; inline ll qpow(ll a,ll b) { ll ans=1; int f=0; while(b) { if(b&1) { ans=ans*a; if(ans>mod) { return -1; } } b>>=1; a*=a; if(b>0) { if(a>mod) { return -1; } } } return ans; } int main() { scanf("%lld",&t); ll zz=0; while(t--) { zz++; scanf("%lld%lld",&n,&k); if(k==1) { printf("Case #%lld: %lldn",zz,n); } else { ll ans=0; ll t1,t2; for(ll i=1;i<=n;++i) { t1=qpow(i,k); t2=qpow(i+1ll,k); if(t1==-1) { break; } if(t1>n) { break; } if(t2>n||t2==-1) { if((n-t1+1)%i) ans+=(n-t1+1)/i+1; else ans+=(n-t1+1)/i; break; } else { if((t2-t1)%i) ans+=(t2-t1)/i+1; else ans+=(t2-t1)/i; } //cout<<ans<<" "; } printf("Case #%lld: %lldn",zz,ans); } } }
K-Kingdom’s Power
直接就子树按深度排序后，我们可以考虑走到下一个叶子结点是从根转移还是从上一次行军的叶子节点转移，而后者可以通过dfs的时候回退实现记录步数。
复制代码
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
94#include<bits/stdc++.h> //#define int long long //using namespace std; const int N=1e6+1; int read(){ int x=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x; } int n,ans,dt,dd,deg[N]; std::vector<int>G[N]; int dep[N],sz[N],son[N],fa[N],bel[N],vis[N],lst,mdep[N]; bool cmp(int& a,int& b){ return mdep[a]<mdep[b]; } void dfs1(int x){ //sz[x]=1; mdep[x]=dep[x]; for(auto to:G[x]){ if(to==fa[x]) continue; dep[to]=dep[x]+1; dfs1(to); if(mdep[to]>mdep[x]) mdep[x]=mdep[to]; } sort(G[x].begin(),G[x].end(),cmp); //子树按深度排序 } void dfs3(int x){ if(deg[x]==1){ if(!lst) ans+=dep[x]; else{ dt=dd+dep[x]-dep[lst]; if(dt>=dep[x]) ans+=dep[x]; else ans+=dt; } lst=x;dd=0; } for(auto to:G[x]){ if(to==fa[x]) continue; dfs3(to); if(lst==to){ lst=x;++dd; //向上移动的距离 } } } void solve(int t){ n=read(); //n=1000000; ans=0;lst=0; for(int i=1;i<=n;++i){ G[i].clear();deg[i]=0; son[i]=mdep[i]=0; } for(int i=2;i<=n;++i){ fa[i]=read(); //x=rand()%i; G[fa[i]].emplace_back(i); ++deg[fa[i]];++deg[i]; } dfs1(1); //dfs2(1,1); dfs3(1); printf("Case #%d: %dn",t,ans); } signed main(){ // ios::sync_with_stdio(0); // cin.tie(0);cout.tie(0); int t=read(); for(int i=1;i<=t;++i){ solve(i); } return 0; } /* 5 3 1 1 6 1 2 3 4 4 8 1 1 2 3 7 4 4 5 1 1 1 1 8 1 2 3 3 5 5 7 */
最后
以上就是纯真黑米最近收集整理的关于2020CCPC 秦皇岛站 个人题解2020CCPC 秦皇岛站 个人题解的全部内容，更多相关2020CCPC内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复