cf比賽賽程，【codeforces】【比賽題解】#950 CF Round #469 (Div. 2)

劇毒比賽，至少漲了分對吧。: (

【A】Left-handers, Right-handers and Ambidexters

cf比賽賽程、題意：

有\(l\)個右撇子，\(r\)個左撇子，\(a\)個雙手都慣用的人。

要讓他們組成兩個隊伍，一邊用左手，一邊用右手，這兩個隊伍人數要相同。

cf總決賽比賽視頻、問最大人數。

題解：

隨便搞……

#include<bits/stdc++.h>
using namespace std;
int l,r,a;
int main(){scanf("%d%d%d",&l,&r,&a);if(l>r) swap(l,r);if(l+a<=r) {printf("%d",(l+a)*2); return 0;}printf("%d",(l+a+r)/2*2);return 0;
}

codeforces卡？【B】Intercepted Message

題意：

有兩個數組\(x_1,x_2,\cdots,x_n\)，\(y_1,x_2,\cdots,y_m\)。

cfs比賽，要把這兩個數組分成若干個子串（個數相等，從左到右一一對應）。

并且每個對應子串的和相等，問最多子串個數。

題解：

cf比賽回放。貪心，雙指針掃過去。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
int n,m,ans;
int a[100001],b[100001];
int main(){scanf("%d%d",&n,&m);F(i,1,n) scanf("%d",a+i);F(i,1,m) scanf("%d",b+i);int l=1,sum1=0,sum2=0;F(i,1,n){sum1+=a[i];while(sum2+b[l]<=sum1) sum2+=b[l] ,++l;if(sum2==sum1) ++ans, sum1=sum2=0;}printf("%d",ans);return 0;
}

【C】Zebras

題意：

codeforces中文官網。給定一個01串，把它分成若干個子序列的并，不重復不遺漏。

并且要滿足每個子序列都是斑馬序列。

斑馬序列的定義是，以0開始，01交替出現，并且以0結尾的字符串。

如果可行，輸出任意方案，不可行輸出-1。

題解：

set暴力上貪一波心。01分開set，能選就選。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
using namespace std;
int n;
int arr[200007],tot,cnt;
char str[200007];
vector<int> ans[200007];
set<int> st1,st2;
set<int>::iterator iter;
int main(){scanf("%s",str+1);n=strlen(str+1);F(i,1,n) if(str[i]=='0') st1.insert(i); else st2.insert(i);while(!st1.empty()){++tot;int lst=*st1.lower_bound(0);st1.erase(lst);ans[tot].push_back(lst);while(1){int tmp1,tmp2;iter=st2.lower_bound(lst);if(iter==st2.end()) break;tmp1=*iter;iter=st1.lower_bound(tmp1);if(iter==st1.end()) break;tmp2=*iter;st2.erase(tmp1), st1.erase(tmp2);ans[tot].push_back(tmp1);ans[tot].push_back(tmp2);lst=tmp2;}}if(!st2.empty()){puts("-1"); return 0;}printf("%d\n",tot);F(i,1,tot){printf("%d ",ans[i].size());F2(j,0,ans[i].size()) printf("%d ",ans[i][j]);puts("");}return 0;
}

【D】A Leapfrog in the Array

題意：略復雜，看原來的題面。

題解：

瞎找規律。

當前的len一開始為n，如果位置pos在這一串的"固定點"(一開始為奇數位)上，直接輸出。

否則進行一波跳，len大致減半，pos大致減半，固定點的奇偶性隨著len的奇偶性改變，答案加上跳過的數。

這么一波分類討論一下就OK。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
typedef long long ll;
ll n; int q;
int main(){scanf("%lld%d",&n,&q);F(i,1,q){ll x, ans=0, len=n;int k=0;scanf("%lld",&x);while(x%2==k){ans+=k==0?(len+1)/2:len/2;x=(x+k)/2;int len2=len;len=k==0?len/2:(len+1)/2;k^=(len2&1);}printf("%lld\n",ans+(x+(k^1))/2);}return 0;
}

【E】Data Center Maintenance

題意：略復雜，看原來的題面。

題解：

對于兩個數據中心，如果有一個數據保存在這兩個數據中心中，并且這兩個數據中心的維護時間差1小時，那么如果其中一個時間小的移動了維護時間，另一個必然也要移動。

這是一個連鎖反應，我們先把這種關系連成有向圖。

那么對于一個圈，要不然全部取要不然全部不取。所以先強連通分量縮一波點。

然后得到一個DAG，那么如果取了一個點，它之后的所有點就都要取了，所以最佳策略是取出度為0的點。

那么就算做完了。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define eF(h,i,u) for(int i=h[u];i;i=nxt[i])
using namespace std;int n,m,H,Ans;
int Ut[100001];int h[100001],h2[100001],nxt[500001],to[500001],tot;
inline void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;h[x]=tot;}
inline void ins2(int x,int y){nxt[++tot]=h2[x];to[tot]=y;h2[x]=tot;}bool vis[100001];
int dfn[100001],idf[100001],siz[100001],SCC[100001],Out[100001],cnt,CCn;int h3[100001];
inline void ins3(int x,int y){nxt[++tot]=h3[x];to[tot]=y;h3[x]=tot;}bool check(int Ut1,int Ut2){return (Ut2-Ut1+H)%H==1;}void init(){int x,y;scanf("%d%d%d",&n,&m,&H);F(i,1,n) scanf("%d",Ut+i);F(i,1,m){scanf("%d%d",&x,&y);if(check(Ut[x],Ut[y])) ins(x,y),ins2(y,x);if(check(Ut[y],Ut[x])) ins(y,x),ins2(x,y);}
}void DFS1(int u){vis[u]=1;eF(h,i,u)if(!vis[to[i]]) DFS1(to[i]);dfn[u]=++cnt; idf[cnt]=u;
}void DFS2(int u){vis[u]=1; SCC[u]=CCn; ++siz[CCn]; ins3(CCn,u);eF(h2,i,u)if(!vis[to[i]]) DFS2(to[i]);
}void Kosaraju(){F(i,1,n) if(!vis[i]) DFS1(i);memset(vis,0,sizeof vis);dF(i,n,1) if(!vis[idf[i]]) ++CCn, DFS2(idf[i]);F(u,1,CCn){eF(h3,i,u)eF(h,j,to[i])if(SCC[to[j]]!=u)Out[u]=1; goto ed;ed : ;}siz[Ans=0]=n+1;F(i,1,CCn) if(!Out[i]&&siz[Ans]>siz[i]) Ans=i;
}int main(){init();Kosaraju();printf("%d\n",siz[Ans]);eF(h3,i,Ans) printf("%d ",to[i]);return 0;
}