csp-s模拟测试53u，v，w题解

概述题面：https://www.cnblogs.com/Juve/articles/11602450.html u： 用差分优化修改 二维差分：给(x1,y1)，(x2,y2)加上s： $d[x1][y1]+=s,d[x1][y2+1]-=s,d[x2+1][y1]-=s,d[x2+1][y2+1]+=s$ 定义2个差分数组d1，d2，分别记录竖列和斜边的差分 $d1[r][c]+=s,d1[r+l

题面：https://www.cnblogs.com/Juve/articles/11602450.html

u：

用差分优化修改

二维差分：给(x1,y1)，(x2,y2)加上s：

$d[x1][y1]+=s,d[x1][y2+1]-=s,d[x2+1][y1]-=s,d[x2+1][y2+1]+=s$

定义2个差分数组d1，d2，分别记录竖列和斜边的差分

$d1[r][c]+=s,d1[r+l-1][c]-=s,d2[r][c+1]-=s,d2[r+l-1][c+l-1]+=s$

统计是求2个前缀和

 

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#define int long longusing namespace std;const int MAXN=1e3+5;int n,q,a[MAXN][MAXN],b[MAXN][MAXN],c[MAXN][MAXN],d[MAXN][MAXN],ans=0;int d1[MAXN][MAXN],d2[MAXN][MAXN];signed main(){	scanf("%lld%lld",&n,&q);	while(q--){		int r,c,l,s;		scanf("%lld%lld%lld%lld",&r,&c,&l,&s);		int N=min(n,r+l-1),M=min(n,c+l-1);		d1[r][c]+=s,d1[N+1][c]-=s;		d2[r][c+1]-=s,d2[N+1][M+2]+=s;	}	for(int i=1;i<=n;++i){		for(int j=1;j<=n;++j){			a[i][j]=(a[i-1][j]+d1[i][j]);			b[i][j]=(b[i-1][j-1]+d2[i][j]);			c[i][j]=a[i][j]+b[i][j];			d[i][j]=d[i][j-1]+c[i][j];		}	}	for(int i=1;i<=n;++i){		for(int j=1;j<=n;++j)			ans^=d[i][j];	}	printf("%lld\n",ans);	return 0;}

 

v：

 

搜索每一个情况，对于重复的用map记忆化一下

注意判断长度为奇数的情况，map超时可以用hash表

 

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define re registerusing namespace std;int n,k,sta=0;char ch[35];struct hash_map{	int pre[40000000],cnt;	struct node{		int nxt,to,w;		double v;	}e[6000000];	double &operator[](int sta){		int key=1LL*sta%30000019;		for(int i=pre[key];i;i=e[i].nxt)			if(e[i].to==sta) return e[i].v;		e[++cnt].nxt=pre[key];e[cnt].to=sta;;e[cnt].v=-1.0;		pre[key]=cnt;		return e[cnt].v;	}}mp;inline double dfs(re int x,re int st){	if(x==n-k) return 0.0;	if(mp[st]!=-1) return mp[st];	mp[st]=0;	re double sum=0.0;	for(re int i=1;i<=x>>1;i++){        re int con1=st>>i-1&1,con2=st>>x-i&1;        re int to1=st>>1&~((1<<i-1)-1)|st&(1<<i-1)-1;        re int to2=st>>1&~((1<<x-i)-1)|st&((1<<x-i)-1);        sum+=2.0*max(dfs(x-1,to1)+con1,dfs(x-1,to2)+con2)/x;    }    if(x&1){        re int i=x+1>>1;        re int to=st>>1&~((1<<i-1)-1)|st&(1<<i-1)-1;        re int con=st>>i-1&1;        sum+=(dfs(x-1,to)+con)/x;    }    return mp[st]=sum;}signed main(){	scanf("%d%d",&k);	scanf("%s",ch+1);	for(re int i=1;i<=n;i++)        sta|=(ch[i]==‘W‘)<<n-i;    sta|=1<<n;	printf("%0.7lf\n",dfs(n,sta));	return 0;}

 

w：

如果我们选出一条边，就给边两端的点度数加一，那么第一个答案就是度数为奇数的点个数除以2

