Codeforces Round #819 (Div. 1 + Div. 2) A-D
过程
本场A小磕一下，浪费了一点时间，随后B的迷惑题面浪费大量时间，心态发生了变化，不过最后还是在强猜后蒙过了，C又浪费了大量时间尝试，还好最后用非常简单的方法A了，D一上来就打了个随机化，可惜用了cin，用了scanf就能过，之后又把复杂度正确的标准做法补了。然后好像因为F是原然后unr，差点掉大分。(普通cin已死，不如scanf或快读)。
A
题意：最大化\(a_n-a_1\)，为此你可进行一次操作，选择一个区间\([l,r]\)然后可将该区间内的数向前轮换任意次，即\(a_l=a_{l+1},a_{l+1}=a_{l+2}....a_{r-1}=a_r,a_r=a_l\)
分析：首先任意相邻的两数都可以做首和尾；
然后保持\(a_1\)不变，任意数可做尾；
同样保持\(a_n\)不变，任意数可做头；
因为区间左边为1,当右边为n时，相当于第一种情况，右边不为n时相当于第二种情况。
当区间左边不为1，当右边为n时，相当于第三种情况，右边不为n时，\(a_n-a_1\)已经确定。
综上只有三种情况。
void solve(){
int n;cin>>n;
vector<int>a(n+1);
rep(i,1,n) cin>>a[i];
int b1=0,b2=0,b3=0;
rep(i,1,n){
b1=max(b1,a[i]-a[1]);
b2=max(b2,a[n]-a[i]);
}
rep(i,1,n-1){
b3=max(b3,a[i]-a[i+1]);
}
cout<<max(b1,max(b2,b3))<<endl;
}
B
题意：称一个数组a为有趣的，当且仅当对于每一个\(a_i\)，\(p_i\)为a数组中严格小于\(a_i\)的数的异或和，满足所有\(p_i\)=0。询问是否存在一个长度为n的有趣的数组满足\(\sum a_i=m\)
分析：
首先因为\(a_i\geq1\)，所以当\(n>m\)情况不合法；
当n为奇数时，我们可以有n-1个1，然后一个m-n+1，这样所有\(p_i\)都为0，满足题意。
当n为偶数时，如果m为奇数，假设n-2个数相互异或为0，那么n个数中一定有一个落单的奇数和落单的偶数， 那么其中较大数的\(p_i\)必不为0，此时无解；如果m为偶数，那么首先n-2个1，在两个\(\frac{n-m+2}{2}\)即可。
事实上只要除最大数外，其他数出现次数均为偶数即可满足有趣的数组的条件。
void solve(){
int n,m;
cin>>n>>m;
if(n>m) ptn;
else {
if(n&1){
pty;
cout<<m-n+1<<" ";
rep(i,1,n-1) cout<<1<<" ";
pts;
}
else{
if(m&1) ptn;
else{
pty;
rep(i,1,n-2) cout<<1<<' ';
m-=n-2;
cout<<m/2<<" "<<m/2<<endl;
}
}
}
}
C
题意：
给定一个长度为2*n的合法括号序列，如果区间[l,r]为合法的括号序列，那么认为点l到r之间有一条边，问最后生成的图中连通块的数量。
分析：
这题方法好像很多，这里说说我的。
首先对于包含关系的必然是不相连的两个连通块，例如\(((()))\)，那么各层的括号是相互独立的，联通的情况为括号并列时，\(()()\)即为基础情况，此时可合成一个连通块，每处现一次并列，变出现一次联通，连通块总数少一，那么什么时候出现并列呢，当且仅当\()\)后出现\((\)，此时这两个括号所构成的合法括号序列一定是可以联通的，由此计数，用总连通块个数n减去即可。
char s[maxn];
void solve(){
int n;cin>>n;
cin>>(s+1);
int sum=0;
rep(i,2,n<<1){
if(s[i]=='('&&s[i-1]==')') sum++;
}
cout<<n-sum<<endl;
}
D
题意：
给定一个n个点m条边无向图，其中\(m\leq n+2\),对每条边进行红蓝染色，使得在仅考虑红边和蓝边的情况时，形成连通块的总和最小，并输出方案。
分析：
因为要形成连通块的总数最小，那么我们是不期望出现环的，因为环会浪费一条边，因此应将图拆成两个森林，此时因为边没有被浪费，因此
m=n-1,cost=n+2
m=n ,cost=n+1
m=n+1,cost=n
m=n+2,cost=n-1
为最佳情况，故此时我们只需要分配边使得红边和蓝边均不出现环即可。
首先直接先对红边进行生成树，如果运气好红边生成树后，剩下的蓝边没有环，否则的话：
随机化做法：将边顺序打乱，重新生成树。
正确做法：选择一条蓝边中的一个端点，将这个端点连接的所有边变为蓝边，而原来的蓝边变为红边，此时可保证单独考虑某种颜色时一定是森林。
另外这道题数入很多，本来我随机化都过了，结果写了cin一直T，改了scanf就过了。
随机化
struct DSU{
vector<int>fa;
void build(int n){
fa.clear();fa.resize(n+1);
rep(i,1,n) fa[i]=i;
}
int find(int x){return x==fa[x]? x:fa[x]=find(fa[x]);}
void merge(int x,int y){
fa[find(x)]=find(y);
}
int same(int x,int y){
return find(x)==find(y);
}
}d1,d2;
struct node{int u,v,id;};
char ans[maxn];
vector<node>G;
int n,m;
bool check(){
d1.build(n),d2.build(n);
rep(i,0,m-1){
if(d1.same(G[i].u,G[i].v)) {
if(d2.same(G[i].u,G[i].v)) return 0;
d2.merge(G[i].u,G[i].v);ans[G[i].id]='0';
}
else ans[G[i].id]='1',d1.merge(G[i].u,G[i].v);
}
return 1;
}
bool cmp(node a,node b){return a.u==b.u? a.v<b.v:a.u<b.u;}
void solve(){
scanf("%d %d",&n,&m);
G.clear();
rep(i,1,m){
int u,v;scanf("%d %d",&u,&v);
G.pb((node){u,v,i});
}
sort(G.begin(),G.end(),cmp);
while(1){
if(check()) break;
random_shuffle(G.begin(),G.end());
}
rep(i,1,m)
putchar(ans[i]);
pts;
}
复杂度稳定正解
int fa[maxn];
int find(int x){return x==fa[x]? x:fa[x]=find(fa[x]);}
P G[maxn];
int ans[maxn];
map<int,int>cnt;
void solve(){
int n,m;scanf("%d %d",&n,&m);
rep(i,1,m){
int u,v;scanf("%d %d",&u,&v);
G[i]={u,v};
}
rep(i,1,n) fa[i]=i;
vector<int>tmp;
rep(i,1,m){
int u=G[i].first,v=G[i].second;
u=find(u),v=find(v);
if(u==v){
tmp.pb(i);
ans[i]=0;
}
else fa[u]=v,ans[i]=1;
}
bool flag=0;
cnt.clear();
for(auto x:tmp) cnt[G[x].first]++,cnt[G[x].second]++;
int mx=-1,mn=inf;
for(auto x:cnt) mx=max(mx,x.second),mn=min(mn,x.second);
if(mx==mn) flag=1;
if(flag){
int now=G[tmp[0]].first;
rep(i,1,m){
if(G[i].second==now||G[i].first==now) ans[i]=0;
}
ans[tmp[0]]=1;
}
rep(i,1,m)
putchar(ans[i]+'0');
pts;
}