JSCPC(江苏省大学生程序设计大赛)

历年题目列表

2024 Jiangsu Collegiate Programming Contest

2023 Jiangsu Collegiate Programming Contest

2022 Jiangsu Collegiate Programming Contest

2021 Jiangsu Collegiate Programming Contest

CSDN

题目(可提交) : JSCPC-Codeforces

题解: 【金山文档】 2023JSCPC_and_Xiangtan_Tutorial

A Today’s Word

题目大意

• 定义 Sn 的构造方式为:

• 其中 + 表示字符串拼接,next(·) 表示把字符串中每一个字符都换成下一个字符,z 换成 a.
• 给定一个长度为偶数且只包含小写字母的字符串S0,按如上方法构造字符串S10100,问这个字符串长为 m 的后缀是什么。

思路

• 考虑当 Sk 长度超过 2m 时,再进行一次操作后,其长度为m 的后缀只会进行 next(·) 变换,把这个长为 m 的后缀的每个字符变成下一个字符。因此考虑暴力将 S0 按构造方式操作,求出一个长度大于 2m 的 Sk,取 Sk 长度为 m 的后缀进行 next(·) 变换即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
using namespace std;
string next(string s,int t)
{
for(int i=0;i<s.size();i++)
s[i] = ((s[i]-'a')+t)%26+'a';
return s;
}
string subSum(string s)
{
int idx = s.size()/2;
string res=s.substr(0,idx);
res += s;
res += next(s.substr(idx),1);
return res;
}
int main()
{
int n,m;
cin>>n>>m;
string s;
cin>>s;
int cnt = 0;
while(s.size()<m*2)
{
cnt ++;
s = subSum(s);
}
s = next(s,((16-cnt)%26+26)%26);
cout<<s.substr(s.size()-m)<<endl;
return 0;
}

点击并拖拽以移动

F Timaeus

题目大意

你有 A 个原料,每 B 个合成一个产品。每一次合成你可以选择下列两种 buff 的任意一种:
1 P% 的概率合成双倍产物
2 Q% 的概率返还一个原料求期望最多合成多少产物。

思路

• 设 dp(i) 表示还剩下 i 个原料时的最大期望。根据题意,容易得到如下 dp 方程:
dp(i) = max{P × (dp(i − B) + 2) + (1 − P) × (dp(i − B) + 1),Q × (dp(i − B + 1) + 1) + (1 − Q) × (dp(i − B) + 1)}
• 注意 B = 1 时需要特判。此时只选择其中一种 buff 是最优的,可以分别算出各自的期望值然后取 max 即可。
• 时间复杂度:O(A)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
const int N = 1000010;
double dp[N];
int main()
{
int a,b;
double p,q;
cin>>a>>b>>p>>q;
p /= 100; q /= 100;
for(int i=b;i<=a;i++)
dp[i] = max(p*(dp[i-b]+2)+(1-p)*(dp[i-b]+1),q*(dp[i-b+1]+1)+(1-q)*(dp[i-b]+1));
printf("%.15f",b==1?max(a*1.0/(1-q),dp[a]):dp[a]);
}

点击并拖拽以移动

H Neil’s Machine

题目大意

• 有两个长度为 n, 数值为 0 − 25 的数组 S, T。每次操作可以选择一个正数 k (1 ≤ k ≤ 25), 并选择 S 的一个后缀加 k模 26,问至少几次操作可以令 S = T。

思路

• 设 S0 = T0 = 0,
DSi = (Si−Si−1+26) mod 26, DTi = (Ti−Ti−1+26) mod 26(1 ≤ i ≤ n),则 S = T 等价于 DS = DT。每次操作可以将一个 DSi 修改为 0 − 25 的任意数,故统计 DSi ≠ DTi 的数
量即可。时间复杂度 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<math.h>
using namespace std;
const int N = 200010;
int f[N];
int main()
{
int n;
string s1,s2;
cin>>n>>s1>>s2;
int last = 0,res = 0;
for(int i=0;i<n;i++)
f[i] = (s1[i]-s2[i]+26)%26;
for(int i=0;i<n;i++)
{
int c = (f[i]-last+26)%26;
if(c!=0) res ++;
last = (last+c)%26;
}
cout<<res<<endl;
return 0;
}

