此次练习的地址： http://acm.hust.edu.cn/vjudge/contest/view.action?cid=26732#overview
密码 acmore
Problem A(POJ1753)
题目： Flip Game
直接拿二进制模拟暴力枚举
之前已经做过了的Flip Game(枚举)
这次又WA了两次才AC，细心细心再细心！！！代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <iostream>
#include <stack>
#include <set>
#include <queue>
#define MAX(a,b) (a) > (b)? (a):(b)
#define MIN(a,b) (a) < (b)? (a):(b)
#define mem(a) memset(a,0,sizeof(a))
#define INF 1000000007
#define MAXN 20005
using namespace std; int ma;
int m;
int ok;
int meiju(int st)
{
int i;
for(i=;i<;i++)
{
if((<<i) & st)
{
m ^= (<<i);
if(i>=)
{
m ^= (<<(i-));
}
if(i%>)
{
m ^= (<<(i-));
}
if(i%<)
{
m ^= (<<(i+));
}
if(i+<)
{
m ^= (<<(i+));
}
}
}
if(m == || m == (<<)-)return ;
return ;
} int main()
{
ok =;
ma =;
int i,j;
char str[];
for(i=;i<;i++)
{
scanf("%s",str);
for(j=;j<;j++)
{
if(str[j] == 'b')
ma ^= (<<(i*+j));
}
}
int min =INF;
for(i=;i<(<<);i++)
{
m = ma;
if(meiju(i))
{
int ans =;
for(j=;j<;j++)
{
if((<<j) & i)ans ++;
}
ok=;
min=MIN(min,ans);
}
}
if(ok)printf("%d\n",min);
else printf("Impossible\n");
return ;
}
Problem B（POJ2965）
题目：The Pilots Brothers' refrigerator
与上题一样，同样两次没过==！
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <iostream>
#include <stack>
#include <set>
#include <queue>
#define MAX(a,b) (a) > (b)? (a):(b)
#define MIN(a,b) (a) < (b)? (a):(b)
#define mem(a) memset(a,0,sizeof(a))
#define INF 1000000007
#define MAXN 20005
using namespace std; int ma;
int m;
int meiju(int st)
{
int i;
for(i=;i<;i++)
{
if((<<i) & st)
{
int j,k=;
k|=(<<i);
for(j=;j<;j++){
k|=<<(i-i%+j);
k|=<<(j*+i%);
}
m^=k;
}
}
if(m == )return ;
return ;
} int main()
{
ma =;
int i,j;
char str[];
for(i=;i<;i++)
{
scanf("%s",str);
for(j=;j<;j++)
{
if(str[j] == '+')
ma ^= (<<(i*+j));
}
}
int min =INF;
int key;
for(i=;i<(<<);i++)
{
m = ma;
if(meiju(i))
{
int ans =;
for(j=;j<;j++)
{
if((<<j) & i)ans ++;
}
if(min > ans)
{
min = ans;
key = i;
}
}
}
printf("%d\n",min);
for(i = ;i<;i++)
{
if((<<i) & key)
{
printf("%d %d\n",i/+, i%+);
}
}
return ;
}
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];
枚举小矩形的起点就行
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <iostream>
#include <stack>
#include <set>
#include <queue>
#define MAX(a,b) (a) > (b)? (a):(b)
#define MIN(a,b) (a) < (b)? (a):(b)
#define mem(a) memset(a,0,sizeof(a))
#define INF 1000000007
#define MAXN 20005
using namespace std; int map[][];
int sum[][];
int n,width,height; int shuru()
{
mem(map);
mem(sum);
while(scanf("%d",&n)!=EOF && n)
{
int j,i,a,b;
for(i=;i<=n;i++)
{
scanf("%d%d",&a,&b);
map[b][a] = ;
}
for(i=;i<=;i++)
{
for(j=;j<=;j++)
{
sum[i][j] = map[i][j]+sum[i-][j]+sum[i][j-]-sum[i-][j-];
}
}
scanf("%d%d", &width, &height);
return ;
}
return ;
} int f()
{
int i,j;
int max = ;
for(i=height;i<=;i++)
{
for(j=width;j<=;j++)
{
max = MAX(sum[i][j]-sum[i][j-width]-sum[i-height][j]+sum[i-height][j-width], max);
}
}
return max;
} int main()
{
while(shuru())
{
printf("%d\n",f());
}
return ;
}
problem D ZOJ 3356
坑爹的题目啊，之前做一直wa，后来实在是没办法，就参见了大神的代码，发现原来自己完全理解错了题目意思了。题目大意是说要让他不能亏，但是每次都是最坏的情况，也就是说每次投注之后，中的都是最少的哪一个。
最后还是参见了大神的思路，按投注的硬币的个数枚举，但每次放一个硬币时都是放在目前能都得到的最少的那一堆。所以复杂度就是O(coins)
代码：
#include <stdio.h>
#include <math.h>
#define MAX(a,b) (a)>(b)?(a):(b)
int main()
{
double x,y,z;
int coins;
int T;
while(~scanf("%d",&T))while(T--)
{
int get[]={},put[]={},mul[];
scanf("%d%lf%lf%lf", &coins, &x, &y, &z);
mul[] = (int)floor(x* + 0.5);
mul[] = (int)floor(y* + 0.5);
mul[] = (int)floor(z* + 0.5);
int i,index = ;
int ans = coins;
for(i=;i<=coins;i++)
{
put[index] ++ ;
get[index] = put[index] * mul[index]/;
index = get[] < get[] ? : ;//找到能够得到的最少的那一堆
index = get[index] < get[] ? index : ;
ans = MAX(ans, get[index]+coins-i);
}
printf("%d\n", ans);
}
return ;
}
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过了，真是奇迹~~~~
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <iostream>
#include <stack>
#include <set>
#include <queue>
#define MAX(a,b) (a) > (b)? (a):(b)
#define MIN(a,b) (a) < (b)? (a):(b)
#define mem(a) memset(a,0,sizeof(a))
#define INF 1000000007
#define MAXN 20005
using namespace std; int f[][][],vis[][][];
int val[]={,,,,,}; int dfs(int v,int c,int rest)
{
if(vis[v][c][rest])return f[v][c][rest];
vis[v][c][rest] = ;
if(c == && rest >= && v<=rest)return f[v][c][rest]=;
else if(c == && (rest < || v > rest))return ;
int i,m = v/val[c];
f[v][c][rest] = ;
for(i=;i<=m;i++)
{
f[v][c][rest]+=dfs(v-val[c]*i, c-, rest-i);
}
return f[v][c][rest];
} int main()
{
mem(f);
mem(vis);
int n;
while(~scanf("%d",&n))
{
int k;
if(n == ){printf("1\n");continue;}
if(n<)k=;
else if(n<)k=;
else if(n<)k=;
else if(n<)k=;
else k =;
printf("%d\n",dfs(n,k,));
}
return ;
}