2023 河南 CCPC省赛

题目链接

VP赛况：

赛况及总结

赛况

开场：我提前打印了题册，于是我们开始分开看题目，我先看了A，发现很签，遂上机，8 min 1A。
接着跟榜看了F，发现枚举长度为k的子区间就行。又上机去写，交上去wa，发现区间min被我直接连续取min。Akimizussq提出单调队列滑动窗口即可。我赶忙上机修改，让他们去看榜上有人开的其他题。结果，我写臭了，被下标疯狂折磨，调试半天交上去还是wa。然后决定拿multiset搞，修改后，感觉没问题交上去还是wa。这时候就有些慌了。Akimizussq和zky0902来机前，我给他们讲了思路，感觉没什么问题。。。看了一会发现我ans初值赋的0x3f3f3f3f,这题数据范围很大。所以改成ans=0x3f3f3f3f3f3f3f3f。1h27min 3A，这三发罚时都是我脑抽贡献的！

赛中：接着我们看榜，我去看B，Akimizussq去看了E，说是个DP。就开始双线程，B题我一开始觉得二分，只要区间最大值小于下一区间最小值即可。思考check函数怎么写的时候，Akimizussq说他会了E，遂上机写，可惜wa了。我上机去写B，码完一交喜提一wa。check函数写假了，改了两次，最后wa在第15个点。最后发现直接维护前缀最大值和后缀最小值即可，然后枚举就能写，赶紧上机码完，2h 8min 4A。
接着开始接手Akimizussq和zky0902在讨论的H题，这时候，我脑子不太清楚，绕在里面，好在Akimizussq很快将情况分类清楚了，我理解完就开始写，结果精度不够，wa了一发，改了一下3h 21min 3A
赛末：这段时间处理的不好，我们没有继续去看别的题，导致简单的C题都没有开，然后我和Akimizussq 决定开E，感觉就是摘花生多加一维而已，柿子当然就没什么问题，结果脑子抽了，空间爆了，就否定了这个想法（前天刚写过滚动数组优化），我的锅！最后我看到群友过了C，就跑去看了一下，大水题，随便写了一下，4h 6min 4A。只打了四个小时，最后就定格在5题870罚时。

总结

临近期末，这是本学期最后一次一起训练，由于环境限制，只能打4个小时，这套题目大部分题目还是不难的，5题罚时870，打的不是很好。我代码精准度不够，罚时较多。并且时间安排和机时安排还存在问题。下次应该一人开题的时候，其他队友继续看其他题目，大概获得方向即可。而不是两人死磕一道题(这样的方式只针对后面难题)
这样简单题可以很快解决完。接着就是继续提升实力！暑假将至，希望大家认真备考(yuxi)期末考试。继续加油！

补题

A 小水獭游河南 签到
题意：给你一个字符串让你判断能否将该字符串拆成两段非空字符串，前半段字符串每个字母只出现一次，后半段是一个回文串。

思路：从头开始遍历，每次判一下后面半部分是不是回文串即可。遇到出现过的字符就跳出循环即可。

参考代码：

#include<bits/stdc++.h>using namespace std;#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;int st[26];
void Showball(){string s;cin>>s;int n=s.size();memset(st,0,sizeof st);int ok=0;for(int i=0;i<n;i++){int t=s[i]-'a';if(st[t]) break;st[t]=1;if(i+1<n){string a=s.substr(i+1);string b=a;reverse(all(a));if(a==b) {ok=1;break;}}}if(ok) cout<<"HE\n";else cout<<"NaN\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T=1;if(cases) cin>>T;while(T--)Showball();return 0;
}

B. Art for Rest 思维
题意：给你一个数组a，对于一个正整数k($1\le k\le n$)，我们把数组a每k个分成一组，一共分$n/k$组，如果我们把每组中的数排序，最后整个数组a都已排好序，那么就是满足条件的k。
让你找出所有满足条件的k有多少个？
思路：一个很显然的性质，我们要满足条件必须保证前一个区间的最大值不大于后一个区间的最小值即可。
但是由于我们需要枚举k，然后进行判断，如果进行滑动窗口就会超时。我们继续探究它的性质。我们发现，因为无论k为多大，我们最终要完成整个数组的排序，那么这个最大值和最小值的关系都是全段满足的。因此，我们可以预处理出前缀最大值，和后缀最小值即可。

参考代码：