我们定义dp[i][0/1]表示i节点，没有/有向父亲的反转i边的两个答案

接下来我们考虑更新：
在更新时我们使用两个参量：p和q，作为更新dp的中间步骤，用p代表不以i为端点做链，q代表以i为端点做链，设i的某个子节点为to，于是有：
p=min(p+dp[to][0],q+dp[to][1])
q=min(p+dp[to][1],q+dp[to][0])
其中p初始化为（0,0），q初始化为（INF，INF）
解释一下：这里pair的add就是对应元素相加（手写！非内置！）
而min *** 作表示先按pair第一关键字比较，再按第二关键字比较
那么这一步就是一个合并的过程：
首先，i不作为链的端点：分两类来合并：如果子节点与i的边翻转了，那么就要累在以i为端点的链里（因为i与父亲的边不翻转，那么i就将是个端点），如果子节点与i的边没有翻转，那么仅针对这棵子树而言，i并没有作为路径的端点，所以更新没有以i为端点链的代价
如果i作为链的端点，同样分两类来合并：如果子节点与i的边翻转了，那么i显然可以成为链的端点，前提是在此之前i并不是链的端点，所以用之前i不是链的端点的代价来更新；反之，如果子节点与i的边没有翻转，那么就此而言i并不是端点，可要求i是链的一个端点，这样就必须用i原先就是链的端点的代价来更新
遍历根节点所有子节点后，更新dp：
如果i与父亲的边没有翻转。即状态dp[i][0]：
首先，i不作为链的端点肯定是一种可能性，直接比较
接着，如果i是链的一个端点，i和父节点的边还没有翻转，那么说明在这个状态下i是真正的奇度点，所以将状态q的first+1后更新
如果i与父亲的边翻转了，同样分两类更新：
首先，i本身作为了链的端点，而由于i本身就是奇度点，所以仅需将q.second+1来更新即可
还有，如果i本身在下面并没有作为链的端点，而i却与父节点的边发生了翻转，所以i就成为了新的奇度点，同时链长还增加了，所以p.first,p.second均增加即可
最后答案即为dp[1][0].first/2,dp[1][0].second

 

#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<algorithm>using namespace std;const int MAXN=5e5+5;const int inf=0x3f3f3f3f;int n;int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],flag[MAXN<<1],cnt=0;voID add(int u,int v,int val){	++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt,flag[cnt]=val;}struct node{	int tim,len;	frIEnd node operator + (node a,node b){		return (node){a.tim+b.tim,a.len+b.len};	}	frIEnd bool operator < (node a,node b){		return a.tim==b.tim?a.len<b.len:a.tim<b.tim;	}}dp[MAXN][2];node min(node a,node b){	return a<b?a:b;}voID dfs(int x,int fa,int fl){	node p={0,0},q={inf,inf};	for(int i=pre[x];i;i=nxt[i]){		int y=to[i];		if(y==fa) continue;		dfs(y,x,flag[i]);		node a=p,b=q;		p=min(a+dp[y][0],b+dp[y][1]);		q=min(b+dp[y][0],a+dp[y][1]);	}	if(fl==2){		dp[x][0]=min(p,q+(node){1,0});		dp[x][1]=min(p+(node){1,1},q+(node){0,1});	}	if(fl==1){		dp[x][0]=(node){inf,inf};		dp[x][1]=min(p+(node){1,1});	}	if(fl==0){		dp[x][0]=min(p,0});		dp[x][1]=(node){inf,inf};	}}signed main(){	scanf("%d",&n);	for(int i=1,a,b,d;i<n;++i){		scanf("%d%d%d%d",&a,&b,&d);		if(d==2){			add(a,2),add(b,2);		}else{			if(c==d) add(a,0),0);			else add(a,1),1);		}	}	dfs(1,0);	printf("%d %d\n",dp[1][0].tim/2,dp[1][0].len);	return 0;}

总结

以上是内存溢出为你收集整理的csp-s模拟测试53u，v，w题解全部内容，希望文章能够帮你解决csp-s模拟测试53u，v，w题解所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。