BUPT2017 wintertraining(15) #3 题解---饶文津

A - 温泉旅店

UESTC - 878 

题意

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

题解：

​

#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("%dn",ans); return 0; }B - Ikki's Story I - Road Reconstruction

POJ - 3204 

题意

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

题解解法1.

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

解法2.

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

//解法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("%dn",num); } return 0; }//解法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("%dn",ans); return 0; }C - Seeing People

HDU - 4938 

题意

题解

#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("%dn",(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

题意

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

题解

匈牙利算法。

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

#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("%dn",solve()); } return 0; }E - Eleven

UVALive - 6529

题意

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

题解

#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("%lldn",dp[9][0][0]); } return 0; }F - Crossed Matchings

POJ - 1692 

#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("%dn",ans); } return 0; }G - Slim Span

POJ - 3522

题意

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

题解

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

#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("%dn",ans); else puts("-1"); } return 0; }H - E. Wet Shark and Blocks

CodeForces - 621E 

题意

题解

#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; } ---来自腾讯云社区的---饶文津