2023CPCC河南省赛题解＋总结
比赛链接：https://codeforces.com/gym/104354
答题情况：
答题情况
开题顺序是：A-F-H-K-E-B-G
题面链接：https://codeforces.com/gym/104354/attachments/download/20061/statements_2.pdf
Problem A. 小水獭游河南
签到题，队友写的
题意：
给你一个字符串s，问该s是否可以分为a,b两个字符串，其中a字符串需要每个字符不重复出现，b字符串需要为回文，且a+b=s。
思路：
由于所给的s的总长度不会超过\(10^5\)，所以可以遍历分开字符串的位置来判断a，b字符串是否合法即可。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using tup = tuple<int, int, int>;
const ll N = 500005;
const ll P = 80112002;
int n, m, sum, ans;
string s;
void solve() {
cin >> s;
n = s.size();
s = ' ' + s;
set<char> se;
se.insert(s[1]);
int flag = 0;
for (int i = 2; i <= n; i++) {//特判a只有一个字符的情况
if (s[i] != s[n - i + 2]) {
break;
}
if (i == n) {
flag = 1;
}
}
for (int i = 2; i <= n; i++) {
if (se.count(s[i])) {
break;
} else {
se.insert(s[i]);
for (int j = i + 1; j <= n; j++) {
if (s[j] != s[n - j + i + 1]) {
break;
}
if (j == n) {
flag = 1;
}
}
}
}
cout << (flag ? "HE\n" : "NaN\n");
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
Problem B. Art for Rest
赛事队友大爹发挥失常没看懂，遂作罢。赛后才补出这题。
题意：
给你一个序列，对于一个正整数k，将序列分为 \(\lceil n/k \rceil\)段，要求每一段的最大值大于下一段的最小值，请求得最大的k的取值。
思路：
首先预先求得序列中每一位所对应往后的最小值。
设置一个vis数组，当从该位置断开分为前后两组时，前者的最大值小于该位置往后的最小值时，vis[i] = 1,即每一段的最大值大于下一段的最小值。
最后遍历k的大小，对每一个k，我们遍历一次序列，遍历时一次＋=k，当当前位置的vis为0时，说明从此处断开不满足每一段的最大值大于下一段的最小值，于是遍历下一个k，直到找到最大的k。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
ll mod = 1e9+7;
int a[1000006],v[1000006];
int mn[1000006];
int main(){
int t;
t = 1;
// cin>>t;
while(t--){
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", a + i);
mn[n+1] = 1e9+2;
for(int i = n;i>=1;i--){
mn[i] = min(a[i],mn[i+1]);
}
int mx = a[1];
for(int i = 1;i<=n;i++){
mx = max(a[i],mx);
if(mx<=mn[i+1]){
v[i] = 1;
}
}
int ans = 0;
for(int k = 1;k<=n;k++){
int f = 1;
for(int j = k;j<=n;j+=k){
if(v[j] == 0){
f = 0;
break;
}
}
ans += f;
}
cout<<ans;
}
}
Problem Problem E. 矩阵游戏
会意错题意以为是双向bfs导致dp写不出来遂寄。
题意：
给定一个矩阵，仅包含01?三种字符。在0处不加分，1处加一分，？可以修改为1。给定修改的次数，只能向右走和向下走，问从左上角走到右下角得分的最大值。
思路：
可以发现对于每一步都有4种情况：
- 格子值为1时，直接加1分
- 格子值为0时，不加分
- 格子为？时，若修改次数不为零，比较修改和不修改的最大值
- 格子为？时，若修改次数为零，不加分
所以我们可以设计一个三维dp[i][k][p],i代表第i行，k代表第k列，p代表剩余p次修改机会。dp[i][k][p]代表到此处时所能获得的最大分数。但是这么写会不够内存，考虑到只能向右和向下走，所以我们可以优化为滚动dp数组。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
char mp[505][505];
int dp[2][505][1003];
int main(){
int t;
t = 1;
cin>>t;
while(t--){
int n,m,x;
cin>>n>>m>>x;
for(int i = 1;i<=n;i++){
for(int k = 1;k<=m;k++){
cin>>mp[i][k];
}
}
for(int i = 0;i<=1;i++){
for(int k = 0;k<=m;k++){
for(int p = 0;p <= x;p++){
dp[i][k][p] = 0;
}
}
}
int now = 1;
for(int i = 1;i<=n;i++){
for(int k = 1;k<=m;k++){
for(int p = 0;p <= x;p++){
if(mp[i][k] == '1'){
dp[now][k][p] = max(dp[now][k-1][p],dp[now^1][k][p])+1;
}
if(mp[i][k] == '0'){
dp[now][k][p] = max(dp[now][k-1][p],dp[now^1][k][p]);
}
if(mp[i][k] == '?'&&p!=0){
dp[now][k][p] = max({dp[now^1][k][p],dp[now][k-1][p],dp[now][k-1][p-1]+1,dp[now^1][k][p-1]+1});
}
if(mp[i][k] == '?'&&p == 0){
dp[now][k][p] = max(dp[now][k-1][p],dp[now^1][k][p]);
}
}
}
now^=1;
}
cout<<dp[now^1][m][x]<<"\n";
}
}
Problem F. Art for Last
队友大跌秒了，我连题都没来得及看。
题意：
思路：
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using tup = tuple<int, int, int>;
const ll N = 500005;
const ll P = 80112002;
ll n, m, sum, ans = 1e18, na[N], nb[N], k, mx;
vector<ll> ve;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> na[i];
}
deque<int> q;
sort(na + 1, na + 1 + n);
for (int i = 1; i < n; i++) {
nb[i] = na[i + 1] - na[i];
}
for (int i = 1; i <= n; i++) {
// cout << na[i] << " ";
}
// cout << "\n";
for (int i = 1; i < n; i++) {
while (q.size() && nb[q.back()] >= nb[i]) {
q.pop_back();
}
q.push_back(i);
while (q.size() && i - k + 2 > q.front()) {
q.pop_front();
}
if (i >= k - 1) {
ve.push_back(nb[q.front()]);
// cout << nb[q.front()] << " ";
}
}
for (int i = 1; i <= n; i++) {
if (i >= k) {
mx = na[i] - na[i - k + 1];
ans = min(ans, ve[i - k] * mx);
}
}
cout << ans;
return 0;
}
Problem G. Toxel 与字符画
字符大模拟题，还有一点点的数学知识，加起来就是折磨题。
题意：
给你\(x^y\)的数学表达式，要求你将\(x^y = z\)绘制出来，当\(z\geq10^{18}\)时绘制\(x^y = INF\)
思路：
首先将0-9的字符数组存入数组中
然后写一个快速幂
然后判断\(z\geq10^{18}\)判断思路在这里
代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
char big[10][10][9] = {
{
"........",
"........",
".0000000",
".0.....0",
".0.....0",
".0.....0",
".0.....0",
".0.....0",
".0000000",
"........"
},
{
"........",
"........",
".......1",
".......1",
".......1",
".......1",
".......1",
".......1",
".......1",
"........"
},
{
"........",
"........",
".2222222",
".......2",
".......2",
".2222222",
".2......",
".2......",
".2222222",
"........"
},
{
"........",
"........",
".3333333",
".......3",
".......3",
".3333333",
".......3",
".......3",
".3333333",
"........"
},
{
"........",
"........",
".4.....4",
".4.....4",
".4.....4",
".4444444",
".......4",
".......4",
".......4",
"........"
},
{
"........",
"........",
".5555555",
".5......",
".5......",
".5555555",
".......5",
".......5",
".5555555",
"........"
},
{
"........",
"........",
".6666666",
".6......",
".6......",
".6666666",
".6.....6",
".6.....6",
".6666666",
"........"
},
{
"........",
"........",
".7777777",
".......7",
".......7",
".......7",
".......7",
".......7",
".......7",
"........"
},
{
"........",
"........",
".8888888",
".8.....8",
".8.....8",
".8888888",
".8.....8",
".8.....8",
".8888888",
"........"
},
{
"........",
"........",
".9999999",
".9.....9",
".9.....9",
".9999999",
".......9",
".......9",
".9999999",
"........"
}
};
char small[10][10][7] = {
{
"......",
".00000",
".0...0",
".0...0",
".0...0",
".00000",
"......",
"......",
"......",
"......"
},
{
"......",
".....1",
".....1",
".....1",
".....1",
".....1",
"......",
"......",
"......",
"......"
},
{
"......",
".22222",
".....2",
".22222",
".2....",
".22222",
"......",
"......",
"......",
"......"
},
{
"......",
".33333",
".....3",
".33333",
".....3",
".33333",
"......",
"......",
"......",
"......"
},
{
"......",
".4...4",
".4...4",
".44444",
".....4",
".....4",
"......",
"......",
"......",
"......"
},
{
"......",
".55555",
".5....",
".55555",
".....5",
".55555",
"......",
"......",
"......",
"......"
},
{
"......",
".66666",
".6....",
".66666",
".6...6",
".66666",
"......",
"......",
"......",
"......"
},
{
"......",
".77777",
".....7",
".....7",
".....7",
".....7",
"......",
"......",
"......",
"......"
},
{
"......",
".88888",
".8...8",
".88888",
".8...8",
".88888",
"......",
"......",
"......",
"......"
},
{
"......",
".99999",
".9...9",
".99999",
".....9",
".99999",
"......",
"......",
"......",
"......"
},
};
char deng[10][9] = {
"........",
"........",
"........",
"........",
".=======",
"........",
".=======",
"........",
"........",
"........"
};
char inf[10][25] = {
"........................",
"........................",
".IIIIIII.N.....N.FFFFFFF",
"....I....NN....N.F......",
"....I....N.N...N.F......",
"....I....N..N..N.FFFFFFF",
"....I....N...N.N.F......",
"....I....N....NN.F......",
".IIIIIII.N.....N.F......",
"........................"
};
long long poww(long long x, long long y) {
long long ans = 1;
if(x == 1)
return 1;
for(int i = 1; i <= y; i++)
ans *= x;
return ans;
};
string ANS[500];
ll t,x,y;
vector<int>a,b,c;
int main() {
scanf("%d", &t);
while(t--) {
a.clear(); b.clear(); c.clear();
for(int i = 0; i < 450; i++)
ANS[i] = "";
scanf("%lld^{%lld}", &x, &y);
long long tx = x, ty = y;
while(tx) {
a.push_back(tx % 10);
tx /= 10;
}
while(ty) {
b.push_back(ty % 10);
ty /= 10;
}
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
// 先把等号及以前的部分加上
for(int i = 0; i < 10; i++) {
for(auto k : a)
ANS[i] += big[k][i];
for(auto k : b)
ANS[i] += small[k][i];
ANS[i] += deng[i];
}
// log(pow(x, y)) < log(1e18)
// y * log10(x) <= 18.0
if(y * log10(x) <= 18.0) {
long long ans = poww(x, y);
while(ans) {
c.push_back(ans % 10);
ans /= 10;
}
reverse(c.begin(), c.end());
// 加上 x ^ y
for(int i = 0; i < 10; i++) {
for(auto k : c)
ANS[i] += big[k][i];
}
}
else {
// 加上 INF
for(int i = 0; i < 10; i++)
ANS[i] += inf[i];
}
// 每行末尾再补上一个 '.'
for(int i = 0; i < 10; i++)
ANS[i] += '.';
for(int i = 0; i < 10; i++)
cout << ANS[i] << endl;
}
return 0;
}
Problem H. Travel Begins
当时看完题感觉模拟一下就过了
题意：
给定n,k,我们可以将n划分为k个实数，要求：
- 该划分加起来等于n
- 不能有划分出的元素大于n或者小于0
然后对划分出的每一个元素四舍五入求得他们和的最大值和最小值。
思路：
我们可以将该题划分成不同的情况，因为我们要四舍五入，所以我们预先将n×2，此时代表有n个0.5。
当n>k时，说明n可以插入k个格子中，此时最大值为k+(n-k)/2；最小值则要分类讨论，当插入k个格子后，剩余的都放入一个格子中，当剩余的个数为偶数个时，不影响四舍五入，最小值为mn = (n-k+1)/2;反之为mn = (n-k+2)/2;
当n=k时，显而易见最大值为k，最小值为1；
当n<k时，可以发现填不满所有格子，说明四舍五入时可以将所有的格子都约为0，则最小值为0，最大值则为n。
（注意以上讨论的n不是题面给出的n，而是0.5的个数，由题面的n乘以2得来）
代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int a[100005];
int main(){
int t;
t = 1;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
ll mn,mx;
n*=2;
if(n>k){
mx = k+(n-k)/2;
if((n-k+1)%2)
{
mn = (n-k+2)/2;
}else{
mn = (n-k+1)/2;
}
}
if(n == k){
mn = 1;
mx = k;
}
if(n<k){
mn = 0;
mx = n;
}
cout<<mn<<" "<<mx<<"\n";
}
}
Problem K. 排列与质数
这道题是开的最后一题，爽爽折磨两个小时没写出来遗憾下班QAQ
题意：
给定一个正整数n，需要构造一个排列P =（\(P_1\),\(P_2\),\(P_3\),...,\(P_n\)）;
满足：| \(P_i\) - \(P_{i mod n+1}\) |为质数
思路：
对于 n ≤ 11，可以暴力枚举排列求解；
对于 n > 11 的奇数，先将数按照 1, 3, 5, . . . , n − 2, n, n −3, n − 5, . . . , 8, 6, 4 排列；
对于 n > 11 的偶数，先将数按照 1, 3, 5, . . . , n − 3, n, n −2, n − 4, . . . , 8, 6, 4 排列；
即先将奇数升序排列，再将偶数降序排列
代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int a[100005];
bool isprime(int tmp){
if(tmp == 1||tmp == 0) return false;
for(int i = 2;i*i<=tmp;i++){
if(tmp%i==0){
return false;
}
}
return true;
}
int main(){
int t;
t = 1;
// cin>>t;
while(t--){
int n;
cin>>n;
if(n<5) cout<<-1;
else if(n<=11){
int tmp[6] = {0,1,3,5,2,4};
for(int i = 1;i<=n-(n%5);i+=5){
a[i] = tmp[1];
a[i+1] = tmp[2];
a[i+2] = tmp[3];
a[i+3] = tmp[4];
a[i+4] = tmp[5];
for(int k = 1;k<=5;k++) tmp[k]+=5;
}
if(n%5 == 1){
a[n] = n;
}
if(n%5 == 2){
a[n] = n-1;
a[n-1] = n-3;
a[n-2] = n-5;
a[n-3] = n;
}
if(n%5 == 3){
a[n] = n;
a[n-1] = n-2;
a[n-2] = n-4;
a[n-3] = n-6;
a[n-4] = n-1;
}
if(n%5 == 4){
a[n] = n-1;
a[n-1] = n-3;
a[n-2] = n-5;
a[n-3] = n;
a[n-4] = n-7;
a[n-5] = n-2;
}
if(n == 10){
swap(a[n],a[5]);
}
if(n == 11){
swap(a[6],a[n]);
}
for(int i = 1;i<=n;i++){
cout<<a[i]<<" ";
}
}
else{
vector<int> p;
if(n%2){
for(int i = 1;i<=n;i+=2){
p.push_back(i);
}
for(int i = n-3;i>=4;i-=2){
p.push_back(i);
}
for(int i = 0;i<p.size();i++){
cout<<p[i]<<" ";
if(p[i] == 5){
cout<<"2 ";
}
if(p[i] == n-6){
cout<<n-1<<" ";
}
}
}
else{
for(int i = 1;i<=n-3;i+=2){
p.push_back(i);
}
for(int i = n;i>=4;i-=2){
p.push_back(i);
}
for(int i = 0;i<p.size();i++){
cout<<p[i]<<" ";
if(p[i] == 5){
cout<<"2 ";
}
if(p[i] == n-4){
cout<<n-1<<" ";
}
}
}
}
}
}