自动搬运

查看原文

来自洛谷，原作者为

	matrixPower &Kevin1211 || 一只鸡块 || 坐标 CQ || 蛋五双修（最近主玩五）|| 关注被清了，原因：JC，要壶关的私信，无条件，先到先得

搬运于2025-08-24 22:00:59，当前版本为作者最后更新于2025-04-04 11:15:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

黄题中的红题。

第一问很简单开桶记录一下就行了。

第二问也很简单，暴力 dfs 搜索每个选举人是否弃权，最后继续开桶记录就行了。

时间复杂度 $O(2^mnm)<5\times{10}^7$，时限 3s，可过。

#include<bits/stdc++.h>
#define endl '\n'
#define lowbit(x) (x)&(-x)
using namespace std;

typedef double db;
typedef long long ll;
typedef __int128 III;
const db eqs=1e-6;
const int inf=1e9;
void ll_cmax(ll &a,ll b){a=a>b?a:b;}
void ll_cmin(ll &a,ll b){a=a<b?a:b;}
void int_cmax(int &a,int b){a=a>b?a:b;}
void int_cmin(int &a,int b){a=a<b?a:b;}
bool db_eq(db a,db b){return fabs(a-b)<eqs;}
bool number(char ch){return ch>='0' && ch<='9';}
bool lowerchar(char ch){return ch>='a' && ch<='z';}
int sqlong(int n){int sq=sqrt(n)+1;return min(sq,n);}

const int MAXN=100+5;
int a[MAXN][MAXN],n,m,k,x[MAXN],b[MAXN],ans=inf;

void dfs(int st,int cnt)
{
	if(st>m)
	{
		memset(x,0,sizeof(x));
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(b[a[i][j]])
				{
					x[a[i][j]]++;
					break;
				}
			}
		}
		int maxn=-1,id;
		for(int i=1;i<=m;i++)
		{
			if(x[i]>maxn) maxn=x[i],id=i;
		}
		if(id==k)
		{
			int_cmin(ans,cnt);
		}
		return ;
	}
	if(st==k)
	{
		b[st]=1;
		dfs(st+1,cnt);
		b[st]=0;
		return ;
	}
	b[st]=1;
	dfs(st+1,cnt);
	b[st]=0;
	dfs(st+1,cnt+1);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) cin>>a[i][j];
		x[a[i][1]]++;
	}
	int maxn=-1,id;
	for(int i=1;i<=m;i++)
	{
		if(x[i]>maxn) maxn=x[i],id=i;
	}
	cout<<id<<endl;
	memset(x,0,sizeof(x));
	dfs(1,0);
	cout<<ans<<endl;
	return 0;
}
//by Matrix_Power