Codeforces Round #816 (Div. 2) A-D

传送门

A

题意：
长为n,m的一个棋盘，左上的旗子要去右下，左下的棋子要去右上，每次移动花费为1，但当一个棋子在另一个棋子的轨迹上时，可以花费1移动到轨迹上的任意位置，求将两个棋子移动到目标位置的最小花费。

分析：
那么至少一个棋子需要走完全程，不妨令\(n>m\)，因此默认左上棋子向下走到头在向右走，此时左下棋子沿轨迹到达左上在向右移，此时花费左上棋子花费\(n+m-2\)，左下棋子\(min(n,m)-1 + 1\),后面+1为在轨迹上转移花费，但当\(n=1\)时不用在轨道上转移，需要特判。

void Solve(){
    int n,m;
    cin>>n>>m;
    cout<<(n+m-2 + min(n,m)-1 + ((max(n,m)==1)? 0:1) )<<endl;
}  

B

题意：
定义一个长为n的非负的数组a的魅力值为\(\sum_{i=1}^{n}\lfloor \frac{a_i}{k}\rfloor\)。现在给定n,k,s,b，你需要找到一个长度为n，魅力值为b，且数组元素总和为s的数组a。

分析：
因为是向下取整，所以当\(s<b*k\)时无解，同时当每个\(a_i\%k=k-1\)时即\(s>n*(k-1)+k*b\)时无解。

此后情况均有解，先给最后一个数分配一个k*b，然后对剩下的数依次分配k-1直至分配完即可。

void Solve(){
    ll n,k,b,s;
    cin>>n>>k>>b>>s;
    if(s<b*k) puts("-1");
    else if(s>n*(k-1)+k*b) puts("-1");
    else{
        s-=k*b;
        ll last=k*b;
        if(s>=k-1) last+=k-1,s-=k-1;
        rep(i,1,n-1){
            if(s>=k-1) s-=k-1,printf("%lld ",k-1);
            else printf("%lld ",s),s=0;
        }
        printf("%lld \n",last);
    }
}  

C

题意：
单点修改，每次求所有区间内的块数和，区间内连续相同的数可以被分为一块。

分析：
对于求所有区间的块数和，我们首先考虑整个序列每个位置所在的块号，然后枚举每个位置作为左端点时所有区间的块数和，此时后面每个位置的贡献即为他们所在的块号减去左端点的块号+1，此处可\(O(n)\)获得。

而对于修改，
首先若修改前后一样，不发生变化。
若不为第一位：
当前值与上一个相等时，修改后若以该点前面的点作为左端点，该点及其后面的点作为右端点，则每一个区间的块数都+1，此时答案为\(+(pos-1)*(n-pos+1)\).
当前值与上一个不相等，但改后相等，此时同上，答案为\(-(pos-1)*(n-pos+1)\)
若不为最后一位：
当前值与下一个相等时，修改后若以该点及其前面的点作为左端点，该点后面的点作为右端点，则每一个区间的块数都+1，此时答案为\(+pos*(n-pos)\)
当前值与下一个不相等时，但改后相等，同上，答案为\(-pos*(n-pos)\)

void solve(){
    int n,m;cin>>n>>m;
    vector<ll>a(n+1);
    rep(i,1,n) cin>>a[i];
    int id=0;
    ll sum=0,ans=0;
    rep(i,1,n){
        if(a[i]!=a[i-1]) id++;
        sum+=id;
    }
    id=0;
    rep(i,1,n){
        if(a[i]!=a[i-1]) id++;
        ans+=sum-1LL*(id-1)*(n-i+1);
        sum-=id;
    }
    while(m--){
        ll pos,x;cin>>pos>>x;
        if(a[pos]==x) {
            cout<<ans<<"\n";continue;
        }
        if(pos!=1){
            if(a[pos-1]==a[pos]){
                ans+=(pos-1)*(n-pos+1);
            }
            else if(a[pos-1]==x){
                ans-=(pos-1)*(n-pos+1);
            }
        }
        if(pos!=n){
            if(a[pos+1]==a[pos]){
                ans+=pos*(n-pos);
            }
            else if(a[pos+1]==x){
                ans-=pos*(n-pos);
            }
        }
        a[pos]=x;
        cout<<ans<<"\n";
    }
}  

D

题意：
你需要给出一个字典序最小长度为n的数组a满足q个条件，每个条件形如\((i,j,x)\)表示\(a_i | a_j = x\)

分析：
首先可以按位考虑，位之间不会干扰。
那么对于每一位，要让字典序最小，那么前面的位置要尽可能地小，因此除已经确定的位置外，我们让前面尽可能地为0，后面为1.
那么首先处理\(i=j\)的关系，将一些位置确定，随后从前往后遍历，如果当前位置未被确定，那么当前位为0，与当前位置有关的所有关系当前位如果或值为1，那么对应位置当前位为1，这样满足先确定前面最小，后面由前面决定。

struct node{int u,v,w;};
struct Edge{
    int v,nxt;
};
int cnt=0;
void solve(){
    int n,q;cin>>n>>q;
    vector<node>p(q+1);
    vector<int>ans(n+1);
    rep(i,1,q){
        int u,v,w; 
        cin>>u>>v>>w;
        p[i]={u,v,w};
    }
    rep(k,0,29){
        vector<int>vis(n+1,-1),last(n+1,0);cnt=0;
        vector<Edge>G(q*2+1);
        rep(i,1,q){
            int u=p[i].u,v=p[i].v,w=((p[i].w>>k)&1);
            if(u!=v && w){
                G[++cnt]={v,last[u]};last[u]=cnt;
                G[++cnt]={u,last[v]};last[v]=cnt;
            }
            else vis[u]=vis[v]=w;
        }
        rep(i,1,n){
            if(!vis[i]){
                for(int j=last[i];j;j=G[j].nxt) vis[G[j].v]=1;
            }
        }
        rep(i,1,n){
            if(vis[i]==1) ans[i]|=(1<<k);
            else{
                for(int j=last[i];j;j=G[j].nxt) vis[G[j].v]=1;
            }
        }
    }
    rep(i,1,n) cout<<ans[i]<<" ";
    pts;
}  

E

斜率优化dp，待补