#include<bits/stdc++.h>using namespace std;#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 2e6 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;int n;
int a[N];
int pre[N];
int suf[N];
void Showball(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}pre[0]=0,suf[n+1]=inf;for(int i=1;i<=n;i++) pre[i]=max(pre[i-1],a[i]);for(int i=n;i>=1;i--) suf[i]=min(suf[i+1],a[i]);int cnt=0;for(int i=1;i<=n;i++){int ok=1;for(int j=i+1;j<=n;j+=i){if(pre[j-1]>suf[j]){ok=0;break;}}if(ok) cnt++;}cout<<cnt<<endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T=1;if(cases) cin>>T;while(T--)Showball();return 0;
}

C Toxel 与随机数生成器 字符串
题意：给你两段生成随机数的代码，其中错误代码会出现周期性重复，给你一段随机数，让你判断是由哪段代码生成的。
思路：很简单，我们直接判断是否存在周期性重复。可以直接暴力判断，这里用kmp写一下。判断next数组最大值是否大于50即可。

参考代码：

#include<bits/stdc++.h>using namespace std;#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;int ne[N];
void Showball(){string s;cin>>s;int n=s.size();s="?"+s;for(int i=2,j=0;i<=n;i++){while(j&&s[i]!=s[j+1]) j=ne[j];if(s[i]==s[j+1]) j++;ne[i]=j;}int ans=0;for(int i=1;i<=n;i++){ans=max(ans,ne[i]);}cout<<(ans>=50?"No\n":"Yes\n");
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T=1;if(cases) cin>>T;while(T--)Showball();return 0;
}

E. 矩阵游戏 线性DP
题意：给你一个矩阵，矩阵有三种值，‘0’，‘1’，‘？’,走到‘1’直接加一分。走到‘0’不加分，走到‘？’可以把‘？’变成‘1’，最多只能变x次。问你从左上角走到右下角最多能获得多少分？

思路：参考摘花生这道题目，可以发现这题就是线性DP，只是多了一维来表示修改次数即可。即$f_{i,j,k}$表示所有到$(i,j)$并且修改了$k$次问号的走法获得的最大分数。因此，可以得到状态转移表达式：
$f_{i,j,k}=max(f_{i-1,j,k},f_{i,j-1,k}),$ 当$s[i][j]=‘0’$
$f_{i,j,k}=max(f_{i-1,j,k},f_{i,j-1,k})+1,$ 当 $s[i][j]=‘1’$
$f_{i,j,k}=max(f_{i-1,j,k},f_{i,j-1,k}),$ 当 $k=0\&\&s[i][j]=‘?’$
$f_{i,j,k}=max(f_{i-1,j,k},f_{i,j-1,k},f_{i-1,j,k-1}+1,f_{i,j-1,k-1}+1),$ 当 $k\ne 0\&\&s[i][j]=‘?’$

三层循环500*500*1000空间会炸，由于我们只用到了当前层和前一层的结果，所以就可以进行经典的滚动数组优化即可。由于是多测，记得初始化，不要无脑用memset(会TLE)。

参考代码：

#include<bits/stdc++.h>using namespace std;#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1010 , M =510;
const int mod = 1e9 + 7;
const int cases = 1;int f[2][M][N];
int n,m,x;
char s[M][M];
void Showball(){cin>>n>>m>>x;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) {cin>>s[i][j];}}for(int j=1;j<=m;j++){for(int k=0;k<=x;k++){f[0][j][k]=0;f[1][j][k]=0;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=0;k<=x;k++){if(s[i][j]=='0') f[i&1][j][k]=max(f[(i-1)&1][j][k],f[i&1][j-1][k]);else if(s[i][j]=='1') f[i&1][j][k]=max(f[(i-1)&1][j][k],f[i&1][j-1][k])+1;else {if(!k) f[i&1][j][k]=max(f[(i-1)&1][j][k],f[i&1][j-1][k]);else {f[i&1][j][k]=max(f[(i-1)&1][j][k],f[i&1][j-1][k]);f[i&1][j][k]=max({f[i&1][j][k],f[(i-1)&1][j][k-1]+1,f[i&1][j-1][k-1]+1});}}}}}int res=0;for(int i=0;i<=x;i++) res=max(res,f[n&1][m][i]);cout<<res<<endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T=1;if(cases) cin>>T;while(T--)Showball();return 0;
}

F Art for Last 贪心+单调队列（Multiset）
题意：给你一个只含有非负整数的数组a，给你正整数k，让你从中随意选出k项，使得这k项任意两数之差绝对值最小值和任意两数之差绝对值最大值的乘积最小，求出这个最小值。

