关键词:
来自 码农场 ? 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搜索的习题做完啦,开始做贪心^ ^
aoj0525osenbei(代码片段)
おせんべい問題IOI製菓では,創業以来の伝統の製法で煎餅(せんべい)を焼いている.この伝統の製法は,炭火で一定時間表側を焼き,表側が焼けると裏返して,炭火で一定時間裏側を焼くというものである.この伝統を守... 查看详情
aoj0033ball题解《挑战程序设计竞赛》
题目:Aizu-0033 思路:二进制枚举,用了昨天学到的2^N以及与运算方法枚举。1#include<iostream>2#include<vector>3#include<algorithm>45usingnamespacestd;67intn;8intball[10];9vector<int>l;10vector<int> 查看详情
挑战程序设计竞赛2.1习题:osenbeiaizu-0525(代码片段)
おせんべい問題IOI製菓では,創業以来の伝統の製法で煎餅(せんべい)を焼いている.この伝統の製法は,炭火で一定時間表側を焼き,表側が焼けると裏返して,炭火で一定時間裏側を焼くというものである.この伝統を守... 查看详情
挑战程序设计竞赛2.5它们其实都是“图”
【Summarize】 1.注意对图是否连通的判定 2.灵活运用边权取负的技巧 AOJ0189:ConvenientLocation/*给出一张无向图,现在求一个点,使得这个点到所有点的距离和最小输出这个点的编号和距离和*/#include<cstdio>#include<... 查看详情
骁龙电竞先锋赛中国赛,4月18日开启移动电竞赛事新篇章
...2022年4月18日正式开赛。中国赛设置了骁龙电竞先锋全民挑战赛(SnapdragonMobileChinaOpen)与骁龙电竞先锋精英邀请赛(SnapdragonMobileChallengeChina)两条赛线、四个赛季,全年总奖金预计达300万元人民币。秉承骁龙移... 查看详情
电竞行业“厮杀”正旺安德斯特电竞椅“护航”玩家
...朝阳行业,同时也是一种新的娱乐手段,电子竞技成为喜欢挑战和创新的年轻人的选择和被广大游戏爱好者所关注。1.png电竞行业在近几年发展迅猛,趋势有点像以前的智能手机和电脑。根据相关可靠行业内调查人士宣称,中国电竞行... 查看详情
0525泰山版java开发手册
六.集合处理 4.在使用java.util.stream.Collectors类的toMap()方法转为Map集合时,一定要注意当value为null时会抛NPE异常NPE:NullPointerException(); 5.ArrayList的subList结果不可强转成ArrayList,否则会抛出ClassCastException异常subList指的是返回一个... 查看详情
aoj2226merrychristmas
MerryChristmasTimeLimit:8sec,MemoryLimit:65536KBProblemJ: MerryChristmasInternationalChristmasPresentCompany(ICPC)isacompanytoemploySantaanddeliverpresentsonChristmas.ManyparentsrequestICPCtodeli 查看详情
poj1979poj3009aoj0033aoj0118[搜索类题目][0033贪心模拟]
/**POJ1979BFS*/#include<stdio.h>#include<string.h>#include<iostream>#include<queue>usingnamespacestd;constintN=20+5;intmp[N][N];intsx,sy;intn,m;intvis[3000];intdirx[]={0,1,0,-1 查看详情
whitebird(aoj2308)(代码片段)
原题如下:AngryBirdsisamobilegameofabigcrazeallovertheworld.Youwereconvincedthatitwasawasteoftimetoplaythegame,soyoudecidedtocreateanautomaticsolver.Youaredescribingaroutinethatoptimizesthewhitebird‘sstrat 查看详情
aoj0118
一、题意:有三种水果分别用,‘@‘,‘*‘,‘#‘三种符号表示,上下左右相连的同种水果被看做是一个区域,问一共有多少个区域 二、思路:用dfs去标记相连区域,然后遍历每个没有被标记的位置进行dfs 三、代码:#inclu... 查看详情
aoj2308whitebird(极限情况)(代码片段)
WhiteBirdTimeLimit:5sec,MemoryLimit:65536KBWhiteBirdAngryBirdsisamobilegameofabigcrazeallovertheworld.Youwereconvincedthatitwasawasteoftimetoplaythegame,soyoudecidedtocreateanautomaticsolver.Youaredes 查看详情
aoj0005gcdandlcm(代码片段)
Writeaprogramwhichcomputesthegreatestcommondivisor(GCD)andtheleastcommonmultiple(LCM)ofgiven a and b.InputInputconsistsofseveraldatasets.Eachdatasetcontains a and b 查看详情
aoj0033
Ball可以用dfs,不过发现用一个循环就可以搞定。 1#include<iostream>2usingnamespacestd;3inta[11],n;4intmain(){5cin>>n;6while(n--){7for(inti=0;i<10;i++)cin>>a[i];8intc=0,b=0,flag=1;9for(inti= 查看详情
aoj0121:sevenpuzzlebfs
From:AOJ0121思路:与前几题的bfs不同,这次的bfs没有明确的移动对象,看似任意一个数都可以当成对象移动。这时我们只需要抓住一个格子就行,比如我们把0作为移动对象,那么0在地图中漫游所有的格子得到的肯定就是问题的解... 查看详情
aoj0009primenumber
题意:给出n,求不大于n的素数有多少个。算法:先用线性时间复杂度的筛法打素数表,对于每个输入统计不超过的素数个数。#include<cstdio>intp[100010];boolnp[1000010];intcntp;voidSievePrime(intn){ for(inti=0;i<=n;++i)np[i]=true; np[0]=false,np[1]... 查看详情
aoj0121sevenpuzzle
7パズル7パズルは8つの正方形のカードとこれらのカードがぴたりと収まる枠で構成されています。それぞれ 查看详情
aoj0189(最短路)(代码片段)
1#include<iostream>2#include<cstdio>3#include<cmath>4#include<cstring>5#include<algorithm>6#include<queue>7#include<stack>8#include<vector>9#include< 查看详情