【CSP-S 2019模拟】题解

T1：

相当于是一个$dpofdp$，第二维背包只用存前$k$项即可

看起来像$2^{k}nk$的 但实际上有用状态很少

#include<bits/stdc++.h> using namespace std; #define re register #define pb push_back #define cs const #define ll long long #define pii pair<int,int> #define fi first #define se second cs int RLEN=1<<20|1; inline char gc(){ static char ibuf[RLEN],*ib,*ob; (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0,f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;} template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;} cs int mod=998244353; inline int add(int a,int b){a+=b-mod;return a+(a>>31&mod);} inline int dec(int a,int b){a-=b;return a+(a>>31&mod);} inline int mul(int a,int b){static ll r;r=1ll*a*b;return r>=mod?r%mod:r;} inline void Add(int &a,int b){a+=b-mod,a+=a>>31&mod;} inline void Dec(int &a,int b){a-=b,a+=a>>31&mod;} inline void Mul(int &a,int b){static ll r;r=1ll*a*b;a=(r>=mod?r%mod:r);} inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1);return res;} inline int Inv(int x){return ksm(x,mod-2);} cs int N=21,M=(1<<20)+5; int n,k,l,sta,lim; int f[N][M]; int main(){ n=read(),k=read(),l=read(); sta=(1<<k)-1,lim=min(k-1,l); f[0][1]=1; for(int i=1;i<=n;i++){ for(int s=0;s<=sta;s++)if(f[i-1][s]){ for(int j=0;j<=lim;j++)if(!((s<<j)&(1<<k))){ Add(f[i][((s<<j)|s)&sta],f[i-1][s]); } if(l>k){ Add(f[i][s],mul(f[i-1][s],(l-k)%mod)); } } } int res=0; for(int s=0;s<=sta;s++)Add(res,f[n][s]); cout<<dec(ksm(add(l,1),n),res); }

T2：

把权值排序后一个一个加，询问子树补集即可

结果脑抽给自己多套了一个$log$

#include<bits/stdc++.h> using namespace std; #define re register #define pb push_back #define cs const #define ll long long #define pii pair<int,int> #define fi first #define se second cs int RLEN=1<<20|1; inline char gc(){ static char ibuf[RLEN],*ib,*ob; (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0,f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } cs int N=500005; char xxx; int dfn,siz[N],son[N],fa[N],top[N],dep[N],in[N],out[N],idx[N]; vector<int> e[N]; int n,rt,val[N],a[N],s[N]; void dfs1(int u){ siz[u]=1; for(int i=0,v;i<e[u].size();i++){ v=e[u][i]; if(v==fa[u])continue; fa[v]=u,dep[v]=dep[u]+1; dfs1(v),siz[u]+=siz[v]; if(siz[v]>siz[son[u]])son[u]=v; } } void dfs2(int u,int tp){ in[u]=++dfn,idx[dfn]=u,top[u]=tp; if(son[u])dfs2(son[u],tp); for(int i=0,v;i<e[u].size();i++){ v=e[u][i]; if(v==fa[u]||v==son[u])continue; dfs2(v,v); } out[u]=dfn; } pii divi[N]; int tot,ans[N]; vector<int>nod[5000005]; namespace Seg{ int s[N<<2]; #define lc (u<<1) #define rc ((u<<1)|1) #define mid ((l+r)>>1) inline void pushup(int u){ s[u]=s[lc]|s[rc]; } void update(int u,int l,int r,int p,int k){ if(l==r){s[u]=k;return;} if(p<=mid)update(lc,l,mid,p,k); else update(rc,mid+1,r,p,k); pushup(u); } int query(int u,int l,int r,int st,int des){ if(st>des)return 0; if(st<=l&&r<=des)return s[u]; int res=0; if(st<=mid)res|=query(lc,l,mid,st,des); if(mid<des)res|=query(rc,mid+1,r,st,des); return res; } } char yyy; int main(){ int size=40<<20;//40M //__asm__ ("movl %0, %%esp\n"::"r"((char*)malloc(size)+size));//调试用这个 __asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));//提交用这个 n=read(),rt=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); e[u].pb(v),e[v].pb(u); } for(int i=1;i<=n;i++)a[i]=read(); dfs1(rt),dfs2(rt,rt); for(int i=1;i<=n;i++)s[i]=s[i-1]+a[idx[i]]; for(int i=1;i<=n;i++)val[i]=s[out[i]]-s[in[i]-1],assert(val[i]!=0); for(int i=1;i<=n;i++)nod[val[i]].pb(i); for(int i=1;i<=s[n];i++)if(nod[i].size()){ for(int j=0;j<nod[i].size();j++){ int u=nod[i][j],res=0; if(in[u]>1)res|=Seg::query(1,1,n,1,in[u]-1); if(out[u]<n)res|=Seg::query(1,1,n,out[u]+1,n); ans[u]=res; } for(int j=0;j<nod[i].size();j++){ int u=nod[i][j]; Seg::update(1,1,n,in[u],val[u]); } } for(int i=1;i<=n;i++)cout<<ans[i]<<" ";exit(0);//必须用exit }

