trash ,但不完全是trash
t1t1t1考了一个神奇的结论还没有证明,t2t2t2玩了一些复杂度的花样,t3t3t3稍微阳间一点,是一个并不复杂的容斥,如果放在t1t1t1可能更合适一些,t4t4t4就是在原题的基础上改了一下然后就成了一道毒瘤数据结构题,
t1t1t1总之感觉还是出的很烂,所以就不管它了
t2t2t2暴力能过,很显然留在最后补
t3t3t3赛时过了,那没什么了
所以只要胡一下t4t4t4就好是吗
补数据结构题是最痛苦的
最小生成树
首先有一道原题:[HNOI2010]城市建设 ,于是你不需要用这道题的任何性质就可以得到80pts80pts80pts。
这就是场上的最优解了,毕竟正解的思路非常人能及,而且也就少了20pts20pts20pts而已,不过唯一的缺点是码量有点大
不过正解的话从链入手似乎非常合理,但是只有40pts40pts40pts,最后的数据结构维护还是非常难想,所以这道题的性价比真的不高啊
对于链的情况,可以看成是[1,n][1,n][1,n]的若干不相交区间[li,ri][l_i,r_i][li,ri]通过与000节点连边从而联通,因此在用线段树维护区间信息时,只用处理中间两个连通块。如果都不与000联通,那么不合法;如果都与000联通,不需要花费代价就可以合并,如果只有一边与000联通,那么需要花费中间那条二类边的代价。结合画图不难理解。
搞清楚链的情况后,我们就有了40pts40pts40pts 好少啊,考场上思考数据结构完全没有动力啊
推广到一般情况,我们只需要一步:求出一棵树对应的等效链 。这看起来非常不可思议,但是如果你把两棵树合并看成两条链合并,然后套用链的维护方式就不难理解了。
复杂度O(nlogn)O(n\log n)O(nlogn)。考场上能想到标算还是挺nbnbnb的
最后还是补一下t2t2t2。代码就算了,能过的代码为什么要优化呀
二进制的世界
用暴力来优化暴力
正解不如暴力
将161616位分为两部分:前888位和后888位。相信大家都猜到复杂度了吧,不过用乱搞优化位运算的确令人烦躁
设fi,jf_{i,j}fi,j表示前888位为iii的数,与某个后888为是jjj的数进行位运算,后888位结果的最大值以及方案数。
那么加入一个数xxx的时候,设它的前888位为aaa,后八位为bbb,只需要枚举jjj,用joptbj\ opt\ bj opt b更新所有fa,jf_{a,j}fa,j。查询xxx的时候,用所有(iopta)<<8∣fi,b(i\ opt\ a)<<8|f_{i,b}(i opt a)<<8∣fi,b更新答案。
复杂度O(nm)O(n\sqrt{m})O(nm)。
代码出奇好写
#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]);}
}