前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >BUPT2017 wintertraining(15) #3 题解

BUPT2017 wintertraining(15) #3 题解

作者头像
饶文津
发布2020-06-02 12:16:35
4050
发布2020-06-02 12:16:35
举报
文章被收录于专栏:饶文津的专栏

A - 温泉旅店

UESTC - 878 

题意

​ 有n张牌,两人都可以从中拿出任意张,各自的得分为他们手中牌上的数字的异或和。求A的得分小于等于B的方案数。

题解:

代码语言:javascript
复制
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 65537
int n,a[N],ans,dp[17][1<<8][1<<8]={1};
using namespace std;
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	for(int j=0;j<=(1<<7);j++)
	for(int k=0;k<=(1<<7);k++){
		dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j^a[i]][k]+dp[i-1][j][k^a[i]];
		if(i==n&&k<=j)ans+=dp[i][j][k];
	}
	printf("%d\n",ans);
	return 0;
}

B - Ikki's Story I - Road Reconstruction

POJ - 3204 

题意

在给定的网络流中找出有多少条弧,扩大它的容量(只扩大它)后可以使最大流增大。

题解
解法1.

我比较暴力:先算一遍最大流,然后枚举每条残流为0的边,容量加一,如果跑一边最大流不为0则ans++;

解法2.

更快的算法是,在残流网络上分别从起点和终点进行dfs,经过的点打上标记,ans就是两头都打了标记的边的数量。

代码语言:javascript
复制
//解法1
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#define N 1005
#define M 10005
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
struct edge{
	int to,next,w;
}e[M],e2[M];
int head[N],g[N],cnt;
int d[N],ans,tans;
int st,ed;
void add(int u,int v,int w){
	e[cnt]=(edge){v,head[u],w};head[u]=cnt++;
	e[cnt]=(edge){u,head[v],0};head[v]=cnt++;
}
int bfs(){
	memset(d,-1,sizeof d);
	queue<int>q;
	q.push(st);
	d[st]=0;
	while(!q.empty()){
		int i,k=q.front();
		q.pop();
		for(i=head[k];~i;i=e[i].next){
			int v=e[i].to;
			if(e[i].w>0&&d[v]==-1){
				d[v]=d[k]+1;
				q.push(v);
			}
		}
	}
	return d[ed]>0;
}
int dinic(int k,int low){
	if(k==ed||low==0)return low;
	int a,res=0;
	for(int &i=g[k];~i;i=e[i].next){
		int v=e[i].to;
		if(d[v]==d[k]+1&&e[i].w>0&&(a=dinic(v,min(low,e[i].w)))){
			res+=a;
			low-=a;
			e[i].w-=a;
			e[i^1].w+=a;
			if(!low)break;
		}
	}
	return res;
}
void solve(){
	ans=0;
	while(bfs()){
		memcpy(g,head,sizeof g);
		while(tans=dinic(st,inf))ans+=tans;
	}
}
void init(){
	cnt=0;
	memset(head,-1,sizeof head);
}
int main() {
	while(~scanf("%d%d",&n,&m)){
		init();
		for(int i=1,u,v,c;i<=m;i++)scanf("%d%d%d",&u,&v,&c),add(u,v,c);
		st=0,ed=n-1;
		solve();
		int num=0;
		memcpy(e2,e,sizeof e2);
		for(int i=0;i<cnt;i+=2){
			memcpy(e,e2,sizeof e);
			if(!e[i].w){
				e[i].w++;
				solve();
				if(ans)num++;
			}
		}
		printf("%d\n",num);	
	}
	return 0;
}
代码语言:javascript
复制
//解法2
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 505
#define M 10005
#define inf 0x3f3f3f3f
using namespace std;
struct edge{int to,next,w;}e[M];
int head[N],g[N],cnt=1;//cnt从1开始
int st,ed;
int d[N],ans;
int flag[N][2];
void add(int u,int v,int w){
	e[++cnt]=(edge){v,head[u],w};head[u]=cnt;
	e[++cnt]=(edge){u,head[v],0};head[v]=cnt;
}
int bfs(){
	memset(d,-1,sizeof d);
	queue<int>q;
	q.push(st);
	d[st]=0;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		for(int i=head[k];i;i=e[i].next){
			int v=e[i].to;
			if(e[i].w>0&&d[v]==-1){
				d[v]=d[k]+1;
				q.push(v);
			}
		}
	}
	return d[ed]>0;
}
int dinic(int k,int low){
	if(k==ed||low==0)return low;
	int a,res=0;
	for(int &i=g[k];i;i=e[i].next){
		int v=e[i].to;
		if(d[v]==d[k]+1&&e[i].w>0&&(a=dinic(v,min(low,e[i].w)))){
			res+=a;
			low-=a;
			e[i].w-=a;
			e[i^1].w+=a;
			if(!low)break;
		}
	}
	return res;
}
void solve(){
	while(bfs()){
		memcpy(g,head,sizeof g);
		while(dinic(st,inf));
	}
}
void dfs(int x,int c){
	flag[x][c]=1;
	for(int k=head[x];k;k=e[k].next)
		if(!flag[e[k].to][c]&&e[k^c].w)dfs(e[k].to,c);
}
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	st=0,ed=n-1;
	solve();
	dfs(st,0);
	dfs(ed,1);
	for(int i=2;i<=cnt;i+=2)
	if(flag[e[i^1].to][0]&&flag[e[i].to][1])ans++;
	printf("%d\n",ans);
	return 0;
}

