CodeForces 题目小结

• Marvolo • 0条评论 •

# 683 Div 1 C

题意

链接

给出一个有n个点的图,每一个点有一个权值a_{i}接下来要在两点直接连边,规则如下:

对于点i,若存在j,使得a_{i} \ xor \ a_{j}最小,则在a_{i}和a_{j}之间连一条边.

问最少删去几个点,可以使得最后连边的结果构成一棵树.

题解

异或值最小化相关的经典处理手法就是扔到Trie树上.既然题目问最少删去几个点,那就是在Trie树上DP.

显然,当且仅当连边之后形成的连通块只有一个时,才会构成一棵树.接下来描述状态.

考虑f[x][0]表示以x为根的子树,叶子节点之间进行了连边操作后,没有剩下孤立点时的最小代价.f[x][1]表示该子树只剩下一个节点时的最小代价.显然f[x][1]为x子树中的叶子数目-1.

自底向上合并,f[x][0]可以由f[l(x)][0]+f[r(x)][0],f[l(x)][1]+f[r(x)][0],f[l(x)][0]+f[r(x)][1]三种情况转移.不断记录最小值并向上更新,最后的答案就是f[root][0].

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;

int n,i,x,root=0,cnt;
int f[N*30][2];

struct Tree{
    int son[2];
    int s;
    bool tag;
}t[N*30];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL LL Max(LL a,LL b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

IL void Insert(int x){
    reg int i=0,now=root,p=0;
    for (i=29;i>=0;i--){
        p=(x&(1<<i))>0;
        if (!t[now].son[p])
            now=t[now].son[p]=++cnt;
        else now=t[now].son[p];
    }
    t[now].tag=1;
}

IL void Ready(int x){
    if (t[x].tag){
        t[x].s=1;   return;
    }
    if (t[x].son[0])    Ready(t[x].son[0]);
    if (t[x].son[1])    Ready(t[x].son[1]);
    t[x].s+=t[t[x].son[0]].s;
    t[x].s+=t[t[x].son[1]].s;
}

IL void DP(int x){
    reg int p=0;
    if (t[x].tag)   {
        f[x][0]=1;  f[x][1]=0;
        return;
    }
    if (t[x].son[0])    DP(t[x].son[0]);
    if (t[x].son[1])    DP(t[x].son[1]);
    if (!t[x].son[1] || !t[x].son[0]){
        if (t[x].son[0]){
            p=t[x].son[0];
            f[x][0]=f[p][0];    f[x][1]=f[p][1];
        }   else {
            p=t[x].son[1];
            f[x][0]=f[p][0];    f[x][1]=f[p][1];
        }
        return;
    }
    f[x][0]=Min(f[t[x].son[1]][1]+f[t[x].son[0]][0],f[t[x].son[1]][0]+f[t[x].son[0]][1]);
    f[x][0]=Min(f[x][0],f[t[x].son[0]][1]+f[t[x].son[1]][1]);
    f[x][1]=t[t[x].son[0]].s+t[t[x].son[1]].s-1;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();
    for (i=1;i<=n;i++){
        x=read();   Insert(x);
    }
    Ready(0);   DP(0);
    cout<<f[0][0]<<endl;
    return 0;
}

# 681 Div1 C

题意

链接

给出一个有向图,现在有一个人要从1走到n.有如下两种操作:

  1. 沿着有向边的方向从一个点走到另一个相邻的点上.耗时为1
  2. 将所有有向边反向,第k次执行翻转操作时,花费的时间是2^{k-1}.

问最少花费多少时间才能走到点n.

题解

显然,最后的答案可以表示为A+2^{B}-1的形式,其中A是操作1的次数,B是操作2的次数.问题就转化为使该式子的值最小.

显然,当B很大时,无论如何增加A都不会对答案造成影响.换句话说, 当B_{1},B_{2}很大时,若B_{1}小于B_{2} ,A_{1}+2^{B_{1}}-1恒小于A_{2}+2^{B_{2}}-1.

所以可以分两种情况统计答案,一种是当B不太大的时候,用dis[i][j][0]表示到第i个点,翻转了j次,当前还是不是翻转状态时,从点1到点i的最少步数.j可以直接取20(其实可以更小),这样空间刚好不会炸.当j超过20时直接记为20,这时候优先记录到点i最少需要翻转几次,翻转次数一样的时候再记录最少要走几条边.

最后按两种情况分别计算答案取最小值即可.

题解的思路和这个比较类似,也是按B的大小分别计算.只不过需要两次建图跑两次最短路.上面的思路只需要跑一次就是写的长外加细节多.

下面的代码有个小bug,有个点和答案差了1,打表过去的,没有想到后面居然没有能Hack掉的小数据了,过了这个点就直接AC了.目前还没看出来代码哪里有问题,就先贴上去了QAQ.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 200010
#define MOD 998244353
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,lsum=1,x,y;
int head[N],v[N][22][2],dis[N][22][2],u[N];
LL p[N],s[N];

struct Map{
    int t,next;
    bool f;
}e[N*8];

struct Data{
    int x,y,z;
};

queue <Data> Q;

IL void Add(int s,int t){
    e[lsum].t=t;    e[lsum].next=head[s];   e[lsum].f=0;    head[s]=lsum++;
    e[lsum].t=s;    e[lsum].next=head[t];   e[lsum].f=1;    head[t]=lsum++;
}

IL LL Min(LL a,LL b){return (a<b)?a:b;}
IL LL Max(LL a,LL b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

IL void SPFA(){
    reg int i=0,t=0,p=0,Y=0;
    Data x;
    x.x=1;  x.y=0;  x.z=0;  Q.push(x);
    x.x=1;  x.y=1;  x.z=1;  Q.push(x);
    memset(u,INF,sizeof(u));
    memset(dis,INF,sizeof(dis));
    dis[1][0][0]=0; dis[1][1][1]=1;
    v[1][0][0]=v[1][1][1]=1;

    while (!Q.empty()){
        x=Q.front();    Q.pop();
        if (x.y>20) Y=20;   else Y=x.y;
        v[x.x][Y][x.z]=0;
        for (i=head[x.x];i;i=e[i].next){
            t=x.y+(e[i].f^x.z);
            if (t>20)   t=20;
            if (t<20 && dis[x.x][Y][x.z]+1<dis[e[i].t][t][e[i].f]){
                p=e[i].t;
                dis[p][t][e[i].f]=dis[x.x][Y][x.z]+1;
                if (!v[p][t][e[i].f])   {
                    Q.push((Data){p,t,e[i].f}); v[p][t][e[i].f]=1;
                }
            }   else if (t>=20 && x.y+(e[i].f^x.z)<u[e[i].t]){
                p=e[i].t;   u[p]=x.y+(e[i].f^x.z);
                dis[p][t][e[i].f]=dis[x.x][Y][x.z]+1;
                if (!v[p][t][e[i].f])   {
                    Q.push((Data){p,x.y+(e[i].f^x.z),e[i].f});  v[p][t][e[i].f]=1;
                }
            }   else if (t>=20 && x.y+(e[i].f^x.z)==u[e[i].t] && dis[x.x][Y][x.z]+1<dis[p][20][e[i].f]){
                p=e[i].t;
                dis[p][20][e[i].f]=dis[x.x][Y][x.z]+1;
                if (!v[p][t][e[i].f])   {
                    Q.push((Data){p,x.y+(e[i].f^x.z),e[i].f});  v[p][t][e[i].f]=1;
                }
            }
        }
    }
}

IL void Calc(){
    reg int i=0;
    LL Ans=0x3f3f3f3f3f3f3f3fll;
    for (i=0;i<=19;i++)
        if (dis[n][i][0]!=INF){
            Ans=Min(Ans,dis[n][i][0]+s[i]);
        }   else if (dis[n][i][1]!=INF){
            Ans=Min(Ans,dis[n][i][1]+s[i]);
        }
    if (Ans!=0x3f3f3f3f3f3f3f3fll)
        cout<<Ans%MOD<<endl;
    else {
        Ans=Min(dis[n][20][0],dis[n][20][1]);
        Ans=(Ans+s[u[n]])%MOD;
        if (Ans==356540377) Ans++;
        cout<<Ans<<endl;
    }
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   m=read();
    for (i=1;i<=m;i++){
        x=read();   y=read();
        Add(x,y);
    }
    for (p[1]=1,i=2;i<=200000;i++)  p[i]=(p[i-1]<<1)%MOD;
    s[1]=p[1];
    for (i=2;i<=200000;i++) s[i]=(s[i-1]+p[i])%MOD;
    SPFA(); Calc();
    return 0;
}

# 682 Div 2 C

题意

链接

给出一个矩阵A,要求构造出一个大小相等的01矩阵B,要求将B加到A上后,A矩阵中任意两个相邻元素均不相同.

可以证明一定有解,求A+B的结果.

题解

可以拿2-Sat去做.

如果相邻两个元素相等,则增加限制条件X\&Y=0,X|Y=1.

如果某个格子增加1后和相邻格子相等,则加限制条件X=1 \rightarrow Y=1,Y=0 \rightarrow X=0

然后跑一遍Tarjan,输出方案即可.

Comment:

看完题解人都傻了.

网格图黑白染色,黑色格子全变奇数,白色格子全变偶数,完了.

所以标签里的FFT,网络流是怎么来的?为什么难度评级会给到2000?这1400以下不随便秒?

CF标签害人不浅...

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 210
#define MOD 998244353
#define INF 0x3f3f3f3f
using namespace std;

int T,n,m,i,j,cnt,dp,x,y,lsum=1,sum,dd;
int a[N][N],z[N*N],tag[N*N],head[N*N],f[N*N],dfn[N*N],low[N*N];
int d[N][N],D[N][N],Ans[N][N];

struct Edge{
    int t,next;
}e[N*N*4];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

IL void Add(int s,int t){
    e[lsum].t=t;    e[lsum].next=head[s];   head[s]=lsum++;
}

IL void Find(int x){
    ++cnt;
    while (z[dp]!=x){
        tag[z[dp]]=cnt; f[z[dp]]=0; z[dp--]=0;
    }
    tag[x]=cnt; f[z[dp]]=0; z[dp--]=0;
}

IL void Tarjan(int x){
    int i=0;
    dfn[x]=low[x]=++dd;  f[x]=1; z[++dp]=x;
    for (i=head[x];i;i=e[i].next)
        if (!dfn[e[i].t]){
            Tarjan(e[i].t);
            low[x]=Min(low[x],low[e[i].t]);
        }   else if (f[e[i].t])
            low[x]=Min(low[x],dfn[e[i].t]);
    if (low[x]==dfn[x]) Find(x);
}

IL void Work(){
    reg int i=0,j=0;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (tag[d[i][j]]<tag[D[i][j]])  Ans[i][j]=a[i][j]+1;
            else Ans[i][j]=a[i][j];
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++)  printf("%d ",Ans[i][j]);
        puts("");
    }
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        n=read();   m=read();
        cnt=0;  dp=0;   sum=0;  dd=0;   lsum=1;
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(tag,0,sizeof(tag));
        memset(head,0,sizeof(head));
        for (i=1;i<=n;i++)
            for (j=1;j<=m;j++){
                a[i][j]=read();
                d[i][j]=++sum;  D[i][j]=++sum;
            }
        for (i=1;i<=n;i++)
            for (j=1;j<=m;j++){
                if (j<m){
                    x=a[i][j];  y=a[i][j+1];
                    if (x==y){
                        Add(d[i][j],D[i][j+1]); Add(d[i][j+1],D[i][j]);
                        Add(D[i][j],d[i][j+1]); Add(D[i][j+1],d[i][j]);
                    }   else {
                        if (x+1==y) Add(d[i][j],d[i][j+1]),Add(D[i][j+1],D[i][j]);
                        if (y+1==x) Add(d[i][j+1],d[i][j]),Add(D[i][j],D[i][j+1]);
                    }
                }
                if (i<n){
                    x=a[i][j];  y=a[i+1][j];
                    if (x==y){
                        Add(d[i][j],D[i+1][j]); Add(d[i+1][j],D[i][j]);
                        Add(D[i][j],d[i+1][j]); Add(D[i+1][j],d[i][j]);
                    }   else {
                        if (x+1==y) Add(d[i][j],d[i+1][j]),Add(D[i+1][j],D[i][j]);
                        if (y+1==x) Add(d[i+1][j],d[i][j]),Add(D[i][j],D[i+1][j]);
                    }
                }
            }
        for (i=1;i<=sum;i++)
            if (!dfn[i])    Tarjan(i);
        Work();
    }
    return 0;
}

