17-06-28模拟赛

T1:考虑求出所有的环。若该环中点的个数为n,则拆环的方法为为C(1,n)+C(2,n)+...+C(n-1,n)=2ⁿ-2种。（全翻转及全不翻转都是环）。

再求出非环节点的个数m，则方法有2^m种。（可以发现每个连通块中中必有环，所以可以都不翻转）根据乘法原理，将所有环的方案数及非环节点的方案数相乘即可。

注意要用到快速幂。

Note:注意到每个连通块中有且仅有一个环，进行一次dfs即可。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 1000000007
#define MN 200005
#define ll long long
using namespace std;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
struct edge{
    int to,next;
}e[MN+5],r[MN+5];
int head[MN],rhed[MN],num[MN],ct[MN];
int cnt=0,rct=0,tmp,n,a,pos,sum;
ll res=1ll,rn;
bool vis[MN];
inline void ins(int x,int y){
    ++cnt;e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt;
    ++rct;r[rct].to=x;r[rct].next=rhed[y];rhed[y]=rct;
}
inline ll qpow(int x){
    ll ans=1ll,mul=2ll;
    while (x){
        if (x&1) ans=(ans*mul)%mod;
        mul=(mul*mul)%mod;x>>=1;
    }return ans;
}
void dfs(int x){
    vis[x]=1;
    for (int i=head[x];i;i=e[i].next){
        int v=e[i].to;
        if (!vis[v]) dfs(v);
    }num[++tmp]=x;
}
void rdfs(int x,int k){
    vis[x]=1;++ct[k];
    for (int i=rhed[x];i;i=r[i].next){
        int v=r[i].to;
        if (!vis[v]) rdfs(v,k);
    }
}
int main()
{
    n=in();for (int i=1;i<=n;++i) a=in(),ins(i,a);memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;++i) if (!vis[i]) dfs(i);memset(vis,0,sizeof(vis));
    for (int i=n;i;--i) if (!vis[num[i]]) rdfs(num[i],++pos);
    for (int i=1;i<=pos;++i){
        if (ct[i]<=1) continue;
        sum+=ct[i];rn=1ll*(qpow(ct[i])-2+mod)%mod;
        res=1ll*(res*rn)%mod;
    }if (!sum) printf("%lld
",1ll*(qpow(n)-1+mod)%mod);
    else {
        rn=1ll*qpow(n-sum)%mod;res=1ll*(res*rn)%mod;
        printf("%lld
",res);
    }return 0;
}

 T2:经过推理可知，若经过操作能够使负数的个数为奇数，则应尽可能使乘积的绝对值大，即每次将绝对值最小的数的绝对值+x.

否则使乘积的最小值尽可能小，即每次将绝对值最小的数的绝对值-x.

若开始时负数的个数为奇数，则每次将绝对值最小的数的绝对值+x.

否则考虑能否使负数的个数为奇数，若能，则通过操作将绝对值最小的数变号，再每次将绝对值最小的数的绝对值+x.

若不能，则每次将绝对值最小的数的绝对值-x.

注意对0的特殊处理。绝对值最小的数用堆维护。

Code:

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
typedef pair <int,int> P;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
inline int abs(int x){return x>0?x:-x;}
int a[200005],nega,posi,n,k,x,pmn,nmx,npos,ppos;
priority_queue<P,vector<P>,greater<P> >q;
int main()
{
    n=in();k=in();x=in();pmn=inf;nmx=-inf;
    for (int i=1;i<=n;++i){
        a[i]=in();q.push(make_pair(abs(a[i]),i));
        if (a[i]<0) {++nega;if (a[i]>nmx) nmx=a[i],npos=i;}
        if (a[i]>0) {++posi;if (a[i]<pmn) pmn=a[i],ppos=i;}
        if (!a[i]&&nmx&&pmn) nmx=pmn=0,npos=ppos=i;
    }
    if (nega&1){
        for (int i=1;i<=k;++i){
            int t=q.top().first,tpos=q.top().second;q.pop();
            if (a[tpos]>=0) a[tpos]+=x;else a[tpos]-=x;
            q.push(make_pair(t+x,tpos));
        }
    }else{
        int d,dpos;
        if (abs(nmx)<pmn) d=abs(nmx),dpos=npos;else d=abs(pmn),dpos=ppos;
        if (1ll*d<1ll*x*k){
            k-=(d/x+1);q.pop();
            if (a[dpos]>=0) a[dpos]-=(d/x+1)*x;
            else a[dpos]+=(d/x+1)*x;
            q.push(make_pair(abs(a[dpos]),dpos));
            for (int i=1;i<=k;++i){
                int t=q.top().first,tpos=q.top().second;q.pop();
                if (a[tpos]>=0) a[tpos]+=x;else a[tpos]-=x;
                q.push(make_pair(t+x,tpos));
            }
        }else {
            for (int i=1;i<=k;++i){
                int t=q.top().first,tpos=q.top().second;q.pop();
                if (a[tpos]>=0) a[tpos]-=x;else a[tpos]+=x;
                q.push(make_pair(t-x,tpos));
            }
        }
    }for (int i=1;i<=n;++i) printf("%d ",a[i]);return 0;
}

T3:

注意到将路变为墙时不会将一个区域分割，也不会将一个只有一格的区域填满，可以发现每块区域都不会被分割或消失，考虑用带权并查集维护一块区域可到达点的个数。

对于初始状态，dfs求出连通块及其点数。

对于查询操作，找到所有点所属连通块的父连通块的点数最大值即可。

对于修墙操作，将该节点所属连通块的父连通块点数减一，并将该节点所属连通块数修改为0.

对于修路操作，将该路设为新连通块，若与该路相连节点为路，则合并该路所属父连通块与该路相连节点所属父连通块。

注意合并时将其中一连通块的权值设为0。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 1000005
using namespace std;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
char mp[MN];
int fa[MN<<1],siz[MN<<1],num[MN];
int n,m,x,y,q,cnt=0,tp,w;
inline int gf(int x){return fa[x]?fa[x]=gf(fa[x]):x;}
inline void dfs(int x,int y,int ct){
    if (mp[x*m+y]!='.'||num[x*m+y]) return;
    num[x*m+y]=ct;++siz[num[x*m+y]];
    if (x) dfs(x-1,y,ct);if (y) dfs(x,y-1,ct);
    if (x+1<n) dfs(x+1,y,ct);if (y+1<m) dfs(x,y+1,ct);
}
inline void uni(int x,int y,int p,int q){
    int f1=gf(num[x*m+y]),f2=gf(num[p*m+q]);
    if (mp[p*m+q]!='.'||f1==f2) return;
    siz[f2]+=siz[f1];siz[f1]=0;fa[f1]=f2;
}

int main()
{
    n=in();m=in();memset(fa,0,sizeof(fa));
    for (int i=0;i<n;++i) scanf("%s",mp+i*m);
    for (int i=0;i<n;++i)
    for (int j=0;j<m;++j)
    if (mp[i*m+j]=='.'&&!num[i*m+j]) dfs(i,j,++cnt);q=in();
    for (int i=1;i<=q;++i){
        tp=in();w=in();
        if (tp==1){
            int mx=0,pos=1;
            for (int j=1;j<=w;++j){
                x=in()-1;y=in()-1;
                if (mp[x*m+y]=='.'&&siz[gf(num[x*m+y])]>mx) mx=siz[gf(num[x*m+y])],pos=j;
            }printf("%d
",pos);
        }else for (int j=1;j<=w;++j){
            x=in()-1;y=in()-1;
            if (mp[x*m+y]=='.'){
                --siz[gf(num[x*m+y])];
                mp[x*m+y]='*';num[x*m+y]=0;
            }else{
                num[x*m+y]=++cnt;++siz[num[x*m+y]];mp[x*m+y]='.';
                if (x) uni(x,y,x-1,y);if (y) uni(x,y,x,y-1);
                if (x+1<n) uni(x,y,x+1,y);if (y+1<m) uni(x,y,x,y+1);
            }
        }
    }return 0;
}