Codeforces Round #821 (Div. 2)

C. Parity Shuffle Sorting

题目大意

每次操作可以选择l,r，如果\(a_l+a_r\)是奇数可以让\(a_l=a_r\)，否则可以让\(a_l=a_r\)，要求使用不超过n次操作使得序列变得有序。

分析

给出以下构造。首先操作1,n让序列首位相同，然后对于[2~n-1]的每个位置i，根据奇偶性选择操作(1,i

)或者(i,n)让第\(a_i=a_1/a_n\)，显然操作完之后徐磊中所有元素都相等且操作次数不超过n次。

AC_code

#include <bits/stdc++.h>
#define fi first    
#define se second    
#define endl '\n'
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
typedef long long LL;
using namespace std;
const int N = 1e5 + 10,M = N*2;
   
void solve() {
    int n;cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<array<int,2>> ans;
    if(a[1]!=a[n])
    {
        ans.push_back({1,n});
        if((a[1]+a[n])&1) a[n] = a[1];
        else a[1] = a[n];
    }
    for(int i=2;i<=n-1;i++)
    {
        if(a[i]==a[1]) continue;
        if(a[i]+a[1]&1) ans.push_back({1,i});
        else ans.push_back({i,n});
    }
    cout<<ans.size()<<'\n';
    for(auto x:ans) cout<<x[0]<<" "<<x[1]<<'\n';
}
 
int main() 
{
    ios;
    int T=1;
    cin>>T;
 
    while(T -- ) {
        solve();
    }
 
    return 0;
}

D2. Zero-One (Hard Version)

题目大意

给两01个字符串a和b，长度都为n。你可以对a做以下操作任意次。

1. 任选\(a_l,a_r\)，将其值翻转
2. 若区间长度>2，则代价为y，否则为x。

分析

我们发现，每次操作的值翻转的都是两个，因此，不同的位置应该有偶数个，否则无解。

我们发现越远的点对使用第二种操作更好，因此使用第二种操作一定是从两边操作。

因此，我们每次操作，要不是改变开头的两个位置，要不是结尾的两个位置，要不就是改变开头和结尾各一个位置。

AC_code

#include <bits/stdc++.h>
#define fi first    
#define se second    
#define endl '\n'
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
typedef long long LL;
using namespace std;
const int N = 5010,M = N*2;

char a[N],b[N];
LL f[N][N];
vector<int> pos;
int n,x,y;

LL dp(int l,int r)
{
    if(l>r) return 0ll;
    if(~f[l][r]) return f[l][r];
    LL ans = 1e18;
    ans = min(ans,dp(l+1,r-1)+y);
    ans = min(ans,dp(l,r-2)+min(1ll*y,1ll*x*(pos[r]-pos[r-1])));
    ans = min(ans,dp(l+2,r)+min(1ll*y,1ll*x*(pos[l+1]-pos[l])));
    return f[l][r] = ans;
}

void solve()
{
    cin>>n>>x>>y>>a+1>>b+1;
    pos.clear();
    for(int i=1;i<=n;i++) 
        if(a[i]!=b[i])
            pos.push_back(i);
    if(pos.size()&1)
    {
        cout<<"-1\n";
        return ;
    }
    if(!pos.size())
    {
        cout<<"0\n";
        return ;
    }
    if(x>=y)
    {
        if(pos.size()!=2)
        {
            cout<<1ll*pos.size()/2*y<<'\n';
            return ;
        }
        if(pos[0]+1!=pos[1])
        {
            cout<<y<<'\n';
            return ;
        }
        cout<<min(2*y,x)<<'\n';
    }
    else 
    {
        for(int i=0;i<pos.size();i++)
            for(int j=i;j<pos.size();j++)
                f[i][j] = -1;
        cout<<dp(0,pos.size()-1)<<'\n';
    }
}
 
int main() 
{
    ios;
    int T=1;
    cin>>T;
 
    while(T -- ) {
        solve();
    }
 
    return 0;
}