A.http://acm.hdu.edu.cn/showproblem.php?pid=5538

求表面积，只需要将所有的1*1的小块扫描一遍。将每一个块与他相邻四周进行比较，如果该快高度大，则将该快高度减去周围块高度然后累加。复杂度O(nm)

#define _CRT_SECURE_NO_DEPRECATE#include
     
      #include
      
       #include
       
        typedef long long LL;const double EPS = 1e-8;const double PI = acos(-1.0);using namespace std;const int MAXN = 55;int n, m;int a[MAXN][MAXN];int dir[4][2] = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };int main(){	int T, i, j, k;	scanf("%d\n", &T);	while (T--){		memset(a, 0, sizeof(a));		int ans = 0;		scanf("%d%d", &n, &m);		for (i = 1; i <= n; i++)		for (j = 1; j <= m; j++){			scanf("%d", &a[i][j]);			if (a[i][j] > 0)				ans++;		}		for (i = 1; i <= n; i++)		for (j = 1; j <= m; j++){			for (k = 0; k < 4; k++){				int x = i + dir[k][0];				int y = j + dir[k][1];				if (a[x][y] < a[i][j]){					ans += a[i][j] - a[x][y];				}			}		}		printf("%lld\n", ans);	}	return 0;}
       
      
     

　　2.http://acm.hdu.edu.cn/showproblem.php?pid=5532

原来序列要么按照升序，要么按照降序去判断，首先可以假定原序列是升序(降序同样来处理).首先将原序列从左到右扫描一遍，不断的比较相邻的两个元素，直到遇到某两元素满足

a[i]>a[i+1]或者扫描到末尾时逃出。若扫描到了末尾，则原序列是增序列，满足条件。若是遇到a[i]>a[i+1]跳出，则我们可以断定，我们要删去的元素一定是a[i]或者a[i+1],可以这样来想，如果删去的是其它元素，则该序列中还是存在a[i]和a[i+1]破坏来递增性。于是问题简单了，只需要分别去掉a[i],和a[i+1]来判断一下原序列是否是递增序列即可。同样的，当假设原序列是递减序列时，处理方法相同。

#define _CRT_SECURE_NO_DEPRECATE#include
     
      #include
      
       #include
       
        typedef long long LL;const double EPS = 1e-8;const double PI = acos(-1.0);using namespace std;const int MAXN =1000001;int a[MAXN];int n;bool UpSroted(){	int i;	for (i = 0; i < n - 1; i++)	  if (a[i]>a[i + 1]) //若遇到降序的则跳出		 break;	if (i>=n - 2) //a[i+1]后面没有数了		return true;   	int j = i + 2; 	while (j < n - 1){		if (a[j]>a[j + 1])			break;		j++;	}	if (j
        
         a[i + 2])		return false;	if (i == 0)		return true;	if (a[i - 1] <= a[i + 1])		return true;	return false;}bool DownSroted(){	int i;	for (i = 0; i < n - 1; i++)	if (a[i]
         
          = n - 2) //a[i+1]后面没有数了		return true;	int j = i + 2;	while (j < n - 1){		if (a[j]
          
           = a[i + 2]) //去掉a[i+1]即可 return true; if (a[i + 1]
           
            = a[i + 1]) return true; return false;}int main(){ int T, i; scanf("%d\n", &T); while (T--){ scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &a[i]); bool flag = UpSroted() || DownSroted(); if (flag) printf("YES\n"); else printf("NO\n"); } return 0;}
           
          
         
        
       
      
     

　　3.http://acm.hdu.edu.cn/showproblem.php?pid=5533

原问题给出的都是整数点，这样以来就只有正方形符合要求了，只需要判断一下给定的是否是4个点，这四个点是否可以构成正方形。

