cf 2000+()-其他
cf 2000+()
D2. Zero-One (Hard Version) 2000 好dp
https://codeforces.com/problemset/problem/1733/D2
题解：
首先取c[i]=a[i]xorb[i],若为1数为odd则无解，否则
1，当x>=y时
若不同数>=4显然我们可以交叉算用n/2y解决，当不同数=2时我们分类讨论，当n<=3时，只能使用x，故此时ans=x；
当n=4，若不同的两点在2，3位置，则需要花费min(3y,x)否则min(2y,x);
当n>=5时，min(2y,x)。
2，x<y时，
使用dp，关键在于确立状态，什么状态好转移，好表征关键特征？首先前i项这个阶段肯定是一维，由于和相对位置有关，故我们需要确定当前位是0/1，才能转移，故另一维表示当前位为0/1，但还是有很多状态重叠，转移时还有什么会变化？前i项处理后仍不同数量，此时已可列出转移方程：
若c[i]=0,
f(0,i,j)=min(f(0,i-1,j),f(1,i-1,j));
f(1,i,j)=min(f(0,i-1,j)+y,f(1,i,j)+x,f(0,i-1,j-2)+x,f(1,i-1,j-2)+y)
若 c[i]=1,
f(1,i,j)=min(f(1,i-1,j-1),f(0,i-1.j-1));
f(0,i,j)=min(f(1,i-1,j+1)+x,f(0,i-1,j+1)+y,f(0,i-1,j-1)+x,f(1,i-1,j-1)+y)
再特判一下j=0,j=i的情况便可，答案即为f(0,n,0)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5050,mod=998244353;
int a[N],b[N],c[N],f0[N][N],f1[N][N];
void solve(){
int n,x,y;cin>>n>>x>>y;
string s;cin>>s;
for(int i=0;i<n;i++) a[i+1]=s[i]-'0';
cin>>s;
for(int i=0;i<n;i++) b[i+1]=s[i]-'0';
int cnt=0;
for(int i=1;i<=n;i++) c[i]=a[i]^b[i],cnt+=c[i];
if(cnt%2){
puts("-1");
return;
}
if(x>=y){
if(cnt==2){
int q=0,w=0;
for(int i=1;i<=n;i++){
if(c[i]==1)
if(!q) q=i;
else w=i;
}
if(abs(q-w)!=1){
cout<<y<<endl;
}
else{
if(n<=3){
cout<<x<<endl;
}
else if(n==4){
if(q==1||w==n){
cout<<min(2*y,x)<<endl;
}
else cout<<min(3*y,x)<<endl;
}
else{
cout<<min(x,2*y)<<endl;
}
}
return;
}
cout<<cnt/2*y<<endl;
return;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++) f0[i][j]=f1[i][j]=1e18;
}
if(c[1]==1) f1[1][1]=0;
else f0[1][0]=0;
for(int i=2;i<=n;i++){
for(int j=0;j<=i;j++){
if(c[i]==0){
f0[i][j]=min(f0[i-1][j],f1[i-1][j]);
if(j<=1) f1[i][j]=min(f0[i-1][j]+y,f1[i-1][j]+x);
else{
f1[i][j]=min({f0[i-1][j]+y,f1[i-1][j]+x,f0[i-1][j-2]+x,f1[i-1][j-2]+y});
}
}
else{
if(j!=0)
f1[i][j]=min(f1[i-1][j-1],f0[i-1][j-1]);
if(j==0){
f0[i][j]=min(f0[i-1][j+1]+y,f1[i-1][j+1]+x);
}
else if(j==i){
f0[i][j]=min(f0[i-1][j-1]+x,f1[i-1][j-1]+y);
}
else{
f0[i][j]=min({f0[i-1][j+1]+y,f1[i-1][j+1]+x,f0[i-1][j-1]+x,f1[i-1][j-1]+y});
}
}
}
}
cout<<f0[n][0]<<endl;
}
signed main(){
int T;cin>>T;
while(T--) solve();
}
C2. Sheikh (Hard Version) 2100
https://codeforces.com/problemset/problem/1732/C2
题解：对于一个区间，其显然其sum-xor最大值为整个区间，若想缩小区间，则需从两端逐渐缩减，一个点对sum-xor无影响当且仅当其让sum和xor增加了相同的数量，即为其所有为1的位上余下的xor为0，而总共只有31位，故当删除32个数时，必有两个某一位上均为1，此时对最大值有影响。故我们可以对每一个询问，枚举合法的左端点，寻找最小右端点，复杂度至多为3131q,可以通过。
代码：略。。
D2. Zero-One (Hard Version) 2000 好dp
https://codeforces.com/problemset/problem/1733/D2
题解：
首先取c[i]=a[i]xorb[i],若为1数为odd则无解，否则
1，当x>=y时
若不同数>=4显然我们可以交叉算用n/2y解决，当不同数=2时我们分类讨论，当n<=3时，只能使用x，故此时ans=x；
当n=4，若不同的两点在2，3位置，则需要花费min(3y,x)否则min(2y,x);
当n>=5时，min(2y,x)。
2，x<y时，
使用dp，关键在于确立状态，什么状态好转移，好表征关键特征？首先前i项这个阶段肯定是一维，由于和相对位置有关，故我们需要确定当前位是0/1，才能转移，故另一维表示当前位为0/1，但还是有很多状态重叠，转移时还有什么会变化？前i项处理后仍不同数量，此时已可列出转移方程：
若c[i]=0,
f(0,i,j)=min(f(0,i-1,j),f(1,i-1,j));
f(1,i,j)=min(f(0,i-1,j)+y,f(1,i,j)+x,f(0,i-1,j-2)+x,f(1,i-1,j-2)+y)
若 c[i]=1,
f(1,i,j)=min(f(1,i-1,j-1),f(0,i-1.j-1));
f(0,i,j)=min(f(1,i-1,j+1)+x,f(0,i-1,j+1)+y,f(0,i-1,j-1)+x,f(1,i-1,j-1)+y)
再特判一下j=0,j=i的情况便可，答案即为f(0,n,0)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5050,mod=998244353;
int a[N],b[N],c[N],f0[N][N],f1[N][N];
void solve(){
int n,x,y;cin>>n>>x>>y;
string s;cin>>s;
for(int i=0;i<n;i++) a[i+1]=s[i]-'0';
cin>>s;
for(int i=0;i<n;i++) b[i+1]=s[i]-'0';
int cnt=0;
for(int i=1;i<=n;i++) c[i]=a[i]^b[i],cnt+=c[i];
if(cnt%2){
puts("-1");
return;
}
if(x>=y){
if(cnt==2){
int q=0,w=0;
for(int i=1;i<=n;i++){
if(c[i]==1)
if(!q) q=i;
else w=i;
}
if(abs(q-w)!=1){
cout<<y<<endl;
}
else{
if(n<=3){
cout<<x<<endl;
}
else if(n==4){
if(q==1||w==n){
cout<<min(2*y,x)<<endl;
}
else cout<<min(3*y,x)<<endl;
}
else{
cout<<min(x,2*y)<<endl;
}
}
return;
}
cout<<cnt/2*y<<endl;
return;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++) f0[i][j]=f1[i][j]=1e18;
}
if(c[1]==1) f1[1][1]=0;
else f0[1][0]=0;
for(int i=2;i<=n;i++){
for(int j=0;j<=i;j++){
if(c[i]==0){
f0[i][j]=min(f0[i-1][j],f1[i-1][j]);
if(j<=1) f1[i][j]=min(f0[i-1][j]+y,f1[i-1][j]+x);
else{
f1[i][j]=min({f0[i-1][j]+y,f1[i-1][j]+x,f0[i-1][j-2]+x,f1[i-1][j-2]+y});
}
}
else{
if(j!=0)
f1[i][j]=min(f1[i-1][j-1],f0[i-1][j-1]);
if(j==0){
f0[i][j]=min(f0[i-1][j+1]+y,f1[i-1][j+1]+x);
}
else if(j==i){
f0[i][j]=min(f0[i-1][j-1]+x,f1[i-1][j-1]+y);
}
else{
f0[i][j]=min({f0[i-1][j+1]+y,f1[i-1][j+1]+x,f0[i-1][j-1]+x,f1[i-1][j-1]+y});
}
}
}
}
cout<<f0[n][0]<<endl;
}
signed main(){
int T;cin>>T;
while(T--) solve();
}
C2. Sheikh (Hard Version) 2100
https://codeforces.com/problemset/problem/1732/C2
题解：对于一个区间，其显然其sum-xor最大值为整个区间，若想缩小区间，则需从两端逐渐缩减，一个点对sum-xor无影响当且仅当其让sum和xor增加了相同的数量，即为其所有为1的位上余下的xor为0，而总共只有31位，故当删除32个数时，必有两个某一位上均为1，此时对最大值有影响。故我们可以对每一个询问，枚举合法的左端点，寻找最小右端点，复杂度至多为3131q,可以通过。
代码：略。。