2023年河南CCPC（ABCEFHK）

2023河南CCPC

A. 小水獭游河南(字符串)

看错题了，上去就wa了

只有26个英文字母，所以a 字符串最长26.直接暴力判断

B. Art for Rest(数组切割)

又看错题了。

以为是切割成，每一段内部都是有序的。

按照错误题意

先 t 后面优化了。

遇到 a[ i ] > a[ i-1 ] 记录一下，再看公共因数 的个数 ，便是答案。

---

虽然知道，前一段的max一定小于等于后一段的min。但一直困在段与段之间。

应该跳出局限，不应将段与段割裂开，整体而言，同样是前面的max，不大于后面的min。

• 初始化两个数组，pre，suf
• 将满足pre<=suf 的标记
• 将标记的i值作为 k ，逐一判断。

调和级数求和，log(n+1)

所以时间复杂度为 $nlog(n)$

const int N=1e6+10;
int a[N],pre[N],suf[N],st[N];
void solve()
{int n,ans=0;cin>>n;suf[n+1]=1e19;fir(i,1,n)cin>>a[i];fir(i,1,n) {if(pre[i-1]<a[i])pre[i]=a[i];else pre[i]=pre[i-1];}  fir_(i,n,1){if(suf[i+1]>a[i])suf[i]=a[i];else suf[i]=suf[i+1];}fir(i,1,n){if(pre[i]<=suf[i+1])st[i]=1;}for(int i=1;i<=n;i++){int f=1;for(int j=i;j<=n;j+=i){if(st[j]==0){f=0;break;}}if(f) ans++;}cout<<ans<<'\n';
}

C. Toxel与随机数生成器(水)

数据很水，原本以为需要从1e3~1e4全考虑。还有一些漏洞需要注意。

没想到，直接判断前1000个字符组成的子串。后面是否出现就可以了。

没意思.

E. 矩阵游戏（dp）

根据题意，只能向下或者向右走。很容易看出dP，可惜刚开始没看出来。

后来看出来了，还是不会写。

不知道怎么将 1 和 ？ ,联系起来。随便写了两个dp，直接相加。果不其然，错了。

关于 dp,想要将两个性质联系到一块，就要想到 分成不同的状态和维度。此题中关于 ？，可以单独一个状态 k ，表示将？换成 1 的数量。

---

所以，此题是一个三维的动态规划，dp[i] [j] [k].

• 当a[i] [j] = 0 ,$dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k])$

• 当a[i] [j] = 1 ,$dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k])+1$

• 当 a[i] [j] = ? ,

  如 01背包考虑选不选，此时应考虑 换不换

  • 换：当前第三个状态为 k ，应由 k-1 选择换，递推而来。

    $dp[i][j][k]=max(dp[i-1][j][k-1],dp[i][j-1][k-1])+1$

  • 不换：

    $dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k])$

总的来说，只有这三种情况。

由于三维数组会爆，省略 i ,滚动数组压缩成二维 ，此时 k 倒着循环。

dp数组需要初始化，k只能从 0开始递推，所以 k取其他值的时候初始化为无穷小。k=0,dp为0。

const int N=5e2+10;
char a[N][N];
int  b[N][1050];//二维压缩成一维
void solve()
{int n,m,x;cin>>n>>m>>x;//初始化fir(j,0,m)fir(k,0,x)b[j][k]=0;fir(j,1,m)fir(k,1,x)b[j][k]=-0x3f3f3f3f;fir(i,1,n)fir(j,1,m)cin>>a[i][j];     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=x;k>=0;k--){if(a[i][j]=='1')b[j][k]=max(b[j-1][k],b[j][k])+1;else if(a[i][j]=='0')b[j][k]=max(b[j-1][k],b[j][k]);else {if(k>0)b[j][k]=max(max(b[j-1][k],b[j][k]),max(b[j][k-1]+1,b[j-1][k-1]+1)) ;//换和不换选最优else b[j][k]=max(b[j][k],b[j-1][k]);}}int ans=0;fir(i,0,x)ans=max(ans,b[m][i]);cout<<ans<<'\n';       
}

