2023 年第五届河南省 CCPC 大学生程序设计竞赛

题目地址

题目PDF地址

题解地址

Problem A. 小水獭游河南

$|a|\le |\Sigma |=26，暴力枚举a判断b是否为是回文串即可，时间复杂度O(|\Sigma ||s|)。$

#include<bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--){string s;cin>>s;if(s.size()==1) {cout<<"NaN\n";continue;} map<char,int> b;bool ok=false;for(int i=0;i<s.size();i++){if(b[s[i]]) break;string str=s.substr(i+1);string ss=str;reverse(str.begin(),str.end());if(str==ss){cout<<"HE\n";ok=true;break;} b[s[i]]++;}if(!ok) cout<<"NaN\n";}return 0;
}

Problem B. Art for Rest

#include<bits/stdc++.h>
using namespace std;const int N = 1000001, M = 21;
int f[N][M],g[N][M];
int lg[N],a[N];
int n;bool st[N];inline int max(int A,int B)
{return A>B?A:B;
}inline int min(int A,int B)
{return A<B?A:B;
}void init()
{lg[1]=0;for(int i=2;i<=1000000;i++) lg[i]=lg[i>>1]+1;for(int j=0;j<20;j++)for(int i=1;i+(1<<j)-1<=n;i++)if(!j) f[i][j]=g[i][j]=a[i];else{f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);}
}inline int query_max(int l,int r)
{int k=lg[r-l+1];return max(f[l][k],f[r-(1<<k)+1][k]);
}inline int query_min(int l,int r)
{int k=lg[r-l+1];return min(g[l][k],g[r-(1<<k)+1][k]);
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];if(is_sorted(a+1,a+n+1)){cout<<n;return 0;}init();int res=1;for(int k=2;k<=n-1;k++){if(st[k]){res++;continue;}bool ok=true;int l=1,r=k;while(r<n){int mx=query_max(l,r);int mn=query_min(l+k,min(r+k,n));if(mx>mn){ok=false;break;}l+=k,r+=k;}if(ok){for(int j=k;j<=n-1;j+=k)st[j]=true;res++;}}cout<<res;return 0;
}

Problem E. 矩阵游戏

#include<bits/stdc++.h>
using namespace std;const int N = 510, M = 1010;
char s[N][N];
int dp[3][N][M];int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--){int n,m,x;cin>>n>>m>>x;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>s[i][j];for(int k=0;k<2;k++)for(int i=0;i<=m;i++)for(int j=0;j<=x;j++)dp[k][i][j]=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') dp[i&1][j][k]=max(dp[i&1][j-1][k],dp[(i-1)&1][j][k]);else if(s[i][j]=='1') dp[i&1][j][k]=max(dp[i&1][j-1][k],dp[(i-1)&1][j][k])+1;else{if(k>=1) dp[i&1][j][k]=max(dp[i&1][j-1][k-1],dp[(i-1)&1][j][k-1])+1;else dp[i&1][j][k]=max(dp[i&1][j-1][k],dp[(i-1)&1][j][k]);}cout<<dp[n&1][m][x]<<"\n";}return 0;
}

Problem F. Art for Last

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N = 500010;
int a[N];int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n,k;cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);multiset<int> b;for(int i=2;i<=k-1;i++)b.insert(a[i]-a[i-1]);LL res=1e18;for(int i=k;i<=n;i++){b.insert(a[i]-a[i-1]);res=min(res,(LL)*b.begin()*(a[i]-a[i-k+1]));b.erase(b.lower_bound(a[i-k+2]-a[i-k+1]));}cout<<res;return 0;
}

Problem G. Toxel 与字符画

按照题意模拟即可。例如，一种实现方式是，将题面提供的各种字符画在程序中存入一个二维字符矩阵中。随后计算表达式的值，并求出该表达式所需使用的各个字符。最后根据这些字符，找到相对应的字符画，拼接在答案后即可。

#include<bits/stdc++.h>
using namespace std;typedef long long LL;string a[]=
{".................................................................................",".................................................................................",".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 b[]=
{".............................................................",".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 c[]=
{".................................",".................................",".........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.......","................................."
};int main()
{int T;scanf("%d",&T);while(T--){LL x,y;scanf("%lld^{%lld}",&x,&y);__int128 sum=1;bool ok=false;if(x!=1){for(LL i=1; i<=y; i++){sum*=x;if(sum>1000000000000000000ll){ok=true;break;}}}vector<string> res(10);string xx=to_string(x);string yy=to_string(y);for(int i=0; i<xx.size(); i++){int number=xx[i]-'0';for(int k=0; k<8; k++)for(int j=0; j<10; j++)res[j].push_back(a[j][number*8+k]);}for(int i=0; i<yy.size(); i++){int number=yy[i]-'0';for(int k=0; k<6; k++)for(int j=0; j<10; j++)res[j].push_back(b[j][number*6+k]);}for(int k=0; k<8; k++)for(int j=0; j<10; j++)res[j].push_back(c[j][k]);if(ok){for(int k=8; k<33; k++)for(int j=0; j<10; j++)res[j].push_back(c[j][k]);}else{string zz=to_string((LL)sum);for(int i=0; i<zz.size(); i++){int number=zz[i]-'0';for(int k=0; k<8; k++)for(int j=0; j<10; j++)res[j].push_back(a[j][number*8+k]);}for(int j=0; j<10; j++)res[j].push_back('.');}for(auto line:res)printf("%s\n",line.c_str());}return 0;
}

Problem H. Travel Begins

Problem K. 排列与质数

对于 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 排列；
即先将奇数升序排列，再将偶数降序排列。

可以发现，现在除了 2 和 n − 1 以外，所有数均已出现，且满足题目的限制。那么我们只需要将这两个数插进合适的位置即可。容易发现一定有解，因为可以将 2 插在 5 和 7 之间，将n − 1 插在 n − 4 和 n − 6 之间。
复杂度取决于判断质数的速度，$O(n\surd n)$ 已经足以通过此题。

#include<bits/stdc++.h>
using namespace std;bool p(int n)
{if(n<=1) return false;for(int i=2;i<=n/i;i++)if(n%i==0)return false;return true;
}int main()
{int n;cin>>n;if(n<=4) cout<<"-1";else if(n<=11){vector<int> pos(n);for(int i=0;i<n;i++) pos[i]=i+1;do{bool ok=false;for(int i=1;i<n;i++)if(!p(abs(pos[i]-pos[i-1]))){ok=true;break;}if(!p(abs(pos[0]-pos[n-1]))) ok=true;if(!ok){for(auto c:pos)cout<<c<<" ";break;}}while(next_permutation(pos.begin(),pos.end()));}else{vector<int> res;if(n&1){for(int i=1;i<=n;i+=2)res.push_back(i);for(int i=n-3;i>=4;i-=2)res.push_back(i);for(int i=0;i<res.size();i++){cout<<res[i]<<" ";if(res[i]==5) cout<<"2 ";if(res[i]==n-6) cout<<n-1<<" ";}}else{for(int i=1;i<=n-3;i+=2)res.push_back(i);for(int i=n;i>=4;i-=2)res.push_back(i);for(int i=0;i<res.size();i++){cout<<res[i]<<" ";if(res[i]==5) cout<<"2 ";if(res[i]==n-4) cout<<n-1<<" ";}} }return 0;
}