#define _CRT_SECURE_NO_DEPRECATE#include
     
      #include
      
       #include
       
        using namespace std;const double PI = acos(-1.0);const int N = 300;const double EPS = 1e-8;//实数精度//点结构类型struct Point{	double x, y;	Point(double a = 0, double b = 0){ x = a; y = b; }};Point operator-(Point a, Point b){	return Point(a.x - b.x, a.y - b.y);}//重载==,判断点a,b是否相等bool operator==(Point a, Point b){	return abs(a.x - b.x) < EPS&&abs(a.y - b.y) < EPS;}//比较实数r1与r2的大小关系int RlCmp(double r1, double r2 = 0){	if (abs(r1 - r2) < EPS)		return 0;	return r1>r2 ? 1 : -1;}double Dot(Point p1, Point p2, Point p3, Point p4){	Point a = p2 - p1;	Point b = p4 - p3;	return a.x*b.x + a.y*b.y;}//检查以p1p2和p3p4为对角线是否可以构成正方形bool firstCheck(Point p1, Point p2, Point p3, Point p4){	Point mid0 = Point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);	Point mid1 = Point((p3.x + p4.x) / 2, (p3.y + p4.y) / 2);	if (!(mid0 == mid1)) //如果中点不重合		return false;	return RlCmp(Dot(p1, p2, p3, p4)) == 0;  //对角线垂直}bool isSqual(Point P[]){	return firstCheck(P[0], P[1], P[2], P[3]) ||		firstCheck(P[0], P[2], P[1], P[3]) ||		firstCheck(P[0], P[3], P[1], P[2]);}int main(){	Point P[N];	int T,i,n;	double x, y;	scanf("%d", &T);	while (T--){		scanf("%d", &n);		for (i = 0; i < n; i++){			scanf("%lf%lf", &x, &y);			P[i] = Point(x, y);		}		if (n != 4){			printf("NO\n");			continue;		}		if (isSqual(P))			printf("YES\n");		else			printf("NO\n");	}	return 0;}
       
      
     

　　4.http://acm.hdu.edu.cn/showproblem.php?pid=5536

该问题是贪心+字典树。虽然网上有O(n^3)爆力剪枝可以过，表示不会。将每一个数字的二进制从高位到低位存入到字典树中形成01串。这时候我们需要一个节点变量v，每次插入只需要将v++.接下来，枚举a[i]，a[j](j>i)，首先在字典树中删掉a[i]和a[j]，删除做法很简单，将对应节点位置v--即可，然后用a[i]+a[j]在字典树中进行01串的匹配，匹配完后再插入a[i],a[j]准备下一次的匹配。匹配方法采用贪心思想，依次从高位向低位匹配，若当前数该位为1则去优先匹配0,若没有0匹配，则只能匹配1了。当前位置是0，则优先去匹配1，当没有1匹配，就只能匹配0了。如此下去，直到匹配到最后一位。这样有一个问题，每一个数二进制串长度不一样，给匹配带来不便，做法是，将所有的串高位补0，使得长度为32位。这样就可开心的匹配了。

