1、最大值
可以用FWT水过去，李巨写了FWT结果中途爆int了炸了几十分好像。
我乱搞了一下把除了大数据有or的搞出来然后90，还是蛮划算的。我yy的做法：
1、xor 字典树上贪心， 一开始我打了线性基，被自己蠢哭了。
&和|
用sum[i]表示i中二进制位为1的位置都是1的且不是i的数是否存在。我乱搞从大到小地把一个一个去掉处理的，FWT也可以处理这个，复杂度是一样的。
2、&
答案一定是a中的某个数，枚举a中的每个数a[i]看sum[a[i]]是否存在即可。
3、|
枚举a中每个数，从高位到低位贪心看它能|出来的最大数。用一个类似前缀和思想的限制，具体说，到某一位如果a[i]是0，看目前的限制|这一位的1的sum存不存在，存在就把目前的限制|这一位的1。
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int N=1e5+7;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int T,n,c,a[N],mxx,b[30],sum[1048579],cnt[1048579];
20
21 template<typename T>void read(T &x) {
22 char ch=getchar(); x=0; T f=1;
23 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
24 if(ch=='-') f=-1,ch=getchar();
25 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
26 }
27
28 int rt,ch[N*25][2],tot;
29 void insert(int v) {
30 int x=rt;
31 For(i,0,20) {
32 int c=((v&(1<<i))!=0);
33 if(!ch[x][c]) {
34 ch[x][c]=++tot;
35 ch[tot][0]=ch[tot][1]=0;
36 }
37 x=ch[x][c];
38 }
39 }
40
41 int qry(int v) {
42 int x=rt,rs=0;
43 For(i,0,20) {
44 if(v&(1<<i)) {
45 if(ch[x][0]) rs+=(1<<i),x=ch[x][0];
46 else x=ch[x][1];
47 }
48 else {
49 if(ch[x][1]) rs+=(1<<i),x=ch[x][1];
50 else x=ch[x][0];
51 }
52 }
53 return rs;
54 }
55
56 #define ANS
57 int main() {
58 #ifdef ANS
59 freopen("maximum.in","r",stdin);
60 freopen("maximum.out","w",stdout);
61 #endif
62 read(T);
63 while(T--) {
64 read(n); read(c);
65 For(i,1,n) { read(a[i]); if(a[i]>mxx) mxx=a[i]; }
66 if(n<=1000) {
67 int ans=0;
68 For(i,1,n) For(j,i+1,n) {
69 if(c==1) ans=max(ans,(a[i]&a[j]));
70 else if(c==2) ans=max(ans,(a[i]^a[j]));
71 else ans=max(ans,(a[i]|a[j]));
72 }
73 printf("%d
",ans);
74 }
75 else if(mxx<=1024) {
76 int ans=0;
77 For(i,0,1024) cnt[i]=0;
78 For(i,1,n) cnt[a[i]]++;
79 For(i,0,1024) if(cnt[i]) {
80 if(cnt[i]>=2) {
81 if(c==1) ans=max(ans,(i&i));
82 else if(c==2) ans=max(ans,(i^i));
83 else ans=max(ans,(i|i));
84 }
85 For(j,i+1,1024) if(cnt[j]) {
86 if(c==1) ans=max(ans,(i&j));
87 else if(c==2) ans=max(ans,(i^j));
88 else ans=max(ans,(i|j));
89 }
90 }
91 printf("%d
",ans);
92 }
93 else {
94 if(c!=2) {
95 memset(cnt,0,sizeof(cnt));
96 memset(sum,0,sizeof(sum));
97 int up=mxx;
98 For(i,1,n) {
99 cnt[a[i]]++;
100 For(j,0,20) if(a[i]&(1<<j))
101 sum[a[i]^(1<<j)]=1;
102 }
103 Rep(i,up,0) if(sum[i]) {
104 For(j,0,20) if(i&(1<<j))
105 sum[i^(1<<j)]=1;
106 }
107 }
108 if(c==1) { //&
109 int ans=0;
110 For(i,1,n) if(cnt[a[i]]>=1||sum[a[i]]) {
111 if(a[i]>ans) ans=a[i];
112 }
113 printf("%d
",ans);
114 }
115 else if(c==2) { //^
116 int rs=0;
117 ch[rt][0]=ch[rt][1]=0;
118 For(i,1,n) insert(a[i]);
119 For(i,1,n) rs=max(rs,qry(a[i]));
120 printf("%d
",rs);
121 }
122 else { // |
123 int ans=0;
124 For(i,1,n) {
125 int pr=0;
126 Rep(j,20,0) if(!(i&(1<<j))) {
127 if(sum[pr|(1<<j)]||cnt[pr|(1<<j)]) pr|=(1<<j);
128 }
129 ans=max(ans,(a[i]|pr));
130 }
131 printf("%d
",ans);
132 }
133 }
134 }
135 Formylove;
136 }
2、独木桥
之前考过的题啊。二分套二分。
老张给的大数据有毒，大数据给错了，害我调了1个小时。。。
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int N=2e5+7;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int n,m,d;
20 int px[N],rak[N],p[N],lp[N],rp[N],mi,mx;
21
22 template<typename T>void read(T &x) {
23 char ch=getchar(); x=0; T f=1;
24 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
25 if(ch=='-') f=-1,ch=getchar();
26 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
27 }
28
29 int find(int ti,int pos) {
30 int rs=0;
31 int l=1,r=lp[0],tp=-1;
32 while(l<=r) {
33 int mid=((l+r)>>1);
34 if(lp[mid]-ti<=pos) tp=mid,l=mid+1;
35 else r=mid-1;
36 }
37 if(tp!=-1) rs+=tp;
38 l=1,r=rp[0],tp=-1;
39 while(l<=r) {
40 int mid=((l+r)>>1);
41 if(rp[mid]+ti<=pos) tp=mid,l=mid+1;
42 else r=mid-1;
43 }
44 if(tp!=-1) rs+=tp;
45 return rs;
46 }
47
48 #define ANS
49 int main() {
50 #ifdef ANS
51 freopen("bridge.in","r",stdin);
52 freopen("bridge.out","w",stdout);
53 #endif
54 read(n);
55 For(i,1,n) read(p[i]),px[i]=p[i];
56 sort(px+1,px+n+1);
57 For(i,1,n) rak[i]=lower_bound(px+1,px+n+1,p[i])-px;
58 For(i,1,n) {
59 read(d);
60 if(d) rp[++rp[0]]=p[i];
61 else lp[++lp[0]]=p[i];
62 mi=min(mi,p[i]); mx=max(mx,p[i]);
63 }
64 sort(rp+1,rp+rp[0]+1);
65 sort(lp+1,lp+lp[0]+1);
66 read(m);
67 For(i,1,m) {
68 int ti,k;
69 read(k); k++; read(ti);
70 k=rak[k];
71 int l=mi-ti,r=mx+ti,rs=-1;
72 while(l<=r) {
73 int mid=(((LL)l+r)/2);
74 if(find(ti,mid)>=k) rs=mid,r=mid-1;
75 else l=mid+1;
76 }
77 printf("%d
",rs);
78 }
79 Formylove;
80 }
81 /*
82 5
83 8 7 8 1 4
84 0 1 1 0 1
85 5
86 5 11
87 */
3、分组
把s从小到大排序，一个个考虑放进组中，这样可以保证新建组的时候放入的一定是组内最小数，结束一个组的时候放入的一定是组内最大数。
f[i][j][c]表示前i个数都分进了组，现在还有j个组没有结束，目前的代价是c的方案数。这样就可以过$sum s_i < 1000$的点了。
算代价的时候是分别在最小的地方-s[i]和在最大的地方+s[i]，显然代价单调不减，也就是虽然某个地方可能代价-s[i]但是后面一定会把这个代价加到非负。所以c一维最大只会到k。
虽然最大只会到k,但是最小可以小到非常小，所以这种算代价的方式不太优秀。利用差分的思想，$s_i-s_j=sum_{k=j}^{k<i}s_{k+1}-s_k$，这样就可以使代价始终为正，把第三维压到k了。
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int p=1e9+7;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int n,k,s[205];
20 LL f[2][205][1005],cf[205];
21
22 template<typename T>void read(T &x) {
23 char ch=getchar(); x=0; T f=1;
24 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
25 if(ch=='-') f=-1,ch=getchar();
26 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
27 }
28
29 #define ANS
30 int main() {
31 #ifdef ANS
32 freopen("group.in","r",stdin);
33 freopen("group.out","w",stdout);
34 #endif
35 read(n); read(k);
36 For(i,1,n) read(s[i]);
37 sort(s+1,s+n+1);
38 For(i,1,n) cf[i]=s[i+1]-s[i];
39 int o=0;
40 f[o][0][0]=1;
41 For(i,0,n-1) {
42 o^=1;
43 memset(f[o],0,sizeof(f[o]));
44 For(j,0,i) For(c,0,k) if(f[o^1][j][c]) {
45 if(c+cf[i]*j<=k) {
46 (f[o][j][c+cf[i]*j]+=f[o^1][j][c]*(j+1)%p)%=p;
47 if(j) (f[o][j-1][c+cf[i]*j]+=(f[o^1][j][c]*j%p))%=p;
48 (f[o][j+1][c+cf[i]*j]+=f[o^1][j][c])%=p;
49 }
50 }
51 }
52 LL ans=0;
53 For(i,0,k)
54 (ans+=f[o][0][i])%=p;
55 printf("%lld
",ans);
56 Formylove;
57 }