USACO 之 Section 2.2 （已解决）

Preface Numbering:

/*
　　发现规律，可生成出个、十、百、千的罗马数字。
　　然后，直接1~N枚举，统计字符出现次数。
*/

  1 /*
  2 ID: Jming
  3 PROG: preface
  4 LANG: C++
  5 */
  6 #include <iostream>
  7 #include <fstream>
  8 #include <sstream>
  9 #include <cstdlib>
 10 #include <cstdio>
 11 #include <cstddef>
 12 #include <iterator>
 13 #include <algorithm>
 14 #include <string>
 15 #include <locale>
 16 #include <cmath>
 17 #include <vector>
 18 #include <cstring>
 19 #include <map>
 20 #include <utility>
 21 #include <queue>
 22 #include <stack>
 23 #include <set>
 24 #include <functional>
 25 using namespace std;
 26 typedef pair<int, int> PII;
 27 typedef long long int64;
 28 const int INF = 0x3f3f3f3f;
 29 const int modPrime = 3046721;
 30 const double eps = 1e-9;
 31 const int MaxN = (1<<8) + 10;
 32 const int MaxM = 20;
 33 
 34 const string sig = "IVXLCDM";
 35 vector<string> one;
 36 vector<string> ten;
 37 vector<string> hundred;
 38 vector<string> thousand;
 39 
 40 int N;
 41 map<int, vector<string> > mapIS;
 42 
 43 void ini(vector<string> &vecStr, string sign)
 44 {
 45     vecStr.push_back("");
 46     string str;
 47     str = sign[0];
 48     for (int i = 0; i < 3; ++i)
 49     {
 50         vecStr.push_back(str);
 51         str += sign[0];
 52     }
 53     if (sign.size() == 1)
 54     {
 55         return;
 56     }
 57     str = sign[1];
 58     vecStr.push_back(sign[0] + str);
 59     for (int i = 0; i < 4; ++i)
 60     {
 61         vecStr.push_back(str);
 62         str += sign[0];
 63     }
 64     str = sign[2];
 65     vecStr.push_back(sign[0] + str);
 66 }
 67 
 68 void Solve()
 69 {
 70     string str;
 71     for (int i = 1; i <= N; ++i)
 72     {
 73         int num = i;
 74         int cnt = 1;
 75         while (num)
 76         {
 77             int digit = num % 10;
 78             str = mapIS[cnt][digit] + str;
 79             num /= 10;
 80             ++cnt;
 81         }
 82     }
 83     map<char, int> mapCI;
 84     for (int i = 0; i < str.size(); ++i)
 85     {
 86         if (mapCI.find(str[i]) == mapCI.end())
 87         {
 88             mapCI[str[i]] = 1;
 89         }
 90         else
 91         {
 92             ++mapCI[str[i]];
 93         }
 94     }
 95     for (int i = 0; i < 7; ++i)
 96     {
 97         if (mapCI.find(sig[i]) != mapCI.end())
 98         {
 99             printf("%c %d
", sig[i], mapCI[sig[i]]);
100         }
101     }
102 }
103 
104 int main()
105 {
106 #ifdef HOME
107     freopen("in", "r", stdin);
108     //freopen("out", "w", stdout);
109 #endif
110 
111     freopen("preface.in", "r", stdin);
112     freopen("preface.out", "w", stdout);
113     
114     ini(one, "IVX");
115     ini(ten, "XLC");
116     ini(hundred, "CDM");
117     ini(thousand, "M");
118 
119     mapIS[1] = one;
120     mapIS[2] = ten;
121     mapIS[3] = hundred;
122     mapIS[4] = thousand;
123     scanf("%d", &N);
124     Solve();
125 
126 
127 #ifdef HOME
128     cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;
129 #endif
130     return 0;
131 }

Subset Sums：

/*
　　01背包变形：
　　　　dp[i][j] := 前i个数，组成和恰为j的方式最大数目
　　　　dp[i][j] = dp[i-1][j] + dp[i-1][j-i] (j>=i)
　　　　空间优化
*/

 1 /*
 2 ID: Jming
 3 PROG: subset
 4 LANG: C++
 5 */
 6 #include <iostream>
 7 #include <fstream>
 8 #include <sstream>
 9 #include <cstdlib>
10 #include <cstdio>
11 #include <cstddef>
12 #include <iterator>
13 #include <algorithm>
14 #include <string>
15 #include <locale>
16 #include <cmath>
17 #include <vector>
18 #include <cstring>
19 #include <map>
20 #include <utility>
21 #include <queue>
22 #include <stack>
23 #include <set>
24 #include <functional>
25 using namespace std;
26 typedef pair<int, int> PII;
27 typedef long long int64;
28 const int INF = 0x3f3f3f3f;
29 const int modPrime = 3046721;
30 const double eps = 1e-9;
31 const int MaxN = 40;
32 const int MaxM = 20;
33 
34 int N;
35 int goal;
36 int ans = 0;
37 
38 // 注意：需为long long类型
39 long long dp[(((1 + MaxN)*MaxN) >> 2) + 10];
40 
41 void Solve()
42 {
43     if ((((1 + N)*N) >> 1) % 2)
44     {
45         // 找不到 the sums of both subsets are identical
46         cout << 0 << endl;
47         return;
48     }
49     int goal = (((1 + N)*N) >> 2);
50 
51     dp[0] = 1;
52     for (int i = 1; i <= N; ++i)
53     {
54         for (int j = goal; j >= i; --j)
55         {
56             dp[j] += dp[j - i];
57         }
58     }
59     cout << (dp[goal] >> 1) << endl;
60 }
61 
62 int main()
63 {
64 #ifdef HOME
65     freopen("in", "r", stdin);
66     //freopen("out", "w", stdout);
67 #endif
68 
69     freopen("subset.in", "r", stdin);
70     freopen("subset.out", "w", stdout);
71 
72     cin >> N;
73     Solve();
74 
75 #ifdef HOME
76     cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;
77 #endif
78     return 0;
79 }

Runaround Numbers：

/*
　　仔细读题，利用hash思想，即可解决
*/

  1 /*
  2 ID: Jming
  3 PROG: runround
  4 LANG: C++
  5 */
  6 #include <iostream>
  7 #include <fstream>
  8 #include <sstream>
  9 #include <cstdlib>
 10 #include <cstdio>
 11 #include <cstddef>
 12 #include <iterator>
 13 #include <algorithm>
 14 #include <string>
 15 #include <locale>
 16 #include <cmath>
 17 #include <vector>
 18 #include <cstring>
 19 #include <map>
 20 #include <utility>
 21 #include <queue>
 22 #include <stack>
 23 #include <set>
 24 #include <functional>
 25 using namespace std;
 26 typedef pair<int, int> PII;
 27 typedef long long int64;
 28 const int INF = 0x3f3f3f3f;
 29 const int modPrime = 3046721;
 30 const double eps = 1e-9;
 31 const int MaxN = 40;
 32 const int MaxM = 20;
 33 
 34 unsigned long N;
 35 
 36 bool isLegal(unsigned long num)
 37 {
 38     char chStr[25];
 39     sprintf(chStr, "%d", num);
 40     string str = chStr;
 41 
 42     bool digit[10];
 43     fill(digit, digit + 10, false);
 44     digit[0] = true;    // none of which is zero
 45     // unique digits
 46     for (int i = 0; i < str.size(); ++i)
 47     {
 48         if (digit[str[i] - '0'])
 49         {
 50             return false;
 51         }
 52         digit[str[i] - '0'] = true;
 53     }
 54 
 55     bool isVisited[25];
 56     fill(isVisited, isVisited + 25, false);
 57     int start = 0, Flag = 0;
 58     // an interesting property
 59     do
 60     {
 61         int pos = (start + (str[start] - '0')) % str.size();
 62         if ((pos == start) || isVisited[pos])
 63         {
 64             return false;
 65         }
 66         isVisited[pos] = true;
 67         start = pos;
 68     } while (start != Flag);
 69     for (int i = 0; i < str.size(); ++i)
 70     {
 71         if (!isVisited[i])
 72         {
 73             return false;
 74         }
 75     }
 76     return true;
 77 }
 78 
 79 void Solve()
 80 {
 81     unsigned long i = N + 1;
 82     while (!isLegal(i))
 83     {
 84         ++i;
 85     }
 86     cout << i << endl;
 87 }
 88 
 89 int main()
 90 {
 91 #ifdef HOME
 92     freopen("in", "r", stdin);
 93     //freopen("out", "w", stdout);
 94 #endif
 95 
 96     freopen("runround.in", "r", stdin);
 97     freopen("runround.out", "w", stdout);
 98 
 99     cin >> N;
100     Solve();
101 
102 #ifdef HOME
103     cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;
104 #endif
105     return 0;
106 }

Party Lamps：

/*
　　首先N最大值100，C最大值为10000，有4个按钮。
　　第一思路，直接暴搜的话，(4^10000)，必然超时。
　　所以，关键在于找出规律。。。
*************************************************************************************************
　　关键：两个规律
　　（1）只要考虑6个灯的状态就好了，编号大于6的灯x与编号为(x%6)的状态是一样的。（即每6个灯的状态是一个循环）
　　　　原因：
　　　　　　　只考虑Button 1：每1个灯的状态是一个循环
　　　　　　　只考虑Button 2：每2个灯的状态是一个循环
　　　　　　　只考虑Button 3：每2个灯的状态是一个循环
　　　　　　　只考虑Button 4：每3个灯的状态是一个循环
　　　　　　　=> 取(1, 2, 2, 3)的最小公倍数，即：6

　　（2）首先我们知道一个button按两下，其实和没按这个button的效果是一样的。所以：
　　　　　　C=0：灯全亮（初始状态）
　　　　　　C=1：可能按了4个button中的任意1个
　　　　　　C=2：可能按了4个button中的任意2个【或者】相当于 C=0（存在有两下相互抵消）
　　　　　　C=3：可能按了4个button中的任意3个【或者】相当于 C=1（存在有两下相互抵消）
　　　　　　C=4：可能按了4个button中的任意4个【或者】相当于 C=2（存在有两下相互抵消）
　　　　　　可以类推至C>4的情况：
　　　　　　　　C=5：仅有4个开关，按了5下，必然至少有两下的作用相互抵消，所以：相当于 C=3
　　　　　　　　C=6：仅有4个开关，按了6下，必然至少有两下的作用相互抵消，所以：相当于 C=4
　　　　　　　　......
　　　　　　　　C=n：仅有4个开关，按了n下，必然至少有两下的作用相互抵消，所以：相当于 C=(n-2)
　　　　　　可递推知，对于C>4，分两种情况:
　　　　　　　　1） C>4且奇数，相当于 C=3
　　　　　　　　2） C>4且偶数，相当于 C=4
*************************************************************************************************

综合以上两个规律，只要求出C=0...4可能被按下的button即可（共2^4种按button的方式）。

  1 /*
  2 ID: Jming
  3 PROG: lamps
  4 LANG: C++
  5 */
  6 #include <iostream>
  7 #include <fstream>
  8 #include <sstream>
  9 #include <cstdlib>
 10 #include <cstdio>
 11 #include <cstddef>
 12 #include <iterator>
 13 #include <algorithm>
 14 #include <string>
 15 #include <locale>
 16 #include <cmath>
 17 #include <vector>
 18 #include <cstring>
 19 #include <map>
 20 #include <utility>
 21 #include <queue>
 22 #include <stack>
 23 #include <set>
 24 #include <bitset>
 25 #include <functional>
 26 using namespace std;
 27 typedef pair<int, int> PII;
 28 typedef long long int64;
 29 const int INF = 0x3f3f3f3f;
 30 const int modPrime = 3046721;
 31 const double eps = 1e-9;
 32 const int MaxN = 40;
 33 const int MaxM = 20;
 34 
 35 int N;
 36 int C;
 37 vector<int> vecInt[5];
 38 vector<int> on;
 39 vector<int> off;
 40 set<string> setAns;
 41 
 42 int button[4];
 43 
 44 void generateCombination(int pos, int cnt, int val, const int lim)
 45 {
 46     // 以val的第i位是否为1，记录在C=lim下，是否会按下按钮i
 47     if (cnt == lim)
 48     {
 49         vecInt[lim].push_back(val);
 50         return;
 51     }
 52     for (int i = pos; i < 4; ++i)
 53     {
 54         generateCombination(i + 1, cnt + 1, val|(1<<i), lim);
 55     }
 56 }
 57 
 58 // 按下按钮 <=> 与button进行异或运算
 59 void getButton()
 60 {
 61     // 1：When this button is pressed, all the lamps change their state.
 62     fill(button, button + 4, 0);
 63     button[0] = (1 << 6) - 1;
 64     // 2:Changes the state of all the odd numbered lamps.
 65     /*注：对应 二进制101010*/
 66     for (int i = 5; i >=0; i -= 2)
 67     {
 68         button[1] |= (1 << i);
 69     }
 70     // 3:Changes the state of all the even numbered lamps.
 71     /*注：对应 二进制010101*/
 72     for (int i = 4; i >= 0; i -= 2)
 73     {
 74         button[2] |= (1 << i);
 75     }
 76     // 4: Changes the state of the lamps whose number is of the form 3xK+1 (with K>=0)
 77     /*注：对应 二进制100100*/
 78     button[3] |= (1 << 2);
 79     button[3] |= (1 << 5);
 80 }
 81 
 82 void ini()
 83 {
 84     getButton();
 85 
 86     // C=0...4时，可能被按下的button
 87     vecInt[0].push_back(0);
 88     for (int i = 1; i <= 4; ++i)
 89     {
 90         generateCombination(0, 0, 0, i);
 91     }
 92     vecInt[2].push_back(0);
 93     for (int i = 0; i < vecInt[1].size(); ++i)
 94     {
 95         vecInt[3].push_back(vecInt[1][i]);
 96     }
 97     vecInt[4].push_back(0);
 98     for (int i = 0; i < vecInt[2].size(); ++i)
 99     {
100         vecInt[4].push_back(vecInt[2][i]);
101     }
102 }
103 
104 // 十进制转换成二进制 eg：2D => 000010B
105 string tenTotwo(int num)
106 {
107     string str;
108     while (num)
109     {
110         if (num & 1)
111         {
112             str = static_cast<char>('0' + 1) + str;
113         }
114         else
115         {
116             str = '0' + str;
117         }
118         num >>= 1;
119     }
120     while (str.size() < 6)
121     {
122         str = '0' + str;
123     }
124     return str;
125 }
126 
127 
128 // 判断生成的结果是否合法
129 bool isLegal(string str)
130 {
131     for (int i = 0; i < on.size(); ++i)
132     {
133         if (str[(on[i] - 1)%6] != '1')
134         {
135             return false;
136         }
137     }
138     for (int i = 0; i < off.size(); ++i)
139     {
140         if (str[(off[i] - 1)%6] != '0')
141         {
142             return false;
143         }
144     }
145     return true;
146 }
147 
148 void getAns(int c, int start)
149 {
150     for (int i = 0; i < vecInt[c].size(); ++i)
151     {
152         int val = vecInt[c][i];
153         int startNum = start;
154         int cnt = 0;
155         while (val)
156         {
157             if (val & 1)
158             {
159                 startNum ^= button[cnt];
160             }
161             val >>= 1;
162             ++cnt;
163         }
164         string str = tenTotwo(startNum);
165         if (isLegal(str))
166         {
167             setAns.insert(str);
168         }
169     }
170 }
171 
172 void Solve()
173 {
174     ini();
175 
176     int start = (1 << 6) - 1;
177     if (C <= 4)
178     {
179         getAns(C, start);
180     }
181     else
182     {
183         if (C&1)
184         {
185             // C>4且奇数
186             getAns(3, start);
187         }
188         else
189         {
190             // C>4且偶数
191             getAns(4, start);
192         }
193     }
194 
195     if (setAns.empty())
196     {
197         printf("IMPOSSIBLE
");
198     }
199     else
200     {
201         for (set<string>::iterator it = setAns.begin(); it != setAns.end(); ++it)
202         {
203             string str = *it;
204             for (int i = 0; i < N; ++i)
205             {
206                 printf("%c", str[i % 6]);
207             }
208             printf("
");
209         }
210     }
211 }
212 
213 int main()
214 {
215 #ifdef HOME
216     freopen("in", "r", stdin);
217     //freopen("out", "w", stdout);
218 #endif
219 
220     freopen("lamps.in", "r", stdin);
221     freopen("lamps.out", "w", stdout);
222 
223     scanf("%d", &N);
224     scanf("%d", &C);
225     int num;
226     while ((scanf("%d", &num)) && (num != -1))
227     {
228         on.push_back(num);
229     }
230     while ((scanf("%d", &num)) && (num != -1))
231     {
232         off.push_back(num);
233     }
234     Solve();
235 
236 #ifdef HOME
237     cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;
238 #endif
239     return 0;
240 }