CQUPT 2025级 数据科学与大数据技术英才班 周测#07

CQUPT 2025级 数据科学与大数据技术英才班 周测#07

A [CSP-J 2024] 扑克牌

做法很多，见题解：

1. STL map
2. STL set
3. 数组模拟

B [CSP-J 2024] 地图探险

模拟一个类似 \(\text{DFS}\) 遍历 的过程

题解

C [CSP-J 2024] 小木棍

先看特殊性质：

• 特殊性质 A：保证 \(n\) 是 \(7\) 的倍数且 \(n\geq 100\)
• 特殊性质 B：保证存在整数 \(k\) 使得 \(n=7k+1\)，且 \(n\geq 100\)

不难猜测，最终答案需要分类讨论得到，依据就是 \(n\%7\) 的值

数字	0	1	2	3	4	5	6	7	8	9
木棍数	6	2	5	5	4	5	6	3	7	6

想要拼出的数字最小，首先保证位数最小，也就是用尽可能多的木棍拼成每一位

最优解就是用 \(7\) 个木棍拼成数字 \(8\)，木棍数是 \(7\) 的多少倍，就拼出多少个 \(8\)，猜测正确

为了保证数字最小，拼出的数字首位需要特殊判断一下。

具体分类：题解

if(n%7==0)
{for(int i=1;i<=n/7;i++)printf("8");puts("");
}
else if(n%7==1)
{if(n/7==0) puts("-1"); else {printf("10");for(int i=1;i<=n/7-1;i++)printf("8");puts("");}
}
else if(n%7==2)
{printf("1");for(int i=1;i<=n/7;i++)printf("8");puts("");
}
else if(n%7==3)
{if(n/7==0) puts("7");else if(n/7==1) puts("22");else{printf("200");for(int i=1;i<=n/7-2;i++)printf("8");puts("");}
}
else if(n%7==4)
{if(n/7==0) puts("4");else{printf("20");for(int i=1;i<=n/7-1;i++)printf("8");puts("");}
}
else if(n%7==5)
{printf("2");for(int i=1;i<=n/7;i++)printf("8");puts("");
}
else if(n%7==6)
{printf("6");for(int i=1;i<=n/7;i++)printf("8");puts("");
}

另一种做法 动态规划：题解

D [CSP-J 2024] 接龙

题目比较难，但是至少可以拿 \(5-15\) 分。

测试点 \(1\)，\(5\) 分

\(r=1\)，不需要接龙，只要一个人，满足存在子序列从 \(1\) 开始，\(c\) 结束，长度在 \([2,k]\) 之间即可。

\(c=1\) 的情况需要特判一下。

for(int i=1;i<=n;i++)
{int pos=0;for(int j=1;j<=l[i];j++){if(c==1&&s[i][j]==c){if(pos&&2<=j-pos+1&&j-pos+1<=k) flag=true;pos=j; }else if(c!=1){if(s[i][j]==1) pos=j;else if(pos&&s[i][j]==c&&j-pos+1<=k) flag=true;						}}
} 
if(flag) puts("1");
else puts("0");

测试点 \(1\to 3\)，\(15\) 分

\(n,r,\sum l,q\) 的范围都很小，用 \(\text{DFS}\) 枚举每一种情况就行了。

结合 \(r=1\) 的特判，就能拿到 \(15\) 分。

void dfs(int x,int st,int cnt)
{if(cnt==r){if(st==c) ans=1;return;}for(int i=1;i<=n;i++){if(i==x) continue;int pos=0;for(int j=1;j<=l[i];j++){if(pos&&2<=j-pos+1&&j-pos+1<=k) dfs(i,s[i][j],cnt+1);if(s[i][j]==st)	pos=j;}}
}

ans=0;
dfs(0,1,0);
printf("%d\n",ans);

正解：动态规划

题解，写得很清晰了

状态：\(dp[i][v]\) 表示第 \(i\) 轮以 \(v\) 结尾的情况

• \(dp[i][v] = 0\)：根本接不到 \(v\)
• \(dp[i][v] = p\)：只有第 \(p\) 个人能接到 \(v\)
• \(dp[i][v] = -1\)：有 **多种不同的人 **都能接到 \(v\)

状态转移：详见代码

• 如果 \(dp[i-1][u] = -1\)：任何人都能在第 \(i\) 轮把 \(u\) 当作起点（因为肯定存在一个 \(p' \neq p\) 也在上一轮接到了 \(u\)）。
• 如果 \(dp[i-1][u] = p\)：除了第 \(p\) 个人，其他人都能把 \(u\) 当作起点。
• 如果 \(dp[i-1][u] == 0\)：死路，谁都不能用。

由于 \(1\leq n\leq 10^5,1 \leq l_i \leq 2\times 10^5\)，不能用数组存 \(s[i][j]\)，要用 vector

while(T--)
{	scanf("%d%d%d",&n,&k,&q);for(int i=1;i<=n;i++){s[i].clear();scanf("%d",&l[i]);for(int j=1;j<=l[i];j++){int x;scanf("%d",&x);s[i].push_back(x);maxc=max(maxc,x); }}for(int i=1;i<=q;i++){scanf("%d%d",&r[i],&c[i]);maxr=max(maxr,r[i]);maxc=max(maxc,c[i]);}for(int i=0;i<=maxr;i++)for(int j=1;j<=maxc;j++)f[i][j]=-1;f[0][1]=0;for(int i=1;i<=maxr;i++){for(int j=1;j<=n;j++){int cnt=0;for(int x:s[j]){if(cnt){if(f[i][x]==-1) f[i][x]=j;else if(f[i][x]!=j) f[i][x]=0; cnt--;}if(f[i-1][x]!=-1&&f[i-1][x]!=j) cnt=k-1;}}}for(int i=1;i<=q;i++){if(f[r[i]][c[i]]!=-1) puts("1");else puts("0"); }maxr=maxc=0; 
}