首发CSP-J2题解

T1 poker

这道题不难用 map 映射就可以做出来了。

#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
int main(){//freopen("poker.in","r",stdin);//freopen("poker.out","w",stdout);int n;cin>>n;int cnt=0;for(int i=1;i<=n;i++){string s;cin>>s;if(!mp[s]){cnt++;mp[s]=1;}}cout<<52-cnt;return 0;
}

T2 explore

直接模拟，题目给的很详细，没什么好说的。

#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
int main(){//freopen("poker.in","r",stdin);//freopen("poker.out","w",stdout);int n;cin>>n;int cnt=0;for(int i=1;i<=n;i++){string s;cin>>s;if(!mp[s]){cnt++;mp[s]=1;}}cout<<52-cnt;return 0;
}

T3 stick

这道题看起来是用搜索算法，实则是一个数论大题。

如果你骗分，能得到 $50\%$ 的分数，正解是数论找规律。

假设我们把所有位数都设置成 $8$，则如果结果大于 $n$，我们就可以减少木棍数量。即 $n=7k-t$，其中 $k$ 为位数，$t$ 为减去几根木棍。

我们分类讨论 $t$ 等于多少：

1. 如果 $t=0$，无需去除木棍。
2. 如果 $t=1$，去除第一位的一个木棍变成 $6$。
3. 如果 $t=2$，去除第一位的两个木棍变成 $2$。
4. 如果 $t=3$，去除第一位的两个木棍变成 $2$，去除第二位的一个木棍变成 $0$。
5. 如果 $t=4$，去除第一位的两个木棍变成 $2$，去除第二位的一个木棍变成 $0$，去除第三位的一个木棍变成 $0$。
6. 如果 $t=5$，去除第一位的五个木棍变成 $1$。
7. 如果 $t=6$，去除第一位的五个木棍变成 $1$，去除第二位的一个木棍变成 $0$。

但这样有缺陷，比如如果 $t=4$ 需要去除 $3$ 位，但是如果 $n=7\times 2-4=10$，只有两位，或者 $n=7\times 1-4=3$。这些情况需要特判。

愣着干什么，赶紧去写代码。

#include<bits/stdc++.h>
using namespace std;
int n,t,ans;
int stick[10]={6,2,5,5,4,5,6,3,7,6}; 
int main(){//freopen("sticks.in","r",stdin);//freopen("sticks.out","w",stdout);cin>>t;while(t--){cin>>n;if(n==1)cout<<-1;else if(n==2)cout<<1;else if(n==3)cout<<7;else if(n==4)cout<<4;else if(n==5)cout<<2;else if(n==6)cout<<6;//上面是算出来的else if(n==7)cout<<8;else if(n%7==0)for(int i=1;i<=n/7;i++)cout<<8;else if(n%7==1){cout<<10;for(int i=1;i<=(n-8)/7;i++)cout<<8;}else if(n%7==2){cout<<1;for(int i=1;i<=(n-2)/7;i++)cout<<8;}else if(n%7==3){if(n==10)cout<<22;else {cout<<200;for(int i=1;i<=(n-17)/7;i++)cout<<8;}}else if(n%7==4){cout<<20;for(int i=1;i<=(n-11)/7;i++)cout<<8;}else if(n%7==5){cout<<2;for(int i=1;i<=(n-5)/7;i++)cout<<8;}else if(n%7==6){cout<<6;for(int i=1;i<=(n-6)/7;i++)cout<<8;}//类似抽屉原理puts("");}return 0;
}

T4 chain

题目描述

在玩惯了成语接龙之后，小 J 和他的朋友们发明了一个新的接龙规则。

总共有 $n$ 个人参与这个接龙游戏，第 $i$ 个人会获得一个整数序列 $S_i$ 作为他的词库。

一次游戏分为若干轮，每一轮规则如下：

• $n$ 个人中的某个人 $p$ 带着他的词库 $S_p$ 进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
• 接龙的人选择一个长度在 $[2,k]$ 的 $S_p$ 的连续子序列 $A$ 作为这一轮的接龙序列，其中 $k$ 是给定的常数。若这是游戏的第一轮，那么 $A$ 需要以元素 $1$ 开头，否则 $A$ 需要以上一轮的接龙序列的最后一个元素开头。
  • 序列 $A$ 是序列 $S$ 的连续子序列当且仅当可以通过删除 $S$ 的开头和结尾的若干元素（可以不删除）得到 $A$。

为了强调合作，小 J 给了 $n$ 个参与游戏的人 $q$ 个任务，第 $j$ 个任务需要这 $n$ 个人进行一次游戏，在这次游戏里进行恰好 $r_j$ 轮接龙，且最后一轮的接龙序列的最后一个元素恰好为 $c_j$。为了保证任务的可行性，小 J 请来你判断这 $q$ 个任务是否可以完成的，即是否存在一个可能的游戏过程满足任务条件。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含三个整数 $n,k,q$，分别表示参与游戏的人数、接龙序列长度上限以及任务个数。

