部分题目题解

J.好长的序列

我们将 $A$ 序列看作完整的一段的话，答案肯定是经过若干个完整的段，然后在下一段的某处满足题目要求。于是我们先算出要经过多少个完整的段，再加上最后一段中要经过的位置数即可。

void solve(){
    int n;cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    long long s=accumulate(a.begin(),a.end(),0ll);
    long long x;cin>>x;
    long long res=x/s*n;
    x%=s;
    for(int i=0;i<n;i++){
        x-=a[i];
        if(x<0){
            res+=i+1;
            break;
        }
    } 
    cout<<res<<endl;
}

I.坐得下吗

对独自前来的人，无论如何都能够坐得下，所以其实我们只要考虑在最坏的情况下，最后一个2人组是否能够坐下即可。那么什么是最坏情况呢？就是每组人从左往右挑选座位，每次都间隔1个座位，保证2人组无法坐下。具体实现看代码。

void solve(){
    int n,m;
    cin>>n>>m;
    vector<int>a(n+1);
    int last=-1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==2)last=i;
    }
    if(last==-1){
        cout<<"Yes"<<endl;
        return;
    }

    for(int i=1;i<last;i++){
        m-=a[i]+1;
    }
    cout<<(m>=2?"Yes":"No")<<endl;
}

H.等等...这是dp对吧

不妨将 $b$ 看作 $0$ ， $p$ 看作 $1$ ，则操作可以描述为：反转一个区间，并对该区间的每个数取反。

由于 $N$ 小于 $5000$ ，我们可以枚举所有可能的区间。具体来说，枚举方式为：先固定区间的中点，然后依次增加区间的半径。

注意到，每次半径增加 1，相比上一个区间，仅新加入了 2 个数，这 2 个数会被交换并取反。有两种情况：

如果新加入的 2 个数不同，那么交换并取反后，区间并不发生变化。
如果新加入的 2 个数相同：
- 若为 $00$ ，操作后变为 $11$ ，此时区间的字典序会变大。
- 若为 $11$ ，操作后变为 $00$ ，此时区间的字典序会变小。

基于贪心，我们可以确定：在当前中间点的情况下，选择会使得字典序变小的最长区间即为局部最优解。

对于每个中间点，分别求出最优解，取最小值。整体时间复杂度为 $O(N^2)$ 。

具体实现见代码：

void solve(){
    int n;cin>>n;
    string s;cin>>s;
    string ans = s;
    vector<char>T(2*n+3);

    //在字符间插入#，方便统一处理奇,偶区间
    int m=0;
    for(int i=0;i<n;i++){
        T[++m]=s[i];
        T[++m]='#';
    }
    m--;

    for(int t=1;t<=2;t++){//分别枚举奇,偶区间
        for(int i=t;i<=m;i+=2){//中间点
            int last=-1;
            for(int j=(i%2==0);i+j<=m and i-j>=1;j+=2){//半径
                int l=i-j,r=i+j;
                if(T[l]!=T[r])continue;

                if(T[l]=='p'){//记录变小的最长半径
                    last=j;
                }
            }

            if(last==-1)continue;

            string tmp=s;
            for(int j=(i%2==0);j<=last;j+=2){
                int l=i-j,r=i+j;
                if(T[l]!=T[r])continue;
                int pl=l/2,pr=r/2;
                if(T[l]=='d'){
                    tmp[pl]=tmp[pr]='p';
                }else{
                    tmp[pl]=tmp[pr]='d';
                }
            }
            ans=min(ans,tmp);
        }
    }
    cout<<ans<<endl;
}

B.欢迎加入实验室

[1] 必要条件

要满足条件，必须有 $N \geq 2K$ 。只有在 $N \geq 2K$ 时，才能找到满足 $1 \leq A_K \leq N$ 且 $\lvert A_K - K\rvert \geq K$ 的 $A_K$ 。

[2] 一个失败的贪心算法

我们可以先尝试一个简单的贪心算法：

从 $i=1$ 开始，选择未使用的最小数字 $x$ ，使得 $\lvert x - i\rvert \geq K$ 。

但这种方法是错误的。例如，在样例输入 2 中，最优解选择 $A_4=7$ ，而不是满足 $\lvert x-4\rvert \geq 3$ 的 $x=1$ 。这是因为设置 $A_i$ 的同时，还需要保证所有数字 $x$ 都有一个对应的 $A_i$ 。如果过早地选择不合适的数字，后面可能无解。

[3] 一个成功的贪心算法

改进的贪心算法如下：

从 $i=1$ 开始：

如果 $i+K$ 未被使用且 $i+K > N-K$ ，选择 $A_i = i+K$ ；

否则，选择满足 $\lvert x - i\rvert \geq K$ 的最小未用数字 $x$ 。

如果按照这种方式成功完成了分配，那么这一定是最优解。问题是这样是否能够成功分配呢？手玩一些情况后可以发现，只要满足必要条件，这样的方式一定能够成功分配所有数字。

void solve(){
    int n,k;
    cin>>n>>k;
    if(n<2*k){
        cout<<-1<<endl;
        return;
    }
    set<int>S;
    for(int i=1;i<=n;i++){
        S.insert(i);
    }

    vector<int>res(n+1);
    for(int i=1;i<=n;i++){
        int j=i+k;
        if(j>n-k and j<=n){
            res[i]=j;
            S.erase(j);
        }else{
            int v=*S.begin();
            if(v>i-k){
                v=*S.lower_bound(i+k);
            }
            res[i]=v;
            S.erase(v);
        }
    }
    for(int i=1;i<=n;i++)cout<<res[i]<<' ';
    cout<<endl;
}