共同兴趣 T561273

​ 那么模拟题目，我们可以分析出以下我们要实现的步骤：

​ 1.对于任意一个学生，寻找除自己以外的学生与自己之间的公共感兴趣有多少项

​ 2.只有公共感兴趣的最多的学生可以得到邀请， 所以我们用一个数组保留最大值。

​ 3.如果小O≥任意一人的公共感兴趣活动，则答案加一;

​ 4.只有将0改成1，才能有更优的答案。（反之如果全是1，则无需修改）。遍历每一个把0改成1的可能，寻找最大的答案。

将步骤以代码呈现出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std ;
using ll = long long ; 
//const int N = 100000 + 10  ; 
//500 * 500 5e4 * 500
const int N = 500 + 10  ;
int a[N][N];
int res[N][N]	;//res[][]，表示以1为对象，对n个人的公共活动数
int max_count[N] ;  //表示每一个人的最大公共活动数
void solve(){
	int ans = 0 ; 
	int n ,m ; 
	cin >> n >> m ; 
	for(int i = 1 ; i<= n ; i++){
		for(int j = 1 ; j<= m ; j++)cin >> a[i][j] ; //输入数据 
	}
	//判断每一个人的共同爱好
	for(int i =1 ; i<= n ; i++){//i指的是对象
		for(int j = 1 ; j<= n ; j++){//j表示的是其它人
			if(i==j)continue ; //跳过自己 
			for(int l = 1 ; l <= m ; l++ ){//每一项
				if(a[i][l] == a[j][l] && a[i][l] ==1 )res[i][j]++ ; //i-j的共同爱好 
			}
		}
	}
	for(int i =1 ; i<= n ; i++){
		for(int j =1 ; j<= n ; j++){//从i-j的共同爱好 
		if(i==j)continue ; //把自己跳了 
//			cout << res[i][j] << ' '; 
			max_count[i] = max(max_count[i] , res[i][j]); //预处理最大值 
		}//预处理出来最大值即可 
//		cout<< '\n' ;
	}
	for(int l = 1 ; l <= m ; l++){
		if(a[1][l]==0){//我们只讨论可能会产生最大值的 
			int count1 = 0 ; 
			for(int j = 2 ; j<= n ; j++){//忽略1本身
				if(a[j][l] == 1 )res[1][j]++ ; //如果其他项此项为1，则以1为起点，以j为终点的共同爱好加一
//				cout << res[1][j] << ' ' << max_count[j] << ' '  ;
				if(res[1][j] >= max_count[j])count1 ++;//如果>=最大值，则count++ 
			}
			//接下来最后判断最多的是谁就行
//			cout << '\n' ; 
			ans=max(count1,ans) ; //更新最大值
			
			for(int j = 2 ; j<= n ; j++){
				if(a[j][l] == 1 )res[1][j]-- ;//回溯，防止答案被污染 
			}
		}
	}	
	 cout << ans ; 
	
 }
	int main(){
	ios::sync_with_stdio(false),cin.tie(0)  ;   cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    } 
    return 0; 
}