CF1105E Helping Hiasat

Codeforces

Luogu

分析

我们以 1 操作为界,划分出若干个块,那么每块只能有一个 id。

预处理出每个好友在哪些块中访问过。可以发现,如果两个好友在同一个块中出现过,则她们不能都高兴。

于是将在同一个块中出现过的好友连边,问题变为求最大独立集。

大力 random_shuffle 即可。如果虚的话可以加个卡时。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <map>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,M=40+10;

int n,m,tim=0,cnt=0;
int p[M];
map<string,int> id;
bitset<N> bit[M];
bitset<M> G[M],now;

inline int calc() {
    now.reset();
    for (re int i=1;i<=m;++i) {
        if ((now&G[p[i]]).any()) continue;
        now[p[i]]=1;
    }
    return now.count();
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) {
        int op=read();
        if (op==1) ++tim;
        else {
            string s; cin>>s;
            if (!id.count(s)) id[s]=++cnt;
            bit[id[s]][tim]=1;
        }
    }
    for (re int i=1;i<=m;++i)
        for (re int j=i+1;j<=m;++j)
            if ((bit[i]&bit[j]).any()) G[i][j]=G[j][i]=1;
    int ans=0;
    for (re int i=1;i<=m;++i) p[i]=i;
    while (1.0*clock()/CLOCKS_PER_SEC<1.8)
        random_shuffle(p+1,p+m+1),ans=max(ans,calc());
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 10 月 30 日 04 : 13 PM

1 条评论

  1. smy

    随 机 算 法

发表评论