分析后 和之前的类似,每一步有六种状态转移的方式 : c->a ;c->b; a->c;b->c,a->b ;b->a那每个状态是 a,b,c 的牛奶数量,因为是是从1 -20 ,那么等于是有20^3种状态、和之前的clock 很像,标记状态hash 判重,遍历所有的情况就可以。
1 /*
2 ID:fuxiang2
3 PROG: ariprog
4 LANG: C++
5 */
6 #include <iostream>
7 #include <fstream>
8 #include <string>
9 #include <vector>
10 #include <map>
11 #include <algorithm>
12 #include <set>
13 #include <cmath>
14
15 #define REP(i, n) for (int i=0;i<int(n);++i)
16 #define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
17 #define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
18 #define REP_1(i, n) for (int i=1;i<=int(n);++i)
19 #define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
20 #define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
21
22 using namespace std;
23 ofstream fout ("ariprog.out");
24 ifstream fin ("ariprog.in");
25
26 int n,m;
27 //set<int> si;
28
29 int hash[62510 * 2];
30
31 class node
32 {
33 public:
34 int a;
35 int b;
36
37 node(int _a, int _b){
38 a = _a;
39 b = _b;
40 }
41 bool operator < (const node & m )const {
42 if(m.b == b) return a < m.a;
43 return b < m.b;
44 }
45 };
46 vector<node> vn;
47
48 //应该是这里比较费时间
49 void work(int a,int b)
50 {
51 int ans = a;
52 if(hash[ans] == 0)
53 return ;
54 FOR(i,0,n-1){
55 ans += b;
56 if(hash[ans] == 0)
57 return ;
58 }
59 node t(a,b);
60 vn.push_back(t);
61
62 }
63 int main()
64 {
65 fin >> n >> m;
66 FOR_1(i,0,m)
67 FOR_1(j,0,m){
68 int ii = i*i;
69 int jj = j*j;
70 hash[ii + jj] = 1;
71 }
72 int end = m*m ;
73 FOR_1(i,0,end)
74 FOR_1(j,1,end){
75 if( (i + (n-1)*j) <= 2*end)
76 work(i,j);
77 else
78 break;
79 }
80 sort(vn.begin(),vn.end());
81 if(vn.empty())
82 fout << "NONE"<<endl;
83 else
84 for(vector<node>::iterator iter = vn.begin() ; iter != vn.end() ; iter ++ ){
85 fout << iter->a << " "<< iter ->b<<endl;
86 }
87
88 return 0;
89 }
原始博客地址:
http://www.fuxiang90.com/2012/06/usaco1-4-mothers-milk/
posted on 2012-07-10 10:39
付翔 阅读(314)
评论(0) 编辑 收藏 引用 所属分类:
ACM 数据结构