CSP历年真题题解思考过程 —— 1

P5662 [CSP-J 2019] 纪念品 题解

题干链接

10pts解法

注意到数据规模中，有10%的数据中t = 1 t = 1t=1，这意味着只有1天，那么不难发现这种情况下我们是赚不到钱的（第一天也是最后一天，买入即卖出），这时不去购买纪念品是最好的选择，所以直接输出m mm

if(t==1)cout<<m;}

25pts解法

继续观察数据规模，发现有15%的数据中n = 1 n = 1n=1，这意味着只有1种纪念品。此时讨论利益最大化就退化成了讨论单日利益最大化，即为选中某些日子i ii，使得所有p i + 1 , 1 − p i , 1 p_{{i+1},1} - p_{i,1}pi+1,1​−pi,1​最大化。显然，选中i的条件只要p i + 1 , 1 − p i , 1 > 0 p_{{i+1},1} - p_{i,1} > 0pi+1,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_{{i+1},1} - p_{i,1})⌊pi,1​m​⌋×(pi+1,1​−pi,1​)的利润。我们只需要以天数循环逐步累加m mm即可。

if(n==1){for(int32_ti=1;i<=t;i++){if(p[i+1][1]>p[i][1]){m+=(m/p[i][1])*(p[i+1][1]-p[i][1]);}}cout<<m;}

40pts解法

回到数据规模，我们还发现有15%的数据中t = 2 t = 2t=2，这意味着只有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(t==2){for(int32_ti=1;i<=n;i++){int32_tw=p[1][i];int32_tv=p[2][i]-p[1][i];if(v<=0)continue;for(int32_tj=w;j<=m;j++){f[j]=max(f[j],f[j-w]+v);}}cout<<m+f[m];}

100pts解法

对于100%的数据，t tt被扩展到了100，但我们只需要把它当作多个$t=2 $来看，在上面的做法基础上增添一次迭代，也就成功了。

for(int32_td=1;d<=t;d++){fill(f.begin(),f.end(),0);for(int32_ti=1;i<=n;i++){int32_tw=p[d][i];int32_tv=p[d+1][i]-p[d][i];if(v<=0)continue;for(int32_tj=w;j<=m;j++){f[j]=max(f[j],f[j-w]+v);}}m+=f[m];}cout<<m;

P5663 [CSP-J 2019] 加工零件

题干链接

20pts解法

观察数据规模，测试点 1∼4 中L = 1 L = 1L=1，这说明提问中只会问该工人加工第一阶段的零件需不需要轩轩提供原材料，也就是判断1号点和a号点是否直接连通。

for(int32_ti=1;i<=q;i++){cin>>a>>l;for(int32_ti=h[a];i!=-1;i=e[i].next){if(e[i].to==1){cout<<"Yes\n";gotonxt;}}cout<<"No\n";nxt:;}

40pts解法

继续观察数据范围，发现测试点5~8中L LL扩展到了1 ≤ L ≤ 10 1\leq L \leq 101≤L≤10，这时简单的判断是否联通已经不再有效了，我们需要使用搜索。

booldfs(int32_tn,int32_tll){if(ll==0){returnn==1;}for(int32_ti=h[n];i!=-1;i=e[i].next){if(dfs(e[i].to,ll-1)){returntrue;}}returnfalse;}int32_tmain(){// 省略部分代码...cout<<(dfs(a,l)?"Yes\n":"No\n");// 省略部分代码...}

80pts解法

对于搜索，最行之有效的优化就是记忆化。

map<pair<int32_t,int32_t>,int32_t>mm;booldfs(int32_tn,int32_tll){if(ll==0){returnn==1;}if(mm[{n,ll}]>0){returnmm[{n,ll}]==1;}for(int32_ti=h[n];i!=-1;i=e[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 ss，s ≡ L ( m o d 2 ) s \equiv L \pmod{2}s≡L(mod2)。这时再使用dfs就不合适了，很显然能发现，大多数情况下不同奇偶性距离的路径只差了一个点，那么bfs就能更快找到那条1~a的路径。

queue<pair<int32_t,int32_t>>qq;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_ti=h[id];i!=-1;i=e[i].next){int32_tto=e[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(a==1&&l>0&&m==0&&h[1]==-1){cout<<"No\n";continue;}if(l%2==0){cout<<(dis[0][a]<=l?"Yes\n":"No\n");}else{cout<<(dis[1][a]<=l?"Yes\n":"No\n");}// 省略部分代码...

注意dis在覆盖时值必须取到足够大。

100pts解法

最后一个点是个奇奇怪怪的hack数据，我还没有找到问题所在……

if(a==1&&l>0&&m==0&&h[1]==-1){cout<<"No\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_ti=2;i<=n;i++){for(int32_tj=int32_t(g.size())-1;j>=0;j--){g.push_back("1"+g[j]);}for(int32_tj=int32_t(g.size()/2)-1;j>=0;j--){g[j]="0"+g[j];}}cout<<g[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个0，2 n − 1 2^{n−1}2n−1个1，2 n − 1 2^{n-1}2n−1个1，2 n − 1 2^{n−1}2n−1个0循环的，那么我们就可以直接从k生成出对应的格雷码了

array<int32_t,4>num{0,1,1,0};for(int64_ti=n;i>1;i--){cout<<num[(k/(1ll<<(i-1))%4)];}cout<<num[k%4];

100pts解法

因为1<<64不在int64_t的范围内，我们只需要把int64_t改为无符号的uint64_t就可以了。

array<int32_t,4>num{0,1,1,0};for(uint64_ti=n;i>1;i--){cout<<num[(k/(1ull<<(i-1))%4)];}cout<<num[k%4];