T20201116

Posted on Edited on In Word count in article: 1.2k Reading time ≈ 4 mins.
大东辰的测试

T1

要或起来的值与异或起来的值相等，那么可以发现异或和一定是或的子集。

所以可以固定或起来的值，然后去异或背包一下就可以了。。。

Code

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

const int maxn = 55;
const int maxm = 16384;

typedef long long ll;
int A[maxn], B[maxn];
int tmp[maxm];
ll f[maxn][maxm], ans;

inline int read()
{
	int x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
		x = (x << 1) + (x << 3) + (o ^ 48);
	return x;
}

int main()
{
	freopen ("orandxor.in", "r", stdin);
	freopen ("orandxor.out", "w", stdout);
	int n = read();
	for (int i = 1; i <= n; ++i) A[i] = read();
	for (int x = 1; x < maxm; ++x) {
		int cnt(0), tot(0);

		for (int p = x; p; p = (p - 1) & x) tmp[++cnt] = p;
		tmp[++cnt] = 0;

		for (int i = 1; i <= n; ++i)
			if ((A[i] | x) == x) B[++tot] = A[i];

		f[0][0] = 1;
		for (int i = 1; i <= tot; ++i)
			for (int j = 1; j <= cnt; ++j) 
				f[i][tmp[j]] = f[i - 1][tmp[j]] + f[i - 1][tmp[j] ^ B[i]];

		ans += f[tot][x];
	}
	printf ("%lld\n", ans);
}

T2

就是说，要尽可能多的满足 f[i - 2] + f[i - 1] = f[i]，这样可以得到一个序列。

那么只要随便在向这个序列中丢一个数（使得序列仍然有序），那么必定会使的至少一个等式不成立，即至少有一组满足条件的解。

然后这个序列可以类似斐波那契数列的方法去构造，然后这个序列最终的长度就是 \(45\)。

所以可以用线段树把区间里的前 \(45\) 大的数求出来，在贪心的找就可以了。。。

Code

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int lim = 30;

int n, q, res[maxn];
int mx[maxn << 2][lim];

inline int read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9')
        o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar()) 
        x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

inline void merge(int *l, int *r)
{
	int i(0), j(0);
	int tmpa[lim], tmpb[lim];
	memcpy (tmpa, l, sizeof tmpa);
	memcpy (tmpb, r, sizeof tmpb);

	while (i + j < lim) {
		if ((tmpa[i] == -1) && (tmpb[j] == -1)) break;
		if (tmpa[i] > tmpb[j]) l[i + j] = tmpa[i], i++;
		else l[i + j] = tmpb[j], j++;
	}
}

void build(int l, int r, int x = 1)
{
	if (l == r) {
		for (int i(1); i < lim; ++i)
			mx[x][i] = -1;
		mx[x][0] = read();
		return ;
	}	
	int mid = (l + r) >> 1;
	build (l, mid, x << 1);
	build (mid + 1, r, x << 1 | 1);
	memcpy (mx[x], mx[x << 1], sizeof mx[x]);
	merge (mx[x], mx[x << 1 | 1]);
}

void update(int l, int r, int pos, int val, int x = 1)
{
	if (l == r) {
		mx[x][0] = val;
		return ;
	}

	int mid = (l + r) >> 1;

	if (pos <= mid) update (l, mid, pos, val, x << 1);
	else update (mid + 1, r, pos, val, x << 1 | 1);
	memcpy (mx[x], mx[x << 1], sizeof mx[x]);
	merge (mx[x], mx[x << 1 | 1]);
}

void getans(int l, int r, int tl, int tr, int x = 1)
{
	if (l >= tl && r <= tr) {
		merge(res, mx[x]);
		return ;
	}

	int mid = (l + r) >> 1;

	if (tl <= mid) getans (l, mid, tl, tr, x << 1);
	if (tr > mid) getans (mid + 1, r, tl, tr, x << 1 | 1);
}

int main()
{
	freopen ("triangle.in", "r", stdin);
	freopen ("triangle.out", "w", stdout);
	int n = read(), q = read(), opt, l, r;
	build (1, n);
	while (q--) {
		opt = read(), l = read(), r = read();
		if (opt == 1) update(1, n, l, r);
		else {
			for (int i = 0; i < lim; ++i)
				res[i] = -1;
			getans(1, n, l, r);
			ll result(0);
			for (int i = 0; i + 2 < lim; ++i) {
				if (res[i] == -1) break;
				if (res[i] < res[i + 1] + res[i + 2]) {
					result = (ll)res[i] + res[i + 1] + res[i + 2];
					break;
				}
			}
			printf ("%lld\n", result);
		}
	}
}

T3

80?

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

const int maxn = 1e7 + 10;
const int lim = (1 << 20) - 1;
int cur, tot, val[maxn], dep[maxn];
int head[maxn], edge[maxn << 1], nxt[maxn << 1];

inline void addedge(int u, int v)
{
	nxt[++cur] = head[u];
	head[u] = cur;
	edge[cur] = v;
}

inline int read()
{
	int x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
		x = (x << 1) + (x << 3) + (o ^ 48);
	return x;
}

void dfs(int u, int f, int d)
{
	dep[d] ^= val[u];
	for (int i = head[u]; i; i = nxt[i]) {
		if (edge[i] == f) continue;
		dfs(edge[i], u, d + 1);
	}
}

int main()
{
	freopen ("tree.in", "r", stdin);
	freopen ("tree.out", "w", stdout);
	int n = read();
	for (int i = 1; i <= n; ++i) val[i] = read();
	for (int i = 1; i < n; ++i) {
		int u = read(), v = read();
		addedge(u, v), addedge(v, u);	
	}
	dfs(1, 0, 0);
	for (int i = 0; i < n; ++i) {
		int ans(dep[0]), sta((~i) & lim);
		for (int j = sta; j; j = (j - 1) & sta)
			ans ^= dep[j];
		printf ("%d ", ans);
	}
}

100?

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

const int maxn = 1e7 + 10;
const int lim = (1 << 20) - 1;
int cur, tot, val[maxn], dep[maxn];
int head[maxn], edge[maxn << 1], nxt[maxn << 1];

inline void addedge(int u, int v)
{
	nxt[++cur] = head[u];
	head[u] = cur;
	edge[cur] = v;
}

inline int read()
{
	int x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
		x = (x << 1) + (x << 3) + (o ^ 48);
	return x;
}

void dfs(int u, int f, int d)
{
	dep[d] ^= val[u];
	for (int i = head[u]; i; i = nxt[i]) {
		if (edge[i] == f) continue;
		dfs(edge[i], u, d + 1);
	}
}

int main()
{
	freopen ("tree.in", "r", stdin);
	freopen ("tree.out", "w", stdout);
	int n = read();
	for (int i = 1; i <= n; ++i) val[i] = read();
	for (int i = 1; i < n; ++i) {
		int u = read(), v = read();
		addedge(u, v), addedge(v, u);	
	}
	
	dfs(1, 0, 0);
	for (int i = 0; i < 20; ++i)
		for (int j = 0; j <= lim; ++j)
			if ((j >> i) & 1)
				dep[j] ^= dep[j ^ (1 << i)];

	for (int i = 0; i < n; ++i)
		printf ("%d ", dep[i ^ lim]);
}