AtCoder Grand Contest 017题解

传送门

\(A\)

直接转移就是了

typedef long long ll;
const int N=55;
ll f[N][2];int a[N],n,p;
int main(){
    scanf("%d%d",&n,&p);
    fp(i,1,n)scanf("%d",&a[i]),a[i]&=1;
    f[0][0]=1;
    fp(i,1,n){
        f[i][0]=f[i-1][0],f[i][1]=f[i-1][1];
        if(a[i]&1)f[i][0]+=f[i-1][1],f[i][1]+=f[i-1][0];
            else f[i][0]+=f[i-1][0],f[i][1]+=f[i-1][1];
    }
    printf("%lld\n",f[n][p]);
    return 0;
}

\(B\)

我是个\(zz\)……

每个数的贡献要么为正要么为负,那么我们枚举有几个贡献为正的,然后算一下贡献总和的上下界就行了

typedef long long ll;
int n,a,b,c,d;ll l,r;
int main(){
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&d),b-=a;
    fp(i,0,n-1){
        l=1ll*i*c-1ll*(n-1-i)*d;
        r=1ll*i*d-1ll*(n-1-i)*c;
        if(b>=l&&b<=r)return puts("YES"),0;
    }
    puts("NO");
    return 0;
}

\(C\)

我脑子里装的都是浆糊吧……

对于一个数\(i\),如果出现了\(cnt[i]\)次,那么我们可以看做把\([i-cnt[i]+1,i]\)的位置给区间加一,那么需要改的次数就是为\(0\)的位置个数,那么修改可以\(O(1)\)

//quming
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=2e5+5;
int cnt[N],vis[N],a[N],n,m,res;
inline void ins(R int x){++cnt[x];if(x-cnt[x]+1>=1&&!vis[x-cnt[x]+1]++)--res;}
inline void del(R int x){if(x-cnt[x]+1>=1&&!--vis[x-cnt[x]+1])++res;--cnt[x];}
int main(){
    scanf("%d%d",&n,&m),res=n;
    fp(i,1,n)scanf("%d",&a[i]),ins(a[i]);
    for(R int i=1,x,y;i<=m;++i){
        scanf("%d%d",&x,&y);
        del(a[x]),a[x]=y,ins(a[x]);
        printf("%d\n",res);
    }
    return 0;
}

\(D\)

想了半天结果一看题解发现并没有神仙结论……

我们考虑每棵子树的\(sg\)值,如果是叶子,那么\(sg(u)=0\),否则每个儿子都相当于一个子游戏,算出儿子节点\(v\)的\(sg\)值后,那么\(v\)的子树加上\((u,v)\)这条边的\(sg\)值就是\(sg(v)+1\)

证明的话,如果删掉的是\((u,v)\)这条边,那么\(sg=0\),否则的话假设删掉的是\(v\)这棵子树中的一条边,得到的是由\(v\)原来的子树\(T\)可以得到的一个\(T'\),如果我们用归纳法,那么\(sg(T')\)可以取遍\([0+1,1+1,2+1,...,sg(T)-1+1]\),所以\(sg(u)=sg(T)+1\)

//quming
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=1e5+5;
struct eg{int v,nx;}e[N<<1];int head[N],tot;
inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}
int sg[N],n;
void dfs(int u,int fa){
    sg[u]=0;
    go(u)if(v!=fa)dfs(v,u),sg[u]^=sg[v]+1;
}
int main(){
    scanf("%d",&n);
    for(R int i=1,u,v;i<n;++i)scanf("%d%d",&u,&v),add(u,v),add(v,u);
    dfs(1,0);
    puts(sg[1]?"Alice":"Bob");
    return 0;
}

\(E\)

对于每一个点\(i\),如果\(c_i=0\)则设\(l=a_i\)否则设\(l=-c_i\),如果\(d_i=0\)则设\(r=-b_i\)否则设\(r=d_i\),那么我们发现如果\((li,ri)\)能接在\((l,r)\)的右边当且仅当\(li=r\)

