虽然说只AC了6题, 但也写一个题解吧
所有的代码可以前往这里查看和clone
A.Today's Word
题意:
给定一个字符串, 给定一个特定操作方式: 该字符串前半段 + 该字符串自己 + 该字符串后半段求next(每一个字符向后移动一个), 组成一个新字符串, 求经过10^100次这样的操作后, 新字符串的后m位是什么
思路
题意说明了字符串一定是偶数长度的, 根据给定的数据范围, 可以确定最终的答案只与后半段字符串有关, 那么我们可以在一开始直接截取原字符串的后半段, 通过模拟该变化, 当字符串长度达到m后, 计算距离10^100次变化还差多少次变化即可. 由于每26次求next后都会变为其本身, 那么我们只要知道10^100 MOD 26的大小, 即可直接求出最终答案
代码
// JSCPC 2023 / Don't WA / A.Today's Word
#include <iostream>
using namespace std;
const int MOD = 16;
string getNext(string s) {
string res;
for(auto ss : s) {
res += ss == 'z' ? 'a' : (char)(ss + 1);
}
return res;
}
int main() {
int n, m;
string s;
cin >> n >> m >> s;
string ss = s.substr(s.length() / 2, s.length() / 2);
int cnt = 0;
while(true) {
if(ss.length() >= m) {
break;
}
cnt ++;
ss = ss + getNext(ss);
}
int xx = MOD - (cnt % 26);
while(xx < 0) {
xx += 26;
}
for(int i = ss.length() - m; i < ss.length(); i++){
int now = ss[i] + xx;
if(now > 'z') {
now -= 26;
}
cout << (char)now;
}
cout << endl;
return 0;
}F.Timaeus
题意
有a个原料, 通过b个原料可以生成一个产品, 有两种buff: p%的概率同样的原料生成2个, q%的概率在生成后拿回一个原料, 每次生成只能选择一个buff, 求最终生成产品个数的期望
思路
很显然是个dp, 定义dp[i]为有i个原料时生成产品个数的期望, 那么转移公式为: dp[i] = max(dp[i - b] + (1 * p%), 1 + q% * dp[i - b + 1] + (1 - q%) * dp[i - b]), 表示每次取两种buff的最大值: 多生成一个, 从dp[i - b]转移而来, 和有q%从dp[i - b + 1]转移而来的概率和1 - q%从dp[i - b] 转移而来. 然而, 还需要考虑一种特殊情况: b == 1时, 会有一种: 每次都有q%的概率不用消耗原料就可以生成结果的情况, 对于这种情况应当修改q部分的公式, 那么对于使用1个原料可以生成的结果的期望为1 / (1 - q%), 因此对于这种情况q部分的公式应当为1 / (1 - q%) + dp[i - b].
代码
// JSCPC 2023 / Don't WA / F.Timaeus
#include <iostream>
using namespace std;
const int MAXN = 1e6 + 10;
long double dp[MAXN];
int main() {
int a, b;
double p, q;
for (long double &i: dp) {
i = 0.0;
}
cin >> a >> b >> p >> q;
for (int i = b; i <= a; i++) {
if (b == 1) {
dp[i] = max((long double) dp[i - b] + (long double) (1.00 + (long double) p / 100.0), // p
(long double) 1.00 / ((long double) 1.00 - q / 100.0) +
(long double) dp[i - b]); // q
} else {
dp[i] = max((long double) dp[i - b] + (long double) (1.00 + (long double) p / 100.0), // p
(long double) 1.00 + (long double) dp[i - b + 1] * (long double) q / 100.0 +
(long double) (1.0 - (long double) q / 100.0) * (long double) dp[i - b]); // q
}
}
printf("%.15Lf", dp[a]);
return 0;
}H.Neil's Machine
题意
两个字符串s和t, 一次修改可以把从某个位置到最后的所有字符向后位移若干位, 求从s修改为t的最少操作次数.
思路
难度仅次于签到题的题目, 对每一位进行判断, 计算s和t相应位上的差值, 如果差值和前一位变化, 那么就需要一次操作, 记录次数即可.
代码
// JSCPC 2023 / Don't WA / H.Neil's Machine
#include <iostream>
using namespace std;
int main() {
int n, ans = 0;
cin >> n;
string s, t;
cin >> s >> t;
int last = 0;
for(int i = 0; i < n; i++){
int now = s[i] - t[i];
if(now < 0) {
now += 26;
}
if(now != last) {
ans ++;
}
last = now;
}
cout << ans;
return 0;
}I.Elevator
题意
一个电梯有n个人, 每个人都有一个想去的楼层, 共有m个楼层需要停靠, 求一层楼最多想去的人数.
思路
签到题. 对于其他m - 1个楼层每层1个人, 那么一层楼最多的想去人数为n - (m - 1) = n - m + 1.
代码
// JSCPC 2023 / Don't WA / I.Elevator
#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个字符串, 求任意两个字符串中相同子串的最长长度.
思路
仅次于仅次于签到题题目的难度. 数据范围很小, 直接枚举所有子串即可. 开一个set记录之前所有子串， 开一个set记录当前字符串所有的子串, 如果当前的子串存在于之前的set中, 更新答案, 子串枚举完成后把所有子串放入前一个set即可.
代码
// JSCPC 2023 / Don't WA / J.Similarity (Easy Version)
#include <iostream>
#include <map>
#include <set>
using namespace std;
set<string> mm;
set<string> ss;
int main() {
int T;
cin >> T;
while(T--) {
int n, ans = 0;
cin >> n;
mm = set<string>();
for(int i = 0; i < n; i++){
string s;
cin >> s;
ss = set<string>();
for(int j = 0; j < s.length(); j++){
string now;
now += s[j];
for(int k = j + 1; k < s.length() + 1; k++){
if(mm.find(now) != mm.end()) {
ans = max(ans, k - j);
} else {
ss.insert(now);
}
if(k != s.length()) {
now += s[k];
}
}
}
for(auto it : ss) {
mm.insert(it);
}
}
cout << ans << "\n";
}
return 0;
}K.Similarity (Hard Version)
题意
上一题反过来, 给定字符串个数, 给定最长相同子串长度, 给定字符串长度, 生成字符串满足要求.
思路
首先生成两个字符串, 使得他们的相同子串长度满足要求, 所以让一个全是a, 一个为aaabbb, 那么相同子串的长度就确定了. 然后生成剩下的字符串: 两重循环生成长度为2的字符串: cd ce cf...yz zz长度不够循环自身即可. 需要判断的特殊情况: 1. 最长长度大于等于要求的字符串的长度 2. m == 1时, 如果要求的字符串个数大于26, 那么就无法满足生成个数要求.
代码
// JSCPC 2023 / Don't WA / K.Similarity (Hard Version)
#include <iostream>
using namespace std;
int main() {
int n, m, k;
cin >> n >> m >> k;
if(m >= k) {
cout << "No" << endl;
return 0;
}
if(m == 0) {
if(n > 26) {
cout << "No" << endl;
} else {
cout << "Yes" << endl;
for(int i = 0; i < n; i++) {
for(int j = 0; j < k; j++) {
cout << (char)('a' + i);
}
cout << endl;
}
}
return 0;
}
cout << "Yes" << endl;
for(int i = 0; i < k; i++) {
cout << 'a';
}
cout << endl;
for(int i = m; i < m; i++) {
cout << 'a';
}
for(int i = m; i < k; i++) {
cout << 'b';
}
cout << endl;
int cnt = 2;
for(int i = 0 ; i < 24; i++) {
for(int j = i; j < 24; j++){
if(cnt == n) {
return 0;
}
cnt ++;
string now;
now += (char)(i + 'c');
now += (char)(j + 'c');
for(int p = 0; p < k / 2; p++){
cout << now;
}
if(k % 2 == 1) {
cout << now[0];
}
cout << endl;
}
}
return 0;
}