【XCPC】2023 JSCPC National Invitational of CCPC (Hunan)——AFHIJK

本文主要是介绍【XCPC】2023 JSCPC National Invitational of CCPC (Hunan)——AFHIJK，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2023 Jiangsu Collegiate Programming Contest, 2023 National Invitational of CCPC (Hunan), The 13th Xiangtan Collegiate Programming Contest

本蒟蒻该阶段应该顶多处理这几题了，希望以后还能补出更多的题！

I. Elevator

签到题

题面解读

一个电梯里有n个人，选择了m个不同的楼层，询问最多可能有多少人在同一楼层。

分析

显然，当其他 $m-1$ 个人在选择其他楼层时，剩下那个楼层的人一定是最多的。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
int n, m;void solve()
{cin >> n >> m;cout << n - (m - 1) << "\n";
}
int main()
{ios::sync_with_stdio(0), cin.tie(0);int t = 1;cin >> t;while(t--) solve();return 0;
}

H.Neil’s Machine

题面解读

将字符串 $S$ 转变成 $T$ 需要的操作次数，每次操作是将字符串的后缀子串全部 $+K$，其中 $1<=K<=25$。

分析

可以看出，每次操作必须先将前部分全部转为与目标串 $T$ 一致；否则，如果先改后面再改前面，会使得改前部分时后缀部分再次被修改。
所以我们从前往后遍历即可，使用标记记录前方已经修改了多少，逐位比较当前是否已经被修改与目标串一致。如果根据前部分的修改，当前位置已经与目标串一致，则无需操作；否则，执行一次后缀修改。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;int n, arr[N], modify = 0, res = 0;
string s, t;int main()
{ios::sync_with_stdio(0), cin.tie(0);cin >> n >> s >> t;int tag = -1;for(int i =0; i < n; ++i){arr[i] = t[i] - s[i];if(tag == -1 && arr[i] != 0) tag = i;}if(tag == -1){cout << 0 << endl; // 说明目标串与初始串完全相同return 0;}for(int i = tag; i < n; ++i){int temp = (arr[i] % 26 + 26) % 26;if(temp == modify % 26) continue;res ++;modify += ((temp - modify) % 26 + 26) % 26; // 记录前面已经修改了多少}cout << res;
}

J.Similarity (Easy Version)

动态规划，最长公共子串

题面解读

对于每组测试数据，给出 $n$ 个字符串，比较这 $n$ 个字符串的最长公共子串的长度。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 55;
int n;
string str[N];int check(string str1, string str2) 
{int len1 = str1.length(), len2 = str2.length();int start = 0, mx = 0;vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));for(int i = 1;i<=len1;i++){for(int j = 1;j<=len2;j++){if(str1[i-1] == str2[j-1])dp[i][j] = dp[i-1][j-1] + 1;if(dp[i][j] > mx){mx = dp[i][j];start = i - mx;}}}// cout << str1.substr(start,mx) << "\n";return mx;
}void solve()
{cin >> n;for(int i = 1; i <= n; ++i) cin >> str[i];int mx = 0;for(int i = 1; i <= n; ++i) for(int j = i + 1; j <= n; ++j){// 比较第i和j个mx = max(mx, check(str[i], str[j]));}cout << mx << "\n";
}int main()
{ios::sync_with_stdio(0), cin.tie(0);int t = 1;cin >> t;while(t--) solve();return 0;
}

K.Similarity (Hard Version)

构造题

题面解读

构造出 $n$ 个长度为 $k$ 的最长公共子串为 $m$ 的字符串，每个字符串不能一样。

分析

首先，排除无法构造出来的情况。如果，最长公共子串长度为 $0$ 且需要的个数大于26，或者最长的长度大于等于其本身的长度 $k$。
第一个可以构造一个全为 $a$ 的字符串，第二个构造一个与第一个相似度刚好为 $m$ 的字符串，后面全跟 $b$。

随后，构造最长公共子串为 $1$ 的字符串。形如 $acac,...,azaz,bcbc,...,bzbz,...,yzyz$。

参考代码

#include<bits/stdc++.h>
using namespace std;int n, m, k;
string s1, s2, s;void solve()
{cin >> n >> m >> k;if((m == 0 && n > 26) || m >= k){cout << "No\n";return;}cout << "Yes\n";if(m == 0){// 相似度为0,则按序输出即可全a,全b...即可for(int i = 0; i < n; ++i){for(int j = 0; j < k; ++j){cout << char('a' + i);}cout << "\n";}return;}for(int i = 1; i <= k; ++i) s1 += 'a';s2 = s1.substr(0, m);for(int i = m + 1; i <= k; ++i) s2 += 'b';cout << s1 << "\n" << s2 << "\n";// 构造一个abab...abab,这个不可采用// 按照之前构造,ab字段与上面相似度至少为2,如果m == 1,则不符合要求.现在需要构造一个相似度最多为1的字符串for(int i = 0; i < k; ++i) s += s1[i]; for(int i = 1; i <= k; i += 2) s[i] = char(s1[i] + 1);// 构造形如acac,...,azaz,bcbc,...,yzyz的字符串int cnt = 3;while(cnt <= n){if(s[1] == 'z'){for(int i = 1; i < k; i += 2) s[i] = s[0] + 1;for(int i = 0; i < k; i += 2) s[i] += 1;}for(int i = 1; i < k; i += 2) s[i] += 1;cout << s << "\n";cnt++;}
}int main()
{ios::sync_with_stdio(0), cin.tie(0);solve();
}

A.Today’s Word

题面解读

将一个字符串分成前后两部分，每次前半部分保持不动，将后部分执行一个next操作，中间插入一个操作前的字符串。询问执行了 $10^{100}$ 之后，长度为 $m$ 的后缀字符串是什么。

分析

因为模拟的次数足够大，所以最后主要就是看next()处理的后缀字符串。
由于next操作是将字母+1，所以会是一个以26为周期的循环，我们先快速幂求一下 $10^{100}mod26$ 的结果为 $16$。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
ll ksm(ll a, ll b, ll mod)
{ll res = 1;while(b){if(b & 1) res = (res * a) % mod;b >>= 1;a = a * a % mod;}return res % mod;
} // 10e100 % 26 = 16
int n, m;
string str;string next(string s)
{string ret;for(int i = 0; i < s.length(); ++i)ret += ((char)('a' + (s[i] - 'a' + 1) % 26));return ret;
}void solve()
{cin >> n >> m >> str;str = str.substr(str.length() / 2);int op = 0;while(str.length() < m) str = str + next(str), op++;str = str.substr(str.length() - m);op = (16 - op + 26) % 26; while(op--) str = next(str);cout << str << "\n";
}int main()
{ios::sync_with_stdio(0), cin.tie(0);int t = 1;// cin >> t;while(t--) solve();return 0;
}

F. Timaeus

题面解读

总共有 $A$ 个常规材料，每次可以将 $B$ 个常规材料合成为一个高级材料，现在有两种buff，每次合成只能使用一个：

• 每次可以合成出两个高级材料，概率为 $P$
• 合成一个高级材料返还一个常规材料，概率为 $Q$

需要最大化合成出的高级材料的数量期望。

分析

此题考虑使用动态规划进行一个概率期望计算，线性判断使用到第 $i$ 个常规材料时的最大期望数量。其中，通过状态转移方程，可以发现，当每次合成只消耗一个时，需要特判。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
int a, b;
double p, q, dp[N];void solve()
{cin >> a >> b >> p >> q;p = p / 100, q = q / 100;for(int i = b; i <= a; ++i)if(b!=1) 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));else dp[i] = max(p * (dp[i - b] + 2) + (1 - p) * (dp[i - b] + 1), 1 / (1 - q) + dp[i - b]);printf("%.9lf\n", dp[a]);
}int main()
{ios::sync_with_stdio(0), cin.tie(0);int t = 1;// cin >> t;while(t--) solve();return 0;
}

这篇关于【XCPC】2023 JSCPC National Invitational of CCPC (Hunan)——AFHIJK的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---