P4520 [COCI 2017/2018 #4] Izbori 题解

· · 题解

传送门

黄题中的红题。

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

第二问也很简单，暴力 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