T20201112

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

T1

就是考虑中位数这个东西该怎么处理。

那么就可以指定某一个数作为中位数，看它是否能够贡献答案，然后就可以先按权值排一次序，然后把时间插入到主席树里面，然后就可以查询到最优的时间，然后这道题就做完了。

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 3e5 + 10;
const int MX = 1e6 + 10;
int n, q, cnt, ans[maxn], root[maxn];
int ls[maxn << 5], rs[maxn << 5], sz[maxn << 5];
ll sm[maxn << 5], T;
pair <int, int> a[maxn];

void insert(int &x, int l, int r, int p)
{
	int pre = x;
	x = ++cnt;
	sz[x] = sz[pre] + 1;
	sm[x] = sm[pre] + p;
	ls[x] = ls[pre], rs[x] = rs[pre];
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (p <= mid) insert(ls[x], l, mid, p);
	else insert(rs[x], mid + 1, r, p);
}

ll query(int tl, int tr, int l, int r, int k)
{
	if (l == r) return 1ll * l * k;
	int mid = (l + r) >> 1, lsz = sz[ls[tr]] - sz[ls[tl]];
	if (k <= lsz) return query(ls[tl], ls[tr], l, mid, k);
	return sm[ls[tr]] - sm[ls[tl]] + query(rs[tl], rs[tr], mid + 1, r, k - lsz);
}

inline ll read()
{
	ll 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 ("treasure.in", "r", stdin);
	freopen ("treasure.out", "w", stdout);

	n = read(), T = read(), q = read();
	
	for (int i = 1; i <= n; ++i) a[i].first = read(), a[i].second = read();
	sort (a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) insert(root[i] = root[i - 1], 0, MX, a[i].second);

	int p = n;
	for (int i = 0; i <= (n - 1) / 2; ++i) {
		ans[i] = -1;
		for (p = min(p, n - i); p > i; --p) {
			ll t = query(root[0], root[p - 1], 0, MX, i) + query(root[p], root[n], 0, MX, i) + a[p].second;				
			if (t <= T) {
				ans[i] = a[p].first;
				break;
			}
		}
	}

	while (q--)
		printf ("%d\n", ans[read() / 2]);
}

T2

就是说，对于一定深度，一定权值的所有点，显然是先走 \(0\) 边，再走 \(1\) 边更优。

那么先把所有的前导零处理了，然后就是按照上面的贪心来就可以了。

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
#include <bits/stdc++.h>

const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int n, m, cur[2], dis[maxn];
int head[2][maxn], edge[2][maxn], next[2][maxn];
int q[maxn], tmp[maxn];
bool vis[maxn];

inline void addedge(int u, int v, int w)
{
	next[w][++cur[w]] = head[w][u];
	head[w][u] = cur[w];
	edge[w][cur[w]] = 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;
}

int main()
{
	freopen ("path.in", "r", stdin);
	freopen ("path.out", "w", stdout);

	n = read(), m = read();
	int u, v, w, tot;
	
	while (m--) {
		u = read(), v = read(), w = read();
		addedge(u, v, w);
	}
	
	int l(1), r(1);
	vis[1] = q[1] = 1;
	while (l <= r) {
		u = q[l++];
		for (int i = head[0][u]; i; i = next[0][i])
			if (!vis[edge[0][i]]) {
				vis[edge[0][i]] = 1;
				q[++r] = edge[0][i];
			}
	}

	l = 1;
	while (l <= r) {
		tot = 0;
		for (int i = l; i <= r && dis[q[i]] == dis[q[l]]; ++i)
			tmp[++tot] = q[i];
		l += tot;
		
		for (int k = 0; k <= 1; ++k)
			for (int j = 1; j <= tot; ++j) {
				u = tmp[j];
				for (int i = head[k][u]; i; i = next[k][i]) 
				if (!vis[edge[k][i]]) {
						vis[edge[k][i]] = 1;
						dis[edge[k][i]] = (2ll * dis[u] + k) % mod;
						q[++r] = edge[k][i];
					}
			}	
	}

	for (int i = 2; i <= n; ++i)
		if (vis[i]) printf ("%d ", dis[i]);
		else printf ("-1 ");
	puts("");
}