一前言去年也是成功的又没有拿到一奖啊于是有了这篇文章。。。今年的集训从2号开始也是终于过了一个完整的生日啊老粉dddd废话不多说看看今年进步了多少吧二成绩1双面展签【100/100】第一题你被毕业了2异组参照【30/100】就做了5分钟得多少分你别管3翻翻转转【0/100】申诉后【100/100】我从地狱回来了整个班里最熟的是这个题4对照实验【55/100】你配第四题总分【285/400】看不到rank这次高分班似乎不公布排名依旧不看难度瞎排除了第一题别的全部打乱题一直接毕业好吧累了搞不动了三题二第三题实在老仇人所以本题没有赛上最不尊重第二题的一把5分钟敲了个暴力还漏了-1特判喜提30分但其实这题出的挺好的看看题面实验室收到了 n 份读数。第 i 份读数的数值为 ai所属小组的编号为 ci。为了交叉核对每份读数都需要寻找一份来自不同小组的读数作为参照。对于第 i 份读数可以选择任意满足 cj≠ci 的读数 j希望两者数值差的绝对值 ∣ai−aj∣尽可能小。请对每份读数分别求出这个最小差值。如果不存在来自不同小组的读数则该份读数的答案为 −1。不同小组可以出现相同数值此时差值为 0。每份读数的参照选择互不影响同一份读数可以被多个对象选作参照。只需输出最小差值不需要输出参照对象的编号。是这样的一个思路可以用结构体或者vector进行存储存完后打排序规则按数值从小到大排组号随便排完之后相同小组编号的不一定都在一块但我的答案一定是出于不同组的这样搞一个前驱数组记录左边离自己最近的不同组的元素编号因为已经数值排序了所以距离最小就是差值最小再搞一个后继数组记录右边离自己最近的不同组的元素编号左边差值最小和右边差值最小取一个最小值就是答案#includebits/stdc.h #define INF 0x3f3f3f3f using namespace std; const int N2e55; int n,a[N],c[N],lnx[N],rnx[N],ans[N]; int main(){ cinn; vectorarrayint,3 v; for(int i1;in;i){ cina[i]c[i]; v.push_back({a[i],c[i],i}); ans[i]INF; } sort(v.begin(),v.end()); lnx[0]-1; for(int i1;in;i){ if(v[i][1]v[i-1][1]){ lnx[i]lnx[i-1]; } else{ lnx[i]i-1; } if(lnx[i]!-1){ ans[v[i][2]]min(ans[v[i][2]],v[i][0]-v[lnx[i]][0]); } } rnx[n]-1; for(int in-2;i0;i--){ if(v[i][1]v[i1][1]){ rnx[i]rnx[i1]; } else{ rnx[i]i1; } if(rnx[i]!-1){ ans[v[i][2]]min(ans[v[i][2]],v[rnx[i]][0]-v[i][0]); } } for(int i1;in;i){ if(ans[i]INF) coutans[i]\n; else coutans[i]\n; } }vector套array连cmp都不用排直接就能按照第一个元素从小到大排序相同则看第二个从小到大排序四题三往年今日 2024.10.1T2https://blog.csdn.net/2301_80046199/article/details/142671263?spm1001.2014.3001.5501西部牛仔开场音乐许多年未见原来你已经成为第三题了吗。。。可惜了今天的我也变强了接受审判吧bushi在场上看到这个题也是直接没有绷住啊仇人见面分外眼红最后还阴了我一手题目名tm的竟然不是flip而是filp这个滚木东西我滴妈也是直接亏掉100分啊回归正题24年做这个的时候还毫无思路的找规律打表呢讲完是二分也不会写今年会打二分了只觉得这个题超级简单换了一个老师换了一种做法但是我还是要用24年的二分题面回顾一下我去竟然24年忘记放题面了定义字符串序列s01sisi−1si−1‾(i≥1其中 si−1‾表示把 si−1 的每一位取反即把 0 变成 1把 1 变成 0。例如s01s110s21001s310010110现在给出若干询问每次询问一个位置 x求 s114514 的第 x 个字符。这个题不是二分答案而是二分查找初始是1翻转左边相同依然是1右边取反变为0按照左不变右取反的思路在最靠近x的2的n次方的连续序列或者直接2的30次方的连续序列(0,1,2,3,4...2^30)中查找x设置一个标记字符sx在mid右边s就取反x在mid左边s就不变直到mid与x完全相同 当前标记字符s就是答案其实我不知道为什么这么做只是通过小样例反推验证的正确性让3作为样例2^3位 10010110 左4和右4取反初始是13在左41不变2^2为 1001 左2和右2取反3在右2 1变为02^1为 01 左1和右1取反3在左1 0不变答案即为0在初始大区间中判断处于左半区间字符不变右半区间字符取反直到走到单字符区间再说推论纯两层的情况下左边的左边和右边的右边取反两次等于取反0次的结果相同左边的右边和右边的左边结果相同也有初始是0在左边就取反在右边就不变的这么一种做法观察序列每4位均为0110或1001即说的两层情况后面再往更高维扩展就是正解好诡异的一个题只能说当年没思路不怪自己啊AC代码#includebits/stdc.h using namespace std; void f(int l,int r,int s,int t){ double mid(lr)*1.0/2; if(midt){ couts\n; return ; } if(tmid){ if(s0) s1; else if(s1) s0; f(ceil(mid),r,s,t); } else{ f(l,floor(mid),s,t); } } int main(){ freopen(flip.in,r,stdin);//空悲切 freopen(flip.out,w,stdout); int T,n; cinT; while(T--){ cinn; if(n1){ cout1\n; } else{ f(1,pow(2,ceil(log2(n))),1,n); } } }五题四直接题面也是第一个考场上拿50分以上的背包题非常简单考场代码改6个字符能A的但可惜背包刷的少调不出来训练营准备了 n 项实验编号为 1∼n。完成实验 i 需要 ti 分钟可以获得 vi 分。学生可以任选一些实验按照编号从小到大的顺序完成。每项实验最多做一次所有被选实验的耗时之和不能超过 B 分钟。为了鼓励对照分析如果编号相邻的实验 i 和 i1 都完成还能额外获得 bi 分奖励不增加耗时。每一对满足条件的相邻实验都分别产生奖励。例如连续完成实验 2,3,4可以同时获得 b2 和 b3如果只完成实验 2,4则不会因这两个实验获得相邻奖励。请计算最高能够获得多少总分。允许不做任何实验此时耗时和得分均为 0也不要求把时间恰好用完。正解思路设立三維dp数组dp[i][j][0]当前第i个物品容量为j当前物品不拿的最大收益dp[i][j][1]当前第i个物品容量为j当前物品必拿的最大收益状态转移也是非常好写了不选择第i项那跟i-1项没有关系直接继承dp[i][j][0]max(dp[i-1][j][0],dp[i-1][j][1]);选择第i项那就分为了两种情况i-1项被选择则dp[i][j][1]dp[i][j-c[i]][0]v[i]i-1项没有被选择则dp[i][j][1]dp[i][j-c[i]][1]v[i]b[i]最后一项可以不选容量消耗也不一定是B所以答案是max(dp[n][j][0]dp[n][j][1]);j0到B循环正片开始考场思路普通两维dpdp[i][j]当前第i个物品容量为j最大收益但是状态转移就有点说法了什么都不做好说直接继承上一个物品dp[i][j]max(dp[i][j],dp[i-1][j]);只选当前这一个没有组合额外奖励注意判断剩余容量dp[i][j]max(dp[i][j],dp[i-1][j-c[i]]v[i]);有组合额外奖励呢连续两个dp[i][j]max(dp[i][j],dp[i-2][j-c[i]-c[i-1]]v[i]v[i-1]b[i]);连续三个dp[i][j] max(dp[i][j],dp[i-3][j-c[i]-c[i-1]-c[i-2]]v[i]v[i-1]v[i-2]b[i]b[i-1]);也是直接得到规律了好吧直接for循环遍历连续的个数注意容量越界判断中间如果组合断开怎么办没关系我们连续转移时候继承的一定是前面的最优方案而这最优方案具体组成结构是什么是否断开我一律不管只要最优就满足dp扣45分是因为状态转移没写好而小样例体现不出来max的首项我没有写dp[i][j]而是写了dp[i-1][j]或者dp[k-1][j]等等诡异的东西本质上没有理解这是一个选择问题来取三方案最优的话首项肯定要是自己啊啊啊哭AC代码#includebits/stdc.h using namespace std; int c[305],w[305],b[305],f[305][3005]; int main(){ freopen(lab.in,r,stdin); freopen(lab.out,w,stdout); int n,B; cinnB; for(int i1;in;i){ cinw[i]c[i]; } for(int i1;in;i){ cinb[i]; } for(int i1;in;i){ for(int jB;j0;j--){ f[i][j]max(f[i][j],f[i-1][j]); if(jw[i]){ f[i][j]max(f[i][j],f[i-1][j-w[i]]c[i]); } int totw[i],ctotc[i],btot0; for(int ki-1;k1;k--){ totw[k]; ctotc[k]; btotb[k]; if(jtot){ f[i][j]max(f[i][j],f[k-1][j-tot]ctotbtot); } } } } /*for(int i1;in;i){ for(int j0;jB;j){ coutf[i][j] ; } cout\n; }*/ coutf[n][B]; }可读性可能比较差见谅六总结生日过完了呜呜呜呜今年加把劲一定要过事不过三
CSP-J复赛模拟赛1 王晨旭补题 2026.10.2
一前言去年也是成功的又没有拿到一奖啊于是有了这篇文章。。。今年的集训从2号开始也是终于过了一个完整的生日啊老粉dddd废话不多说看看今年进步了多少吧二成绩1双面展签【100/100】第一题你被毕业了2异组参照【30/100】就做了5分钟得多少分你别管3翻翻转转【0/100】申诉后【100/100】我从地狱回来了整个班里最熟的是这个题4对照实验【55/100】你配第四题总分【285/400】看不到rank这次高分班似乎不公布排名依旧不看难度瞎排除了第一题别的全部打乱题一直接毕业好吧累了搞不动了三题二第三题实在老仇人所以本题没有赛上最不尊重第二题的一把5分钟敲了个暴力还漏了-1特判喜提30分但其实这题出的挺好的看看题面实验室收到了 n 份读数。第 i 份读数的数值为 ai所属小组的编号为 ci。为了交叉核对每份读数都需要寻找一份来自不同小组的读数作为参照。对于第 i 份读数可以选择任意满足 cj≠ci 的读数 j希望两者数值差的绝对值 ∣ai−aj∣尽可能小。请对每份读数分别求出这个最小差值。如果不存在来自不同小组的读数则该份读数的答案为 −1。不同小组可以出现相同数值此时差值为 0。每份读数的参照选择互不影响同一份读数可以被多个对象选作参照。只需输出最小差值不需要输出参照对象的编号。是这样的一个思路可以用结构体或者vector进行存储存完后打排序规则按数值从小到大排组号随便排完之后相同小组编号的不一定都在一块但我的答案一定是出于不同组的这样搞一个前驱数组记录左边离自己最近的不同组的元素编号因为已经数值排序了所以距离最小就是差值最小再搞一个后继数组记录右边离自己最近的不同组的元素编号左边差值最小和右边差值最小取一个最小值就是答案#includebits/stdc.h #define INF 0x3f3f3f3f using namespace std; const int N2e55; int n,a[N],c[N],lnx[N],rnx[N],ans[N]; int main(){ cinn; vectorarrayint,3 v; for(int i1;in;i){ cina[i]c[i]; v.push_back({a[i],c[i],i}); ans[i]INF; } sort(v.begin(),v.end()); lnx[0]-1; for(int i1;in;i){ if(v[i][1]v[i-1][1]){ lnx[i]lnx[i-1]; } else{ lnx[i]i-1; } if(lnx[i]!-1){ ans[v[i][2]]min(ans[v[i][2]],v[i][0]-v[lnx[i]][0]); } } rnx[n]-1; for(int in-2;i0;i--){ if(v[i][1]v[i1][1]){ rnx[i]rnx[i1]; } else{ rnx[i]i1; } if(rnx[i]!-1){ ans[v[i][2]]min(ans[v[i][2]],v[rnx[i]][0]-v[i][0]); } } for(int i1;in;i){ if(ans[i]INF) coutans[i]\n; else coutans[i]\n; } }vector套array连cmp都不用排直接就能按照第一个元素从小到大排序相同则看第二个从小到大排序四题三往年今日 2024.10.1T2https://blog.csdn.net/2301_80046199/article/details/142671263?spm1001.2014.3001.5501西部牛仔开场音乐许多年未见原来你已经成为第三题了吗。。。可惜了今天的我也变强了接受审判吧bushi在场上看到这个题也是直接没有绷住啊仇人见面分外眼红最后还阴了我一手题目名tm的竟然不是flip而是filp这个滚木东西我滴妈也是直接亏掉100分啊回归正题24年做这个的时候还毫无思路的找规律打表呢讲完是二分也不会写今年会打二分了只觉得这个题超级简单换了一个老师换了一种做法但是我还是要用24年的二分题面回顾一下我去竟然24年忘记放题面了定义字符串序列s01sisi−1si−1‾(i≥1其中 si−1‾表示把 si−1 的每一位取反即把 0 变成 1把 1 变成 0。例如s01s110s21001s310010110现在给出若干询问每次询问一个位置 x求 s114514 的第 x 个字符。这个题不是二分答案而是二分查找初始是1翻转左边相同依然是1右边取反变为0按照左不变右取反的思路在最靠近x的2的n次方的连续序列或者直接2的30次方的连续序列(0,1,2,3,4...2^30)中查找x设置一个标记字符sx在mid右边s就取反x在mid左边s就不变直到mid与x完全相同 当前标记字符s就是答案其实我不知道为什么这么做只是通过小样例反推验证的正确性让3作为样例2^3位 10010110 左4和右4取反初始是13在左41不变2^2为 1001 左2和右2取反3在右2 1变为02^1为 01 左1和右1取反3在左1 0不变答案即为0在初始大区间中判断处于左半区间字符不变右半区间字符取反直到走到单字符区间再说推论纯两层的情况下左边的左边和右边的右边取反两次等于取反0次的结果相同左边的右边和右边的左边结果相同也有初始是0在左边就取反在右边就不变的这么一种做法观察序列每4位均为0110或1001即说的两层情况后面再往更高维扩展就是正解好诡异的一个题只能说当年没思路不怪自己啊AC代码#includebits/stdc.h using namespace std; void f(int l,int r,int s,int t){ double mid(lr)*1.0/2; if(midt){ couts\n; return ; } if(tmid){ if(s0) s1; else if(s1) s0; f(ceil(mid),r,s,t); } else{ f(l,floor(mid),s,t); } } int main(){ freopen(flip.in,r,stdin);//空悲切 freopen(flip.out,w,stdout); int T,n; cinT; while(T--){ cinn; if(n1){ cout1\n; } else{ f(1,pow(2,ceil(log2(n))),1,n); } } }五题四直接题面也是第一个考场上拿50分以上的背包题非常简单考场代码改6个字符能A的但可惜背包刷的少调不出来训练营准备了 n 项实验编号为 1∼n。完成实验 i 需要 ti 分钟可以获得 vi 分。学生可以任选一些实验按照编号从小到大的顺序完成。每项实验最多做一次所有被选实验的耗时之和不能超过 B 分钟。为了鼓励对照分析如果编号相邻的实验 i 和 i1 都完成还能额外获得 bi 分奖励不增加耗时。每一对满足条件的相邻实验都分别产生奖励。例如连续完成实验 2,3,4可以同时获得 b2 和 b3如果只完成实验 2,4则不会因这两个实验获得相邻奖励。请计算最高能够获得多少总分。允许不做任何实验此时耗时和得分均为 0也不要求把时间恰好用完。正解思路设立三維dp数组dp[i][j][0]当前第i个物品容量为j当前物品不拿的最大收益dp[i][j][1]当前第i个物品容量为j当前物品必拿的最大收益状态转移也是非常好写了不选择第i项那跟i-1项没有关系直接继承dp[i][j][0]max(dp[i-1][j][0],dp[i-1][j][1]);选择第i项那就分为了两种情况i-1项被选择则dp[i][j][1]dp[i][j-c[i]][0]v[i]i-1项没有被选择则dp[i][j][1]dp[i][j-c[i]][1]v[i]b[i]最后一项可以不选容量消耗也不一定是B所以答案是max(dp[n][j][0]dp[n][j][1]);j0到B循环正片开始考场思路普通两维dpdp[i][j]当前第i个物品容量为j最大收益但是状态转移就有点说法了什么都不做好说直接继承上一个物品dp[i][j]max(dp[i][j],dp[i-1][j]);只选当前这一个没有组合额外奖励注意判断剩余容量dp[i][j]max(dp[i][j],dp[i-1][j-c[i]]v[i]);有组合额外奖励呢连续两个dp[i][j]max(dp[i][j],dp[i-2][j-c[i]-c[i-1]]v[i]v[i-1]b[i]);连续三个dp[i][j] max(dp[i][j],dp[i-3][j-c[i]-c[i-1]-c[i-2]]v[i]v[i-1]v[i-2]b[i]b[i-1]);也是直接得到规律了好吧直接for循环遍历连续的个数注意容量越界判断中间如果组合断开怎么办没关系我们连续转移时候继承的一定是前面的最优方案而这最优方案具体组成结构是什么是否断开我一律不管只要最优就满足dp扣45分是因为状态转移没写好而小样例体现不出来max的首项我没有写dp[i][j]而是写了dp[i-1][j]或者dp[k-1][j]等等诡异的东西本质上没有理解这是一个选择问题来取三方案最优的话首项肯定要是自己啊啊啊哭AC代码#includebits/stdc.h using namespace std; int c[305],w[305],b[305],f[305][3005]; int main(){ freopen(lab.in,r,stdin); freopen(lab.out,w,stdout); int n,B; cinnB; for(int i1;in;i){ cinw[i]c[i]; } for(int i1;in;i){ cinb[i]; } for(int i1;in;i){ for(int jB;j0;j--){ f[i][j]max(f[i][j],f[i-1][j]); if(jw[i]){ f[i][j]max(f[i][j],f[i-1][j-w[i]]c[i]); } int totw[i],ctotc[i],btot0; for(int ki-1;k1;k--){ totw[k]; ctotc[k]; btotb[k]; if(jtot){ f[i][j]max(f[i][j],f[k-1][j-tot]ctotbtot); } } } } /*for(int i1;in;i){ for(int j0;jB;j){ coutf[i][j] ; } cout\n; }*/ coutf[n][B]; }可读性可能比较差见谅六总结生日过完了呜呜呜呜今年加把劲一定要过事不过三