概述
title : 2020CCPC 秦皇岛站 个人题解
date : 2022-11-21
tags : ACM,题解，练习记录
author : Linno
2020CCPC 秦皇岛站 个人题解
题目链接：https://codeforces.com/gym/102769
补题进度：5/12
A-A Greeting from Qinhuangdao
#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
#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
缩点之后答案其实就变成了每一个强连通分量内部的对数减去分量大小之和了，直接计算贡献。
#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
#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的时候回退实现记录步数。
#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 秦皇岛站 个人题解2020CCPC 秦皇岛站 个人题解所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复