Test - 3 20260226

Test - 3

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; 
}