C - Seeing People

HDU - 4938 

题意

题解

代码语言:javascript
复制
#include <cstdio>
#include <algorithm>
#define N 100005
#define ll long long
using namespace std;
int t,n,s[2],k[N];
ll v[2],g[2][N],f[N][2];
int main() {
	scanf("%d",&t);
	for(int c=1;c<=t;c++){
		printf("Case #%d:\n",c);
		scanf("%d%lld%lld",&n,v,v+1);
		s[0]=s[1]=0;
		for(int i=0,a;i<n;i++){
			ll t,p,w;
			scanf("%d%lld%lld%lld",&a,&t,&p,&w);a--;
			g[a][s[a]++]=p*v[a]-t*v[0]*v[1];
			k[i]=a;
			f[i][0]=(p-t*v[!a])*v[a];
			f[i][1]=f[i][0]+w*v[a];
		}
		sort(g[0],g[0]+s[0]);
		sort(g[1],g[1]+s[1]);
		for(int i=0;i<n;i++){
			printf("%d\n",(int)(upper_bound(g[!k[i]], g[!k[i]]+s[!k[i]], f[i][1])-lower_bound(g[!k[i]], g[!k[i]]+s[!k[i]], f[i][0])));
		}
	}	
	return 0;
}

D - Attacking rooks

UVALive - 6525

题意

'.'的位置可以放车,两车若要在同一行或者同一列必须中间有'#'。

题解

匈牙利算法。

同一行连续的'.'作为一块,同一列连续的'.'也作为一块。行块和列块对应二分图的点。每个'.'代表有一条边连接了所在行块和列块。求出二分图最大匹配就是答案。

代码语言:javascript
复制
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
const int N=5060;
using namespace std;
char m[105][105];
int a[105][105],b[105][105],cc,cr;
int n,lk[N];//一不小心把lk设置为bool型,无限wa
bool vis[N],g[N][N];
bool find(int u){
	for(int i=1;i<=cr;i++)
	if(g[u][i]&&!vis[i]){
		vis[i]=1;
		if(!lk[i]||find(lk[i])){
			lk[i]=u;
			return 1;
		}
	}
	return 0;
}
int solve(){
	memset(lk,0,sizeof lk);
	int ans=0;
	for(int i=1;i<=cc;i++){
		memset(vis,0,sizeof vis);
		if(find(i))ans++;
	}
	return ans;
}
int main() {
	while(~scanf("%d",&n)){
		memset(g,0,sizeof g);
		cc=cr=0;
		for(int i=0;i<n;i++){
			scanf("%s",m[i]);
			for(int j=0;j<n;j++)if(m[i][j]=='.'){
				if(j==0||m[i][j-1]=='X')
					a[i][j]=++cc;
				else a[i][j]=a[i][j-1];
				if(i==0||m[i-1][j]=='X')
					b[i][j]=++cr;
				else b[i][j]=b[i-1][j];
			}
		}
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(m[i][j]=='.')
		g[a[i][j]][b[i][j]]=1;
		printf("%d\n",solve());
	}
	return 0;
}

E - Eleven

UVALive - 6529

题意

给定一串数字,求所有排列组合里没有前导0的且能被11整除的方案数。

题解

代码语言:javascript
复制
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define ll long long
#define N 105
const int M = 1e9+7;
using namespace std;
char s[N];
ll C[N][N];
ll dp[11][11][N];
int num[11],tot[11];
int main() {
	for(int i=0;i<=N/2;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%M;
	}
	while(~scanf("%s",s)){
		memset(dp,0,sizeof dp);
		memset(num,0,sizeof num);
		int len=strlen(s),half=len/2;
		for(int i=0;s[i];i++)num[s[i]-'0']++;
		tot[0]=num[0];
		for(int i=1;i<10;i++)tot[i]=tot[i-1]+num[i];
		for(int i=0;i<=half&&i<=num[0];i++)
			if(len%2==0)dp[0][0][half-i]=C[half-1][i]*C[half][num[0]-i]%M;
			else dp[0][0][half-i]=C[half][i]*C[half][num[0]-i]%M;
		
		for(int i=1;i<10;i++)//统计数字i的贡献
		for(int remain=0;remain<11;remain++)//之前的余数是remain
		for(int e=0;e<=num[i]&&e<=half;e++)//最多把全部i放在偶数位,偶数位只有half个
		for(int k=e;k<=len-tot[i-1]&&k<=half;k++){//之前剩下的k个偶数位上选e个放i,k不超过剩下的所有位置(len-tot[i-1]),且偶数位只有half个
			int re=(e-(num[i]-e))*i%11;//(放在偶数位-放在奇数位)*i。i贡献的余数
			int j=(remain+re)%11;//新的余数
			j=(j+11)%11;
			dp[i][j][k-e]=(dp[i][j][k-e]+dp[i-1][remain][k]*C[k][e]%M*C[len-k-tot[i-1]][num[i]-e]%M)%M;
			//剩下的奇数位有t个,t=len-k-tot[i-1]
		}
		printf("%lld\n",dp[9][0][0]);
	}
	return 0;
}