T3：

写$50$~$?$的轮廓线写挂没调出来

建图还是挺妙的

考虑把方向相同的时候看做减少了$val$，那就是让直的最少

先把整个图黑白染色 于是相邻连边可以看做都是从黑点流到白点 那么显然的一个条件就是最后黑白点数量要相同 于是起点$\to u(cap=2,val=0)$ 每个点再建两个方向点，分别表示像上下，左右 $u$向方向点连$cap=1,val=0$的边 方向点之间互相连$cap=1,val=Val$的边 这样如果方向相同的话就会产生$val$的代价 方向点再向对于的白点连边 白点类似的连向终点就可以跑最小费用最大流了

#include<bits/stdc++.h> using namespace std; #define re register #define pb push_back #define cs const #define ll long long #define pii pair<int,int> #define fi first #define se second #define bg begin cs int RLEN=1<<20|1; inline char gc(){ static char ibuf[RLEN],*ib,*ob; (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0,f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;} template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;} cs int N=50005,inf=1e9; int str,des,tot; namespace Flow{ struct edge{ int v,cap,val,r; edge(int a=0,int b=0,int c=0,int d=0):v(a),cap(b),val(c),r(d){} }; vector<edge> e[N]; typedef vector<edge>::iterator It; It tp[N]; inline void add(int u,int v,int w,int c){ e[u].pb(edge(v,w,c,e[v].size())); e[v].pb(edge(u,0,-c,e[u].size()-1)); } int mxflow,mncost; int dis[N],vis[N]; int q[500005],hd,tl; inline bool spfa(){ memset(dis,127/3,sizeof(int)*(tot+1)); dis[str]=0;q[hd=tl=1]=str; while(hd<=tl){ int u=q[hd++];vis[u]=0; for(edge &x:e[u]){ if(dis[x.v]>dis[u]+x.val&&x.cap>0){ dis[x.v]=dis[u]+x.val; if(!vis[x.v]){ vis[x.v]=1; if(dis[x.v]<dis[q[hd]])q[--hd]=x.v; else q[++tl]=x.v; } } } } return dis[des]<dis[0]; } int dfs(int u,int flow){ if(u==des)return flow; vis[u]=1;int res=0; for(It &it=tp[u];it!=e[u].end();it++){ if(!vis[it->v]&&dis[it->v]==dis[u]+it->val&&it->cap>0){ int now=dfs(it->v,min(it->cap,flow-res)); res+=now,it->cap-=now,e[it->v][it->r].cap+=now,mncost+=now*it->val; if(res==flow)break; } } vis[u]=0; return res; } inline void mcmf(){ while(spfa()){ for(int i=1;i<=tot;i++)tp[i]=e[i].bg(); mxflow+=dfs(str,inf); } } } int n,m,cnt,num,all; int a[155][55],val[155][55],pos[155][55][3]; inline bool ok(int x,int y){ return !a[x][y]&&(1<=x&&x<=n&&1<=y&&y<=m); } int main(){ #ifdef Stargazer freopen("lx.cpp","r",stdin); #endif n=read(),m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) val[i][j]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)if(!a[i][j])pos[i][j][0]=++tot,pos[i][j][1]=++tot,pos[i][j][2]=++tot,all+=val[i][j]; str=++tot,des=++tot; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!a[i][j]){ if((i+j)&1){ num+=2,cnt++; Flow::add(str,pos[i][j][0],2,0),Flow::add(pos[i][j][0],pos[i][j][1],1,0),Flow::add(pos[i][j][0],pos[i][j][2],1,0); Flow::add(pos[i][j][1],pos[i][j][2],1,val[i][j]),Flow::add(pos[i][j][2],pos[i][j][1],1,val[i][j]); if(ok(i-1,j))Flow::add(pos[i][j][1],pos[i-1][j][1],1,0); if(ok(i+1,j))Flow::add(pos[i][j][1],pos[i+1][j][1],1,0); if(ok(i,j-1))Flow::add(pos[i][j][2],pos[i][j-1][2],1,0); if(ok(i,j+1))Flow::add(pos[i][j][2],pos[i][j+1][2],1,0); } else{ cnt--; Flow::add(pos[i][j][0],des,2,0),Flow::add(pos[i][j][1],pos[i][j][0],1,0),Flow::add(pos[i][j][2],pos[i][j][0],1,0); Flow::add(pos[i][j][1],pos[i][j][2],1,val[i][j]),Flow::add(pos[i][j][2],pos[i][j][1],1,val[i][j]); } } if(cnt)return puts("-1"),0; Flow::mcmf(); if(Flow::mxflow<num)return puts("-1"),0; cout<<all-Flow::mncost<<'\n'; }