191101CSP模拟题解

T1：给定$n,k,l$，求$n$个数每个取值$[0,l]$，其一个子序列和为$k$的方案数，$n,k\le 20$ 补集转化，是个背包，然后状压算方案，dp of dp

Code：

#include<bits/stdc++.h> #define ll long long #define mod 998244353 using namespace std; inline int read(){ int res=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();} while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();} return res*f; } inline int add(int x,int y){x+=y;if(x>=mod) x-=mod;return x;} inline int dec(int x,int y){x-=y;if(x<0) x+=mod;return x;} inline int mul(int x,int y){return 1ll*x*y%mod;} inline void Mul(int &x,int y){x=1ll*x*y%mod;} inline void inc(int &x,int y){x+=y;if(x>=mod) x-=mod;} inline int ksm(int a,int b){int res=1;for(;b;b>>=1,Mul(a,a)) if(b&1) Mul(res,a);return res;} const int N=21,M=(1<<20); int n,k,l,S,lim; int f[N][M]; inline void file(){freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);} int main(){ n=read(),k=read(),l=read(); S=(1<<k)-1,lim=min(k-1,l); f[0][1]=1; for(int i=1;i<=n;i++) for(int s=0;s<=S;s++) if(f[i-1][s]){ for(int j=0;j<=lim;j++) if(!((s<<j)&(1<<k))) inc(f[i][((s<<j)|s)&S],f[i-1][s]); if(l>k) inc(f[i][s],mul(f[i-1][s],(l-k)%mod)); } int res=0; for(int s=0;s<=S;s++) inc(res,f[n][s]); cout<<dec(ksm(add(l,1),n),res); return 0; }

T2：给定一棵树，每个点有一个值，定义一个点的权值为子树的值之和，求对于每一个点，它能到达的，路径上既有权值比他大又有比他小的点的权值的或和，$\sum a_i\le 1e6，n\le 4e5$ 显然是走子树外，然后一定有一个权值比它大的，那么就是询问子树外权值比它小的点的或和，dfs序拆成一个前缀和一个后缀用主席树维护即可

Code：

#include<bits/stdc++.h> #define mp make_pair #define pii pair<int,int> #define ll long long #define pli pair<ll,int> #define fi first #define se second using namespace std; inline int read(){ int res=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();} while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();} return res*f; } char xx; const int N=1e6+5,M=4e5+5; struct President_tree{ struct seg{int l,r,sum;}tr[(N<<2)+M*40]; int cnt; #define ls(k) tr[k].l #define rs(k) tr[k].r #define mid (l+r>>1) void build(int &rt,int l,int r){ rt=++cnt; tr[rt].sum=0; if(l==r) return; build(ls(rt),l,mid);build(rs(rt),mid+1,r); } void ins(int &rt1,int rt2,int l,int r,int pos,int x){ tr[rt1=++cnt]=tr[rt2];tr[rt1].sum|=x; if(l==r) return; if(pos<=mid) ins(ls(rt1),ls(rt2),l,mid,pos,x); else ins(rs(rt1),rs(rt2),mid+1,r,pos,x); } int query(int rt1,int l,int r,int ql,int qr){ if(ql>r || qr<l) return 0; if(ql<=l && r<=qr) return tr[rt1].sum; if(qr<=mid) return query(ls(rt1),l,mid,ql,qr); else if(ql>mid) return query(rs(rt1),mid+1,r,ql,qr); else return query(ls(rt1),l,mid,ql,mid)|query(rs(rt1),mid+1,r,mid+1,qr); } }T[2]; int vis[M<<1],head[M],nxt[M<<1],tot=0; inline void add(int x,int y){vis[++tot]=y;nxt[tot]=head[x];head[x]=tot;} int dfn[M],sign=0,id[N]; int f[M]; int siz[M]; void dfs(int v,int fa){ siz[v]=1;dfn[v]=++sign;id[sign]=v; for(int i=head[v];i;i=nxt[i]){ int y=vis[i]; if(y==fa) continue; dfs(y,v); f[v]+=f[y];siz[v]+=siz[y]; } } int R; int rt[M][2]; char yy; inline void file(){freopen("forever.in","r",stdin);freopen("forever.out","w",stdout);} int main(){ file(); T[0].cnt=T[1].cnt=0; int n=read();R=read(); for(int x,y,i=1;i<n;i++){ x=read(),y=read(); add(x,y);add(y,x); } for(int i=1;i<=n;i++) f[i]=read(); dfs(R,0); int mx=f[R]; T[0].build(rt[0][0],1,mx);T[1].build(rt[n+1][1],1,mx); for(int i=1;i<=n;i++) T[0].ins(rt[i][0],rt[i-1][0],1,mx,f[id[i]],f[id[i]]); for(int i=n;i;i--) T[1].ins(rt[i][1],rt[i+1][1],1,mx,f[id[i]],f[id[i]]); for(int i=1;i<=n;i++){ int res=0; res|=T[0].query(rt[dfn[i]-1][0],1,mx,1,f[i]-1); res|=T[1].query(rt[dfn[i]+siz[i]][1],1,mx,1,f[i]-1); cout<<res<<" "; } return 0; }

