# Codeforces round #469 (div. 2) 解题报告

## 智商round

Posted by yjjr's blog on March 10, 2018

# A. Left-handers, Right-handers and Ambidexters

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
#define pi acos(-1)
#define mp make_pair
#define pb push_back
#define pa pair<int,int>
#define fi first
#define se second
#define lowbit(x) ((x)&(-x))
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll getgcd(ll x,ll y){return !x?y:getgcd(y%x,x);}
inline ll getlcm(ll x,ll y){return x/getgcd(x,y)*y;}
inline ll qpow(int x,int y,int p){
ll re=1;
while(y){
if(y&1)re=(re*x)%p;
y>>=1,x=(x*x)%p;
}
return re;
}
int l,r,a,ans;
int main()
{
ans=min(l,r);
int tmp=max(l,r)-min(l,r);
if(a<tmp)ans+=a;else ans=max(l,r),a=a-tmp,ans+=(a/2);
cout<<ans*2<<endl;
return 0;
}


# B. Intercepted Message

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
#define pi acos(-1)
#define mp make_pair
#define pb push_back
#define pa pair<int,int>
#define fi first
#define se second
#define lowbit(x) ((x)&(-x))
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll getgcd(ll x,ll y){return !x?y:getgcd(y%x,x);}
inline ll getlcm(ll x,ll y){return x/getgcd(x,y)*y;}
inline ll qpow(int x,int y,int p){
ll re=1;
while(y){
if(y&1)re=(re*x)%p;
y>>=1,x=(x*x)%p;
}
return re;
}
const int maxn=1e6+6;
int ans,a[maxn],b[maxn],n,m;
int main()
{
int i=1,j=1;ll s1=a[i],s2=b[j];
while(i<=n&&j<=m){
if(s1<s2){s1+=a[++i];continue;}
if(s1>s2){s2+=b[++j];continue;}
if(s1==s2){ans++;s1=a[++i],s2=b[++j];continue;}
}
cout<<ans<<endl;
return 0;
}


# C. Zebras

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
#define pi acos(-1)
#define mp make_pair
#define pb push_back
#define pa pair<int,int>
#define fi first
#define se second
#define lowbit(x) ((x)&(-x))
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll getgcd(ll x,ll y){return !x?y:getgcd(y%x,x);}
inline ll getlcm(ll x,ll y){return x/getgcd(x,y)*y;}
inline ll qpow(int x,int y,int p){
ll re=1;
while(y){
if(y&1)re=(re*x)%p;
y>>=1,x=(x*x)%p;
}
return re;
}
const int maxn=2e5+6;
int n,m,k,num;char s[maxn];
vector<int> a[maxn];
int main()
{
scanf("%s",s+1);
int len=strlen(s+1);
rep(i,1,len){
if(s[i]=='0')a[++num].pb(i);
else{
if(!num){puts("-1");return 0;}
a[num--].pb(i);
}
k=max(k,num);
}
if(k!=num){puts("-1");return 0;}
printf("%d\n",k);
rep(i,1,k){
printf("%d ",a[i].size());
for(int j=0;j<a[i].size();j++)printf("%d ",a[i][j]);printf("\n");
}
return 0;
}


# D. A Leapfrog in the Array

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
#define pi acos(-1)
#define mp make_pair
#define pb push_back
#define pa pair<int,int>
#define fi first
#define se second
#define lowbit(x) ((x)&(-x))
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll getgcd(ll x,ll y){return !x?y:getgcd(y%x,x);}
inline ll getlcm(ll x,ll y){return x/getgcd(x,y)*y;}
inline ll qpow(int x,int y,int p){
ll re=1;
while(y){
if(y&1)re=(re*x)%p;
y>>=1,x=(x*x)%p;
}
return re;
}
ll n,q,x;
int main()
{
while(q--){
while(!(x&1))x=(x>>1)+n;
printf("%I64d\n",(x+1)>>1);
}
return 0;
}


# E. Data Center Maintenance

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
#define pi acos(-1)
#define mp make_pair
#define pb push_back
#define pa pair<int,int>
#define fi first
#define se second
#define lowbit(x) ((x)&(-x))
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll getgcd(ll x,ll y){return !x?y:getgcd(y%x,x);}
inline ll getlcm(ll x,ll y){return x/getgcd(x,y)*y;}
inline ll qpow(int x,int y,int p){
ll re=1;
while(y){
if(y&1)re=(re*x)%p;
y>>=1,x=(x*x)%p;
}
return re;
}
#define inf 0x3f3f3f3f
const int maxn=1e5+6;
struct edge{int to,next;}e[maxn<<2];
int last[maxn],n,top,cnt,m,h,tim,scc,t[maxn],dfn[maxn],low[maxn],que[maxn<<2];
int dg[maxn],belong[maxn],re=inf,pos;
bool inque[maxn];
vector<int>ans[maxn];
void insert(int u,int v){
e[++cnt]=(edge){v,last[u]};last[u]=cnt;
}
void tarjan(int x){
int now=0;
dfn[x]=low[x]=++tim;
que[++top]=x;inque[x]=1;
reg(x)
if(!dfn[e[i].to]){tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);}
else if(inque[x])low[x]=min(low[x],dfn[e[i].to]);
if(low[x]==dfn[x]){
scc++;
while(now!=x){
now=que[top--];
inque[now]=0;belong[now]=scc;ans[scc].pb(now);
}
}
}

int main()
{
rep(i,1,m){
if((t[c1]+1)%h==t[c2])insert(c1,c2);
if((t[c2]+1)%h==t[c1])insert(c2,c1);
}
rep(i,1,n)
if(!dfn[i])tarjan(i);
rep(u,1,n)
reg(u)
if(belong[u]!=belong[e[i].to])dg[belong[u]]++;
rep(i,1,scc)
if(dg[i]==0&&ans[i].size()<re)re=ans[i].size(),pos=i;
printf("%d\n",re);
for(int i=0;i<ans[pos].size();i++)printf("%d ",ans[pos][i]);
printf("\n");
return 0;
}


# 总结

C题题意卡了半小时（感觉我每次打的实时CF场都是阅读理解大赛）

AB写题这次准确度挺高的

Pascal->C++选手对STL使用还不是很熟练啊（话说熟练运用些常用的应该就行了吧）

D题应该分类讨论的，我一直往各种数列上去想，还是要多做做数学题啊