题目分数第一题100第二题65第三题100第四题60总分325考试过程第一题10分钟不到做完了第二题一开始看到想写正解但是想了好几种思路例如二分排序从中间一个数往两边找……但是我最终没有想起来所以我就先写第三题第三题有思路就10分钟写出来了但是中间的细节比较多所以调试接近50分钟最后一个题我看完以为是优先队列但是仔细一看好像是个dp所以我就开始写最终没写出来还剩40分钟的时候我回去想了一下第二题最终选择了从中间往两边寻找的策略。第一题双面展签tag题目大意有n个展签第一个放正面后面的如果正面比前一个放的大就放正面否则如果反面比他大就放反面如果都不大就不要了我的思路这个题很水所以直接过了我的代码#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 cnt1,cnt2,n,ans; PII a[N]; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen(tag.in,r,stdin); freopen(tag.out,w,stdout); cinn; for(int i1;in;i) cina[i].fa[i].s; for(int i1;in;i){ if(cnt10cnt20) cnt1,ansa[i].f; else if(a[i].fans) cnt1,ansa[i].f; else if(a[i].sans) cnt1,cnt2,ansa[i].s; } coutcnt1 cnt2; return 0; } //5 //4 2 //3 5 //4 1 //4 6 //6 9第二题异组参照peer题目大意有n个数他们都属于不同的组让找每一个数的不同组别的数使他们的绝对值最小我的思路先按照数的从小到大排序每一个数从左边找比他小的数最大但不在一个组里的从右边找比他大的数最小也是不在一个组的但是应该是TLE O(n^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 1e610; int n,b[N]; struct node{ int shu,f,s; }a[N]; bool cmp(node a,node b){ if(a.fb.f) return a.sb.s; else return a.fb.f; } int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen(peer.in,r,stdin); freopen(peer.out,w,stdout); cinn; for(int i1;in;i) cina[i].fa[i].s,a[i].shui; sort(a1,a1n,cmp); for(int i1;in;i){ int minnINT_MAX,minnnINT_MAX; for(int ji-1;j1;j--){ if(a[i].s!a[j].s){ minna[i].f-a[j].f; break;} } for(int ji1;jn;j){ if(a[i].s!a[j].s){ minnna[j].f-a[i].f; break;} } if(minnINT_MAXminnnINT_MAX) b[a[i].shu]-1; else b[a[i].shu]min(minn,minnn); } for(int i1;in;i) coutb[i] ; return 0; } //4 //10 1 //12 1 //12 2 //17 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 1e610; int n,b[N],l[N],r[N],ans[N],anss[N]; struct node{ int shu,f,s,l,r; }a[N]; bool cmp(node a,node b){ return a.fb.f; } int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinn; for(int i1;in;i) cina[i].fa[i].s,a[i].shui; sort(a1,a1n,cmp); for(int i2;in;i){ if(a[i].s!a[i-1].s) l[i]i-1; else l[i]l[i-1]; } for(int in-1;i1;i--){ if(a[i].s!a[i1].s) r[i]i1; else r[i]r[i1]; } for(int i1;in;i){ int minnINT_MAX; if(l[i]) minnmin(minn,abs(a[i].f-a[l[i]].f)); if(r[i]) minnmin(minn,abs(a[r[i]].f-a[i].f)); if(minnINT_MAX) ans[a[i].shu]-1; else ans[i]minn; } for(int i1;in;i) anss[a[i].shu]ans[i]; for(int i1;in;i) coutanss[i] ; return 0; } //4 //10 1 //12 1 //12 2 //17 2第三题翻翻转转filp题目大意一开始一个字符串为s1里面只有‘1’后面的一个字符串s2里面是前面一个字符串加上前面一个字符串的取反值就是1变00变1最后问第114514个字符串的某一个位置是什么我的思路我们发现每一个数字都是从前面变化过来的并且我们注意到数组的长度为124816……都是2的几次方所以我们不妨可以找出某一个位置x在哪两个2的次方数的中间可以从前卖你那个区间里找到是从哪里变化来的所以这么推下去一定会回到1但是这里我是直接判断如果这个位置是前8个直接看看翻折了几次如果是偶数次就不用变如果是奇数次的话就取反为了加快速度我们可以看他在翻折过程中是不是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 1e610; int t,n; ll a[50]; string s 10010110; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); ll ans1; freopen(filp.in,r,stdin); freopen(filp.out,w,stdout); for(int i1;i39;i) ans*2,a[i]ans; // for(int i1;i40;i) couta[i] ; cint; while(t--){ int cnt0,anss0; bool flag0; cinn; if(n1n8){couts[n]endl; continue;} for(int i1;i39;i){ if(na[i]){ cnti-1; break;} } if(na[cnt1]){ if((cnt1)%21) cout0endl; else cout1endl; flag1; continue; } while(n8){ nn%a[cnt]; anss; // coutcnt nendl; for(int i1;i39;i){ if(na[i]){ cnti-1; break;} } if(na[cnt1]){ if((cnt1anss)%21) cout0endl; else cout1endl; flag1; break; } } // coutanss s[n] nendl; if(!flag){ if(anss%21){ if(s[n]1) cout0endl; else cout1endl; } else couts[n]endl; } } return 0; } //5 //4 2 //3 5 //4 1 //4 6 //6 9第四题对照实验lab题目大意就是有n组实验每一组数都对应一个得分和时间如果完成了相邻的两个实验就会获得b数组中相对应的得分最后问B分钟内的最大得分我的思路就是顺序思维如果这个数没选那么以这个任务为结尾的最大得分就是前一个实验做和不做的最大值如果这个实验做这个的最大得分就是前面一个实验做了的总得分和两个实验连续的奖励分数和前面一个实验不做的分数的最大值中间经过一系列分类讨论最终我发现了一个bug就是没办法看好几条线路的分开的最大值所以最后还是选择了暴力拿部分分我的代码#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 ans,dpp[N],n,B,b[N],cntttt; pll a[N],dp[N][5];//0为不选1为选 first为得分 second为时间 int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen(lab.in,r,stdin); freopen(lab.out,w,stdout); cinnB; for(int i1;in;i) cina[i].sa[i].f; for(int i2;in;i){ cinb[i]; if(b[i]0) cntttt; } if(cnttttn-1){ for(int i1;in;i){ for(int jB;ja[i].s;j--){ dpp[j]max(dpp[j],dpp[j-a[i].s]a[i].f); } } coutdpp[B]; return 0; } dp[1][0]{0,0},dp[1][1]a[1]; for(int i2;in;i){ int pdp[i-1][0].sa[i].s,qdp[i-1][1].sa[i].s; int ppdp[i-1][0].f,qqdp[i-1][1].f; //pp:当前的上一步没有选择的得分 qq:当前的上一步选了的得分 //p: 当前这一步选了的上一步没有选择的用时 q:当前这一步选了上一步也选择的用时 if(ppqq){ dp[i][0]dp[i-1][1]; if(pBqB) dp[i][1]{dp[i-1][1].fb[i]a[i].f,dp[i-1][1].sa[i].s}; else if(pBqB) dp[i][1]{dp[i-1][0].fa[i].f,dp[i-1][0].sa[i].s}; else if(pBqB) dp[i][1]{dp[i-1][1].fb[i]a[i].f,dp[i-1][1].sa[i].s}; else dp[i][1]{INT_MIN,B1}; } if(ppqq){ dp[i][0]dp[i-1][0]; if(pBqB) dp[i][1]{dp[i-1][0].fb[i]a[i].f,dp[i-1][0].sa[i].s}; else if(pBqB) dp[i][1]{dp[i-1][0].fa[i].f,dp[i-1][0].sa[i].s}; else if(pBqB) dp[i][1]{dp[i-1][1].fb[i]a[i].f,dp[i-1][1].sa[i].s}; else dp[i][1]{INT_MIN,B1}; } } // for(int i1;in;i) coutdp[i][0].f dp[i][0].s dp[i][1].f dp[i][1].sendl; ll maxxLONG_LONG_MIN; for(int i1;in;i){ if(dp[i][0].sB) maxxmax(maxx,dp[i][0].f); if(dp[i][1].sB) maxxmax(maxx,dp[i][1].f); } coutmaxx; return 0; } //4 5 //1 2 //1 3 //1 4 //1 1 //5 6 7正确思路应该是01背包的一个变型,就是如果这个实验不选是前面的实验做或者不做的一个最大值如果这个实验能做就做并且还要分成两种情况就是前面一个选了就是这两个的得分加上奖励的分数第二种情况就是前面一个不做光做这个实验的得分的情况两个求一个最大值正确代码#includebits/stdc.h #define ll long long using namespace std; int n,B,dp[2][3005][2]; struct node{ int t,v,b; }a[305]; int main(){ cinnB; for(int i1;in;i) cina[i].ta[i].v; for(int i2;in;i) cina[i].b; for(int i1;in;i){ int nowi1,pre(i1)^1; for(int j0;jB;j){ dp[now][j][0]max(dp[pre][j][0],dp[pre][j][1]); dp[now][j][1]0; if(ja[i].t) dp[now][j][1]dp[pre][j-a[i].t][0]a[i].v; if(ja[i-1].ta[i].t) dp[now][j][1]max(dp[pre][j-a[i].t][1]a[i].va[i].b,dp[now][j][1]); } } coutmax(dp[n1][B][0],dp[n1][B][1]); return 0; }