那么我们把\((l,r)\)当做从\(l\)连到\(r\)的一条边,那么现在要把这个图分解成若干条路径,使得每条路径的开头是正数,结尾是负数。那么显然正数的出度大于等于入度,而负数的入度大于等于出度,且对于每一个连通块至少有一个点的出度不等于入度(否则这个东西成环且永远没办法分解成若干条路径)

//quming
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=405;
int fa[N],vis[N],in[N],out[N],n,h;
inline int find(R int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main(){
    scanf("%d%d",&n,&h);
    fp(i,0,h<<1)fa[i]=i;
    for(R int i=1,a,b,c,d,l,r;i<=n;++i){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        l=(c?-c:a)+h,r=(d?d:-b)+h,fa[find(l)]=find(r);
        ++out[l],++in[r];
    }
    fp(i,-h,-1)if(out[i+h]>in[i+h])return puts("NO"),0;
    fp(i,1,h)if(in[i+h]>out[i+h])return puts("NO"),0;
    fp(i,0,h<<1)if(in[i]!=out[i])vis[find(i)]=1;
    fp(i,0,h<<1)if(in[i]&&out[i]&&!vis[find(i)])return puts("NO"),0;
    puts("YES");
    return 0;
}

\(F\)

首先可以把路径压缩成二进制数,这样暴力的话可以写出一个\(O(2^{2n})\)的\(dp\)

考虑怎么优化,我们发现一条路径合法,当且仅当任意时刻前缀和都小于等于前一条路径的前缀和

设现在在考虑第\(i\)条路径,然后强制前\(j-1\)步和上一条相同,那么考虑第\(j\)步

如果相同直接无视,否则如果上一步走\(1\)这一步走\(0\)显然\(gg\),那么只需要考虑上一步走\(1\)这一步走\(0\)

我们找到\(i-1\)的下一个\(1\)的位置,然后把那个\(1\)的位置移到前面来,这样的话限制条件仍然合法

如果不存在下一个\(1\)那么当前这条路显然可以随便走了

那么直接\(dp\)就可以了

//quming
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int P=1e9+7;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
    R int res=1;
    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
    return res;
}
const int N=(1<<20)+5;
int f[25][N],g[N],is[25][25],nxt[N][25],n,m,k,res,lim;
int main(){
//  freopen("testdata.in","r",stdin);
    scanf("%d%d%d",&n,&m,&k),--n,lim=(1<<n);
    memset(is,-1,sizeof(is));
    for(R int i=1,a,b,c;i<=k;++i)scanf("%d%d%d",&a,&b,&c),is[a][b-1]=c;
    fp(s,0,lim-1){
        R int p=-1;
        fd(i,n-1,0){
            if(s>>i&1)p=i;
            nxt[s][i]=p;
        }
    }
    f[n][0]=1;
    fp(i,1,m){
        fp(j,0,lim-1)g[j]=f[n][j];
        memset(f,0,sizeof(f));
        fp(j,0,lim-1)f[0][j]=g[j];
        fp(j,0,n-1)fp(k,0,lim-1)if(f[j][k])
            fp(l,0,1){
                if(is[i][j]!=-1&&l!=is[i][j])continue;
                R int t=k>>j&1;
                if(l==0&&t==1)continue;
                if(l==t)upd(f[j+1][k],f[j][k]);
                else{
                    R int p=nxt[k][j];
                    if(p==-1)upd(f[j+1][k|(1<<j)],f[j][k]);
                    else upd(f[j+1][k^(1<<j)^(1<<p)],f[j][k]);
                }
            }
    }
    fp(i,0,lim-1)upd(res,f[n][i]);
    printf("%d\n",res);
    return 0;
}
上一篇:L1-017 到底有多二 (15分)


下一篇:漏洞学习笔记-017-ASLR简介