首发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 % 50\% 50% 的分数,正解是数论找规律。
假设我们把所有位数都设置成 8 8 8,则如果结果大于 n n n,我们就可以减少木棍数量。即 n = 7 k − t n=7k-t n=7k−t,其中 k k k 为位数, t t t 为减去几根木棍。
我们分类讨论 t t t 等于多少:
- 如果 t = 0 t=0 t=0,无需去除木棍。
- 如果 t = 1 t=1 t=1,去除第一位的一个木棍变成 6 6 6。
- 如果 t = 2 t=2 t=2,去除第一位的两个木棍变成 2 2 2。
- 如果 t = 3 t=3 t=3,去除第一位的两个木棍变成 2 2 2,去除第二位的一个木棍变成 0 0 0。
- 如果 t = 4 t=4 t=4,去除第一位的两个木棍变成 2 2 2,去除第二位的一个木棍变成 0 0 0,去除第三位的一个木棍变成 0 0 0。
- 如果 t = 5 t=5 t=5,去除第一位的五个木棍变成 1 1 1。
- 如果 t = 6 t=6 t=6,去除第一位的五个木棍变成 1 1 1,去除第二位的一个木棍变成 0 0 0。
但这样有缺陷,比如如果 t = 4 t=4 t=4 需要去除 3 3 3 位,但是如果 n = 7 × 2 − 4 = 10 n=7\times2-4=10 n=7×2−4=10,只有两位,或者 n = 7 × 1 − 4 = 3 n=7\times1-4=3 n=7×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 n n 个人参与这个接龙游戏,第 i i i 个人会获得一个整数序列 S i S_i Si 作为他的词库。
一次游戏分为若干轮,每一轮规则如下:
- n n n 个人中的某个人 p p p 带着他的词库 S p S_p Sp 进行接龙。若这不是游戏的第一轮,那么这一轮进行接龙的人不能与上一轮相同,但可以与上上轮或更往前的轮相同。
- 接龙的人选择一个长度在 [ 2 , k ] [2, k] [2,k] 的 S p S_p Sp 的连续子序列 A A A 作为这一轮的接龙序列,其中 k k k 是给定的常数。若这是游戏的第一轮,那么 A A A 需要以元素 1 1 1 开头,否则 A A A 需要以上一轮的接龙序列的最后一个元素开头。
- 序列 A A A 是序列 S S S 的连续子序列当且仅当可以通过删除 S S S 的开头和结尾的若干元素(可以不删除)得到 A A A。
为了强调合作,小 J 给了 n n n 个参与游戏的人 q q q 个任务,第 j j j 个任务需要这 n n n 个人进行一次游戏,在这次游戏里进行恰好 r j r_j rj 轮接龙,且最后一轮的接龙序列的最后一个元素恰好为 c j c_j cj。为了保证任务的可行性,小 J 请来你判断这 q q q 个任务是否可以完成的,即是否存在一个可能的游戏过程满足任务条件。
输入格式
本题有多组测试数据。
输入的第一行包含一个正整数 T T T,表示数据组数。
接下来包含 T T T 组数据,每组数据的格式如下:
第一行包含三个整数 n , k , q n, k, q n,k,q,分别表示参与游戏的人数、接龙序列长度上限以及任务个数。
接下来 n n n 行:
第 i i i 行包含 ( l i + 1 ) (l_i + 1) (li+1) 个整数 l i , S i , 1 , S i , 2 , … , S i , l i l_i, S_{i,1}, S_{i,2}, \dots , S_{i,l_i} li,Si,1,Si,2,…,Si,li,其中第一个整数 l i l_i li 表示序列 S i S_i Si 的长度,接下来 l i l_i li 个整数描述序列 S i S_i Si。
接下来 q q q 行:
第 j j j 行包含两个整数 r j , c j r_j, c_j rj,cj,描述一个任务。
输出格式
对于每个任务:输出一行包含一个整数,若任务可以完成输出 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 p_1 = 1 p1=1、 A 1 = 12 A_1 = 12 A1=12 是一个满足条件的游戏过程。
- 对于第二组询问,可以证明任务不可完成。注意 p 1 = 1 p_1 = 1 p1=1、 A 1 = 1234 A_1 = 1234 A1=1234 不是合法的游戏过程,因为此时 ∣ A 1 ∣ = 4 > k |A_1| = 4 > k ∣A1∣=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 k 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 2 2,因此 A 1 = 1 A_1 = 1 A1=1 不是一个合法的游戏过程。
- 对于第七组询问,所有人的词库均不存在字符 7 \tt 7 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 ≤ 1000 n \leq 1000 n≤1000、 r ≤ 10 r \leq 10 r≤10、单组测试数据内所有词库的长度和 ≤ 2000 \leq 2000 ≤2000、 q ≤ 1000 q \leq 1000 q≤1000。
【样例 5】
见选手目录下的 chain/chain5.in 与 chain/chain5.ans。
该样例满足特殊性质 B,其中前两组测试数据满足 n ≤ 1000 n \leq 1000 n≤1000、 r ≤ 10 r \leq 10 r≤10、单组测试数据内所有词库的长度和 ≤ 2000 \leq 2000 ≤2000、 q ≤ 1000 q \leq 1000 q≤1000。
【样例 6】
见选手目录下的 chain/chain6.in 与 chain/chain6.ans。
该样例满足特殊性质 C,其中前两组测试数据满足 n ≤ 1000 n \leq 1000 n≤1000、 r ≤ 10 r \leq 10 r≤10、单组测试数据内所有词库的长度和 ≤ 2000 \leq 2000 ≤2000、 q ≤ 1000 q \leq 1000 q≤1000。
【数据范围】
对于所有测试数据,保证:
- 1 ≤ T ≤ 5 1 \leq T \leq 5 1≤T≤5;
- 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105, 2 ≤ k ≤ 2 × 1 0 5 2 \leq k \leq 2 \times 10^5 2≤k≤2×105, 1 ≤ q ≤ 1 0 5 1 \leq q \leq 10^5 1≤q≤105;
- 1 ≤ l i ≤ 2 × 1 0 5 1 \leq l_i \leq 2 \times 10^5 1≤li≤2×105, 1 ≤ S i , j ≤ 2 × 1 0 5 1 \leq S_{i,j} \leq 2 \times 10^5 1≤Si,j≤2×105;
- 1 ≤ r j ≤ 1 0 2 1 \leq r_j \leq 10^2 1≤rj≤102, 1 ≤ c j ≤ 2 × 1 0 5 1 \leq c_j \leq 2 \times 10^5 1≤cj≤2×105;
- 设 ∑ l \sum l ∑l 为单组测试数据内所有 l i l_i li 的和,则 ∑ l ≤ 2 × 1 0 5 \sum l\leq 2\times 10^5 ∑l≤2×105。
测试点 | n ≤ n\leq n≤ | r ≤ r\leq r≤ | ∑ l ≤ \sum l\leq ∑l≤ | q ≤ q\leq q≤ | 特殊性质 |
---|---|---|---|---|---|
1 1 1 | 1 0 3 10^3 103 | 1 1 1 | 2000 2000 2000 | 1 0 3 10^3 103 | 无 |
2 , 3 2,3 2,3 | 10 10 10 | 5 5 5 | 20 20 20 | 1 0 2 10^2 102 | 无 |
4 , 5 4,5 4,5 | 1 0 3 10^3 103 | 10 10 10 | 2000 2000 2000 | 1 0 3 10^3 103 | A |
6 6 6 | 1 0 5 10^5 105 | 1 0 2 10^2 102 | 2 × 1 0 5 2\times 10^5 2×105 | 1 0 5 10^5 105 | A |
7 , 8 7,8 7,8 | 1 0 3 10^3 103 | 10 10 10 | 2000 2000 2000 | 1 0 3 10^3 103 | B |
9 , 10 9,10 9,10 | 1 0 5 10^5 105 | 1 0 2 10^2 102 | 2 × 1 0 5 2\times 10^5 2×105 | 1 0 5 10^5 105 | B |
11 , 12 11,12 11,12 | 1 0 3 10^3 103 | 10 10 10 | 2000 2000 2000 | 1 0 3 10^3 103 | C |
13 , 14 13,14 13,14 | 1 0 5 10^5 105 | 1 0 2 10^2 102 | 2 × 1 0 5 2\times 10^5 2×105 | 1 0 5 10^5 105 | C |
15 ∼ 17 15\sim 17 15∼17 | 1 0 3 10^3 103 | 10 10 10 | 2000 2000 2000 | 1 0 3 10^3 103 | 无 |
18 ∼ 20 18\sim 20 18∼20 | 1 0 5 10^5 105 | 1 0 2 10^2 102 | 2 × 1 0 5 2\times 10^5 2×105 | 1 0 5 10^5 105 | 无 |
特殊性质 A:保证 k = 2 × 1 0 5 k = 2 \times 10^5 k=2×105。
特殊性质 B:保证 k ≤ 5 k ≤ 5 k≤5。
特殊性质 C:保证在单组测试数据中,任意一个字符在词库中出现次数之和均不超过 5 5 5。
特别难的题!
思路
我们把所有人的序列依次排列成的一个序列设为 a a a,设第 i i i 个人的序列对应长序列中的 L i ∼ R i L_i\sim R_i Li∼Ri 这一段。
当我们看到 r j ≤ 100 r_j\le100 rj≤100,可以用动态规划,设 f i , t f_{i,t} fi,t 表示当前为第 i i i 轮,结束位置是 t t t 的方案数答案就是 F ( f r j , c j ) F(f_{r_j,c_j}) F(frj,cj),其中当 f r j , c j > 0 f_{r_j,c_j}>0 frj,cj>0 函数返回 1 1 1,反之返回 0 0 0。然而转移需要枚举上一轮的结束点,再检查是否有合法的起始点,这样复杂度至少也要 O ( m 2 r ) O(m^2r) O(m2r),其中 m = ∑ l i m=\sum l_i m=∑li。
我们可以把一轮接龙的过程分成两步:先选择一个和上一次接龙未尾数字相同的起始点,在选择一个满足是同一个人,且位置相差在 2 ∼ k 2\sim k 2∼k 之间的结束点。
这样,我们发现,第一步只和每个位置上的数字有关,而第二步只和位置有关。因此我们可以把转移分成两步,先根据上一轮的 f f f,计算出合法的起始点,再根据起始点,转移到结束点。
我们再设 g i , s g_{i,s} gi,s 表示第 i i i 轮,结束的位置数字为 s s s 的方案数。则我们可以在求完 f i − 1 f_{i-1} fi−1 后直接计算出函数 g g g。
现在我们想如何利用 g i − 1 g_{i-1} gi−1,计算出 f i f_i fi。如果没有两轮接龙不能使用同一个人的序列,则我们发现,
f i , t = ∑ l t ≤ j ≤ t − 1 g i − 1 , a j f_{i,t}=\sum_{l_t\le j\le t-1}g_{i-1,a_j} fi,t=lt≤j≤t−1∑gi−1,aj
其中 l t l_t lt 是 t − k + 1 t-k+1 t−k+1 和 t t t 对应的小序列的第一项较大值,因为 l t l_t lt 是单调的,所以利用一个指针,同时记录区间和就可以快速求出 f i , t f_{i,t} fi,t。
但是题目要求两轮接龙不能使用同一个人的序列,而 g g g 并没有考虑结束的位置属于哪一个人的序列,因此我们需要把两轮接龙相同的人的方案数减掉。考虑这个限制后,新的转移方程为:
f i , t = ∑ l t ≤ j ≤ t − 1 ( g i − 1 , a j − ∑ L B t ≤ b ≤ R B t , a b = a j f i − 1 , b ) 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}) fi,t=lt≤j≤t−1∑(gi−1,aj−LBt≤b≤RBt,ab=aj∑fi−1,b)
其中 B t B_t Bt 表示 t t t 属于哪一个人的序列,而 ∑ L B t ≤ b ≤ R B t , a b = a j f i − 1 , b \sum_{L_{B_t}\le b\le R_{B_t},a_b=a_j}f_{i-1,b} ∑LBt≤b≤RBt,ab=ajfi−1,b 可以求出在 f i − 1 f_{i-1} fi−1 后的东西。通过维护数组 p r e i pre_i prei 表示上一个 a j = a i a_j=a_i aj=ai 的位置 j j j 快速计算求出。
综上我们可以在 O ( m r ) O(mr) 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 考的比以往难不难