【学习笔记】NOIP爆零赛8

trash ,但不完全是trash

$t1$考了一个神奇的结论还没有证明，$t2$玩了一些复杂度的花样，$t3$稍微阳间一点，是一个并不复杂的容斥，如果放在$t1$可能更合适一些，$t4$就是在原题的基础上改了一下然后就成了一道毒瘤数据结构题，

$t1$总之感觉还是出的很烂，所以就不管它了

$t2$暴力能过，很显然留在最后补

$t3$赛时过了，那没什么了

所以只要胡一下$t4$就好是吗

补数据结构题是最痛苦的

最小生成树

首先有一道原题：[HNOI2010]城市建设 ，于是你不需要用这道题的任何性质就可以得到$80pts$。

这就是场上的最优解了，毕竟正解的思路非常人能及，而且也就少了$20pts$而已，不过唯一的缺点是码量有点大

不过正解的话从链入手似乎非常合理，但是只有$40pts$，最后的数据结构维护还是非常难想，所以这道题的性价比真的不高啊

对于链的情况，可以看成是$[1,n]$的若干不相交区间$[l_i,r_i]$通过与$0$节点连边从而联通，因此在用线段树维护区间信息时，只用处理中间两个连通块。如果都不与$0$联通，那么不合法；如果都与$0$联通，不需要花费代价就可以合并，如果只有一边与$0$联通，那么需要花费中间那条二类边的代价。结合画图不难理解。

搞清楚链的情况后，我们就有了$40pts$ 好少啊，考场上思考数据结构完全没有动力啊

推广到一般情况，我们只需要一步：求出一棵树对应的等效链 。这看起来非常不可思议，但是如果你把两棵树合并看成两条链合并，然后套用链的维护方式就不难理解了。

这个地方很容易给人一个误解，就是直接将结论扩展好像可以一步到位。

事实上，我们还需要下一个结论：假设当前加的边是$u,v$，其分属于连通块$S$,$T$，那么我们可以把$u,v$这条边等效成任意$u^{\prime }\in S,v^{\prime }\in T$之间的连边，当然边权不变。其原因在于，如果$u,v$这条边在$MST$中，那么此时$S,T$一定是联通的（假设不是联通的，那么跑$\text{kruskal}$算法的流程就会出现矛盾）。因此，我们可以把一棵树 彻底等效成一条链 。

基于上述观察，我们不难得到将所有的二类边构成的森林等价转化成若干条链，然后用线段树维护答案的做法。

复杂度$O(n\log n)$。考场上能想到标算还是挺$nb$的

最后还是补一下$t2$。代码就算了，能过的代码为什么要优化呀

二进制的世界

用暴力来优化暴力

正解不如暴力

将$16$位分为两部分：前$8$位和后$8$位。相信大家都猜到复杂度了吧，不过用乱搞优化位运算的确令人烦躁

设$f_{i,j}$表示前$8$位为$i$的数，与某个后$8$为是$j$的数进行位运算，后$8$位结果的最大值以及方案数。

那么加入一个数$x$的时候，设它的前$8$位为$a$，后八位为$b$，只需要枚举$j$，用$joptb$更新所有$f_{a,j}$。查询$x$的时候，用所有$(iopta)<<8|f_{i,b}$更新答案。

复杂度$O(n\sqrt{m})$。

代码出奇好写

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N=1e5+5;
int n,type,a[N],f[1<<8][1<<8],g[1<<8][1<<8];
string op;
int calc(int x,int y){if(op[0]=='x')return x^y;else if(op[0]=='o')return x|y;return x&y;
}
void ins(int x){int a=x>>8,b=x^(a<<8);for(int i=0;i<1<<8;i++){if(calc(b,i)>f[a][i]){f[a][i]=calc(b,i);g[a][i]=1;}else if(calc(b,i)==f[a][i]){g[a][i]++;}}
}
pair<int,int>solve(int x){int a=x>>8,b=x^(a<<8),res=0,res2=0;for(int i=0;i<1<<8;i++){if(g[i][b]&&((calc(a,i)<<8)|f[i][b])>res){res=((calc(a,i)<<8)|f[i][b]);}} for(int i=0;i<1<<8;i++){if(g[i][b]&&((calc(a,i)<<8)|f[i][b])==res){res2+=g[i][b];}}return {res,res2};
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>op>>type;for(int i=1;i<=n;i++)cin>>a[i];ins(a[1]);for(int i=2;i<=n;i++){pair<int,int>res=solve(a[i]);if(!type){cout<<res.fi<<"\n";}else {cout<<res.fi<<" "<<res.se<<"\n";}ins(a[i]);}
}