T1：
30pts：暴力枚举点对
70pts：考虑O(n)算法，优化枚举点对过程，考虑对于i，如何确定[l,i]区间内maxor
可以按位考虑，求出i二进制下“补位”x，问题转化为判断[l,i]区间与x最大交，
在[l,r]区间枚举过程中利用sum记录所有出现过的二进制位，与x取交即可
100pts：考虑优化70分过程，由于或的性质，可以贪心选择高位，于是问题转化为
固定r，求解maxor，考虑优化上述判断过程，显然方法为二进制考虑，我们
只需要判断[l,r]区间是否存在该二进制位，暴力枚举即可O(log^2w)
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I long long
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 #define memset(name,val,typ,len) memset (name,val,sizeof (typ) * len)
20 #define Mod1(a,b) (a = a + b > mod ? a + b - mod : a + b)
21 #define Mod2(a,b) (a = a - b < 0 ? a - b + mod : a - b)
22 inline I read () {
23 I x(0),y(1); C z(getchar());
24 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
25 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
26 return x * y;
27 }
28 inline V Max (I &a,I &b) { a = a > b ? a : b; }
29 inline V Min (I &a,I &b) { a = a < b ? a : b; }
30 inline I max (I &a,I &b) { return a > b ? a : b; }
31 inline I min (I &a,I &b) { return a < b ? a : b; }
32 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
33 inline I abs (I &a) { return a >= 0 ? a : -a; }
34 inline P operator + (const P &a,const P &b) {
35 return MP (a.a + b.a,a.b + b.b);
36 }
37 inline P operator - (const P &a,const P &b) {
38 return MP (a.a - b.a,a.b - b.b);
39 }
40 signed main () {
41 FP (maxor.in), FC (maxor.out);
42 I T (read ());
43 while (T -- ) {
44 B buc[63];
45 I l (read ()), r (read ()), ans (0);
46 memset (buc,0,B,63);
47 for (I i(0);i < 63; ++ i) {
48 I s (1ll << i);
49 if (s >= l && s <= r) {
50 buc[i] = 1; continue;
51 }
52 for (I j(62);j >= 0; -- j) {
53 if ((s | (1ll << j)) <= r)
54 s |= (1ll << j);
55 if (s >= l && s <= r) {
56 buc[i] = 1; break;
57 }
58 }
59 }
60 for (I i(0);i < 63; ++ i) if (buc[i])
61 ans |= (1ll << i);
62 printf ("%lld\n",ans);
63 }
64 }
View Code
T2：
50pts：暴力Dfs枚举选择即可
60~70pts：考虑问题实际上是求方案数k / (1 << n) >= p，观察到值域并不大
背包转移方案数即可，需要卡空间
100pts：考虑再次进行优化，考虑上述过程实际上是求区间第k大值使得所有
小于等于k的方案数大于等于(1 << n) * p，在观察数据范围，可以考虑
meet in the middle ，将两侧所有方案数进行记录，二分第k大值，计算
满足条件的方案数进行判断即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 #define memset(name,val,typ,len) memset (name,val,sizeof (typ) * len)
20 #define Mod1(a,b) (a = a + b > mod ? a + b - mod : a + b)
21 #define Mod2(a,b) (a = a - b < 0 ? a - b + mod : a - b)
22 D p;
23 LL sch;
24 I n,tot,cnt,ans,tmp1,sigma,a[25],b[1 << 20],c[1 << 20];
25 inline I read () {
26 I x(0),y(1); C z(getchar());
27 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
28 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
29 return x * y;
30 }
31 inline V Max (I &a,I b) { a = a > b ? a : b; }
32 inline V Min (I &a,I b) { a = a < b ? a : b; }
33 inline I max (I &a,I &b) { return a > b ? a : b; }
34 inline I min (I &a,I &b) { return a < b ? a : b; }
35 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
36 inline I abs (I &a) { return a >= 0 ? a : -a; }
37 inline P operator + (const P &a,const P &b) {
38 return MP (a.a + b.a,a.b + b.b);
39 }
40 inline P operator - (const P &a,const P &b) {
41 return MP (a.a - b.a,a.b - b.b);
42 }
43 V Dfs1 (I num) {
44 if (num > tmp1)
45 return b[cnt++] = sigma, V ();
46 sigma += a[num], Dfs1 (num + 1), sigma -= a[num];
47 Dfs1 (num + 1);
48 }
49 signed main () {
50 n = read (); scanf ("%lf",&p);
51 sch = ceil (p * (1ll << n));
52 tmp1 = n >> 1; ans = INT_MAX;
53 for (I i(1);i <= tmp1; ++ i)
54 a[i] = read ();
55 Dfs1 (1); sort (b,b + cnt);
56 memcpy (c,b,sizeof b);
57 tmp1 = n - tmp1; tot = cnt, cnt = 0;
58 for (I i(1);i <= tmp1; ++ i)
59 a[i] = read ();
60 Dfs1 (1); sort (b,b + cnt);
61 I l (0), r (b[cnt - 1] + c[tot - 1]);
62 while (l < r) { I mid (l + r >> 1);
63 I p1 (0), p2 (tot - 1); LL sum (0);
64 while (p1 < cnt) {
65 while (b[p1] + c[p2] > mid && p2 >= 0) p2 -- ;
66 sum += tot - p2 - 1; p1 ++ ;
67 }
68 (1ll << n) - sum >= sch ? (Min (ans,mid), r = mid) : l = mid + 1;
69 }
70 printf ("%d\n",ans);
71 }
View Code
T3：
计算空间发现bitset刚好，利用bitset判断连通性，枚举中转点，再枚举贡献点即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 #define memset(name,val,typ,len) memset (name,val,sizeof (typ) * len)
20 #define Mod1(a,b) (a = a + b > mod ? a + b - mod : a + b)
21 #define Mod2(a,b) (a = a - b < 0 ? a - b + mod : a - b)
22 const I N = 3e4 + 3;
23 I n,m,t,w[N];
24 LL MA(-1);
25 LL sum;
26 vector <I> to[N];
27 vector <bitset <N>> s;
28 inline I read () {
29 I x(0),y(1); C z(getchar());
30 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
31 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
32 return x * y;
33 }
34 inline V Max (LL &a,LL b) { a = a > b ? a : b; }
35 inline V Min (I &a,I b) { a = a < b ? a : b; }
36 inline I max (I &a,I &b) { return a > b ? a : b; }
37 inline I min (I &a,I &b) { return a < b ? a : b; }
38 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
39 inline I abs (I &a) { return a >= 0 ? a : -a; }
40 inline P operator + (const P &a,const P &b) {
41 return MP (a.a + b.a,a.b + b.b);
42 }
43 inline P operator - (const P &a,const P &b) {
44 return MP (a.a - b.a,a.b - b.b);
45 }
46 signed main () {
47 FP (link.in), FC (link.out);
48 n = read (), m = read (), t = read ();
49 s.resize (n + 1);
50 for (I i(1);i <= m; ++ i) {
51 I x (read ()), y (read ());
52 s[x][y] = s[y][x] = 1;
53 to[x].push_back (y), to[y].push_back (x);
54 }
55 for (I i(1);i <= n; ++ i) w[i] = read ();
56 for (I i(1);i <= n; ++ i)
57 for (I j(0);j < to[i].size (); ++ j)
58 for (I k(j + 1);k < to[i].size (); ++ k) if (!s[to[i][j]][to[i][k]])
59 Max (MA,1ll * w[to[i][j]] * w[to[i][k]]), sum += w[to[i][j]] * w[to[i][k]];
60 printf ("%lld\n%lld\n",t != 2 ? MA : 0,t != 1 ? sum << 1 : 0);
61 }
View Code
T4：
70pts：bitset暴力维护区间关系即可
100pts：题目关键信息之一为每个原件只参与一次融合，因此可以想到树形结构，
问题转化为判断两点树上关系，首先若无祖先关系puts （0）即可
考虑若y为x祖先，那么满足条件为x到y路径上只存在或运算
反之，为y到x路径上只存在与运算，考虑如何维护
首先只需要判断祖先关系，于是可以利用dfn序进行判断，区间是否有交即可
（若求具体祖先则只能树剖或倍增进行维护）
考虑如何维护一条链上的操作，树剖+线段树显然是可以的，考虑一种新的维护方法
由于需要维护的是与或关系，考虑使用并查集进行关系维护，分别建立与或并查集
利用信息传递即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 #define memset(name,val,typ,len) memset (name,val,sizeof (typ) * len)
20 #define Mod1(a,b) (a = a + b > mod ? a + b - mod : a + b)
21 #define Mod2(a,b) (a = a - b < 0 ? a - b + mod : a - b)
22 const I N = 5e5 + 3;
23 I n,m,k,x,y,ban;
24 I tot,head[N],to[N],nxt[N],In[N];
25 I cnt,dfn[N],size[N];
26 vector <P> que;
27 inline I read () {
28 I x(0),y(1); C z(getchar());
29 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
30 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
31 return x * y;
32 }
33 inline V Max (I &a,I &b) { a = a > b ? a : b; }
34 inline V Min (I &a,I &b) { a = a < b ? a : b; }
35 inline I max (I &a,I &b) { return a > b ? a : b; }
36 inline I min (I &a,I &b) { return a < b ? a : b; }
37 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
38 inline I abs (I &a) { return a >= 0 ? a : -a; }
39 inline P operator + (const P &a,const P &b) {
40 return MP (a.a + b.a,a.b + b.b);
41 }
42 inline P operator - (const P &a,const P &b) {
43 return MP (a.a - b.a,a.b - b.b);
44 }
45 struct DJS {
46 #define F(x) get (x)
47 I f[N];
48 inline V initital () {
49 for (I i(1);i <= n; ++ i)
50 f[i] = i;
51 }
52 I get (I x) {
53 return x == f[x] ?
54 x : f[x] = get (f[x]);
55 }
56 }D1,D2;
57 inline V found (I x,I y) { In[y] ++ ;
58 to[++tot] = y, nxt[tot] = head[x], head[x] = tot;
59 }
60 V Dfs (I x) {
61 dfn[x] = ++cnt, size[x] = 1;
62 for (I i(head[x]),y(to[i]); i ;i = nxt[i],y = to[i])
63 Dfs (y), size[x] += size[y];
64 }
65 signed main () {
66 FP (friendship.in), FC (friendship.out);
67 n = read (), m = read (); ban = n;
68 D1.initital (), D2.initital ();
69 while (m -- )
70 switch (read ()) {
71 case 0 :
72 ban ++ ; D1.f[ban] = D2.f[ban] = ban;
73 switch (read ()) {
74 case 0 :
75 k = read ();
76 if (k == 1) { x = read ();
77 D1.f[D1.F (x)] = ban;
78 D2.f[D2.F (x)] = ban;
79 found (ban,x);
80 }
81 else
82 for (I i(1);i <= k; ++ i) { x = read ();
83 D1.f[D1.F (x)] = ban, found (ban,x);
84 }
85 break;
86 default :
87 k = read ();
88 if (k == 1) { x = read ();
89 D1.f[D1.F (x)] = ban;
90 D2.f[D2.F (x)] = ban;
91 found (ban,x);
92 }
93 else
94 for (I i(1);i <= k; ++ i) { x = read ();
95 D2.f[D2.F (x)] = ban, found (ban,x);
96 }
97 }
98 break;
99 default :
100 que.push_back (MP (read (),read ()));
101 }
102 for (I i(1);i <= ban; ++ i) if (!In[i])
103 Dfs (i);
104 for (auto tmp : que) {
105 x = tmp.b, y = tmp.a;
106 if (dfn[y] + size[y] <= dfn[x] || dfn[y] >= dfn[x] + size[x])
107 puts ("0");
108 else switch (dfn[y] <= dfn[x]) {
109 case 1 :
110 puts (dfn[D2.F (x)] <= dfn[y] ? "1" : "0");
111 break;
112 default :
113 puts (dfn[D1.F (y)] <= dfn[x] ? "1" : "0");
114 }
115 }
116 }
View Code