http://acm.hust.edu.cn/vjudge/contest/view.action?cid=76492#overview password 123
D - Frame
长x个正方形 宽y正方形 ，问能否用 1*n的长方形无重叠覆盖最外围一圈 ，写一个函数判断，模拟放一圈。
1 #include<cstdio> 2 int b[8]; 3 bool f(int x,int y,int a){ 4 b[0]=b[2]=x; 5 b[1]=b[3]=y; 6 for(int i=0,m;i<4;i++){ 7 m=b[i]%a; 8 if(m>1) return false; 9 if(!m) b[i+1]--; 10 } 11 return true; 12 } 13 int main(){ 14 int x,y,n,a; 15 while(~scanf("%d%d%d",&x,&y,&n)){ 16 while(n--){ 17 scanf("%d",&a); 18 puts(f(x,y,a)||f(y,x,a)?"YES":"NO"); 19 } 20 } 21 return 0; 22 }
H - Triples
问满足 0<=x<=y<=z<=m x^j+y^j==z^j （ j=2...n ） 满足以上条件的xyz有多少组。
当j>2时，不存在正整数满足等式，所以2次方以上的，x必须是0，y必须等于z才能满足，对于2次方的种类就n^3暴力求，3次方以上的，每一种次方都有m+1对答案
1 #include<cstdio> 2 int main(){ 3 int n,m; 4 while(~scanf("%d%d",&m,&n)){ 5 int ans=0; 6 for(int i=0;i<=m;i++){ 7 for(int j=i;j<=m;j++){ 8 for(int k=j;k<=m;k++){ 9 if(i*i+j*j==k*k) ans++; 10 } 11 } 12 } 13 printf("%d ",ans+(n-2)*(m+1)); 14 } 15 return 0; 16 }
E - Points
用一个多边形包围输入的点，使得输入的点严格在多边形内部，多边形只能沿着格点的边或者单位格点的对角线走。问满足条件的多边形最小周长。
将输入的点变成4个点，分别在上下左右，距离一个单位长度。然后对分出来的点求凸包，再求凸包周长，周长不是两点距离，而是尽量用对角线，多余部分再走格点的边。
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 const double eps=1e-8; 6 const int M=4e5+10; 7 struct point{ 8 double x,y; 9 }p[M],r[M]; 10 int dx[]={0,0,1,-1}; 11 int dy[]={1,-1,0,0}; 12 bool operator < (const point &l, const point &r) { 13 return l.y < r.y || (fabs(l.y- r.y)<eps && l.x < r.x); 14 } 15 class ConvexHull { //凸包 16 bool mult(point sp, point ep, point op) {//>包括凸包边上的点,>=不包括 17 return (sp.x - op.x) * (ep.y - op.y)>= (ep.x - op.x) * (sp.y - op.y); 18 } 19 public: 20 int graham(int n,point p[],point res[]) {//多边形点个数和点数组，凸包存res 21 sort(p, p + n); 22 if (n == 0) return 0; 23 res[0] = p[0]; 24 if (n == 1) return 1; 25 res[1] = p[1]; 26 if (n == 2) return 2; 27 res[2] = p[2]; 28 int top=1; 29 for (int i = 2; i < n; i++) { 30 while (top && mult(p[i], res[top], res[top-1])) top--; 31 res[++top] = p[i]; 32 } 33 int len = top; 34 res[++top] = p[n - 2]; 35 for (int i = n - 3; i >= 0; i--) { 36 while (top!=len && mult(p[i], res[top],res[top-1])) top--; 37 res[++top] = p[i]; 38 } 39 return top; // 返回凸包中点的个数 40 } 41 } f; 42 double two=sqrt(2); 43 double getdist(point &a,point &b){ 44 double x=fabs(a.x-b.x); 45 double y=fabs(a.y-b.y); 46 return min(x,y)*two+fabs(x-y); 47 } 48 int main(){ 49 int n,x,y; 50 while(~scanf("%d",&n)){ 51 int lp=0; 52 for(int i=0;i<n;i++){ 53 scanf("%d%d",&x,&y); 54 for(int j=0;j<4;j++){ 55 p[lp].x=x+dx[j]; 56 p[lp].y=y+dy[j]; 57 lp++; 58 } 59 } 60 int len=f.graham(lp,p,r); 61 r[len]=r[0]; 62 double ans=0; 63 for(int i=0;i<len;i++){ 64 ans+=getdist(r[i],r[i+1]); 65 } 66 printf("%.6f ",ans); 67 } 68 return 0; 69 }
A - Banks
输入n个整数，每次操作可以将一个负数变成相反数，然后将前后两个数减少当前数的值，问最少操作数使得所有数都不为负。
暴力，找到一个负数就操作一次。
1 #include<cstdio> 2 const int M=1e4+10; 3 int a[M]; 4 int main(){ 5 int n; 6 while(~scanf("%d",&n)){ 7 for(int i=0;i<n;i++){ 8 scanf("%d",&a[i]); 9 } 10 int ans=0,bid=0; 11 for(int i=0;;){ 12 if(a[i]<0){ 13 ans++; 14 bid=i; 15 a[i]=-a[i]; 16 a[(i+n-1)%n]-=a[i]; 17 a[(i+1)%n]-=a[i]; 18 } 19 if(i==n-1){ 20 i=0; 21 } 22 else{ 23 i++; 24 } 25 if(i==bid) break; 26 } 27 printf("%d ",ans); 28 } 29 return 0; 30 }