E. Making Anti-Palindromes地址跳转若n为奇数或某个数字出现的次数n/2不合法先统计出所有的非法对发现通过一次交换 非法对的个数可能少2也可能少1尽可能多地让非法对的个数少2记最大的非法对的字符是x总非法对数为kx的对数为cntx若cntxk/2那么需要的交换次数为cntx因为每对x都需要一次交换若cntxk/2那么需要的交换次数为k/2发现k/2次交换每次均可以让非法对的个数少2(k为奇数时最后一次交换只能少1所以答案为k/2上取整)先判掉不合法的情况n为奇数或某个字符出现的次数n/2memset(num,0,sizeof(num));cinn;for(inti1;in;i){cinc[i];num[c[i]-a];}if(n%2){cout-1endl;return;}intmaxx0;for(inti0;i26;i){if(num[i]maxx)maxxnum[i];}if(maxxn/2){cout-1endl;return;}统计出总的非法对数和最大的非法对数的字符所对应的非法对数memset(num,0,sizeof(num));for(inti1;in/2;i){if(c[i]c[n-i1])cnt,num[c[i]-a];}maxx0;for(inti0;i26;i){if(maxxnum[i])maxxnum[i];}通过比较总的非法对数和非法对数最多的字符所对应的非法对数来得出需要交换的次数if(maxx*2cnt)cnt(cnt1)/2;elsecntmaxx;coutcntendl;完整代码#includebits/stdc.h#defineintlonglong#defineendl\nusingnamespacestd;constintN200010;intn,cnt;charc[N];intnum[30];voidsolve(){cnt0;memset(num,0,sizeof(num));cinn;for(inti1;in;i){cinc[i];num[c[i]-a];}if(n%2){cout-1endl;return;}intmaxx0;for(inti0;i26;i){if(num[i]maxx){maxxnum[i];}}if(maxxn/2){cout-1endl;return;}memset(num,0,sizeof(num));for(inti1;in/2;i){if(c[i]c[n-i1])cnt,num[c[i]-a];}maxx0;for(inti0;i26;i){if(num[i]maxx)maxxnum[i];}if(maxx*2cnt)cnt(cnt1)/2;elsecntmaxx;coutcntendl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cint;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]特判掉根据状态转移写dpconstintN2001;inta[N][N],b[N*N];intcnt1;for(inti1;i2000;i){for(intj1;ji;j){a[i][j]cnt*cnta[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;cinn;coutb[n]endl;完整代码#includebits/stdc.h#defineintlonglong#defineendl\nusingnamespacestd;constintN2001;inta[N][N],b[N*N];voidsolve(){intn;cinn;coutb[n]endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intcnt1;for(inti1;i2000;i){for(intj1;ji;j){a[i][j](i1)?1:cnt*cnta[i-1][j-1]a[i-1][j]-a[i-2][j-1];b[cnt]a[i][j];cnt;}}intt;cint;while(t--)solve();return0;}E. Round Dance地址跳转并查集intfind(intx){if(fa[x]!x)fa[x]find(fa[x]);returnfa[x];}读入每个数for(inti1;in;i){cina[i],fa[i]i,du[i]0;}构建并查集并给每个数的度数打上标记for(inti1;in;i){intui,va[i];fa[find(u)]find(v);!vis[{u,v}](du[u],du[v]);vis[{u,v}]vis[{v,u}]1;}统计有多少个集合统计有多少个度为1的点for(inti1;in;i){st.insert(fa[i]);if(du[i]1)cnt;}最大值即为set st 的数量每两个cnt为1的点就可以首尾相连减去一个集合数量最小值为min(st.size(),st.size()-cnt/21);coutmin(st.size(),st.size()-cnt/21) st.size()endl;完整代码#includebits/stdc.h#defineintlonglong#defineendl\nusingnamespacestd;constintN200010;setintst;mappairint,int,boolvis;intn,cnt;intdu[N];intfa[N],a[N];intfind(intx){if(fa[x]!x)fa[x]find(fa[x]);returnfa[x];}voidsolve(){cinn;st.clear();cnt0;vis.clear();for(inti1;in;i){cina[i],fa[i]i,du[i]0;}for(inti1;in;i){intui,va[i];fa[find(u)]find(v);!vis[{u,v}](du[u],du[v]);vis[{u,v}]vis[{v,u}]1;}for(inti1;in;i){st.insert(find(i));cnt(du[i]1);}coutmin(st.size(),st.size()-cnt/21) st.size()endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cint;while(t--)solve();return0;}