本文主要是介绍男人八题系列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
POJ 1742 Coins
这是一道多重背包的题目，题意大体是给你n中硬币，每种硬币分别有v[i]个。让你求出不超过m能组成的钱数种类。
一开始准备用多重背包写，发现写着写着就复杂了（背包不太会），O(n*m)的算法必然会超时，就想着用数组标记的方法去写了。1282MS，不算长也不算短，等以后更强再去优化吧。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int dp[111111],w[111],v[111],map[111111];
inline void RD(int &ret)//输入优化，后来发现对这题基本上没用
{char c;do{c=getchar();}while(c<'0'||c>'9');ret=c-'0';while((c=getchar())>='0'&&c<='9'){ret=ret*10+(c-'0');}
}
int main()
{int n,m,i,s,j;while(scanf("%d%d",&n,&m)){s=0;if(n==0&&m==0){break;}for(i=1; i<=n; ++i){RD(w[i]);}for(i=1; i<=n; ++i){RD(v[i]);}memset(map,0,sizeof(map));//数组标记map[0]=1;for(i=1; i<=n; ++i){memset(dp,0,sizeof(dp));//清空状态数组for(j=w[i]; j<=m; ++j){if(map[j]==0&&map[j-w[i]]==1&&dp[j-w[i]]<v[i])//状态转移{map[j]=1;dp[j]=dp[j-w[i]]+1;//记录是否存在s++;//记下次数}}}printf("%d\n",s);}return 0;
}POJ1740 A New Stone Game
一道博弈题，题意就是可以选定多个石堆中的一堆，舍弃至少一个石子，然后可以把多个石子分配给其它石堆。然后谁拿走最后一堆获胜。
首先找必败态（1,1）为先手必败，然后往后推。对任意状态，把所有的堆从大到小排序，设为a[1]，a[2]，a[3]……，a[n]>0。
首先确定操作最大的一堆a[1]。把a[2]-a[3]个石子放到第3堆，a[4]-a[5]个石子放到第5堆，等等。
如果n是奇数，直接把剩下的石子扔掉。如果n是偶数，最后第一堆留an个石子，其余扔掉。
当n是奇数，扔掉的石子数为a[1]-(a[2]-a[3])-(a[4]-a[5])-……-(a[n-1]-a[n])=a[1]-a[2]+a[3]-a[4]+……+a[n-2]-a[n-1]+a[n]>=a[n]>0，操作必定成功。
当n是偶数，扔掉的石子数为a[1]-(a[2]-a[3])-(a[4]-a[5])-……-a[n]=a[1]-a[2]+a[3]-a[4]+……+a[n-1]-a[n]。操作不成功<=>扔掉的石子数为0<=>a[1]-a[2]=a[3]-a[4]=……=a[n-1]-a[n]=0，即当前已经为必败态。
所以综上所述：当石堆不成对时，先手必胜，成对时先手必败。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int map[1001];
int main()
{int n,x,f,i;while(scanf("%d",&n)){if(n==0){break;}memset(map,0,sizeof(map));//标记while(n--){scanf("%d",&x);map[x]++;//记录组数}f=0;for(i=0;i<=100;++i){if(map[i]%2==1)//判断是否成对{f=1;break;}}if(f==1){printf("1\n");}else{printf("0\n");}}return 0;
}POJ1737 Connected Graph
男人第三题，一道数论题，加上高精度，题意是给你n个点，让你求其中所有点连起来，没有交叉的所有情况数。由于有n个点，所以就是在n个点中取2个点就是所有的直线数，所有直线又有连和不连两种情况，所有总共有2^C(n,2)种情况。得到递推式f(n)=2^C(n,2)-(C(n,1)*f(1)+C(n,2)*f(2)+...+C(n,n-1)*f(n-1));
由于C++的高精度太神了，不太会，所以直接用JAVA飘过，不多说了，表示还可以打表，但是实在太辛苦就算了...
import java.io.*;
import java.util.*;
import java.math.*;
import java.text.*;
public class Main
{public static void main(String[] args){Scanner cin=new Scanner(System.in);int n,i,j;BigInteger Cn[][]=new BigInteger[51][51];BigInteger f[]=new BigInteger[51];BigInteger t,tt;BigInteger a=new BigInteger("2");for(i=0; i<=50; i++){Cn[i][0]=Cn[i][i]=BigInteger.valueOf(1);}for(i=1; i<=50; i++){for(j=1; j<i; j++){Cn[i][j]=Cn[i-1][j-1].add(Cn[i-1][j]);}}f[1]=BigInteger.valueOf(1);f[2]=BigInteger.valueOf(1);for(i=3; i<=50; i++){f[i]=BigInteger.valueOf(0);for(j=1; j<i; j++){t=BigInteger.valueOf(0);t=f[j].multiply(f[i-j]).multiply(Cn[i-2][j-1]);tt=BigInteger.valueOf(1);t=t.multiply(a.pow(j).subtract(tt));f[i]=f[i].add(t);}}while(cin.hasNext()){n=cin.nextInt();if(n==0){break;}System.out.println(f[n]);}}
}POJ 1743 Musical Theme
求最大不重合子段。。过的人数在8题中算多，，但是由于一直不太懂后缀数组LCP，所以再看了罗穗骞大神的后缀数组后才勉强懂了一点，，sa数组和height数组我只是直接套的模板，最后需要二分求解。。。后缀数组反正还是不太懂（Orz罗大神），，，
1/2水男人。。。
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<iomanip>
#include<cstdio>
using namespace std;
int n;
int a[20001],f[20001];
int rank[20001],sa[20001],top[20001],tmp[20001],height[20001],wa[20001],wb[20001];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];
}
void makesa()//后缀数组模板
{int i,j,p=0,*t,*x=wa,*y=wb,m=200;for(i=0; i<m; i++){top[i]=0;}for(i=0; i<n; i++){top[x[i]=f[i]]++;}for(i=1; i<m; i++){top[i]+=top[i-1];}for(i=n-1; i>=0; i--){sa[--top[x[i]]]=i;}for(j=1; p<n; j+=j,m=p){for(p=0,i=n-j; i<n; i++){y[p++]=i;}for(i=0; i<n; i++){if(sa[i]>=j){y[p++]=sa[i]-j;}}for(i=0; i<n; i++){tmp[i]=x[y[i]];}for(i=0; i<m; i++){top[i]=0;}for(i=0; i<n; i++){top[tmp[i]]++;}for(i=1; i<m; i++){top[i]+=top[i-1];}for(i=n-1; i>=0; i--){sa[--top[tmp[i]]]=y[i];}for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++){x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}}
}
void makeheight()
{int j,i,k;for(i=1; i<=n; i++){rank[sa[i]]=i;}for(i=0,k=0; i<n; height[rank[i++]]=k){for(k?k--:0,j=sa[rank[i]-1]; f[i+k]==f[j+k]; k++);}
}
bool ok(int x)
{int p,q,i;p=q=sa[1];for(i=2; i<=n+1; ++i){if(height[i]<x){p=q=sa[i];}else{p=min(p,sa[i]);q=max(q,sa[i]);if((q-p)>=x){return true;}}}return false;
}
int main()
{int i,l,mid,h;while(scanf("%d",&n)){if(n==0){break;}for(i=0; i<n; ++i){scanf("%d",&a[i]);}for(i=0; i<n-1; ++i){f[i]=a[i+1]-a[i]+89;}a[n-1]=0;makesa();n--;makeheight();l=4;h=n/2+1;while(l<h){mid=(l+h)/2;//cout<<mid<<endl;if(ok(mid)==true){l=mid+1;}else{h=mid;}}if(l<5){l=0;}printf("%d\n",l);}return 0;
}POJ 1738 An old Stone Game
GarsiaWachs算法，看了大牛的blog才知道原来还有这么神的算法，朴素地写得O(n*n)的复杂度。居然1A。。。
算法内容如下：设一个序列是A[0..n-1]，每次寻找最小的一个满足A[k-1]<=A[k+1]的k，（方便起见设A[-1]和A[n]等于正无穷大）
那么我们就把A[k]与A[k-1]合并，之后找最大的一个满足A[j]>A[k]+A[k-1]的j,把合并后的值A[k]+A[k-1]插入A[j]的后面。
有定理保证，如此操作后问题的答案不会改变。
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
int a[50001];
int n,tmp,ans;
void f(int tt)//直到找出全部
{int i,j,id=a[tt-1]+a[tt];ans+=id;tmp--;for(i=tt;i<tmp;++i){a[i]=a[i+1];}for(i=tt-1;i>0&&a[i-1]<id;--i){a[i]=a[i-1];}a[i]=id;while(i>=2&&a[i]>=a[i-2]){j=tmp-i;f(i-1);i=tmp-j;}
}
int main()
{int i;while(scanf("%d",&n)){if(n==0){break;}for(i=0;i<n;++i){scanf("%d",&a[i]);}tmp=1;ans=0;for(i=1;i<n;++i){a[tmp++]=a[i];while(tmp>=3&&a[tmp-3]<=a[tmp-1])//找中间的小值{f(tmp-2);}}while(tmp>1){f(tmp-1);}printf("%d\n",ans);}return 0;
}POJ 1744 Elevator Stopping Plan
一道二分贪心题，需要比较选择不同楼层停下所花费的最短时间，设定每个楼层都停是最长的上限=14*(n-1)。
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<iomanip>
#include<cstdio>
using namespace std;
inline void RD(int &ret)
{char c;do{c=getchar();}while(c<'0'||c>'9');ret=c-'0';while((c=getchar())>='0'&&c<='9'){ret=ret*10+(c-'0');}
}
inline void OT(int a)
{if(a>=10){OT(a/10);}putchar(a%10+'0');
}
int v[30001],mm;
bool f(int x)//贪心比较
{int i=x/20+2,j,cnt=0;while(i<=mm){while(i<=mm&&v[i]==0){i++;}if(((i-1)*4+10*cnt)>x){return false;}j=(x-10*cnt+20*i+4)/24;i=(x-10*cnt+16*j+4)/20+1;cnt++;}return true;
}
int main()
{int n,i,l,r,m,o,s;while(1){RD(n);if(n==0){break;}r=0;memset(v,0,sizeof(v));for(i=0; i<n; ++i){RD(o);r=max(r,o);v[o]=1;}l=0;mm=r;r=14*(r-1);while(l<=r)//二分{m=(l+r)/2;if(f(m)==true){s=m;r=m-1;}else{l=m+1;}}OT(s);printf("\n");}return 0;
}POJ 1741 Tree
树的分治，数据结构的题一直不太会做，所以直到现在才A了这题，典型的树中点对统计，理解了好久才AC了。。。看了QZC大神的论文和PPT很有收获：传送门
最近一直在训练，所以代码变得喜欢用宏定义和输入优化这类的东西。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(i,m,n) for(i=m;i<n;++i)
using namespace std;
inline void RD(int &ret)
{char c;do{c=getchar();}while(c<'0'||c>'9');ret=c-'0';while((c=getchar())>='0'&&c<='9'){ret=ret*10+(c-'0');}
}
inline void OT(int a)
{if(a>=10){OT(a/10);}putchar(a%10+'0');
}
struct xl
{int x,y,z;
}e[200001];
int p,q,l,r,ans;
int t[100001],d[100001],a[100001],b[100001];
bool vis[100001];
void dfs(int u,int de)
{vis[u]=1;d[u]=de;int w=t[u],v;while(w!=-1){v=e[w].x;if(!vis[v]){dfs(v,de+1);}w=e[w].z;}if(d[u]>d[q]){q=u;}if(d[u]==(d[q]+1)/2){p=u;}
}
void dist(int u)
{int i,j,w=t[u],s=l,t,v,sp,sq;vis[u]=1;a[l++]=0;t=l;while(w!=-1){v=e[w].x;if(!vis[v]){dist(v);FOR(i,t,l){a[i]+=e[w].y;}j=l-1;FOR(i,s,t){while(j>=t&&a[j]+a[i]>r){j--;}ans+=j-t+1;}sp=s;sq=t;FOR(i,s,l){if(sq==l||(sp<t&&a[sp]<a[sq])){b[i]=a[sp++];}else{b[i]=a[sq++];}}for(i=s; i<l; i++){a[i]=b[i];}t=l;}w=e[w].z;}return ;
}
int main()
{int i,n,u,v,w;while(1){RD(n);RD(r);if(n==0&&r==0){break;}mem(t,-1);FOR(i,0,n-1){RD(u);RD(v);RD(w);e[2*i].x=v;e[2*i].y=w;e[2*i].z=t[u];t[u]=2*i;e[2*i+1].x=u;e[2*i+1].y=w;e[2*i+1].z=t[v];t[v]=2*i+1;}mem(vis,0);q=1;dfs(1,0);mem(vis,0);dfs(q,0);mem(vis,0);ans=0;l=0;dist(p);OT(ans);printf("\n");}return 0;
}
这篇关于男人八题系列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
