2019.10.9 noip多校联测

T1

Solution:

我们先钦定一个根节点1，设\(f1[x]\)表示\(x\)的儿子的异或和，\(f2[x]\)表示\(x\)的孙子的异或和

那么每次修改操作，我们只需要修改\(f1[fa[x]]\)和\(f2[fa[fa[x]]]\)即可，答案也很好算，不过要特判\(x\)没有父亲的情况

Code:

#include<cstdio>
#include<ctype.h>
#define int long long
using namespace std;
const int N=1e6+1;
const int mod=1e9+7;
int n,m,cnt,ans,head[N],a[N];
int fa[N],f1[N],f2[N];
struct Edge{int nxt,to;}edge[N<<1];
void ins(int x,int y){
    edge[++cnt].nxt=head[x];
    edge[cnt].to=y;head[x]=cnt;
}
void dfs1(int x){
    for(int i=head[x];i;i=edge[i].nxt){
        int y=edge[i].to;
        if(y==fa[x]) continue;
        fa[y]=x;dfs1(y);
        f1[x]^=a[y];
    }
}
void dfs2(int x){
    for(int i=head[x];i;i=edge[i].nxt){
        int y=edge[i].to;
        if(y==fa[x]) continue;
        dfs2(y);f2[x]^=f1[y]; 
    }
}
void modify(int x,int v){
    if(fa[x]) f1[fa[x]]^=a[x]^v;
    if(fa[fa[x]]) f2[fa[fa[x]]]^=a[x]^v;
    a[x]=v;
}
int calc(int x){
    int re=0;
    re^=f1[x]^f2[x];re^=f1[fa[x]];
    re^=a[fa[x]]^a[fa[fa[x]]];
    if(!fa[x]) re^=a[x];
    return re;
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
signed main(){
    freopen("blossom.in","r",stdin);
    freopen("blossom.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        ins(x,y),ins(y,x);
    }dfs1(1);dfs2(1);
    for(int i=1;i<=m;i++){
        int x=read(),y=read();modify(x,y);
        ans+=(i*1ll*i%mod*1ll*calc(x)),ans%=mod;
    }printf("%lld\n",ans%mod);
    return 0;
}

T2

Solution:

用\(f[0/1][x]\)表示从1号点或2号点出发到达点集\(x\)的连边方案，其中\(x\)是一个点集状态，转移：
\[ f[a][x]=2^{S(x)}-\sum_{u\subseteq x,a\in u,u\not =x}f[a][u]\times 2^{S(x-u)} \]
其中\(S(x)\)表示点集\(x\)仅在內部连边的边的数量，正难则反，考虑如何计算不合法的方案

我们每次枚举两个没有边相连的点集，让1走到其中1个，2走到另一个

这两个点集连向剩下的点的边的方向应该是确定的，而剩下的点集不连出来的边可以乱连，即
\[ ans=2^m-\sum_{u1,u2\subseteq V,u1\land u2=\emptyset,1\in u1,2\in u2}f[0][u1]\times f[1][u2]\times 2^{S(V-u1-u2)} \]

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1<<17;
const int mod=1e9+7;
int n,m,ans,f[2][N];
int a[221],b[221],g[N],w[N];
int qpow(int a,int b){
    int re=1;
    while(b){
        if(b&1) re=(re*1ll*a)%mod;
        b>>=1;a=(a*1ll*a)%mod;
    }return re;
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
signed main(){
    freopen("moviestar.in","r",stdin);
    freopen("moviestar.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        a[i]=read(),b[i]=read();
        --a[i],--b[i];
        g[(1<<a[i])]|=(1<<b[i]);
        g[(1<<b[i])]|=(1<<a[i]);
    }int M=1<<n;
    for(int i=1;i<M;i++){
        for(int j=1;j<=m;j++)
            if((i&(1<<a[j]))&&(i&(1<<b[j]))) ++w[i];
        w[i]=qpow(2,w[i]);
    }
    for(int i=1;i<M;i++)
        for(int j=i;j;j=(j-1)&i) g[i]|=g[j];
    for(int i=0;i<2;i++)
        for(int j=1;j<M;j++){
            if(!(j&(1<<i))) continue;
            f[i][j]=w[j];
            for(int k=(j-1)&j;k;k=(k-1)&j)
                f[i][j]=(f[i][j]-(w[j-k]*1ll*f[i][k])%mod+mod)%mod;
        }
    int sum=0;ans=qpow(2,m);
    for(int i=1,s=(M-1)-i;i<M;i++,s=(M-1)-i){
        if(!i&1) continue;
        for(int j=s;j;j=(j-1)&s){
            if(!(j&2)) continue;
            if((g[i]&j)||(g[j]&i)) continue;
            sum=(sum+f[0][i]*1ll*f[1][j]%mod*w[s-j])%mod;
        }
    }
    printf("%lld\n",(ans+mod-sum)%mod);
    return 0;
}

T3

Solution:

考虑将区间操作转化为单点修改，我们用差分来实现，\(b[x]=a[x]\oplus a[x-1]\)

那么问题就转换成了每次选一个奇质数\(p\)和一个位置\(x\)，把\(b[x]\)和\(b[x+p]\)反转，求最小操作数

考虑两个为1的点\(i,j\)，有哪些情况：

当\(|i-j|\)为奇质数时，显然只需要一次操作

当\(|i-j|\)为偶数时，考虑哥德巴赫猜想，则需要两次操作(当\(|i-j|=4\)时，分为两个奇质数之差)

当\(|i-j|\)为奇数且不为质数时，它可以分为一个偶数加一个奇质数，即3次操作

我们贪心的采用第一个操作，按照坐标奇偶性划分，用网络流跑二分图最大匹配即可

若还剩下未能匹配的点，在考虑剩下两种情况即可

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+11;
const int M=7e5+11;
const int MAXN=1e7+11;
const int inf=2147483647;
int n,tot,cnt=1,t1,t2,mx,S,T,hd[M];
int ans,pri[M],L[N<<1],R[N<<1];
bitset<MAXN> is,a;
struct Edge{int nxt,to,val;}e[M];
void ins(int x,int y,int z){
    e[++cnt].nxt=hd[x];
    e[cnt].to=y;hd[x]=cnt;
    e[cnt].val=z;
}
void prepare(){
    is[0]=is[1]=1;
    for(int i=2;i<MAXN;i++){
        if(!is[i]) pri[++tot]=i;
        for(int j=1;j<=tot&&i*pri[j]<=MAXN;j++){
            is[pri[j]*i]=1;
            if(i%pri[j]==0) break;
        }
    }
}
namespace Network_Flow{
    queue<int> p;
    int dep[N<<1];
    int bfs(){
        memset(dep,0,sizeof(dep));
        p.push(S);dep[S]=1;
        while(!p.empty()){
            int x=p.front();p.pop();
            for(int i=hd[x];i;i=e[i].nxt){
                int y=e[i].to,v=e[i].val;
                if(!dep[y]&&v){
                    dep[y]=dep[x]+1;
                    p.push(y);
                }
            }
        }
        if(dep[T]) return 1;
        return 0;
    }
    int dfs(int x,int flow){
        if(x==T||flow<=0) return flow;
        int rest=0;
        for(int i=hd[x];i;i=e[i].nxt){
            int j=e[i].to;int v=e[i].val;
            if(dep[j]==dep[x]+1&&v){
                int now=dfs(j,min(v,flow));
                e[i].val-=now;
                e[i^1].val+=now;
                flow-=now;rest+=now;
                if(flow<=0) break;
            }
        }if(!rest) dep[x]=-1;
        return rest;
    }
    int dinic(){
        int maxflow=0;
        while(bfs()) maxflow+=dfs(S,inf);
        return maxflow;
    }
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
signed main(){
    freopen("oatmeal.in","r",stdin);
    freopen("oatmeal.out","w",stdout);
    prepare();n=read();
    for(int i=1;i<=n;i++){
        int x=read();
        a[x]=1,mx=max(mx,x);
    }
    for(int i=1;i<=mx+1;i++)
        if(a[i]!=a[i-1]) i&1?L[++t1]=i:R[++t2]=i;
    S=0,T=t1+t2+1;
    for(int i=1;i<=t1;i++)
        ins(S,i,1),ins(i,S,0);
    for(int i=1;i<=t2;i++)
        ins(i+t1,T,1),ins(T,i+t1,0);
    for(int i=1;i<=t1;i++)
        for(int j=1;j<=t2;j++)
            if(!is[abs(L[i]-R[j])])
                ins(i,j+t1,1),ins(j+t1,i,0);
    int Val=Network_Flow::dinic();
    ans+=Val;ans+=(t1-Val)/2*2+(t2-Val)/2*2;
    ans+=((t1-Val)&1)*3;printf("%d\n",ans);
    return 0;
}

2019.10.9 noip多校联测

原文：https://www.cnblogs.com/NLDQY/p/11668544.html