思路：为了方便，我们将任意两数之差绝对值最小值定义为$amin$，最大值为$amax$。我们先将这个数组进行排序，现在让我们从中选取k个数，由于这些数都是非负数，所以我们可以知道$amax$的值就等于选出来的值最大值减去最小值。而$amin$等于两两相邻数之差。为了让$amin$更小，所以根据贪心策略，我们连续的选k个数，比间隔选k个数的策略是更优的。问题转化为：对于连续的长度为k的区间，求出$amin\ast amax$的最小值。那么我们就可以来枚举每个连续的长度为k的区间。设左端点为$l$,右端点是$r$。容易得知$amax=a[r]-a[l]$，那么对于$amin$,就等于这一段区间的相邻数之差的最小值，我们可以提前处理出两数之差的数组b，然后对于定长区间最值，很显然的滑动窗口最值问题，用单调队列维护一下就可以了。记得开long long！ans初始化大一些（血的教训！！！）

参考代码：

#include<bits/stdc++.h>using namespace std;#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 5e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;LL a[N],b[N],q[N];
int n,k;
void Showball(){cin>>n>>k;for(int i=0;i<n;i++) {cin>>a[i];}sort(a,a+n);for(int i=0;i<n;i++){if(i) b[i-1]=a[i]-a[i-1];}vector<LL> res;int kk=k-1;int hh=0,tt=-1;for(int i=0;i<n-1;i++){if(hh<=tt&&i-kk+1>q[hh]) hh++;while(hh<=tt&&b[q[tt]]>=b[i]) tt--;q[++tt]=i;if(i>=kk-1) res.pb(b[q[hh]]);}LL ans=0x3f3f3f3f3f3f3f3f;LL minn=0;for(int i=0;i+k-1<n;i++){int r=i+k-1;minn=res[i];ans=min(ans,minn*(a[r]-a[i]));     }cout<<ans<<endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T=1;if(cases) cin>>T;while(T--)Showball();return 0;
}

当然本题也可以用multiset解决，每次移动我们把$a[l]-a[l-1]$删去，然后加上$a[r]-a[r-1]$即可。
参考代码：

#include<bits/stdc++.h>using namespace std;#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 5e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;LL a[N],b[N],q[N];
int n,k;
void Showball(){cin>>n>>k;for(int i=0;i<n;i++) {cin>>a[i];}sort(a,a+n);multiset<LL> st;for(int i=1;i<k;i++){st.insert(a[i]-a[i-1]);}LL minn=0;LL ans=0x3f3f3f3f3f3f3f3f;for(int i=0;i+k-1<n;i++){int l=i;int r=i+k-1;if(i){auto x=st.find(a[l]-a[l-1]);st.erase(x);st.insert(a[r]-a[r-1]);}minn=*st.begin();ans=min(ans,minn*(a[r]-a[l]));     }cout<<ans<<endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T=1;if(cases) cin>>T;while(T--)Showball();return 0;
}

