此次练习的地址： http://acm.hust.edu.cn/vjudge/contest/view.action?cid=26732#overview
密码 acmore
Problem A(POJ1753)
题目： Flip Game
直接拿二进制模拟暴力枚举
之前已经做过了的Flip Game(枚举)
这次又WA了两次才AC，细心细心再细心！！！代码
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <math.h>
5 #include <iostream>
6 #include <stack>
7 #include <set>
8 #include <queue>
9 #define MAX(a,b) (a) > (b)? (a):(b)
10 #define MIN(a,b) (a) < (b)? (a):(b)
11 #define mem(a) memset(a,0,sizeof(a))
12 #define INF 1000000007
13 #define MAXN 20005
14 using namespace std;
15
16 int ma;
17 int m;
18 int ok;
19 int meiju(int st)
20 {
21 int i;
22 for(i=0;i<16;i++)
23 {
24 if((1<<i) & st)
25 {
26 m ^= (1<<i);
27 if(i>=4)
28 {
29 m ^= (1<<(i-4));
30 }
31 if(i%4>0)
32 {
33 m ^= (1<<(i-1));
34 }
35 if(i%4<3)
36 {
37 m ^= (1<<(i+1));
38 }
39 if(i+4<16)
40 {
41 m ^= (1<<(i+4));
42 }
43 }
44 }
45 if(m == 0 || m == (1<<16)-1)return 1;
46 return 0;
47 }
48
49 int main()
50 {
51 ok =0;
52 ma =0;
53 int i,j;
54 char str[4];
55 for(i=0;i<4;i++)
56 {
57 scanf("%s",str);
58 for(j=0;j<4;j++)
59 {
60 if(str[j] == 'b')
61 ma ^= (1<<(i*4+j));
62 }
63 }
64 int min =INF;
65 for(i=0;i<(1<<16);i++)
66 {
67 m = ma;
68 if(meiju(i))
69 {
70 int ans =0;
71 for(j=0;j<16;j++)
72 {
73 if((1<<j) & i)ans ++;
74 }
75 ok=1;
76 min=MIN(min,ans);
77 }
78 }
79 if(ok)printf("%d
",min);
80 else printf("Impossible
");
81 return 0;
82 }
Problem B（POJ2965）
题目：The Pilots Brothers' refrigerator
与上题一样，同样两次没过==！
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <math.h>
5 #include <iostream>
6 #include <stack>
7 #include <set>
8 #include <queue>
9 #define MAX(a,b) (a) > (b)? (a):(b)
10 #define MIN(a,b) (a) < (b)? (a):(b)
11 #define mem(a) memset(a,0,sizeof(a))
12 #define INF 1000000007
13 #define MAXN 20005
14 using namespace std;
15
16 int ma;
17 int m;
18 int meiju(int st)
19 {
20 int i;
21 for(i=0;i<16;i++)
22 {
23 if((1<<i) & st)
24 {
25 int j,k=0;
26 k|=(1<<i);
27 for(j=0;j<4;j++){
28 k|=1<<(i-i%4+j);
29 k|=1<<(j*4+i%4);
30 }
31 m^=k;
32 }
33 }
34 if(m == 0)return 1;
35 return 0;
36 }
37
38 int main()
39 {
40 ma =0;
41 int i,j;
42 char str[5];
43 for(i=0;i<4;i++)
44 {
45 scanf("%s",str);
46 for(j=0;j<4;j++)
47 {
48 if(str[j] == '+')
49 ma ^= (1<<(i*4+j));
50 }
51 }
52 int min =INF;
53 int key;
54 for(i=0;i<(1<<16);i++)
55 {
56 m = ma;
57 if(meiju(i))
58 {
59 int ans =0;
60 for(j=0;j<16;j++)
61 {
62 if((1<<j) & i)ans ++;
63 }
64 if(min > ans)
65 {
66 min = ans;
67 key = i;
68 }
69 }
70 }
71 printf("%d
",min);
72 for(i =0 ;i<16;i++)
73 {
74 if((1<<i) & key)
75 {
76 printf("%d %d
",i/4+1, i%4+1);
77 }
78 }
79 return 0;
80 }
problem C ZOJ 1716
我的方法是直接用一个数组 sum[i][j]存入从左上角为0,0，右下角为（i，j）的矩形的树的个数。
这样的话边长为a， b的矩形内部的树的个数就是
sum[i][j]-sum[i-a][j]-sum[i][j-b]+sum[i-a][j-b];
枚举小矩形的起点就行
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <math.h>
5 #include <iostream>
6 #include <stack>
7 #include <set>
8 #include <queue>
9 #define MAX(a,b) (a) > (b)? (a):(b)
10 #define MIN(a,b) (a) < (b)? (a):(b)
11 #define mem(a) memset(a,0,sizeof(a))
12 #define INF 1000000007
13 #define MAXN 20005
14 using namespace std;
15
16 int map[101][101];
17 int sum[101][101];
18 int n,width,height;
19
20 int shuru()
21 {
22 mem(map);
23 mem(sum);
24 while(scanf("%d",&n)!=EOF && n)
25 {
26 int j,i,a,b;
27 for(i=0;i<=n;i++)
28 {
29 scanf("%d%d",&a,&b);
30 map[b][a] = 1;
31 }
32 for(i=1;i<=100;i++)
33 {
34 for(j=1;j<=100;j++)
35 {
36 sum[i][j] = map[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
37 }
38 }
39 scanf("%d%d", &width, &height);
40 return 1;
41 }
42 return 0;
43 }
44
45 int f()
46 {
47 int i,j;
48 int max = 0;
49 for(i=height;i<=100;i++)
50 {
51 for(j=width;j<=100;j++)
52 {
53 max = MAX(sum[i][j]-sum[i][j-width]-sum[i-height][j]+sum[i-height][j-width], max);
54 }
55 }
56 return max;
57 }
58
59 int main()
60 {
61 while(shuru())
62 {
63 printf("%d
",f());
64 }
65 return 0;
66 }
problem D ZOJ 3356
坑爹的题目啊，之前做一直wa，后来实在是没办法，就参见了大神的代码，发现原来自己完全理解错了题目意思了。题目大意是说要让他不能亏，但是每次都是最坏的情况，也就是说每次投注之后，中的都是最少的哪一个。
最后还是参见了大神的思路，按投注的硬币的个数枚举，但每次放一个硬币时都是放在目前能都得到的最少的那一堆。所以复杂度就是O(coins)
代码：
1 #include <stdio.h> 2 #include <math.h> 3 #define MAX(a,b) (a)>(b)?(a):(b) 4 int main() 5 { 6 double x,y,z; 7 int coins; 8 int T; 9 while(~scanf("%d",&T))while(T--) 10 { 11 int get[3]={0},put[3]={0},mul[3]; 12 scanf("%d%lf%lf%lf", &coins, &x, &y, &z); 13 mul[0] = (int)floor(x*100 + 0.5); 14 mul[1] = (int)floor(y*100 + 0.5); 15 mul[2] = (int)floor(z*100 + 0.5); 16 int i,index = 0; 17 int ans = coins; 18 for(i=1;i<=coins;i++) 19 { 20 put[index] ++ ; 21 get[index] = put[index] * mul[index]/100; 22 index = get[0] < get[1] ? 0 : 1;//找到能够得到的最少的那一堆 23 index = get[index] < get[2] ? index : 2; 24 ans = MAX(ans, get[index]+coins-i); 25 } 26 printf("%d ", ans); 27 } 28 return 0; 29 }
problem E URAL 1010
WA了
problem F HDU 2069
起初觉得可以拿母函数做但是却发现，有个坑爹的条件就是Your program should be able to handle up to 100 coins.这句话，银币数目不可以超过100个
于是我换了一个想法，用记忆化的搜索，d[i][j][k]表示要凑齐i数值，开始用第j种硬币，还可以用k个硬币，为了不超时，记忆化一下。结果居然0Ms过了，真是奇迹~~~~
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <math.h>
5 #include <iostream>
6 #include <stack>
7 #include <set>
8 #include <queue>
9 #define MAX(a,b) (a) > (b)? (a):(b)
10 #define MIN(a,b) (a) < (b)? (a):(b)
11 #define mem(a) memset(a,0,sizeof(a))
12 #define INF 1000000007
13 #define MAXN 20005
14 using namespace std;
15
16 int f[251][6][101],vis[251][6][101];
17 int val[6]={0,1,5,10,25,50};
18
19
20 int dfs(int v,int c,int rest)
21 {
22 if(vis[v][c][rest])return f[v][c][rest];
23 vis[v][c][rest] = 1;
24 if(c == 1 && rest >= 0 && v<=rest)return f[v][c][rest]=1;
25 else if(c == 1 && (rest <0 || v > rest))return 0;
26 int i,m = v/val[c];
27 f[v][c][rest] = 0;
28 for(i=0;i<=m;i++)
29 {
30 f[v][c][rest]+=dfs(v-val[c]*i, c-1, rest-i);
31 }
32 return f[v][c][rest];
33 }
34
35 int main()
36 {
37 mem(f);
38 mem(vis);
39 int n;
40 while(~scanf("%d",&n))
41 {
42 int k;
43 if(n == 0){printf("1
");continue;}
44 if(n<5)k=1;
45 else if(n<10)k=2;
46 else if(n<25)k=3;
47 else if(n<50)k=4;
48 else k =5;
49 printf("%d
",dfs(n,k,100));
50 }
51 return 0;
52 }