【CSP-S 2019模拟】题解

T1：

相当于是一个dp of dpdp of dp，第二维背包只用存前kk项即可

看起来像2knk2^knk的
但实际上有用状态很少

#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：

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

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

#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
"::"r"((char*)malloc(size)+size));//调试用这个 
    __asm__ ("movq %0,%%rsp
"::"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：

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

建图还是挺妙的

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

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

#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<<'
';
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/stargazer-cyk/p/12328379.html