首页 > 代码库 > (DFS、bitset)AOJ-0525 Osenbei
(DFS、bitset)AOJ-0525 Osenbei
题目地址
简要题意:
给出n行m列的0、1矩阵,每次操作可以将任意一行或一列反转,即这一行或一列中0变为1,1变为0。问通过任意多次这样的变换,最多可以使矩阵中有多少个1。
思路分析:
行数比较小,先不考虑对列的操作,将行数的所有情况举出来最多2^10种情况。对于已经固定了对行进行怎样的操作后,这种情况下对列的最优操作就是对每一列,如果此时1比0多就不变,不然就反转。实现在代码中就是一个for循环扫一遍。注意本题反转行、列采用bitset中的flip函数是非常合适的,因为每个数也不是1就是0,恰好符合位数。
参考代码:
1 #include <iostream> 2 #include <bitset> 3 #include <algorithm> 4 5 using namespace std; 6 bitset<10000>bing[10];//建立bitset数组储存数据,方便反转行列 7 int main() 8 { 9 int hang,lie,i,j,ci,k,re=0; 10 bool tem; 11 while(cin>>hang>>lie&&hang>0) 12 { 13 re=0; 14 for(i=0;i<hang;i++) 15 { 16 for(j=0;j<lie;j++) 17 { 18 cin>>tem; 19 bing[i][j]=tem; 20 } 21 } 22 ci=1<<hang;//使用二进制的遍历已经是见了很多次的技巧了 23 for(i=0;i<ci;i++) 24 { 25 for(j=0;j<hang;j++) 26 { 27 if(i&(1<<j)) 28 { 29 bing[j].flip();//进行反转 30 } 31 } 32 int an=0,anhe=0; 33 for(j=0;j<lie;j++) 34 { 35 an=0; 36 for(k=0;k<hang;k++) 37 { 38 if(bing[k][j]) 39 { 40 an++; 41 } 42 } 43 an=max(an,hang-an); 44 anhe+=an; 45 } 46 re=max(anhe,re); 47 for(j=0;j<hang;j++) 48 { 49 if(i&(1<<j)) 50 { 51 bing[j].flip();//再转回来 52 } 53 } 54 } 55 cout<<re<<"\n"; 56 } 57 return 0; 58 }
(DFS、bitset)AOJ-0525 Osenbei
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。