首页 > 代码库 > [转] 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 }
____________________总结的分割线____________________
- 原博有一个很妙的写法,permute = 2^N,循环 permute 次,每次又根据 (i & (1 << j)) 为真来确定特定要翻转的煎饼,这样,用二重循环加一个if判断就可以代替任意N重循环。【手动插入“你太强啦”表情包】
- bitset是个好东西,尖括号里写的不是数据类型,而是二进制的位数。
- 原博的写法是先定义了 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版)》练习题答案
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。