<span>省选模拟13 题解</span>

每个人渴望与一个人当同桌。

容易发现这个关系形成内向基环树森林。

问题转化为求基环树森林的最大匹配。

任意选一条环上的边，分别尝试该边为匹配边、非匹配边即可。

 1 #include<bits/stdc++.h>
 2 #define ull unsigned long long
 3 using namespace std;
 4 const int N=1e5+7;
 5 int n,k;
 6 pair<int,int> f[N],t[10];
 7 struct Hash{
 8     const static int p=2333333;
 9     int tot,head[p],nxt[p],val[p];
10     ull to[p];
11     inline int& operator [](ull x){
12         int y=x%p;
13         for(int i=head[y];i;i=nxt[i]) if(to[i]==x) return val[i];
14         nxt[++tot]=head[y]; to[head[y]=tot]=x;
15         return val[tot]=-1;
16     }
17 }mp;
18 int lst[10],cnt[10][N];
19 ull pw[10];
20 inline int calc(int s,int t){
21     int r=0;
22     for(int i=1;i<=8;++i) if(cnt[i][t]-cnt[i][s]) r|=1<<i-1;
23     return r;
24 }
25 inline ull solve(int x,int s){
26     ull r=0; int fir=8;
27     for(int i=1;i<=8;++i) if(s>>i-1&1){ fir=i; break; }
28     for(int i=fir+1;i<=8;++i) if(s>>i-1&1) r=r*133331+cnt[i][x]-cnt[fir][x];
29     return r+s*pw[8];
30 }
31 inline int read(register int x=0,register char ch=getchar(),register int f=0){
32     for(;!isdigit(ch);ch=getchar()) f=ch=='-';
33     for(; isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
34     return f?-x:x;
35 }
36 int main(){
37     n=read(); k=read();
38     for(int i=1;i<=n;++i) f[i].first=read(),f[i].second=read();
39     sort(f+1,f+n+1); int ans=-1;
40     for(int i=pw[0]=1;i<=8;++i) pw[i]=pw[i-1]*133331;
41     for(int i=1;i<=n;++i) ++cnt[f[i].second][i];
42     for(int i=1;i<=8;++i) for(int j=1;j<=n;++j) cnt[i][j]+=cnt[i][j-1];
43     mp[0]=f[1].first;
44     for(int i=1;i<=n;++i){
45         for(int j=lst[f[i].second];j<i;++j){
46             int x=calc(j,i-1),t=x|(1<<f[i].second-1); mp[solve(j,x)]=-1;
47             int &val=mp[solve(j,t)]; if(val==-1) val=f[j+1].first;
48         }
49         lst[f[i].second]=i;
50         for(int j=1;j<=8;++j) t[j]=make_pair(lst[j],j);
51         sort(t+1,t+9); reverse(t+1,t+9);
52         for(int j=1,now=0;j<=8&&t[j].first;++j){
53             now|=1<<t[j].second-1;
54             if(j>=k&&mp[solve(i,now)]!=-1) ans=max(ans,f[i].first-mp[solve(i,now)]);
55         }
56         mp[0]=f[i+1].first;
57     }
58     printf("%d\n",ans);
59     return 0;
60 }

刚开始想的是只需要判定是否为二分图，然后想用并查集来维护这个东西，然后发现有些东西没法搞。

考虑枚举答案$da$,$db$，满足$da<db$。

对于边权$w<=da$，可以忽略。

对于边权$w>db$，要将所连的点放入不同的集合。

对于边权$da<w<=db$，所连的点应满足二者都在$B$中，或二者一个在$A$中，而另一个在$B$中。

并查集维护前两种情况是简单的，但是对于第三种就伪了。

注意第三种情况可以转化为$u,v$至少一个在$B$中，这一步是考试时没想到的。

于是问题可以用2-sat解决，定义选$B$为$1$，那么情况二对应着$u$ $xor$ $v=1$，情况三对应着$u$ $or$ $v=1$。

容易发现对于确定的$db$，一个$da$是否成立具有单调性，于是可以二分判断。

还有很大的优化空间。

这里抛出一个结论：只需要考虑$db$对应最大生成树上的边和 $A$与$B$分别对应最大生成树上的黑点和白点。

考虑首先生成最大生成树并黑白染色。

如果集合$B$中同时含有黑点和白点，那么如果$db$不为最大生成树上边，原图会形成一个偶环，这样环上一定存在一条边使得这条边权大于$db$，所以$db$为最大生成树上的边。

否则，可以认为集合$B$中只含有黑点，特判这种情况就可以了。

省选模拟13 题解

A. 同桌的你

B. 大水题

C. 佛罗里达