526互联

cf1869 div.1,div.2做题记录

发布时间 2023-09-19 09:40:55作者: luo_shen

赛时总结

div.2A

题面

对于任意一个区间，我们可以通过一次操作将区间内的数变得全部相同。如果区间内的全部数都相同，那么我们再做一遍区间操作，当这个区间长度为偶数时，区间异或和为 \(0\)，会清空区间；当区间长度为奇数时，区间内的数不会发生改变。但我们可以将一个长度为奇数的区间拆成两个长度为偶数的区间，只要这两个长度为偶数的区间的并为原区间即可。我们令上述的区间为整个区间 \([1,n]\) 即可。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=110;
int n,a[N],xsum[N];
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        xsum[i]=xsum[i-1]^a[i];
    }
    if(n%2==0){
        write_endl(2);
        write_space(1),write_endl(n);
        write_space(1),write_endl(n);
        return;
    }
    write_endl(4);
    write_space(1),write_endl(n);
    write_space(1),write_endl(2);
    write_space(2),write_endl(n);
    write_space(2),write_endl(n);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

div.2B

题面

分类讨论。两个点均为关键点，答案为 \(0\)；一个为关键点，另一个为非关键点，答案为该非关键点到所有关键点的距离中最小的；如果两个点均为非关键点，答案如果经过关键点，为两个点到关键点的最小距离的和，如果不经过关键点，为两点的曼哈顿距离，取两者中较小的即可。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e18;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e5+10;
int n,x[N],y[N],k,st,ed;
void solve(){
    read(n),read(k),read(st),read(ed);
    for(int i=1;i<=n;i++){
        read(x[i]),read(y[i]);
    }
    if(st>k&&ed>k){
        int suml=inf,sumr=inf;
        for(int i=1;i<=k;i++){
            suml=min(suml,abs(x[st]-x[i])+abs(y[st]-y[i]));
            sumr=min(sumr,abs(x[ed]-x[i])+abs(y[ed]-y[i]));
        }
        write_endl(min(suml+sumr,abs(x[st]-x[ed])+abs(y[st]-y[ed])));
        return;
    }
    if(st<=k&&ed<=k){
        write_endl(0);
        return;
    }
    if(st<=k){
        swap(st,ed);
    }
    int ans=inf;
    for(int i=1;i<=k;i++){
        ans=min(ans,abs(x[st]-x[i])+abs(y[st]-y[i]));
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

div.2C,div.1A

题面

如果只有一列，答案显然为 \(0\)，因为所有的格子都只能填 \(0\)，这时候该列的 \(\mathop{\mathrm{mex}}\) 值为 \(1\)，所有列的 \(\mathop{\mathrm{mex}}\) 值的 \(\mathop{\mathrm{mex}}\) 为 \(0\)。

如果只有一行且不止一列，答案显然为 \(2\)，因为是一个排列，所以 \(0\) 必然出现，则必然有一列的 \(\mathop{\mathrm{mex}}\) 值为 \(1\)，其它列的 \(\mathop{\mathrm{mex}}\) 值为 \(0\)，所有列的 \(\mathop{\mathrm{mex}}\) 值的 \(\mathop{\mathrm{mex}}\) 为 \(2\)。

特判掉上述两种情况，剩下的就是正常情况了。

假定我们已经知道了答案的值为 \(ans\)，我们该如何构造一个合法的解。其实我们只需要一个大小为 \(ans-1\times ans\) 的矩阵即可，将第一行变为 \(0\sim m\)，之后每一列都往后面循环位移一位。此时 \(\mathop{\mathrm{mex}}=0\sim ans-1\) 就都构造出来了。根据上面的构造，答案的最大值为 \(\min(n+1,m)\)，剩下位置可以随便填，只要保证每行是个排列就行。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
int n,m;
void solve(){
    read(n),read(m);
    if(m==1){
        write_endl(0);
        for(int i=1;i<=n;i++){
            write_endl(0);
        }
        return;
    }
    if(n==1){
        write_endl(2);
        for(int i=0;i<m;i++){
            write_space(i);
        }
        putchar('\n');
        return;
    }
    if(n+1<m){
        write_endl(n+1);
        for(int i=0;i<m;i++){
            write_space(i);
        }
        putchar('\n');
        for(int i=1;i<n;i++){
            for(int j=0;j<=n;j++){
                write_space((i+j)%(n+1));
            }
            for(int j=n+1;j<m;j++){
                write_space(j);
            }
            putchar('\n');
        }
        return;
    }
    write_endl(m);
    for(int i=0;i<m;i++){
        write_space(i);
    }
    putchar('\n');
    for(int i=1;i<m-1;i++){
        for(int j=0;j<m;j++){
            write_space((i+j)%m);
        }
        putchar('\n');
    }
    for(int i=m-1;i<n;i++){
        for(int j=0;j<m;j++){
            write_space(j);
        }
        putchar('\n');
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

div.2D,div.1B

Easy Version

题面

根据题意，每个人要送出 \(2^x\) 个，收到 \(2^y\) 个。令 \(p\) 表示所有数的平均数，\(delta_i\) 表示 \(a_i-p\)。若 \(p\) 不是整数或者 \(delta_i\) 不能被分成 \(2^x-2^y\)，显然无解。假设要有 \(m\) 个人送出 \(2^x\) 个，有 \(n\) 个人收到 \(2^x\) 个，若 \(m\not=n\)，不满足题目条件，无解。剩下的情况均有解，因为对于任意一个合法的 \(delta\) 序列，必然存在一个操作顺序使得没有任何人在给出操作前满足拥有的数量少于给出的数量。详细证明可以看CF官方题解。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e5+10;
int n,a[N],cnt[100];
void solve(){
    read(n);
    int sum=0;
    for(int i=1;i<=n;i++){
        read(a[i]);
        sum+=a[i];
    }
    for(int i=0;i<=70;i++){
        cnt[i]=0;
    }
    if(sum%n!=0){
        puts("No");
        return;
    }
    int p=sum/n;
    for(int i=1;i<=n;i++){
        int delta=a[i]-p;
        if(delta==0){
            continue;
        }
        if(delta<0){
            delta=-delta;
            int x=60,y=60;
            for(int i=60;i>=0;i--){
                if((1ll<<i)>delta){
                    x=i;
                }
                if(delta>>i&1){
                    y=i;
                }
            }
            if((1ll<<x)-(1ll<<y)!=delta){
                puts("No");
                return;
            }
            cnt[y]++;
            cnt[x]--;
        }
        else{
            int x=60,y=60;
            for(int i=60;i>=0;i--){
                if((1ll<<i)>delta){
                    x=i;
                }
                if(delta>>i&1){
                    y=i;
                }
            }
            if((1ll<<x)-(1ll<<y)!=delta){
                puts("No");
                return;
            }
            cnt[x]++;
            cnt[y]--;
        }
    }
    for(int i=0;i<=70;i++){
        if(cnt[i]){
            puts("No");
            return;
        }
    }
    puts("Yes");
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

Hard Version

题面

这里新增了一个条件：对于所有的 \(delta_i=2^x\)，可以拆分成 \(2^x\) 和 \(2^{x+1}-2^x\)。因为这种情况不好处理，所以先处理只有一种拆分的情况。有两种拆分情况的如果必须拆成 \(2^{x+1}-2^x\) 则拆，否则以 \(2^x\) 的形式计入答案。如果最后有没有被抵消的，则答案为 No，否则为 Yes。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e5+10;
int n,a[N],cnt[100],totl[100],totr[100];
void solve(){
    read(n);
    int sum=0;
    for(int i=1;i<=n;i++){
        read(a[i]);
        sum+=a[i];
    }
    for(int i=0;i<=70;i++){
        cnt[i]=0;
        totl[i]=totr[i]=0;
    }
    if(sum%n!=0){
        puts("No");
        return;
    }
    int p=sum/n;
    for(int i=1;i<=n;i++){
        int delta=a[i]-p;
        // cerr<<delta<<endl;
        if(delta==0){
            continue;
        }
        if(delta<0){
            delta=-delta;
            if((delta&(-delta))==delta){
                int x=0;
                while(delta>1){
                    x++;
                    delta=delta>>1ll;
                }
                totr[x]++;
                continue;
            }
            int x=60,y=60;
            for(int i=60;i>=0;i--){
                if((1ll<<i)>delta){
                    x=i;
                }
                if(delta>>i&1){
                    y=i;
                }
            }
            if((1ll<<x)-(1ll<<y)!=delta){
                puts("No");
                return;
            }
            cnt[y]++;
            cnt[x]--;
        }
        else{
            if((delta&(-delta))==delta){
                int x=0;
                while(delta>1){
                    x++;
                    delta=delta>>1ll;
                }
                totl[x]++;
                continue;
            }
            int x=60,y=60;
            for(int i=60;i>=0;i--){
                if((1ll<<i)>delta){
                    x=i;
                }
                if(delta>>i&1){
                    y=i;
                }
            }
            if((1ll<<x)-(1ll<<y)!=delta){
                puts("No");
                return;
            }
            cnt[x]++;
            cnt[y]--;
        }
    }
    // for(int i=70;i>=0;i--){
    //     cerr<<i<<' '<<cnt[i]<<' '<<tot[i]<<endl;;
    // }
    for(int i=70;i>=0;i--){
        if(cnt[i+1]){
            int x=cnt[i+1];
            if(x>0){
                if(totr[i]<x){
                    puts("No");
                    return;
                }
                totr[i]-=x;
                cnt[i]+=x;
                cnt[i+1]=0;
            }
            else{
                x=-x;
                if(totl[i]<x){
                    puts("No");
                    return;
                }
                totl[i]-=x;
                cnt[i]-=x;
                cnt[i+1]=0;
            }
        }
        cnt[i]+=totl[i];
        cnt[i]-=totr[i];
    }
    for(int i=0;i<=70;i++){
        if(cnt[i]){
            puts("No");
            return;
        }
    }
    puts("Yes");
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

这次 2A，2B 做得太nt了，两题加起来做了30min，太慢了，还好一个小时内写完 2D，但是没时间写 2E 了。

补题

div.2E,div.1C

题面

因为值域很小，所以考虑枚举最大值进行容斥。令 \(F_x\) 表示对于每条链，链上的点 \(max\le x\)，其它点随意填的方案数，所以答案为 \(\sum\limits_{i=1}^mi(F_i-F_{i-1})\)。

考虑树形dp求解，令 \(f_k\) 表示大小为 \(k\) 的子树内的方案数，\(g_k\) 表示到大小为 \(k\) 树的内部到根的路径填法和。

可以写出转移式：

\[g_k=x(g_{sizl}m^{sizr}+g_{sizr}m^{sizl}+m^{k-1}) \]

\[f_k=g_k+xg_{sizl}g_{sizr}+m(f_{sizl}m^{sizr}+f_{sizr}m^{sizl}) \]

其中 \(sizl,sizr\) 分别表示左右子树的大小，因为是完全二叉树，所以左右子树中必然有一个是满二叉树，可以记录下这些答案，实际状态就为 \(O(\log n)\) 级别的了。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=1e5+10,mod=998244353;
int k,ans[N];
int n;
struct node{
    int ans,val,mul;
}F[100];
node dfs(int u,int mx){
    if(!u){
        return node{0,0,1};
    }
    if(u==1){
        return node{mx,mx,k};
    }
    u++;
    if(__builtin_popcountll(u)==1ll&&F[__builtin_ctzll(u)].mul){
        return F[__builtin_ctzll(u)];
    }
    u--;
    int ri=1ll<<(64-__builtin_clzll(u));
    ri--;
    int lx=(ri-1)>>1ll,rx=lx;
    int li=ri-u,di=(ri+1)>>2ll;
    if(li<=di){
        rx-=li;
    }
    else{
        rx-=di;
        lx-=li-di;
    }
    node lans=dfs(lx,mx),rans=dfs(rx,mx),res;
    res.mul=1ll*lans.mul*rans.mul%mod;
    res.val=(1ll*lans.val*rans.mul%mod+1ll*lans.mul*rans.val%mod+res.mul)%mod*mx%mod;
    res.mul=1ll*res.mul*k%mod;
    res.ans=(1ll*lans.val*rans.val%mod*mx%mod+res.val+(1ll*lans.ans*rans.mul%mod+1ll*lans.mul*rans.ans%mod)%mod*k%mod)%mod;
    u++;
    if(__builtin_popcountll(u)==1){
        F[__builtin_ctzll(u)]=res;
    }
    return res;
}
void solve(){
    read(n),read(k);
    for(int i=1;i<=k;i++){
        memset(F,0,sizeof(F));
        ans[i]=dfs(n,i).ans;
    }
    int res=0;
    for(int i=k;i;i--){
        ans[i]=(ans[i]-ans[i-1]+mod)%mod;
        res=(res+1ll*ans[i]*i%mod)%mod;;
    }
    write_endl(res);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

div.2F,div.1D

咕咕咕