F - Crossed Matchings

POJ - 1692 

代码语言:javascript
复制
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 105
using namespace std;
int t,n,m;
int a[N],b[N],dp[N][N];
int main() {
	scanf("%d",&t);	
	while(t--){
		scanf("%d %d",&n,&m);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=m;i++)scanf("%d",&b[i]);
		memset(dp,0,sizeof dp);
		int ans=0;
		for(int i=2;i<=n;i++)
		for(int j=2;j<=m;j++){
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			for(int k=1;k<i;k++)
			for(int l=1;l<j;l++)
			if(a[i]==b[l]&&b[j]==a[k]&&a[i]!=b[j]){
				dp[i][j]=max(dp[i][j],dp[k-1][l-1]+2);
				ans=max(ans,dp[i][j]);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

G - Slim Span

POJ - 3522

题意

求给定图的差值最小的生成树。

题解

差值最小的生成树一定是以某条边为最小的边的最小生成树。枚举每一条边作为最小的边,再用kruskal算法求出最小生成树。

代码语言:javascript
复制
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 105
#define inf 0x3f3f3f3f
using namespace std;
struct edge{int u,v,w;}e[N*N];
int fa[N];
int n,m;
int find(int x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
bool cmp(edge a,edge b){
	return a.w<b.w;
}
int main() {
	while(scanf("%d%d",&n,&m),n){
		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
		sort(e+1,e+1+m,cmp);
		int ans=inf,ok=0;
		for(int i=1;i<=m-n+2;i++){//最小的是e[i]
			for(int i=1;i<=n;i++)fa[i]=i;
			int j,cnt=0;
			for(j=i;j<=m;j++){
				int fu=find(e[j].u),fv=find(e[j].v);
				if(fu!=fv){
					fa[fu]=fv;
					cnt++;
				}
				if(cnt==n-1){
					ok=1;
					ans=min(e[j].w-e[i].w,ans);
					break;
				}
			}
		}
		if(ok)printf("%d\n",ans);
		else puts("-1");
	}	
	return 0;
}

H - E. Wet Shark and Blocks

CodeForces - 621E 

题意

题解

代码语言:javascript
复制
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#define N 50005
#define M 1000000007
#define ll long long
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> Mat;
int n,b,k,x,c[10];
Mat mul(Mat A,Mat B){
	Mat C(A.size(),vec(B[0].size()));
	for(int i=0;i<A.size();i++)
	for(int j=0;j<B[0].size();j++)
	for(int k=0;k<B.size();k++)
		C[i][j]=(C[i][j]+A[i][k]*B[k][j])%M;
	return C;
}
Mat pow(Mat A,int t){
	Mat B(A.size(),vec(A.size()));
	for(int i=0;i<B.size();i++)B[i][i]=1;
	for(;t;t>>=1,A=mul(A,A))if(t&1)B=mul(B,A);
	return B;
}
int main() {
	scanf("%d%d%d%d",&n,&b,&k,&x);
	for(int i=1,a;i<=n;i++) scanf("%d",&a),c[a]++;
	Mat A(x,vec(x)),B(x,vec(1));
	for(int i=0;i<x;i++)
		for(int j=0;j<10;j++) A[(i*10+j)%x][i]+=c[j];
	B[0][0]=1; A=pow(A,b); B=mul(A,B);
	printf("%lld",B[k][0]);
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-02-15 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • A - 温泉旅店
    • 题意
      • 题解:
      • B - Ikki's Story I - Road Reconstruction
        • 题意
          • 题解
          • C - Seeing People
            • 题意
              • 题解
              • D - Attacking rooks
                • 题意
                  • 题解
                  • E - Eleven
                    • 题意
                      • 题解
                      • F - Crossed Matchings
                      • G - Slim Span
                        • 题意
                          • 题解
                          • H - E. Wet Shark and Blocks
                            • 题意
                              • 题解
                              领券
                              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档