总分第一题30分钟100分第二题50分钟100分第三题50分钟 40分第四题50分钟 20分比赛过程我用了30分钟把第一题的大样例给成功AC了第二题我想到了思路并用了50分钟成功AC结果最后两题根本不会于是进行骗分最终成功骗到60分。第一题比较简单的一道题很像哈希表AC代码#includeiostream #includecstdio using namespace std; int n,m,a,b; bool f[1005],ff; int main(){ freopen(cabinet.in,r,stdin); freopen(cabinet.out,w,stdout); ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinnm; for(int i1;in;i){ cinab; ff0; while(b--){ if(am1){ a1; } if(f[a]0){ f[a]1; couta\n; ff1; break; } a; } if(ff0){ cout0\n; } } return 0; }第二题题意对于a长度为n数组如果能找到一个kkn/2使a[ i ]与a[ n-ki ]交换ik最终让a数组b数组输出Yes或No对于这个题我的思路是从头开始只要a[ i ]不等于b[ i ]in/2,那就让ki.不然的话对于a[ i ]一定不会改变也就一定会不等于b[ i ]。然后再拿我们的k进行模拟得出新的a[ i ],最后再拿a[ i ]与b[ i ]比较如果还不相等就coutNoAC代码#includeiostream #includecstdio using namespace std; const int I1e65; int n,a[I],b[I],t,p,k; bool f[I]; int main(){ //freopen(same.in,r,stdin); //freopen(same.out,w,stdout); ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cint; while(t--){ cinn; for(int i1;in;i){ cina[i]; } for(int i1;in;i){ cinb[i]; } pk0; for(int i1;in;i){ f[i]0; if(a[i]!b[i]){ if(in/2){ ki; } p1; f[i]0; } else{ f[i]1; } } if(p0){ coutYes\n; continue; } for(int i1;ik;i){ pa[i]; a[i]a[n-ki]; a[n-ki]p; } p0; for(int i1;in;i){ if(a[i]!b[i]){ p1; coutNo\n; break; } } if(!p){ coutYes\n; continue; } } return 0; }第三题题意还是有两个序列a与b可以选择a中的任意一个数放到a中的第一个问最少多少次后使a数组等于b数组这道题我想了很久but没有想到思路于是进行骗分但是实际上思路很简单思路就是从后往前遍历只要当前的两个指针类似于双指针所指的两个a[ i ]和b[ j ]不相等那就i--,从前面找应该在这个位置的数字。例如a: 1 2 3 4 b: 4 1 2 3然后发现a[ i ]和b[ j ]不相等所以相等了所以到了这里我们发现 i 到头了而 j 没到头说明 j 前面的一定是从后面过来的所以coutj;于是你就能写出正确代码了#includeiostream #includecstdio #includealgorithm using namespace std; int n,a[200005],b[200005],aa[200005],bb[200005],f; int main(){ //freopen(front.in,r,stdin); //freopen(front.out,w,stdout); ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinn; for(int i1;in;i){ cina[i]; aa[i]a[i]; } for(int i1;in;i){ cinb[i]; bb[i]b[i]; if(a[i]!b[i]){ f; } } if(f0){ cout0; return 0; } sort(aa1,aa1n); sort(bb1,bb1n); for(int i1;in;i){ if(aa[i]!bb[i]){ cout-1; return 0; } } int in;//i是a序列,j是b序列 for(int jn;j1;j--,i--){ while(a[i]!b[j]i0){ i--; } if(i0){ coutj; return 0; } } cout0; return 0; }第四题题意有 n 个人如果 i 认识 j 那么a[ i ][ j ]1,然后有两个桌子当两个人互相认识时才可以在同一个桌子上问两张桌子中人数最多的那张桌子的最少人数。这个题我在考场上没有思路于是进行合理的得分策略俗称骗分其实这道题就是不简单要用搜索和背包。思路就是先搜索出每一个人应该在哪一个桌子然后因为两个桌子可以互换所以要背包正确代码如下#includeiostream #includecstdio #includealgorithm #includevector using namespace std; int n,a[515][515],vis[515],x[100005],y[100005],cnt,xx,yy; bool dp[515],f; void dfs(int p,int zh){ if(f){ return; } vis[p]zh; //A7 if(zh1){ xx; } else{ yy; } for(int i1;in;i){ if(ip){ continue; } if(a[p][i]0||a[i][p]0){ //A8 if(vis[i]0){ dfs(i,3-zh); } else if(vis[p]vis[i]!3){ //A9 f1; return ; } } } } int main(){ //freopen(party.in,r,stdin); //freopen(party.out,w,stdout); ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinn; for(int i1;in;i){ for(int j1;jn;j){ cina[i][j]; } } for(int i1;in;i){ if(vis[i]0){ //A1 xxyyf0; dfs(i,1); if(f){ coutNo; return 0; } x[cnt]xx; y[cnt]yy; } } dp[0]1; int mn/2; for(int i1;icnt;i){ bool ndp[n5]{}; //A2 for(int jm;j0;j--){ //A3 if(x[i]jy[i]j){ //A4 break; } if(x[i]j){ ndp[j]|dp[j-x[i]]; } if(y[i]j){ ndp[j]|dp[j-y[i]]; } } for(int j0;jn;j){ //A5 dp[j]ndp[j]; } } for(int im;i0;i--){ //A6 if(dp[i]){ coutYes\nn-i; return 0; } } return 0; }A1:当这个数还没有访问过时我们就访问dfs(i,1)的意思是让 i 进入到第一个桌子上我们看到dfs中的A7这也与A9结合当两个数不同组时也就是一个是1一个是2加起来是3所以当vis[p]vis[i]!3时他俩在同一组而A8是说明这两个不能在一起所以当他俩都访问过且还在同一组那就coutNo.回到主函数A2这是一个滚动数组在A5滚动。dp是上一次的dp,ndp是这一次的dp,在A4,当这两个无法进入break。在A6倒着循环从n/2~0,当可以凑成i时最大的那个就是n-i,所以输出n-i
