[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;
}