<span>省选模拟13 题解</span>
A. 同桌的你
每个人渴望与一个人当同桌。
容易发现这个关系形成内向基环树森林。
问题转化为求基环树森林的最大匹配。
任意选一条环上的边，分别尝试该边为匹配边、非匹配边即可。
B. 大水题
一个常用的但想不到的东西：将每种颜色出现次数的差值为定值，转化为对颜色序列差分后相等。
然后暴力的做法是枚举2^8，表示答案出现在指定的颜色集合中，分别将差分数组插入、查询哈希表即可。
下面是一个优化：
容易发现可行的颜色集合对于同一个时刻只有不超过8种。
对于每一个左端点，随着右端点的右移，区间颜色集合改变次数不超过8次。
当右端点右移时，给区间颜色集合需要改变的，添加新的一种颜色。
具体实现方式是维护一个$lst$数组，表示第$i$种颜色的最后一次出现位置。
可以参考代码。
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 }
C. 佛罗里达
刚开始想的是只需要判定是否为二分图，然后想用并查集来维护这个东西，然后发现有些东西没法搞。
考虑枚举答案$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$中只含有黑点，特判这种情况就可以了。
投递荣耀等公司10个岗位