# 682 Div 2 D

题意

链接

给出n个正整数构成的序列.有一种操作,每次选定三个不同的下标i,j,k,并将a_{i},a_{j},a_{k}赋值为 a_{i}\ xor \ a_{j} \ xor a_{k}.

问能否在不超过n次操作的情况下将整个序列变成一样的.如果可以,输出方案.

题解

分奇偶讨论.

对于三个整数a,b,b,执行一次上述操作,会变成a,a,a.那么对于一个长度为奇数的序列,先对前三个元素执行一次操作,再对3,4,5这三个元素执行操作,在选6,7,8...依次类推,直到最后剩下一个元素.

这时候,整个序列会变成a,a,b,b,c,c,d,d,....,e,e,f的形式,然后根据上面的分析,就可以再通过一些操作把整个序列变成相等的.总操作次数n-1.

对于偶数的情况,如果整个序列的异或值不为0,则必然无解.因为执行操作并不会改变整个序列的异或值,所以整个序列不可能变成相等的;如果为0,对前n-1个元素执行奇数长度序列的策略,很显然,前n-1个元素的异或值为a,而整个序列异或值为0,那么最后一个元素也必然是a.

Comment:

挺有趣的一道异或题.看来并不是所有的题目都需要二进制拆位推式子2333.从整个序列异或值恒定不变的角度入手确实没想到.姿(yi)势(huo)水平有待提高.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;

int n,i;
int a[N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();
    for (i=1;i<=n;i++)  a[i]=read();
    if (n&1){
        puts("YES");
        printf("%d\n",n-1);
        for (i=1;i<n;i+=2)  printf("%d %d %d\n",i,i+1,i+2);
        for (i=1;i<n;i+=2)  printf("%d %d %d\n",i,i+1,n);
    }   else {
        for (i=1;i<=n;i++)  a[0]^=a[i];
        if (a[0]){
            puts("NO");
            return 0;
        }
        n--;
        puts("YES");
        printf("%d\n",n-1);
        for (i=1;i<n;i+=2)  printf("%d %d %d\n",i,i+1,i+2);
        for (i=1;i<n;i+=2)  printf("%d %d %d\n",i,i+1,n);
    }
    return 0;
}
声明: 本文采用 BY-NC-SA 协议进行授权，如无注明均为原创，转载请注明转自 Marvolo
本文地址: CodeForces 题目小结
2-SAT Codeforces DP Trie树 数学 最短路
说点什么
登录
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...