付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0
分析后 和之前的类似,每一步有六种状态转移的方式 : 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 付翔 阅读(300) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