接下来 $n$ 行：

第 $i$ 行包含 $(l_i+1)$ 个整数 $l_i,S_{i,1},S_{i,2},\dots ,S_{i,l_i}$，其中第一个整数 $l_i$ 表示序列 $S_i$ 的长度，接下来 $l_i$ 个整数描述序列 $S_i$。

接下来 $q$ 行：

第 $j$ 行包含两个整数 $r_j,c_j$，描述一个任务。

输出格式

对于每个任务：输出一行包含一个整数，若任务可以完成输出 1，否则输出 0。

样例 #1

样例输入 #1

1
3 3 7
5 1 2 3 4 1
3 1 2 5
3 5 1 6
1 2
1 4
2 4
3 4
6 6
1 1
7 7

样例输出 #1

1
0
1
0
1
0
0

提示

【样例 1 解释】

在下文中，我们使用 { A i } = { A 1 , A 2 , … , A r } \{A_i\} = \{A_1, A_2, \dots , A_r\} {Ai​}={A1​,A2​,…,Ar​} 表示一轮游戏中所有的接龙序列， { p i } = { p 1 , p 2 , … , p r } \{p_i\} = \{p_1, p_2, \dots , p_r\} {pi​}={p1​,p2​,…,pr​} 表示对应的接龙的人的编号。由于所有字符均为一位数字，为了方便我们直接使用数字字符串表示序列。

• 对于第一组询问，$p_1=1$、$A_1=12$ 是一个满足条件的游戏过程。
• 对于第二组询问，可以证明任务不可完成。注意 $p_1=1$、$A_1=1234$ 不是合法的游戏过程，因为此时 $|A_1|=4>k$。
• 对于第三组询问， { p i } = { 2 , 1 } \{p_i\} = \{2, 1\} {pi​}={2,1}、 { A i } = { 12 , 234 } \{A_i\} = \{12, 234\} {Ai​}={12,234} 是一个满足条件的游戏过程。
• 对于第四组询问，可以证明任务不可完成。注意 { p i } = { 2 , 1 , 1 } 、 { A i } = { 12 , 23 , 34 } \{p_i\} = \{2, 1, 1\}、\{A_i\} = \{12, 23, 34\} {pi​}={2,1,1}、{Ai​}={12,23,34} 不是一个合法的游戏过程，因为尽管所有的接龙序列长度均不超过 $k$，但第二轮和第三轮由同一个人接龙，不符合要求。
• 对于第五组询问， { p i } = { 1 , 2 , 3 , 1 , 2 , 3 } \{p_i\} = \{1, 2, 3, 1, 2, 3\} {pi​}={1,2,3,1,2,3}、 { A i } = { 12 , 25 , 51 , 12 , 25 , 516 } \{A_i\} = \{12, 25, 51, 12, 25, 516\} {Ai​}={12,25,51,12,25,516} 是一个满足条件的游戏过程。
• 对于第六组询问，可以证明任务不可完成。注意每个接龙序列的长度必须大于等于 $2$，因此 $A_1=1$ 不是一个合法的游戏过程。
• 对于第七组询问，所有人的词库均不存在字符 $7$，因此任务显然不可完成。

【样例 2】

见选手目录下的 chain/chain2.in 与 chain/chain2.ans。

该样例满足测试点 1 的特殊性质。

【样例 3】

见选手目录下的 chain/chain3.in 与 chain/chain3.ans。

该样例满足测试点 2 的特殊性质。

【样例 4】

见选手目录下的 chain/chain4.in 与 chain/chain4.ans。

该样例满足特殊性质 A，其中前两组测试数据满足 $n\le 1000$、$r\le 10$、单组测试数据内所有词库的长度和 $\le 2000$、$q\le 1000$。

【样例 5】

见选手目录下的 chain/chain5.in 与 chain/chain5.ans。

该样例满足特殊性质 B，其中前两组测试数据满足 $n\le 1000$、$r\le 10$、单组测试数据内所有词库的长度和 $\le 2000$、$q\le 1000$。

【样例 6】

见选手目录下的 chain/chain6.in 与 chain/chain6.ans。

该样例满足特殊性质 C，其中前两组测试数据满足 $n\le 1000$、$r\le 10$、单组测试数据内所有词库的长度和 $\le 2000$、$q\le 1000$。

【数据范围】

对于所有测试数据，保证：

• $1\le T\le 5$；
• $1\le n\le 10^5$，$2\le k\le 2\times 10^5$，$1\le q\le 10^5$；
• $1\le l_i\le 2\times 10^5$，$1\le S_{i,j}\le 2\times 10^5$；
• $1\le r_j\le 10^2$，$1\le c_j\le 2\times 10^5$；
• 设 $\sum l$ 为单组测试数据内所有 $l_i$ 的和，则 $\sum l\le 2\times 10^5$。

