[LUOGU] NOIP提高组模拟赛Day1

题外话：以Ingress为题材出的比赛好评，绿军好评

---

T1

考虑枚举第\(i\)个人作为左边必选的一个人，那左边剩余\(i-1\)个人，选法就是\(2^{i-1}\)，也就是可以任意选或不选，右侧剩余\(n-i\)个人，选法就是\(\sum\limits_{j=1}^{n-i}C_{n-i}^j\)，容易发现就是\(2^{n-i}-1\)种选法，于是第i个人的贡献就是\(2^{i-1}\times(2^{n-i}-1)\)，化简式子即可得到答案。

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long ll;

const ll MOD = 1e9+7;

ll qpow(ll x,ll y){

    ll ret=1;

    while(y){

        if(y&1)(ret*=x)%=MOD;

        y>>=1ll;(x*=x)%=MOD;

    }

    return ret;

}

ll n;

int main(){

    cin>>n;

    n--;

    ll ans=(qpow(2ll,n)*(n-1ll))%MOD+1;

    cout<<ans;

    return 0;

}

T2

发现\(T[i]\)就是物品体积，\(C[i]\)就是物品价值，背包大小就是\(D[i]\)

按\(D[i]\)升序枚举每个元素，做背包即可

统计答案？逆序枚举状态即可

#include<algorithm>

#include<iostream>

#include<cstdio>

#include<cctype>

#include<vector>

using namespace std;

inline int rd(){

    int ret=0,f=1;char c;

    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;

    while(isdigit(c))ret=ret*10+c-'0',c=getchar();

    return ret*f;

}

const int MAXN = 2005;

int n;

struct Node{

    int t,d,c,id;

    bool operator<(const Node &rhs)const{

        return d<rhs.d;

    }

}a[MAXN];

int f[MAXN];

bool vis[MAXN][MAXN];

vector<int> vec[MAXN];

int ans=0;

int sta[MAXN],top;

int main(){

    n=rd();

    for(int i=1;i<=n;i++){

        a[i].t = rd();

        a[i].d = rd();

        a[i].c = rd();

        a[i].id = i;

    }

    sort(a+1,a+1+n);

    for(int i=1;i<=n;i++){

        for(int j=a[i].d;j>a[i].t;j--){

            if(f[j]<f[j-a[i].t]+a[i].c){

                f[j]=f[j-a[i].t]+a[i].c;

                vis[i][j]=1;

            }

        }

    }

    int ansid=0;

    for(int i=0;i<=a[n].d;i++){

        if(f[i]>f[ans]) ans=i;

    }

    cout<<f[ans]<<endl;

    for(int i=n;i>=1;i--){

        if(vis[i][ans]){

            sta[++top]=a[i].id;

            ans-=a[i].t;

        }

    }

    cout<<top<<endl;

    while(top) cout<<sta[top--]<<" ";

    return 0;

}

T3

类似一个流量平衡的问题

本着NOIP不考网络流的思想，先写了高斯消元，发现自由元极多，很复杂，就弃坑了

开始想网络流，拆点套路题，S向左侧点连\(A[i]\)的边，右侧点向T连\(B[i]\)的边，点的流量可以流给自己，也可以给别人，分别建向自己的边和向相连的点的边即可

判断有解就看T的入边是否均满流，统计答案就记录点之间的边的流量

#include<iostream>

#include<cstring>

#include<cctype>

#include<cstdio>

#include<queue>

using namespace std;

const int MAXN=100005;

const int INF=1<<30;

int n,m,s,t;

int mxflow;

inline int rd(){

    int ret=0,f=1;char c;

    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;

    while(isdigit(c))ret=ret*10+c-'0',c=getchar();

    return ret*f;

}

struct Edge{

    int next,to,w;

}e[MAXN*10];

int ecnt=1,head[MAXN],cur[MAXN];

inline void adds(int x,int y,int w){

    e[++ecnt].next = head[x];

    e[ecnt].to = y;

    e[ecnt].w = w;

    head[x] = ecnt;

}

inline void add(int x,int y,int w){

    adds(x,y,w);adds(y,x,0);

}

int dis[MAXN];

queue<int> Q;

bool bfs(){

    memset(dis,0,sizeof(dis));

    Q.push(s);dis[s]=1;

    while(!Q.empty()){

        int top=Q.front();Q.pop();

        for(int i=head[top];i;i=e[i].next){

            int v=e[i].to;

            if(dis[v]||!e[i].w) continue;

            Q.push(v);dis[v]=dis[top]+1;

        }

    }

    return dis[t];

}

int dfs(int x,int val){

    if(x==t) return val;

    int used=0,tmp;

    for(int i=cur[x];i;i=e[i].next){

        int v=e[i].to;

        if(dis[v]!=dis[x]+1) continue;//

        tmp=dfs(v,min(val-used,e[i].w));

        used+=tmp;

        e[i].w-=tmp;

        e[i^1].w+=tmp;

        if(e[i].w) cur[x]=i;

        if(val==used) return val;

    }

    if(!used) dis[x]=0;

    return used;

}

void dinic(){

    while(bfs()){

        memcpy(cur,head,sizeof(head));

        mxflow+=dfs(s,INF);

    }

}

int A[MAXN],B[MAXN];

int ans[256][256];

int main(){

    //magic spj :)

    n=rd();m=rd();

    s=n*2+1,t=s+1;

    int x,y,w;

    for(int i=1;i<=n;i++)A[i]=rd();

    for(int i=1;i<=n;i++)B[i]=rd();

    for(int i=1;i<=n;i++){

    	add(s,i,A[i]);

        add(i+n,t,B[i]);

        add(i,i+n,INF);

    }

    for(int i=1;i<=m;i++){

    	int x,y;

        x=rd();y=rd();

        add(x,y+n,INF);

        add(y,x+n,INF);

    }

    dinic();

    for(int i=n+1;i<=n+n;i++){

    	for(int j=head[i];j;j=e[j].next){

            int v=e[j].to;

            if(v!=t) continue;

            if(e[j].w) return puts("NO"),0;

        }

    }

    puts("YES");

    for(int i=1;i<=n;i++){

    	for(int j=head[i];j;j=e[j].next){

            int v=e[j].to;

            if(v==s) continue;

            ans[i][v-n]+=e[j^1].w;

        }

    }

    for(int i=1;i<=n;i++){

    	for(int j=1;j<=n;j++){

    		printf("%d",ans[i][j]);

    		if(j!=n)putchar(' ');

    	}

    	if(i!=n)putchar('\n');

    }

    return 0;

}

[LUOGU] NOIP提高组模拟赛Day1的相关教程结束。