题解：CF1288D Minimax Problem

Nt_Tsumiki · 2024-11-06 22:52:41 · 题解

提供一个爆标的做法。

常规的做法是二分答案然后对于每个 i 用 01 串去表示状态，看是否存在并集为全集的状态对。

这样的话复杂度带个 \log 非常不美观，我们考虑给他优化掉。

对于这种问题我们有一个比较经典的做法是把更新答案这一步的复杂度给他摊掉。

我们考虑维护一个 id_{sta} 表示有哪些状态包含这个状态 sta，不难发现由于我们只在意 sta 是否被包含，所以我们只用记录任意一个数即可。

那么这样的话每个 id_{sta} 只会最多更新一次，又因为一个状态 sta 被标记了，那么它所有的子集都会被标记，我们从大到小枚举去暴力更新状态，遇到被标记的就跳，就可以把复杂度摊掉了。

因为还有转移和排序的复杂度，所以复杂度是 O(nm\log nm+m2^m) 的。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

#define N 300005

inline int R() {
    int x=0; bool f=0; char c=getchar();
    while (!isdigit(c)) f|=(c=='-'),c=getchar();
    while (isdigit(c)) x=x*10+c-'0',c=getchar();
    return f?-x:x;
}

template<typename T>
void W(T x,int op=0) {
    if (x<0) return putchar('-'),W(-x,op);
    if (x>9) W(x/10); putchar(x%10+'0');
    if (op) putchar(op==1?' ':'\n');
}

using namespace std;
int n,m,cnt,a[N][8],vis[1<<8],sta[N];
struct Tmp { int x,y; } p[8*N];

void dfs(int sta,int id) {
    vis[sta]=id;
    for (int i=sta;i&-i;i-=(i&-i))
        if (!vis[sta-(i&-i)]) dfs(sta-(i&-i),id);
}

int main() {
    n=R(),m=R();
    for (int i=1;i<=n;i++)
        for (int j=0;j<m;j++)
            a[i][j]=R(),p[++cnt]={i,j};
    sort(p+1,p+cnt+1,[](Tmp tmp1,Tmp tmp2) {
        return a[tmp1.x][tmp1.y]>a[tmp2.x][tmp2.y];
    });
    vis[0]=1;
    for (int i=1;i<=cnt;i++) {
        auto [x,y]=p[i]; sta[x]|=(1<<y);
        if (vis[((1<<m)-1)^sta[x]]) {
            W(x,1),W(vis[((1<<m)-1)^sta[x]],2);
            return 0;
        }
        if (!vis[sta[x]]) dfs(sta[x],x);
    }
    return 0;
}