测试点	$n\le$	$r\le$	$\sum l\le$	$q\le$	特殊性质
$1$	$10^3$	$1$	$2000$	$10^3$	无
$2,3$	$10$	$5$	$20$	$10^2$	无
$4,5$	$10^3$	$10$	$2000$	$10^3$	A
$6$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	A
$7,8$	$10^3$	$10$	$2000$	$10^3$	B
$9,10$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	B
$11,12$	$10^3$	$10$	$2000$	$10^3$	C
$13,14$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	C
$15\sim 17$	$10^3$	$10$	$2000$	$10^3$	无
$18\sim 20$	$10^5$	$10^2$	$2\times 10^5$	$10^5$	无

特殊性质 A：保证 $k=2\times 10^5$。

特殊性质 B：保证 $k\le 5$。

特殊性质 C：保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超过 $5$。
特别难的题！

思路

我们把所有人的序列依次排列成的一个序列设为 $a$，设第 $i$ 个人的序列对应长序列中的 $L_i\sim R_i$ 这一段。

当我们看到 $r_j\le 100$，可以用动态规划，设 $f_{i,t}$ 表示当前为第 $i$ 轮，结束位置是 $t$ 的方案数答案就是 $F(f_{r_j,c_j})$，其中当 $f_{r_j,c_j}>0$ 函数返回 $1$，反之返回 $0$。然而转移需要枚举上一轮的结束点，再检查是否有合法的起始点，这样复杂度至少也要 $O(m^{2}r)$，其中 $m=\sum l_i$。

我们可以把一轮接龙的过程分成两步：先选择一个和上一次接龙未尾数字相同的起始点，在选择一个满足是同一个人，且位置相差在 $2\sim k$ 之间的结束点。

这样，我们发现，第一步只和每个位置上的数字有关，而第二步只和位置有关。因此我们可以把转移分成两步，先根据上一轮的 $f$，计算出合法的起始点，再根据起始点，转移到结束点。

我们再设 $g_{i,s}$ 表示第 $i$ 轮，结束的位置数字为 $s$ 的方案数。则我们可以在求完 $f_{i-1}$ 后直接计算出函数 $g$。

现在我们想如何利用 $g_{i-1}$，计算出 $f_i$。如果没有两轮接龙不能使用同一个人的序列，则我们发现，

$$f_{i,t}=\sum _{l_t\le j\le t-1}{g}_{i-1,a_j}$$

其中 $l_t$ 是 $t-k+1$ 和 $t$ 对应的小序列的第一项较大值，因为 $l_t$ 是单调的，所以利用一个指针，同时记录区间和就可以快速求出 $f_{i,t}$。

但是题目要求两轮接龙不能使用同一个人的序列，而 $g$ 并没有考虑结束的位置属于哪一个人的序列，因此我们需要把两轮接龙相同的人的方案数减掉。考虑这个限制后，新的转移方程为：

$$f_{i,t}=\sum _{l_t\le j\le t-1}(g_{i-1,a_j}-\sum _{L_{B_t}\le b\le R_{B_t},a_b=a_j}{f}_{i-1,b})$$

其中 $B_t$ 表示 $t$ 属于哪一个人的序列，而 ${\sum }_{L_{B_t}\le b\le R_{B_t},a_b=a_j}{f}_{i-1,b}$ 可以求出在 $f_{i-1}$ 后的东西。通过维护数组 $pr{e}_i$ 表示上一个 $a_j=a_i$ 的位置 $j$ 快速计算求出。

综上我们可以在 $O(mr)$ 的时间复杂度通过此题，但此题要开 long long。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=100;
int f[M+5][N],g[M+5][N],h[M+5][N],a[N],l[N],r[N],last[N];
int tmp;
int main(){int T;cin>>T;while(T--){int n,k,q,s;cin>>n>>k>>q;for(int i=1;i<=n;i++){cin>>s;l[i]=r[i-1]+1;r[i]=r[i-1]+s;for(int j=l[i];j<=r[i];j++)cin>>a[i];}memset(g,0,sizeof(g));g[0][1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int L=l[j],cnt=0;f[i][L]=0;for(int t=l[j]+1;t<=r[j];t++){if(t-L+1>k){cnt-=g[i-1][a[L]]-f[i-1][L];L++;}cnt+=g[i-1][a[t-1]]-f[i-1][t-1];f[i][t]=cnt?1:0;g[i][a[t]]+=f[i][t];}for(int t=l[j];t<=r[j];t++){if(last[a[t]])f[i][t]+=f[i][last[a[t]]];last[a[t]]=t;}for(int t=l[j];t<=r[j];t++){last[a[t]]=0;}for(int t=r[j];t>=l[j];t--){if(last[a[t]])f[i][t]=f[i][last[a[t]]];last[a[t]]=t;}for(int t=l[j];t<=r[j];t++)last[a[t]]=0;}int x,y;while(q-->0){tmp++;cin>>x>>y;cout<<(g[x][y]?1:0)<<endl;}}}return 0;
}

最后跟大家投稿票，你觉得今年 CSP 考的比以往难不难