首页 > 代码库 > [转] AOJ 0525 Osenbei《挑战程序设计竞赛(第2版)》练习题答案

[转] AOJ 0525 Osenbei《挑战程序设计竞赛(第2版)》练习题答案

来自 码农场 ? AOJ 0525 Osenbei《挑战程序设计竞赛(第2版)》练习题答案

只把代码复制过来,原博的其他分析请看链接。

 1 #include <iostream>
 2 #include <bitset>
 3 #include <algorithm>
 4  
 5 using namespace std;
 6  
 7 bitset<10000> cookie[10];
 8  
 9 ///////////////////////////SubMain//////////////////////////////////
10 int main(int argc, char *argv[])
11 {
12  
13     int R, C;
14     while(cin >> R >> C && R > 0)
15     {
16         int i, j;
17         for (i = 0; i < R; ++i)
18         {
19             for (j = 0; j < C; ++j)
20             {
21                 bool upwards;
22                 cin >> upwards;
23                 cookie[i][j] = upwards;
24             }
25         }
26  
27         // 在横向一共有2^R种变换
28         int permute_r = 1 << R;
29         int result = 0;
30         for (i = 0; i < permute_r ; ++i)
31         {
32             // 完成当前的变换
33             for (j = 0; j < R; ++j)
34             {
35                 // 这一行是否应当翻个面
36                 if (i & (1 << j))
37                 {
38                     cookie[j].flip();
39                 }
40             }
41             
42  
43             // 对每一列分别算出朝上和朝下的煎饼个数,取其最大值
44             int possible_answer = 0;
45             for (j = 0; j < C; ++j)
46             {
47                 int up_cookie_count = 0;
48                 for (int k = 0; k < R; ++k)
49                 {
50                     if (cookie[k][j])
51                     {
52                         ++up_cookie_count;
53                     }
54                 }
55                 possible_answer += max(up_cookie_count, R - up_cookie_count);
56             }
57             // 结果取最大值
58             result = max(result, possible_answer);
59             
60             // 复原
61             for (j = 0; j < R; ++j)
62             {
63                 if (i & (1 << j))
64                 {
65                     cookie[j].flip();
66                 }
67             }
68         }
69         cout << result << endl;
70     }
71  
72     return 0;
73 }

 ____________________总结的分割线____________________

  1. 原博有一个很妙的写法,permute = 2^N,循环 permute 次,每次又根据 (i & (1 << j)) 为真来确定特定要翻转的煎饼,这样,用二重循环加一个if判断就可以代替任意N重循环。【手动插入“你太强啦”表情包】
  2. bitset是个好东西,尖括号里写的不是数据类型,而是二进制的位数。
  3. 原博的写法是先定义了 int i,j ,以后的每次循环都直接用,和我的习惯不一样。我照着原博代码写的时候就发现了一个问题,经过测试如下:
     1 #include <iostream> 
     2 using namespace std;
     3 
     4 int main() {
     5     int i;
     6     for (i = 0; i < 3; i++) {
     7         for (i = 0; i < 5; i++) {
     8             cout << i;  //-->01234
     9         }
    10     }
    11     return 0;
    12 }
     1 #include <iostream> 
     2 using namespace std;
     3 
     4 int main() {
     5     for (int i = 0; i < 3; i++) {
     6         for (int i = 0; i < 5; i++) {
     7             cout << i; //-->012340123401234
     8         }
     9     }
    10     return 0;
    11 } 

    因此决定以后还是直接在for循环内定义变量,虽然麻烦点,但是减少了出错概率,以及不用想那么多变量名。

2.1搜索的习题做完啦,开始做贪心^ ^

[转] AOJ 0525 Osenbei《挑战程序设计竞赛(第2版)》练习题答案