G Toxel与字符画 模拟题
题意：给你两个数让你求出$x^y$，如果结果小于1e18，就用字符画输出整个式子，否则结果输出字符画"INF"。
思路：对于输出直接模拟就可以，比较好实现的方法就是，用三个字符数组，把样例直接粘进去，然后输出的时候截取一下就行，我为了代码优雅，选择了手打分号！(赛场上非要这样建议让手速队友去搞hh），然后说一下这个判是否超过1e18，一开始用快速幂，发现会wa，可能中间就爆了，所以判断不准确，其实，直接循环乘就行，对于底数为1的情况直接输出即可，否则超时。然后中途直接判断即可。
(buyao)参考代码：

#include<bits/stdc++.h>using namespace std;#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;typedef pair<int, int> PII;
typedef unsigned long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const LL mod = 1e18;
const int cases = 1;//龟速幂 a^b mod p
string qmi(LL a, LL b)
{LL res=1;if(a==1) return "1";for(int i=1;i<=b;i++){res*=a;if(res>mod) return "?";}return to_string(res);
}string dishu[10][10]={"........","........","........","........","........","........","........","........","........","........","........","........","........","........","........","........","........","........","........","........","0000000.","......1.","2222222.","3333333.","4.....4.","5555555.","6666666.","7777777.","8888888.","9999999.","0.....0.","......1.","......2.","......3.","4.....4.","5.......","6.......","......7.","8.....8.","9.....9.","0.....0.","......1.","......2.","......3.","4.....4.","5.......","6.......","......7.","8.....8.","9.....9.","0.....0.","......1.","2222222.","3333333.","4444444.","5555555.","6666666.","......7.","8888888.","9999999.","0.....0.","......1.","2.......","......3.","......4.","......5.","6.....6.","......7.","8.....8.","......9.","0.....0.","......1.","2.......","......3.","......4.","......5.","6.....6.","......7.","8.....8.","......9.","0000000.","......1.","2222222.","3333333.","......4.","5555555.","6666666.","......7.","8888888.","9999999.","........","........","........","........","........","........","........","........","........","........"
};string zhishu[10][10]={"......","......","......","......","......","......","......","......","......","......","00000.","....1.","22222.","33333.","4...4.","55555.","66666.","77777.","88888.","99999.","0...0.","....1.","....2.","....3.","4...4.","5.....","6.....","....7.","8...8.","9...9.","0...0.","....1.","22222.","33333.","44444.","55555.","66666.","....7.","88888.","99999.","0...0.","....1.","2.....","....3.","....4.","....5.","6...6.","....7.","8...8.","....9.","00000.","....1.","22222.","33333.","....4.","55555.","66666.","....7.","88888.","99999.","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......","......"
};string fuhao[10][2]={"........","........................","........","........................","........","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.......","........","........................"
};        
void Showball(){LL x,y;char c;cin>>x>>c>>c>>y>>c;string xx=to_string(x);string yy=to_string(y);string zz=qmi(x,y);string ans=xx+"#"+yy+"="+zz;for(int i=0;i<10;i++){cout<<".";int ok=0;for(auto c:ans){if(c=='=') ok=0,cout<<fuhao[i][0];else if(c=='#') ok=1;else if(c=='?') cout<<fuhao[i][1];else{int t=c-'0';if(ok) cout<<zhishu[i][t];else cout<<dishu[i][t];}}cout<<endl;}cout<<endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T=1;if(cases) cin>>T;while(T--)Showball();return 0;
}

H Travel Begins 思维 贪心
题意：给你两个数n和k，表示有k个实数之和为n。你可以随意安排这k个实数的值，求
这k个实数四舍五入之后求和的结果最小值和最大值。
思路：对于最小值来说：我们给k-1个数分配一个无限接近0.5的数，然后剩下的数分给第k个数，设这个数为z，这样前k-1个数对于最小值的贡献为0。如果$z<0.5$，说明最小值为0，最大值则为n/0.5然后四舍五入即可。如果$z\ge 0.5$，那么最小值为$z/0.5$,最大值为$n-（k-1）\ast 0.5+k-1$。
参考代码：

#include<bits/stdc++.h>using namespace std;#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;
const double eps = 1e-8;
const double res = 0.49999999999999;void Showball(){int n,k;cin>>n>>k;double z=n-(k-1)*res;int minn=0,maxn=0;if(z<0.5){maxn=(int)(n/0.5);cout<<minn<<" "<<maxn<<endl;}else{minn=(int)(z+0.5);double e=n-(k-1)*0.5;maxn=(int)(e+0.5)+k-1;cout<<minn<<" "<<maxn<<endl;}}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T=1;if(cases) cin>>T;while(T--)Showball();return 0;
}

K 排列与质数
题意：构造一个长度为n的排列$P=（P_1,P_2,...,P_n）$，要求满足：
$\forall i\in [1,n],|P_i-P_{imodn+1}|$为质数。有解输出任意满足条件的排列，否则输出-1。
思路：遇见这种构造先打个表。打表发现当n小于5时，是无解的。还发现当$5\le n\le 9$的时候我们可以直接先排列奇数然后排列偶数即可。但是对于较大的数就不成立了。我们可以尝试2个2个间隔去放，这里提供一种构造思路：
奇数:1,3,5,7…n,n-3,n-5…8,6,4
偶数:1,3,5,7…n-3,n,n-2,n-4…8,6,4
可以发现，现在除了 2 和 n − 1 以外，所有数均已出现，且满足题目的限制。那么我们只需要将这两个数插进合适的位置即可。容易发现一定有解，因为可以将 2 插在 5 和 7 之间，将n − 1 插在 n − 4 和 n − 6 之间。

参考代码：

#include<bits/stdc++.h>using namespace std;#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;void Showball(){int n;cin>>n;if(n<5) cout<<-1<<endl;else if(5<=n&&n<10){for(int i=1;i<=n;i+=2) cout<<i<<" ";for(int i=2;i<=n;i+=2) cout<<i<<" ";cout<<endl;}else{if(n&1){for(int i=1;i<=n;i+=2){cout<<i<<" ";if(i==5) cout<<2<<" ";if(n==11&&i==3) cout<<n-1<<" ";else if(n!=11&&i==n-6) cout<<n-1<<" ";}for(int i=n-3;i>4;i-=2){cout<<i<<" ";}cout<<4<<endl;}else{for(int i=1;i<=n-3;i+=2){cout<<i<<" ";if(i==5) cout<<2<<" ";}for(int i=n;i>4;i-=2){cout<<i<<" ";if(i==n-4) cout<<n-1<<" ";}cout<<4<<endl;}}
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T=1;if(cases) cin>>T;while(T--)Showball();return 0;
}

完结撒花~