https://codeforces.com/contest/1339

C. Powered Addition

 

题意：n个数，第 xx 秒可以选任意个数各加上 2x−12^{x-1}，问最少过几秒能使数列非递减。

加的数字越小，要过的时间越少。

所以就贪心地少加即可，每个数最多只加到和前一个数相等。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
int T;
int n;
ll a[N];
int cal(ll x) {
	for (int i = 30; i >= 0; i--) {
		if (x&(1ll << i)) {
			return i + 1;
		}
	}
	return 0;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		int ans = 0;
		for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
		for (int i = 2; i <= n; i++) {
			ll to = max(a[i - 1], a[i]);
			ans = max(ans, cal(to-a[i]));
			a[i] = to;
		}
		printf("%d\n", ans);
	}
	return 0;
}

 

D. Edge Weight Assignment

 

题意：给定一棵树，要给边赋值，满足每对叶子的路径上所有边权异或和为0。问边权最少/最多有几个不同的数。

从少到多看，两个点时边权有1个，3个点时1个，4个点时如果一条直线最少要3个，否则最少还是1个。

如果有奇数长度的叶子间的路径，那么最少要3个，否则最少1个。

再看最多，如果两个叶子路径长度为2，那么路径上的这两条边一点要相等，否则一定可以不相等。

所以只要看有几对路径长为2的叶子，可以dfs时统计节点连了几个叶子，这些叶子的边都要相等。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
int n;
vector<int>G[N], de[N];
int d[N], cnt[2], ans;
void dfs(int u, int _fa, int dep) {
	d[u] = dep;
	if ((int)G[u].size() == 1) {
		de[d[u]].push_back(u);
		cnt[d[u] % 2]++;
	}
	for (int v : G[u]) {
		if (v != _fa)dfs(v, u, dep + 1);
	}
	int tmp = 0;
	for (int v : G[u]) {
		if ((int)G[v].size() == 1)tmp++;
	}
	ans -= max(0, tmp - 1);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	ans = n - 1;
	dfs(1, 0, 1);
	if (cnt[0]&&cnt[1])printf("3 ");
	else printf("1 ");
	printf("%d\n", ans);
	return 0;
}

 

E. Perfect Triples

 

题意：有一个数组初始为空，每次找出3个数异或和为0，且都没被用过且字典序最小，加入数组最后，多次询问，问第n个数。

打表找规律

容易想到，a要是最小的没用过的数，b的最高位要比a高，且在a的最高为上b要为0，所以要打二进制的表。

以上是每一对a，b。

然后就是神仙找规律了，发现a中二进制00对应b中00，01对应10，10对应11，11对应01，对于每两个分一组，都是这样。

那就说明知道了a，就知道了b，以及c。

a是从4的幂次开始，连续4的幂次个。比如：1，4，5，6，7，16，17，18，···，31，···。

所以先把n按3个分一块，再看块在4的哪个幂次段里，再找到段内偏移，得到a，再二进制下2位分一组，翻译出b。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int T;
ll n;
int mp[]{ 0,2,3,1 };
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld", &n);
		ll p = 0, m = n;
		while (m) {
			m >>= 2;
			p++;
		}
		p--;
		ll a = (1ll << (2 * p)) + (n - 1) / 3 - ((1ll << (2 * p)) - 1) / 3, b = 0;
		for (int i = 0; i <= 2*p; i += 2) {
			int c = ((a >> i) & 1) + 2 * ((a >> (i + 1)) & 1);
			b += (1ll*(mp[c]) << i);
		}
		if (n % 3 == 0)printf("%lld\n", a);
		else if (n % 3 == 1)printf("%lld\n", b);
		else printf("%lld\n", a^b);
	}
	return 0;
}