資源限制
時間限制：1.0s 記憶體限制：256.0MB
問題描述
《審美的歷程》課上有n位學生，帥老師展示了m幅畫，其中有些是梵高的作品，另外的都出自五歲小朋友之手，老師請同學們分辨哪些畫的作者是梵高，但是老師自己并沒有答案，因為這些畫看上去都像是小朋友畫的……老師只想知道，有多少對同學給出的答案完全相反，這樣他就可以用這個資料去揭穿披著皇帝新衣的抽象藝術了（支持帥老師^_^），
答案完全相反是指對每一幅畫的判斷都相反，
輸入格式
第一行兩個數n和m，表示學生數和圖畫數；
接下來是一個n*m的01矩陣A：
如果aij=0，表示學生i覺得第j幅畫是小朋友畫的；
如果aij=1，表示學生i覺得第j幅畫是梵高畫的，
輸出格式
輸出一個數ans：表示有多少對同學的答案完全相反，
樣例輸入
3 2
1 0
0 1
1 0
樣例輸出
2
樣例說明
同學1和同學2的答案完全相反；
同學2和同學3的答案完全相反；
所以答案是2，
資料規模和約定
對于50%的資料：n<=1000；
對于80%的資料：n<=10000；
對于100%的資料：n<=50000，m<=20，
暴力法只能獲得70分，需要用map存盤資料，并將學生的答案處理為二進制數（異或取反）或字串，
1、二進制數（異或取反）
#include<iostream> #include<map> using namespace std; int main() { map<int,int>a; //用map存盤資料，it->first表示將n位學生的答案視為二進制數以十進制數存盤，it->second表示該種答案的相同個數 int n,m; cin>>n>>m; for(int i=0;i<n;i++) { int num=0; int x; for(int j=0;j<m;j++) { cin>>x; num=(num<<1)+x; } a[num]++; } int sum=0,maxn=(1<<m)-1,mid=maxn/2; //maxn為m位全為1的二進制數 for(map<int,int>::iterator it=a.begin();it!=a.end();it++) { int x=it->first; if(x>mid) //[0,mid]中的任意一個數x與maxn進行異或運算的值一定在(mid,maxn]中，所以遍歷0-maxn/2即可(map默認按key值從小到大排序) { break; } int num=x^maxn; //與maxn進行異或運算即可取反 sum+=a[num]*it->second; //當前答案取反的相同個數*當前答案的相同個數 } cout<<sum<<endl; return 0; }
2、字串
#include<iostream> #include<map> using namespace std; int main() { map<string,int>num; //用map存盤資料，it->first表示n位學生答案的字串形式，it->second表示該種答案的相同個數 int m,n; cin>>n>>m; for(int i=0;i<n;i++) { string s=""; char x; for(int j=0;j<m;j++) { cin>>x; s+=x; } num[s]++; } int sum=0; for(map<string,int>::iterator it=num.begin();it!=num.end();it++) { string s=""; for(int i=0;i<m;i++) { if(it->first[i]=='0') s+='1'; else s+='0'; } //將答案取反 sum+=num[s]*it->second; //當前答案取反的相同個數*當前答案的相同個數 } cout<<sum/2<<endl; //重復計算了所以除以2 return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/6720.html
標籤：其他