题目分数第一题100第二题100第三题60加一个一就过了第四题85总分345考试过程第一题5分钟写完调bug的时间有点长本题大约用了15分钟第二题本人感觉有点难一开始我以为是很难的所以我一开始想要用dfs最后我仔细看一眼题所以就想到了用前缀和第三题我看了一眼就想到了所以本人以为做出来了但是并没有第四题直接暴力枚举所以拿了部分分。题目解析第一题下棋chess上一题下一题题目大意一个合成类小游戏就是一个合成排序的过程我的思路一目了然不言而喻就是模拟如果有3个以上的1星就合成2星有3个以上的2星就合成3星根据题目中的式子x3y18z可以知道怎么做都不会亏所以模拟即可我的代码#includebits/stdc.h using namespace std; #define endl \n #define ll long long #define f first #define s second #define PII pairint,int #define pll pairll,ll int n; const int N 1e610; struct node{ ll x,y,z,num; ll fen; }a[N]; bool cmp(node a,node b){ if(a.fenb.fen) return a.numb.num; return a.fenb.fen; } int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen(chess.in,r,stdin); freopen(chess.out,w,stdout); cinn; for(int i1;in;i){ cina[i].xa[i].ya[i].z; if(a[i].x3) a[i].ya[i].x/3,a[i].x%3; if(a[i].y3) a[i].za[i].y/3,a[i].y%3; // coutendla[i].x a[i].y a[i].zendl; a[i].fena[i].x3*a[i].y18*a[i].z,a[i].numi; } // for(int i1;in;i) couta[i].fenendl; sort(a1,a1n,cmp); for(int i1;in;i) couta[i].num ; return 0; } //2 //1 2 0 //1 2 2第二题汪洋BigWater题目大意long long ago 有一个人一开始有100的开心值每次可以按照当前方向走一步或者是可以按照顺时针走90°就是往右走转了以后为往下走但是在一个格子中不能连续转两次一开始是往右走的同一个格子只能走一遍除了11路过的每一个格子都是需要加起来路径为从起点11开始转一圈回到11要求开心值最大。我的思路因为他是只能顺时针旋转并且一个格子只能走一遍所以我们可以想到就是走一个环直接绕回来所以我么们可以想到用二维前缀和用容斥原理就可以知道这一个环的路径大小最后这个环的大小求一个最大的环的路径大小以ij为右下角顶点的环的值为sum[i][j]-sum[i-1][j-1]sum[1][j-1]sum[i-1][1]中间要确定把一个点会转两次的情况给排除掉即可我的代码;#includebits/stdc.h using namespace std; #define endl \n #define ll long long #define f first #define s second #define PII pairint,int #define pll pairll,ll const int N 1005; int cnt1,n,a[N][N]; ll sum[N][N]; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen(BigWater.in,r,stdin); freopen(BigWater.out,w,stdout); cinn; for(int i1;in;i){ for(int j1;jn;j){ cina[i][j]; } } for(int i1;in;i){ for(int j1;jn;j){ sum[i][j]sum[i][j-1]sum[i-1][j]-sum[i-1][j-1]a[i][j]; } } ll maxxLONG_LONG_MIN; for(int i1;in;i){ for(int j1;jn;j){ if(i1||j1) continue; maxxmax(maxx,sum[i][j]-sum[i-1][j-1]sum[1][j-1]sum[i-1][1]); } } cout100maxx; return 0; } //5 //0 5 2 2 -7 //10 7 -5 7 1 //4 -1 -5 4 -6 //3 -2 3 4 0 //-6 -1 -8 9 -6第三题拯救小精灵gremlin题目大意有x个精灵有y个恶魔有m条绳子只要绳子的两端不是恶魔就要割下来那个绳子的强度是可以加强的用一点魔法能量就可以如果有两个恶魔被拴在一起就不用管他剩下的恶魔要用绳子捆起来如果不行输出-1最后用最少的魔力可以全部解决。我的思路把所有的能割下来的绳子割下来用一个数组存起来把所有的不用捆起来的恶魔给单独标记一下最后把恶魔的恶魔值从大到小排序用一个计数器看看需要捆起来几个恶魔如果绳子的个数如果不如需要捆起来的恶魔多的话直接输出-1否则把绳子的能力值也是从小到大排序最后拿大绳子捆住大恶魔如果大绳子不行就用魔法能量去加强最后输出用了多少魔法能量我的错因遍历所有的恶魔的时候把最后一个精灵也算进去了所以多了一个我加上了这1两个字符就从60分变成100分了我的代码#includebits/stdc.h using namespace std; #define endl \n #define ll long long #define f first #define s second #define PII pairint,int #define pll pairll,ll const int N 1e610; ll x,y,m,cnt,b[N],cntt; pairll,bool a[N]; bool cmp(pairll,bool a,pairll,bool b){ return a.fb.f; } int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen(gremlin.in,r,stdin); freopen(gremlin.out,w,stdout); cinxym; for(int i1;iy;i) cina[ix].f; for(int i1;im;i){ ll u,v,w; cinuvw; if(ux||vx) b[cnt]w; if(uxvx) a[u].sa[v].s1; } sort(b1,b1cnt,greaterint ()); sort(a1x,ax1y,cmp); for(int ix;ixy;i){ if(a[i].s0) cntt; } ll cnttt1,ans0; if(cnttcnt){ cout-1; return 0;} // for(int ix1;ixy;i) couta[i].f a[i].sendl; // coutendl; // for(int i1;icnt;i) coutb[i]endl; for(int ix1;ixy;i){ if(a[i].s0b[cnttt]a[i].f) cnttt,a[i].s1; else if(a[i].s0b[cnttt]a[i].f) ans(a[i].f-b[cnttt]),cnttt; } coutans; return 0; } //1 3 1 //5 6 7 //1 2 100正确代码不仔细看根本看不出来和我的代码的差异#includebits/stdc.h using namespace std; #define endl \n #define ll long long #define f first #define s second #define PII pairint,int #define pll pairll,ll const int N 1e610; ll x,y,m,cnt,b[N],cntt; pairll,bool a[N]; bool cmp(pairll,bool a,pairll,bool b){ return a.fb.f; } int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen(gremlin.in,r,stdin); freopen(gremlin.out,w,stdout); cinxym; for(int i1;iy;i) cina[ix].f; for(int i1;im;i){ ll u,v,w; cinuvw; if(ux||vx) b[cnt]w; if(uxvx) a[u].sa[v].s1; } sort(b1,b1cnt,greaterint ()); sort(a1x,ax1y,cmp); for(int ix;ixy;i){ if(a[i].s0) cntt; } ll cnttt1,ans0; if(cnttcnt){ cout-1; return 0;} // for(int ix1;ixy;i) couta[i].f a[i].sendl; // coutendl; // for(int i1;icnt;i) coutb[i]endl; for(int ix1;ixy;i){ if(a[i].s0b[cnttt]a[i].f) cnttt,a[i].s1; else if(a[i].s0b[cnttt]a[i].f) ans(a[i].f-b[cnttt]),cnttt; } coutans; return 0; } //1 3 1 //5 6 7 //1 2 100第四题平分糖果candy题目大意有6种糖果有不同的得分给你他们的数量最后问你能不能把他们平均分成两堆使他们的得分相等我的思路每个糖果都分类讨论如果是第一堆分少就给第一堆否则就给第二堆我的错因想到了这个感觉是01背包并且是全部装满的背包但是我的时间复杂度可能会爆炸所以我就写了一个随缘代码没想到85分我的代码#includebits/stdc.h using namespace std; #define endl \n #define ll long long #define f first #define s second #define PII pairint,int #define pll pairll,ll const int N 1e610; int a[10]; ll sum,cnt1,cntt; bool flag0; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen(candy.in,r,stdin); freopen(candy.out,w,stdout); while(cina[1]a[2]a[3]a[4]a[5]a[6]){ if(a[1]0a[2]0a[3]0a[4]0a[5]0a[6]0) return 0; coutCollection #cnt:endl; cnt; ll sum10,sum20; for(int i6;i1;i--){ for(int j1;ja[i];j){ if(sum1sum2) sum1i; else sum2i; } } if(sum1!sum2) coutCant be divided.endl; else coutCan be divided.endl; coutendl; } return 0; } //1 0 1 2 0 0 //1 0 0 0 1 1 //0 0 0 0 0 0正确思路用多重背包完全装满的中间需要用二进制拆位去优化他。所以最后看看如果最终的得分数是个偶数并且得分总数的1/2是可以拆出来的我们就说他是可以的否则就是不可以的正确代码#includebits/stdc.h using namespace std; #define endl \n #define ll long long #define f first #define s second #define PII pairint,int #define pll pairll,ll const int N 1.2e510; int a[10]; ll dp[N],sum,cnt1,cntt; bool flag0; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen(candy.in,r,stdin); // freopen(candy.out,w,stdout); while(cina[1]a[2]a[3]a[4]a[5]a[6]){ if(a[1]0a[2]0a[3]0a[4]0a[5]0a[6]0) return 0; coutCollection #cnt:endl; cnt; sum0; for(int i1;i6;i) sumi*a[i];//统计得分 // assert(sum120000); for(int i1;isum;i) dp[i]0;//初始化 dp[0]1;//是否装满的初始化 for(int i1;i6;i){ for(int k1;ka[i];k1){//二进制 for(int jsum;ji*k;j--) dp[j]dp[j]|dp[j-i*k];//或的意思是这次装满或者是之前装满 a[i]-k;//把装满的减去 } if(a[i]){//如果还有剩下的 for(int jsum;ji*a[i];j--) dp[j]dp[j]|dp[j-i*a[i]];//做一次不同的01背包用或的理由和上面一样 } } if(!(sum1)dp[sum1]) coutCan be divided.endlendl;//如果这个得分是一个偶数并且可以平均分成两份就是可以 else coutCant be divided.endlendl;//否则就是不可以 } return 0; } //1 0 1 2 0 0 //1 0 0 0 1 1 //0 0 0 0 0 0可以总结的套路1.遇到路径只能顺时针或者逆时针走的并且还要回起点的就可以想到二维前缀和2.碰到有些组合问题可以用dp去做