T3：BZOJ建设游乐场 想起建图方法的时候只有10min了，就是TC SRM 500多的一道题，一毛一样

#include<bits/stdc++.h> using namespace std; inline int read(){ int res=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();} while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();} return res*f; } const int N=2e5,INF=1e9; const int NN=1000; int vis[N],nxt[N],head[N],c[N],e[N],tot=1; inline void add(int x,int y,int z,int w){ vis[++tot]=y;nxt[tot]=head[x];head[x]=tot;c[tot]=z;e[tot]=w; vis[++tot]=x;nxt[tot]=head[y];head[y]=tot;c[tot]=0;e[tot]=-w; } int d[N],pt[N]; int S,T; inline bool spfa(){ memset(d,0x3f,sizeof(d)); queue<int>q; q.push(S);d[S]=0; while(!q.empty()){ int x=q.front();q.pop();pt[x]=0; for(int i=head[x];i;i=nxt[i]){ int y=vis[i]; if(d[y]>d[x]+e[i] && c[i]){ d[y]=d[x]+e[i]; if(!pt[y]) pt[y]=1,q.push(y); } } } return d[T]<INF; } int cur[N]; int mncost,mxflow; int dfs(int v,int flow){ if(v==T) {mxflow+=flow;return flow;} int res=0,k;pt[v]=1; for(int i=cur[v];i;i=nxt[i]){ int y=vis[i]; if(c[i] && !pt[y] && d[y]==d[v]+e[i]){ cur[v]=i; k=dfs(y,min(flow-res,c[i])); c[i]-=k;c[i^1]+=k;res+=k;mncost+=k*e[i]; if(res==flow) break; } } pt[v]=0;return res; } inline void mcmf(){mxflow=mncost=0;while(spfa()){memcpy(cur,head,sizeof(cur));dfs(S,INF);}} int n,m; int id1[NN][NN],id2[NN][NN],tt=0; int val[NN][NN]; int SS=0; char s[NN][NN]; int main(){ n=read();m=read(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int pt=read(); if(pt==0) s[i-1][j-1]='c'; else s[i-1][j-1]='w'; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) val[i][j]=read(); S=0;int sum=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(s[i-1][j-1]!='w'){ id1[i][j]=++tt;id2[i][j]=++tt; ++sum; } T=++tt; int flag=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(s[i-1][j-1]!='w'){ SS+=val[i][j]; if((i^j)&1){ ++flag; add(id1[i][j],T,1,0); add(id2[i][j],T,1,0); } else{ --flag; add(S,id1[i][j],1,0); add(S,id2[i][j],1,0); if(i>1 && s[i-2][j-1]!='w') add(id1[i][j],id2[i-1][j],1,0); if(i<n && s[i][j-1]!='w') add(id1[i][j],id2[i+1][j],1,0); if(j>1 && s[i-1][j-2]!='w') add(id2[i][j],id1[i][j-1],1,0); if(j<m && s[i-1][j]!='w') add(id2[i][j],id1[i][j+1],1,0); } add(id1[i][j],id2[i][j],1,val[i][j]); add(id2[i][j],id1[i][j],1,val[i][j]); } if(flag){cout<<"-1";return 0;} mcmf(); if(mxflow!=sum) {cout<<"-1";return 0;} cout<<SS-mncost; return 0; }