abc386

· · 题解

A题

暴力统计每个数出现次数。

B题

枚举每一位，如果是零，找到后面有连续多少个，除以二向上取整。

C题

从左往右枚举一样的前缀，从右往左枚举一样的后缀，统计两个字符串除去前后缀还剩多少个字符，如果都小于等于1，可以一次操作完成。注意枚举后缀时不要与前缀重合。

void solve(){
    int k;
    string s,t;
    cin>>k>>s>>t;
    int sl=0,sr=s.size()-1,tl=0,tr=t.size()-1;
    while(sl<s.size()&&tl<t.size()&&s[sl]==t[tl])sl++,tl++;
    while(sr>=sl&&tr>=tl&&s[sr]==t[tr])sr--,tr--;
    int lens=sr-sl+1,lent=tr-tl+1;
    if(max(lens,lent)<=1)cout<<"Yes";
    else cout<<"No";
}

D题

每个点按行升序排列，从上往下扫，维护到现在为止白色点所在列最靠左的位置，从这个位置往右必须填白色，所以如果枚举到有黑色点在右边，显然无解。

void solve(){
    int n,m;
    cin>>n>>m;
    vector<tuple<int,int,char>>v(m);
    for(auto&[x,y,c]:v)cin>>x>>y>>c;
    sort(all(v));
    int mn=n+1;
    for(auto[x,y,c]:v){
        if(c=='W')mn=min(mn,y);
        else if(mn<=y){
            cout<<"No";
            return;
        }
    }
    cout<<"Yes";
}

也可以求出所有必须填黑色的点，判断是否有重合部分。

E题

看到题面就是暴力DFS，在DFS时，有几个小优化，可以大大降低时间复杂度。

  1. 如果剩下的数字不够选，直接退出。
  2. 在DFS时没有必要枚举后面每一个可选的数，像01背包一样只枚举当前数字选或不选

具体实现见代码。

int n,k,ans=0;
vector<int>v;
void dfs(int x,int xr,int cnt){
    if(k==cnt){ans=max(ans,xr);return;}
    if(n-x<k-cnt)return;
    dfs(x+1,xr^v[x],cnt+1);
    dfs(x+1,xr,cnt);
}
void solve(){
    cin>>n>>k;
    v.resize(n);
    cin>>v;
    if(k*2>n){
        int all=0;
        for(auto&i:v)all^=i;
        k=n-k;
        dfs(0,all,0);
    }
    else dfs(0,0,0);
    cout<<ans;
}

F题

DP。看C题的时候就想到编辑距离这题，设计DP状态：dp(i,j) 表示 s 的前 i 个字符与 t 的前 j 个字符之间最少操作次数。如果最后一次使用替换字符，那么从 dp(i-1,j-1)+1 转移来，如果使用删除，那么从 dp(i,j-1)+1 转移来，如果使用插入，那么从 dp(i-1,j)+1 转移来，如果 s_i=t_j，还可以直接从 dp(i-1,j-1) 转移来。dp(i,j)=max\{dp(i-1,j-1)+[s_i\not=t_j],dp(i-1,j)+1,dp(i,j-1)+1\}

但是有一些不同，如数据范围 n\le5\times10^5，看似得用更快的做法，实际上操作次数大于 k 的，我们并不需要知道它们具体多少，压根不用算。观察到当 |i-j|>k 时，操作次数显然大于 k，只需开一个 f 数组，用 f(i,i-j) 表示 dp(i,j)（由于 i-j 可能是负数，真正实现时我额外加上了 22），f 数组开到 n\times45 就绝对够了。状态转移方程不变。

记得特判 \lvert\lvert s\rvert-\lvert t\rvert\rvert>k 的情况。

代码：

int k;
string s,t;
int f[500010][45];
int&dp(int i,int j){return f[i][i-j+22];}//通过传引用的方式实现dp与f的转化
void solve(){
    cin>>k>>s>>t;
    int n=s.size(),m=t.size();
    if(abs(n-m)>k){
        cout<<"No";
        return;
    }
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<=k;i++){
        dp(0,i)=i;
        dp(i,0)=i;
    }
    for(int i=1;i<=n;i++)for(int j=max(1ll,i-k);j<=min(i+k,m);j++){
        dp(i,j)=min({dp(i-1,j)+1,dp(i,j-1)+1,dp(i-1,j-1)+(s[i-1]!=t[j-1])});
    }
    if(dp(n,m)<=k)cout<<"Yes";
    else cout<<"No";
}