题解：P10854 【MX-X2-T3】「Cfz Round 4」Ninelie

ppllxx_9G · 2024-08-11 17:33:03 · 题解

题目大意

对于一个长度为 n 的 01 串 s，你可以对其进行最多 r 次操作，对于每次操作，你可以选择一个下标 p 满足 p=1，p=n，s_{p-1}\not=s_{p+1} 中的至少一个，将 s_p 反转。输出操作方案。

解题思路

最大限制次数 r=10^6，恰好是 \frac{n^2}{4} 次，所以考虑能否使每一个位置的操作次数近似 \frac{n}{4}。所以想到从中点向两侧遍历。每侧 \frac{n}{2} 个点，每个点可以进行 \frac{n}{4} 次操作。

显然，如果一个点当前不能被改变，那我们能通过改变它一侧的点，使它变成可以被改变状态。其实这就是一个递归求解的过程。

• 对于中点左侧的点，如果不能被改变，选择向左递归。
• 对于中点右侧的点，如果不能被改变，选择向右递归。

这样我们先钦定中间两个点，使其变成一样的（最多需要 \frac{n}{2} 次）。然后向左右分别求解（还剩 \frac{n}{2}-1 个点），最坏情况是 \frac{\frac{n}{2}(\frac{n}{2}-1)}{2} \times 2 次，加上最开始钦定时的 \frac{n}{2} 次，刚刚好（应该卡不到吧）。

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+5;
int n,a[N],r,ans,op[2000005],limit;
inline void change(int x,int o)
{
    if(x==1||x==n||a[x-1]!=a[x+1]) return a[x]^=1,op[++ans]=x,void(0);
    if(o) change(x-1,o),a[x]^=1,op[++ans]=x;
    else change(x+1,o),a[x]^=1,op[++ans]=x;
}
int main()
{
    scanf("%d%d",&n,&limit);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int l=n>>1,r=l+1;
    if(a[l]!=a[r]) change(l,1);
    l--,r++;
    while(l>=1) a[l]!=a[l+1]?change(l,1),l--:l--;
    while(r<=n) a[r]!=a[r-1]?change(r,0),r++:r++;
    printf("%d\n",ans);
    for(int i=1;i<=ans;i++) printf("%d ",op[i]);
    return 0;
}