点击并拖拽以移动

I Elevator

题目大意

• 电梯里有 n 个人(你是其中一个),这些人想去 m 个楼层,每个人只想去一个楼层。到达一个楼层,所有想去这个楼层的人都会下电梯。问在你想去的楼层最多有多少人下电梯。

思路

考虑鸽巢原理,其中人数最多的情况为:在你不想去的楼层每层只下一个人,在你想去的楼层能下的都下。考虑在m − 1 个不想去的楼层每层分配一个人下梯,那么在想去的楼层一起下梯的就有 n − (m − 1) 人。考虑调整法,可以证明这是最多情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
cout<<n-m+1<<endl;
}
return 0;
}

点击并拖拽以移动

J Similarity (Easy Version)

题目大意

• 给定 n 个串,求两两之间最长公共子串的最大值。

思路

• 直接暴力对 n2 个二元组 (si, sj) 跑最长公共子串即可,或者考虑暴力枚举匹配也可以通过。
• 复杂度 O(T × n4) 或 O(T × n5)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<cstring>
using namespace std;
const int N = 55;
int dp[N][N];
int match(string s1,string s2)
{
memset(dp,0,sizeof dp);
int res = 0;
int n = s1.size(),m = s2.size();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(s1[i-1]==s2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
res = max(dp[i][j],res);
}
return res;
}
string f[N];
int main()
{
int T;
cin>>T;
while(T--)
{
int n,res = 0;
cin>>n;
for(int i=0;i<n;i++)
cin>>f[i];
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
res = max(match(f[i],f[j]),res);
cout<<res<<endl;
}
return 0;
}

点击并拖拽以移动

K Similarity (Hard Version)

题目大意

• 构造 n 个不同的长度为 k 的只由小写字符组成的字符串,使得其两两之间最长公共子串的最大值等于 m。

思路

• 首先特判如下情况无解:1 m = 0, n > 26 时无解2 m != 0, m ≥ k 时无解
• 剩下的有解情况可以按如下方式构造:
1 m = 0 时,直接输出长度为 k 的只由第 i 个字母组成的小写字母组成的串即可。
2 m != 0,时,我们考虑构造如下形式的字符串:
a1a2a1a2a1a2a1a2 · · ·
其中 a1 和 a2 分别表示一种不同的小写字母,且 a1 < a2 < z
• 那么对于这种类型的串一共有 25×(25−1)/2= 300 种,两两之间的最长公共子串长度均不超过 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<cstring>
using namespace std;
string s1 = "",s2 = "";
string make(int k,char c)
{
string s = "";
for(int i=0;i<k;i++)
s += c;
return s;
}
void print(int len,int n,int m)
{
if(m==0) {
string s = make(len,'a');
for(int i=0;i<n+2;i++){
cout<<s<<endl;
for(int j=0;j<len;j++)
s[j]++;
}
}
else{
string s = make(len,'a');
for(int j=1;j<len;j+=2)
s[j] = s[j]+1;
for(int i=0;i<800;i++)
{
if(s[1]=='z')
{
for(int j=1;j<len;j+=2)
s[j] = s[0]+1;
for(int j=0;j<len;j+=2)
s[j] = s[j]+1;
}
for(int j=1;j<len;j+=2)
s[j] = s[j]+1;
if(n!=0 && s1!=s && s2!=s) cout<<s<<endl,n--;
else if(n==0) break;
}
}
}
int main()
{
int n,m,k;
cin>>n>>m>>k;
if(m>=k || (n>26 && m==0))
puts("No");
else{
puts("Yes");
s1 = make(k,'a');
s2 = s1.substr(0,m);
for(int i=0;i<k-m;i++)
s2 += 'b';
if(m!=0)cout<<s1<<"\n"<<s2<<"\n";
print(k,n-2,m);
}
return 0;
}

点击并拖拽以移动


JSCPC(江苏省大学生程序设计大赛)
https://leaf-domain.gitee.io/2023/10/01/JSCPC/
作者
叶域
发布于
2023年10月1日
许可协议