cf rating 1600

E. Making Anti-Palindromes

地址跳转

若n为奇数或某个数字出现的次数>n/2
不合法

先统计出所有的非法对
发现通过一次交换 非法对的个数可能少2也可能少1
尽可能多地让非法对的个数少2

记最大的非法对的字符是x，总非法对数为k，x的对数为cntx
若cntx>=k/2
那么需要的交换次数为cntx，因为每对x都需要一次交换
若cntx<=k/2
那么需要的交换次数为k/2
发现k/2次交换，每次均可以让非法对的个数少2
(k为奇数时，最后一次交换只能少1，所以答案为k/2上取整)

先判掉不合法的情况
n为奇数或某个字符出现的次数>n/2

memset(num,0,sizeof(num));cin>>n;for(inti=1;i<=n;i++){cin>>c[i];num[c[i]-'a']++;}if(n%2){cout<<-1<<endl;return;}intmaxx=0;for(inti=0;i<26;i++){if(num[i]>maxx)maxx=num[i];}if(maxx>n/2){cout<<-1<<endl;return;}

统计出总的非法对数，和最大的非法对数的字符所对应的非法对数

memset(num,0,sizeof(num));for(inti=1;i<=n/2;i++){if(c[i]==c[n-i+1])cnt++,num[c[i]-'a']++;}maxx=0;for(inti=0;i<26;i++){if(maxx>num[i])maxx=num[i];}

通过比较总的非法对数和非法对数最多的字符所对应的非法对数
来得出需要交换的次数

if(maxx*2<=cnt)cnt=(cnt+1)/2;elsecnt=maxx;cout<<cnt<<endl;

完整代码：

#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;constintN=200010;intn,cnt;charc[N];intnum[30];voidsolve(){cnt=0;memset(num,0,sizeof(num));cin>>n;for(inti=1;i<=n;i++){cin>>c[i];num[c[i]-'a']++;}if(n%2){cout<<-1<<endl;return;}intmaxx=0;for(inti=0;i<26;i++){if(num[i]>maxx){maxx=num[i];}}if(maxx>n/2){cout<<-1<<endl;return;}memset(num,0,sizeof(num));for(inti=1;i<=n/2;i++){if(c[i]==c[n-i+1])cnt++,num[c[i]-'a']++;}maxx=0;for(inti=0;i<26;i++){if(num[i]>maxx)maxx=num[i];}if(maxx*2<=cnt)cnt=(cnt+1)/2;elsecnt=maxx;cout<<cnt<<endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cin>>t;while(t--)solve();return0;}

G. Hits Different

地址跳转

f[i][j]=f[i-1][j-1]+f[i-1][j]-f[i-2][j-1];
当i为0时，会访问f[-1][0]，特判掉
根据状态转移写dp

constintN=2001;inta[N][N],b[N*N];intcnt=1;for(inti=1;i<=2000;i++){for(intj=1;j<=i;j++){a[i][j]=cnt*cnt+a[i-1][j-1]+a[i-1][j]-a[i-2][j-1];b[cnt]=a[i][j];cnt++;}}

预处理后，根据读入
O ( 1 ) O(1)O(1)输出

intn;cin>>n;cout<<b[n]<<endl;

完整代码：

#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;constintN=2001;inta[N][N],b[N*N];voidsolve(){intn;cin>>n;cout<<b[n]<<endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intcnt=1;for(inti=1;i<=2000;i++){for(intj=1;j<=i;j++){a[i][j]=(i==1)?1:cnt*cnt+a[i-1][j-1]+a[i-1][j]-a[i-2][j-1];b[cnt]=a[i][j];cnt++;}}intt;cin>>t;while(t--)solve();return0;}

E. Round Dance

地址跳转

并查集

intfind(intx){if(fa[x]!=x)fa[x]=find(fa[x]);returnfa[x];}

读入每个数

for(inti=1;i<=n;i++){cin>>a[i],fa[i]=i,du[i]=0;}

构建并查集，
并给每个数的度数打上标记

for(inti=1;i<=n;i++){intu=i,v=a[i];fa[find(u)]=find(v);!vis[{u,v}]&&(du[u]++,du[v]++);vis[{u,v}]=vis[{v,u}]=1;}

统计有多少个集合
统计有多少个度为1的点

for(inti=1;i<=n;i++){st.insert(fa[i]);if(du[i]==1)cnt++;}

最大值即为set st 的数量
每两个cnt为1的点，就可以首尾相连，减去一个集合数量
最小值为min(st.size(),st.size()-cnt/2+1);

cout<<min(st.size(),st.size()-cnt/2+1)<<' '<<st.size()<<endl;

完整代码：

#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;constintN=200010;set<int>st;map<pair<int,int>,bool>vis;intn,cnt;intdu[N];intfa[N],a[N];intfind(intx){if(fa[x]!=x)fa[x]=find(fa[x]);returnfa[x];}voidsolve(){cin>>n;st.clear();cnt=0;vis.clear();for(inti=1;i<=n;i++){cin>>a[i],fa[i]=i,du[i]=0;}for(inti=1;i<=n;i++){intu=i,v=a[i];fa[find(u)]=find(v);!vis[{u,v}]&&(du[u]++,du[v]++);vis[{u,v}]=vis[{v,u}]=1;}for(inti=1;i<=n;i++){st.insert(find(i));cnt+=(du[i]==1);}cout<<min(st.size(),st.size()-cnt/2+1)<<' '<<st.size()<<endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cin>>t;while(t--)solve();return0;}