#define _CRT_SECURE_NO_DEPRECATE#include
     
      #include
      
       typedef long long LL;const int MAXN = 1000+10;using namespace std;struct TrieNode{	TrieNode(){ memset(next, 0, sizeof(next)); v = 0; }	TrieNode* next[2];	LL v;};LL MAX;TrieNode *root;void Insert(LL x){	TrieNode*p = root;	MAX = 1;	MAX <<= 32;	for (LL i =MAX; i >0; i>>=1){		LL id =(i&x)>0;		if (p->next[id] == NULL)			p->next[id] = new TrieNode;		p = p->next[id];		p->v++;	}}void Delete(LL x){	TrieNode*p = root;	MAX = 1;	MAX <<= 32;	for (LL i = MAX; i >0; i >>= 1){		LL id = (i&x)>0;		p = p->next[id];		p->v--;	}}LL getMAX(LL x){	TrieNode *p = root;	MAX = 1;	MAX <<= 32;	LL rt,ans=x,i=-1;	for (LL i = MAX; i >0;i>>=1){		LL id = (x&i)>0;		if (p->next[id ^ 1] && p->next[id ^ 1]->v > 0){			if ((id == 0))  //说明x当前位为0，即将变为1				ans +=i ;			p = p->next[id ^ 1];			continue;		}		if (id)  //如果x当前位置为1,则即将要变为0			ans -= i;		p = p->next[id];	}	return ans;}void Free(TrieNode*T){	if (T){		for (int i = 0; i < 2; i++)			Free(T->next[i]);		free(T);		T = NULL;	}}LL a[MAXN];int main(){	LL n,i,j,T;	scanf("%I64d", &T);	while (T--){		root = new TrieNode;		scanf("%I64d", &n);		for (i = 0; i < n; i++){			scanf("%I64d", &a[i]);			Insert(a[i]);		}		LL ans =0;		for (i = 0; i < n; i++){			Delete(a[i]);			for (j = i + 1; j < n; j++){				Delete(a[j]);				ans = max(ans, getMAX(a[i] + a[j]));				Insert(a[j]);			}			Insert(a[i]);		}		printf("%I64d\n",ans);		Free(root);	}	return 0;}
      
     

　5.http://acm.hdu.edu.cn/showproblem.php?pid=5534

思维比较巧妙的一道DP题目。首先n个节点的无向树有2*(n-1)个度。每一节点至少有一个度，所以可以这样考虑，首先给每个节点分配一个度，这样还剩下2*n-2个度，于是问题就转化为了完全背包问题。需要注意的是此时背包总容量是2*n-2，价值转移方程为p[i]-p[0];

#define _CRT_SECURE_NO_DEPRECATE#include
     
      #include
      
       using namespace std;const int MAXN = 2005 * 2 + 1;#define INF 0x3f3f3f3fint n;int p[MAXN],f[MAXN],V;//完全背包问题void ComplePack(int w, int i){	for (int j = i; j <= V; j++)		f[j] = max(f[j],f[j-i] + w);}int main(){	int i, T;	scanf("%d", &T);	while (T--){		scanf("%d", &n);		for (i = 0; i < n - 1; i++)			scanf("%d", &p[i]);		V = n - 2;		for (i = 1; i < n - 1; i++)			p[i] -= p[0];   //价值转移		for (i = 1; i < n - 1; i++)			f[i] = -INF;		f[0] = p[0] * n;		for (i = 1; i <= n - 2; i++){			ComplePack(p[i], i);		}		printf("%d\n",f[n-2]);	}	return 0;}
      
     

　　6.http://acm.hdu.edu.cn/showproblem.php?pid=5531

题目很长，其实题目意思很简单。题意：在一个多边形每一个顶点以顶点为圆心都构造一个园，相邻顶点的园外切，不相邻的顶点的圆无限制。问是否存在这样的构造，存在则还要要求求出所有圆面积和的最小值，以及对应的园的半径。

设多边形的n个点是p1,p2,...pn.n个园半径依次为r1,r2,r3...rn.设d1=p1p2,d2=p2p3,...,d_n-1=p_n-1p_n,dn=p_np1.于是由园相切，我们可以得到n个关系式：

r1+r2=d1

r2+r3=d2

.....

r_n-1+r_n=d_n-1

r_n+r1=d_n

这时候我们要对n分奇偶数讨论。设数组dis[i]=d[1]-d[2]+d[3]-d[4]...+(-1)^i-1*d[i];如果n是奇数，则迭代可知上面n个等式必然有唯一解，求出此解，然后看是否所有的解大于等0即可。如果n是偶数，则上面等式前n项可以变为

r1+r2=dis[1]

r1-r3=dis[2]

r1+r4=dis[3]

....

r1+r_n=dis[n-1]

r1+r_n=d[n]

显然只有当d[n]==dis[n-1]时才有解。于是接下来只有n-1个方程和n个未知量，一定有解。我们注意到0<=r_i<=min(d[i-1],d[i]),(i=2,3..n).而0<=r₁<=min(d1,d_n)

.利用以上不等式可以求出r1的取值区间。而目标函数area=(r1²+r2²...+r_n²) *π。aera是关于r1的二次函数，对应开口向上，对称轴为(dis[1]+disp[2]...+dis[n-1])/n.

这样最值问题就求解了。

#define _CRT_SECURE_NO_DEPRECATE#include
     
      #include
      
       #include
       
        using namespace std;const double EPS = 1e-8;const double pi = acos(-1.0);const int MAXN = 100000 + 10;struct Point{	double x, y;};struct Intervel{	double s, e;	Intervel(double a = 0, double b = 0) :s(a), e(b){}};int n;Point P[MAXN];double r[MAXN], d[MAXN],dis[MAXN];double Distance(Point p1, Point p2){	return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));}int RlCmp(double r1, double r2 = 0){	if (abs(r1 - r2) < EPS)		return 0;	return r1>r2?1 : -1;}bool Intersect(Intervel x, Intervel y,Intervel &ans){	if (RlCmp(x.e, y.s) == -1)		return false;	if (RlCmp(y.e, x.s) == -1)		return false;	ans =Intervel(max(x.s, y.s), min(x.e, y.e));	return true;}bool isPossible(double &area){	if (n & 1){		r[1] = dis[n]/ 2;		if (RlCmp(r[1])==-1)			return false;		area = r[1] * r[1];		for (int i = 2; i <= n; i++){			if (i & 1)				r[i] = r[1] - dis[i-1];			else				r[i] = dis[i-1] - r[1];			if (RlCmp(r[i])==-1)				return false;			area += r[i] * r[i];		}		area *= pi;		return true;	}	else{		if (RlCmp(dis[n]))			return false;		bool flag = 1;		Intervel curr(0,min(d[1],d[n]));		for (int i = 2; i <=n; i++){			if (i & 1)				flag = Intersect(curr, Intervel(dis[i - 1], dis[i - 1] + min(d[i], d[i - 1])), curr);			else				flag = Intersect(curr, Intervel(dis[i - 1] - min(d[i], d[i - 1]),dis[i-1]), curr);			if (!flag)				return false;		}		double t = 0;		for (int i = 1; i <= n - 1; i++)			t += dis[i];		t /= n;		if (t < curr.s)			r[1] = curr.s;		else if (t>curr.e)			r[1] = curr.e;		else			r[1] = t;		area = r[1] * r[1];		for (int i = 2; i <= n; i++){			if (i & 1)				r[i] = r[1] - dis[i - 1];			else				r[i] = dis[i - 1] - r[1];			area += r[i] * r[i];		}		area *= pi;		return true;	}}int main(){	int T, i;	scanf("%d", &T);	while (T--){		scanf("%d", &n);		for (i = 1; i <= n; i++)			scanf("%lf%lf", &P[i].x, &P[i].y);		for (i = 1; i < n; i++)			d[i] = Distance(P[i], P[i + 1]);		d[n] = Distance(P[1], P[n]);		dis[0] = 0;		for (i = 1; i <= n; i++){			if (i & 1)				dis[i]=dis[i-1]+d[i];			else				dis[i]=dis[i-1]-d[i];		}		double area;		bool ans = isPossible(area);		if (ans){			printf("%.2lf\n", area);			for (i = 1; i <= n; i++)				printf("%.2lf\n",r[i]);		}		else			printf("IMPOSSIBLE\n");	}	return 0;}
       
      
     

　　7.http://acm.hdu.edu.cn/showproblem.php?pid=5527

    一道很好的贪心题目。我们要考虑选取数来凑p，但是呢，每个硬币个数是有限制的，顺着贪心是无法下手的。总的硬币个数num和总的钱total是知道的，求凑p得到最大也就是求凑total-p的最小,因为他们的和就是num。于是我们来逆向考虑求最小值。这样我们从最大的硬币选取，一直贪心选下来，基于这样算法成立的条件是，前面硬币面值一定是后面硬币面值的约数，只有这样，前面硬币能达到超过该硬币的值，一定可以用该硬币来替代而使得总硬币个数更小。硬币面值 1  5 10 20 50 100 200 500 1000 2000,我们发现有两对不满足，20 50和200 500,于是会产生这样一个问题。比如我现在有20硬币*3，50硬币*1,当前要选取等于60的硬币，如果贪心来选首选的是50，而实际应该选择是20*3.产生这个原因是由于20不是50的约数。解决的办法就是对50,500进行特判，枚举他们的奇偶情况，因为2个50可以当做100来使用。1. 50奇500偶数。2. 50偶数 500奇数

3. 50奇数 500奇数 4. 50偶数 500偶数。然后把4种情况跑一下就OK了。

#define _CRT_SECURE_NO_DEPRECATE#include
     
      #include
      
       using namespace std;typedef  long long LL;LL p, total,num;LL nl[11];LL c[11] = { 0, 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000 };LL Compute(LL pp){	LL i, ans = 0;	if (pp<0)		return -1;	for (i = 10; i > 0; i--){		LL k = min(pp/c[i],nl[i]);		if ((k&1)&&(i == 5 || i == 8))				k--;        //只可以用掉偶数个		ans += k;		pp-= k*c[i];	}	if  (pp!= 0)		return -1;	return num - ans;}LL Slove(){	LL ans = -1,pp,ret;	//下面对四中情况进行枚举	if (nl[5] > 0){		nl[5]--;		pp = p - c[5];		ret=Compute(pp);		ans = max(ans, ret-1);		nl[5]++;	}	if (nl[8] > 0){		nl[8]--;		pp = p - c[8];		ret = Compute(pp);		ans = max(ans, ret-1);		nl[8]++;	}	if (nl[5] > 0 && nl[8] > 0){		nl[5]--;nl[8]--;		pp = p - c[5] - c[8];		ret = Compute(pp);		ans = max(ans, ret-2);		nl[5]++; nl[8]++;	}	pp = p;	ret=Compute(pp);	ans = max(ans, ret);	return ans;}int main(){	LL i, T;	scanf("%I64d", &T);	while (T--){		total = num = 0;		scanf("%I64d", &p);		for (i = 1; i <= 10; i++)			scanf("%I64d", &nl[i]);		for (i = 1; i <=10; i++){			num += nl[i];       //计算总个数			total += c[i] * nl[i];  //计算总money		}		p = total - p;           //从反面考虑 				LL ans = Slove();		printf("%I64d\n", ans);	}	return 0;}