刷luogu2018号题单记录

codeforces 刷题

就当锻炼思维罢

CF1304C

初始区间设为 $[m,m]$，即 $L=R=m$，然后每过一个时间间隔 $d=t_i-t_{i-1}$，$L\leftarrow L-d$，$R\leftarrow R+d$，变成 $[L-d,R+d]$，然后再和当前需求区间 $[l_i,h_i]$ 取交，如果交到最后 $R>L$ 就不行，不然就行呗

#include<bits/stdc++.h>
using namespace std;
int q,n,m,t[105],l[105],r[105];
int main(){
    cin>>q;
    while(q--){
        cin>>n>>m;
        int L,R;L=R=m;
        for(int i=1;i<=n;i++) cin>>t[i]>>l[i]>>r[i];
        bool flg=1;
        for(int i=1;i<=n;i++){
            int d=t[i]-t[i-1];
            L-=d,R+=d;
            L=max(L,l[i]);
            R=min(R,r[i]);
            if(L>R){flg=0;break;}
        }
        cout<<(flg?"YES\n":"NO\n");
    }  
}

CF1385D

这个 $2^K$ 真的是个非常大的提示了，遂考虑分治。

$div(l,r,c)$ 表示把子串 $[l,r]$ 变成 $c$ 好串的代价。

为了维护这个信息，我们还需要知道

• 把左半以及右半区间变成好串的代价

• 把左右半边变成全部相同的代价

分治递归求解即可

#include<bits/stdc++.h>
using namespace std;
int t;
int n;
char s[200005];
int a[200005];
int div(int l,int r,int c){
    if(l==r){
        return a[l]!=c;
    }
    int mid=(l+r)>>1;
    int tot1,tot2;
    tot1=tot2=0;
    for(int i=l;i<=mid;i++){
        tot1+=(a[i]!=c); 
    }
    for(int i=mid+1;i<=r;i++){
        tot2+=(a[i]!=c);
    }
    return min(tot1+div(mid+1,r,c+1),tot2+div(l,mid,c+1));
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;cin>>(s+1);
        for(int i=1;i<=n;i++){
            a[i]=s[i]-'a'+1;
        }
        cout<<div(1,n,1)<<"\n";
    }
}