F. Art for Last(区间最小差分)

先将数组排序，每次选择相邻的k个为最优。最大差值是第一个和最后一个。最小差值，是相邻的两个。

可以用滑动窗口，求区间内最小差分，或者ST表，或者线段树。前者比较便捷。

开个优先队列，不断推进去新的值，再访问最小值，超出窗口就弹出去。

const int N=1e6+10;
int a[N];
void solve()
{int n,k;int mi=1e18+10;cin>>n>>k;fir(i,1,n)cin>>a[i];sort(a+1,a+n+1);priority_queue<PII,vector<PII>,greater<PII> > q;for(int i=2;i<=k;i++)q.push({a[i]-a[i-1],i});for(int i=1;i<=n-k+1;i++){int x=a[i+k-1]-a[i];while(q.size()&&q.top().se<=i){q.pop();}int y=q.top().fi;mi=min(mi,x*y);q.push({a[i+k]-a[i+k-1],i+k});}       cout<<mi<<'\n'; 
}

H. Travel Begins(数学思维)

题目很好懂，有多人错在精度。当然不考虑精度，直接思维也能过、

• 最大值好算：尽量每个整数，都加一个0.5

​ max=n+min(n*2,k) * 0.5

• 最小值：尽量每个数，都加上0.4999999…

  可以近似看作 0.5

  也就是对于每一段，可以减少将近 0.5 。小差值 0.00…01可以在最后一段弥补。如果 k-1是偶数，将减少 （k-1）* 0.5 .反之为奇数，多出的0.499…9需要在最后弥补，（k+1）/2 ,就需要向下取整

  min=max(0ll,n-(k-1) / 2 )

void solve()
{int n,k;cin>>n>>k;int x=n+min(k,n*2)*0.5;int y=max(0ll,n-(k-1)/2);cout<<y<<' '<<x<<'\n';
}

K. 排列与质数（规律）

这个题并不难，可惜当时没好好想。凭借错误的记忆，还以为是偏暴力的解法。

想找规律，就需要列举。当列出前几项没发现规律，或者规律不通用。就该想着用几个大数试试。

也许前面就需要暴力枚举，真正的规律就在后面。

这个题有很多解法，主要考虑一下几点：

• 利用 2，3，5这些小的质数
• 奇偶分开，他们之间的连接
• 首尾

我选用“6 3 1 4 2 5”固定为中间连接部分。前面放偶数，后面放奇数。首尾通过小质数就行调整。

例：

（15）

13 15 10 8 6 3 1 4 2 5 7 9 12 14 11

（16）

15 12 10 8 6 3 1 4 2 5 7 9 11 14 16 13

void solve()
{int n;cin>>n;if(n==2||n==3||n==4)cout<<"-1\n";else if(n==5)cout<<"4 1 3 5 2\n";else if(n==6)cout<<"3 1 6 4 2 5\n";else if(n==7)cout<<"3 1 6 4 2 7 5\n";else if(n==8)cout<<"8 3 1 6 4 2 7 5\n";else if(n==9)cout<<"8 3 1 6 4 2 9 7 5\n";else{if(n&1){cout<<n-2<<' '<<n<<' ';for(int i=n-5;i>=6;i-=2)cout<<i<<' ';cout<<"3 1 4 2 ";for(int i=5;i<=n-6;i+=2)cout<<i<<' ';cout<<n-3<<' '<<n-1<<' '<<n-4<<'\n';}else{cout<<n-1<<' ';for(int i=n-4;i>=6;i-=2)cout<<i<<' ';cout<<"3 1 4 2 ";for(int i=5;i<=n-5;i+=2)cout<<i<<' ';cout<<n-2<<' '<<n<<' '<<n-3<<'\n';}}	           
}

总结

个人赛3.5h 赛时过了3道，补题7道。

还有一道大模拟没补。

2024年CCPC，赛时也是过了3道，补题六道。