CSP历年真题题解思考过程 —— 1P5662 [CSP-J 2019] 纪念品 题解10pts解法25pts解法40pts解法100pts解法P5663 [CSP-J 2019] 加工零件20pts解法40pts解法80pts解法95pts解法100pts解法P5657 [CSP-S 2019] 格雷码50pts解法95pts解法100pts解法P5662 [CSP-J 2019] 纪念品 题解题干链接10pts解法注意到数据规模中有10%的数据中t 1 t 1t1这意味着只有1天那么不难发现这种情况下我们是赚不到钱的第一天也是最后一天买入即卖出这时不去购买纪念品是最好的选择所以直接输出m mmif(t1)coutm;}25pts解法继续观察数据规模发现有15%的数据中n 1 n 1n1这意味着只有1种纪念品。此时讨论利益最大化就退化成了讨论单日利益最大化即为选中某些日子i ii使得所有p i 1 , 1 − p i , 1 p_{{i1},1} - p_{i,1}pi1,1​−pi,1​最大化。显然选中i的条件只要p i 1 , 1 − p i , 1 0 p_{{i1},1} - p_{i,1} 0pi1,1​−pi,1​0即可那对于这个i ii我们便能得到⌊ m p i , 1 ⌋ × ( p i 1 , 1 − p i , 1 ) \lfloor \frac{m}{p_{i, 1}} \rfloor \times (p_{{i1},1} - p_{i,1})⌊pi,1​m​⌋×(pi1,1​−pi,1​)的利润。我们只需要以天数循环逐步累加m mm即可。if(n1){for(int32_ti1;it;i){if(p[i1][1]p[i][1]){m(m/p[i][1])*(p[i1][1]-p[i][1]);}}coutm;}40pts解法回到数据规模我们还发现有15%的数据中t 2 t 2t2这意味着只有2天。我们希望利益p 2 , i − p 1 , i p_{2,i} - p_{1, i}p2,i​−p1,i​最大化却又只能选中有限的战利品Σ p 1 , i m \Sigma p_{1,i} mΣp1,i​m我们惊喜的发现这变成了一个背包问题我们只需要把p 2 , i − p 1 , i p_{2,i} - p_{1, i}p2,i​−p1,i​当作物品的价值p 1 , i p_{1,i}p1,i​当作物品的大小m mm当作背包的容量就可以用背包问题的方法解决这道题了。if(t2){for(int32_ti1;in;i){int32_twp[1][i];int32_tvp[2][i]-p[1][i];if(v0)continue;for(int32_tjw;jm;j){f[j]max(f[j],f[j-w]v);}}coutmf[m];}100pts解法对于100%的数据t tt被扩展到了100但我们只需要把它当作多个$t2 $来看在上面的做法基础上增添一次迭代也就成功了。for(int32_td1;dt;d){fill(f.begin(),f.end(),0);for(int32_ti1;in;i){int32_twp[d][i];int32_tvp[d1][i]-p[d][i];if(v0)continue;for(int32_tjw;jm;j){f[j]max(f[j],f[j-w]v);}}mf[m];}coutm;P5663 [CSP-J 2019] 加工零件题干链接20pts解法观察数据规模测试点 1∼4 中L 1 L 1L1这说明提问中只会问该工人加工第一阶段的零件需不需要轩轩提供原材料也就是判断1号点和a号点是否直接连通。for(int32_ti1;iq;i){cinal;for(int32_tih[a];i!-1;ie[i].next){if(e[i].to1){coutYes\n;gotonxt;}}coutNo\n;nxt:;}40pts解法继续观察数据范围发现测试点5~8中L LL扩展到了1 ≤ L ≤ 10 1\leq L \leq 101≤L≤10这时简单的判断是否联通已经不再有效了我们需要使用搜索。booldfs(int32_tn,int32_tll){if(ll0){returnn1;}for(int32_tih[n];i!-1;ie[i].next){if(dfs(e[i].to,ll-1)){returntrue;}}returnfalse;}int32_tmain(){// 省略部分代码...cout(dfs(a,l)?Yes\n:No\n);// 省略部分代码...}80pts解法对于搜索最行之有效的优化就是记忆化。mappairint32_t,int32_t,int32_tmm;booldfs(int32_tn,int32_tll){if(ll0){returnn1;}if(mm[{n,ll}]0){returnmm[{n,ll}]1;}for(int32_tih[n];i!-1;ie[i].next){if(dfs(e[i].to,ll-1)){mm[{n,ll}]1;returntrue;}}mm[{n,ll}]2;returnfalse;}95pts解法搜索记忆化似乎已经走到了尽头我们必须尝试换一种方法。假如a号点和b号点相连那么a号点在加工1阶段零件就需要b号点提供原材料加工2阶段零件需要自己给出原材料加工3阶段零件又需要b号点提供原材料……我们发现给定工人加工L LL阶段零件是否需要1号点提供原材料只需要看是否存在a号点到1号点的距离s sss ≡ L ( m o d 2 ) s \equiv L \pmod{2}s≡L(mod2)。这时再使用dfs就不合适了很显然能发现大多数情况下不同奇偶性距离的路径只差了一个点那么bfs就能更快找到那条1~a的路径。queuepairint32_t,int32_tqq;qq.emplace(1,0);fill(range(dis[0]),0x3f3f3f3f);fill(range(dis[1]),0x3f3f3f3f);dis[0][1]0;while(!qq.empty()){int32_tid,d;tie(id,d)qq.front();qq.pop();for(int32_tih[id];i!-1;ie[i].next){int32_ttoe[i].to;if(dis[d^1][to]dis[d][id]1){dis[d^1][to]dis[d][id]1;qq.emplace(to,d^1);}}}// 省略部分代码...if(a1l0m0h[1]-1){coutNo\n;continue;}if(l%20){cout(dis[0][a]l?Yes\n:No\n);}else{cout(dis[1][a]l?Yes\n:No\n);}// 省略部分代码...注意dis在覆盖时值必须取到足够大。100pts解法最后一个点是个奇奇怪怪的hack数据我还没有找到问题所在……if(a1l0m0h[1]-1){coutNo\n;continue;}P5657 [CSP-S 2019] 格雷码题干链接50pts解法对于50%的数据n ≤ 10 n \leq 10n≤10这说明最长的格雷码不会超过1024位所有的格雷码不会超过1024个那我们随便模拟即可。g.push_back(0);g.push_back(1);for(int32_ti2;in;i){for(int32_tjint32_t(g.size())-1;j0;j--){g.push_back(1g[j]);}for(int32_tjint32_t(g.size()/2)-1;j0;j--){g[j]0g[j];}}coutg[k];95pts解法对于更大数据模拟肯定行不通的不仅会TLE还会MLE那我们就要考虑找规律了。尝试竖着排列1~32的5位格雷码0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1我们会发现对于从低到高第i位它是以2 n − 1 2^{n−1}2n−1个02 n − 1 2^{n−1}2n−1个12 n − 1 2^{n-1}2n−1个12 n − 1 2^{n−1}2n−1个0循环的那么我们就可以直接从k生成出对应的格雷码了arrayint32_t,4num{0,1,1,0};for(int64_tin;i1;i--){coutnum[(k/(1ll(i-1))%4)];}coutnum[k%4];100pts解法因为164不在int64_t的范围内我们只需要把int64_t改为无符号的uint64_t就可以了。arrayint32_t,4num{0,1,1,0};for(uint64_tin;i1;i--){coutnum[(k/(1ull(i-1))%4)];}coutnum[k%4];