[ARC106E] Medals 题解

题目链接

题目链接

题目解法

感觉不难啊，怎么想到网络流和 \(hall\) 定理后面就屁都没想到呢

首先一眼网络流
先二分答案
考虑一个朴素的建图方法是：把每个人拆成 \(k\) 个点，然后往在的天连边，跑最大流，满流即合法

可以发现，跑网络流对这道题还说没有必要，因为只要判是否有完美匹配
不难想到 \(hall\) 定理，定理具体自己查

观察到 \(n\le 18\)，所以考虑状压状物
考虑每个点拆分成的 \(k\) 个点连出去的边都相同，所以如果只包含了 \(i\) 拆分出去的一个点，一定不够极限，所以需要枚举的点集要么不包含 \(i\) 拆分的点，要么包含所有的 \(k\) 个点

当前天是邻边当且仅当它包含的人的集合与枚举的人的集合有交集
可以想到在补集上做文章，即补集与枚举的人的集合不交，不难发现可以高位前缀和优化

时间复杂度 \(O(n2^n\log nk)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=18;
int n,k,a[N],f[1<<N];
int main(){
    n=read(),k=read();
    F(i,0,n-1) a[i]=read();
    int l=0,r=4000000;
    while(l<r-1){
        int mid=(l+r)>>1;
        F(S,0,(1<<n)-1) f[S]=0;
        F(i,1,mid){
            int st=0;
            F(j,0,n-1) if(~((i-1)/a[j])&1) st|=1<<j;
            f[st]++;
        }
        F(i,0,n-1) F(S,0,(1<<n)-1) if(!(S>>i&1)) f[S^1<<i]+=f[S];
        bool flg=1;
        F(i,0,(1<<n)-1) if(__builtin_popcount(i)*k>mid-f[(1<<n)-1-i]){ flg=0;break;}
        if(!flg) l=mid;
        else r=mid;
    }
    printf("%d\n",r);
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}