https://ac.nowcoder.com/acm/contest/1083

C. 勾股定理

 

题意：给出直角三角形其中一条边的长度n，要求构造剩下的两条边，使这三条边能构成一个直角三角形。

打表找规律。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int main() {
	ll n;
	cin >> n;
	if (n <= 2) {
		puts("-1");
		return 0;
	}
	if (n & 1)
		printf("%lld %lld\n", (n*n - 1) / 2, (n*n - 1) / 2 + 1);
	else
		printf("%lld %lld\n", (n*n - 4) / 4, (n*n - 4) / 4 + 2);
	return 0;
}

 

D. 羊吃草

 

题意：1到400的数轴上有多个区间，每个区间里任选一个点，不能有重复，多次询问，每次给定一个范围，问范围内最多有几个点。1≤n，q≤400,1≤ai≤bi≤400,1≤l≤r≤4001\leq n，q\leq 400,1\leq ai\leq bi\leq 400,1\leq l\leq r\leq 400

看似贪心，但就是不可以的，[1,4],[1,3],[2,2]问[1,4]

但是看到数据范围很小，考虑枚举每个点。先把所有区间按照左端点递增，右端点递增排序，对于每个询问的范围[l,r]，从小到大枚举范围中的每个点，最终符合条件的点数就是答案。每次找到包含这个点的所有区间，再贪心选择右端点最小的那个，因为它以后的用处最小。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int n, T;
typedef pair<int, int>pii;
pii a[N];
priority_queue<int, vector<int>, greater<int> >q;
int main() {
	scanf("%d%d", &n, &T);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i].first);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i].second);
	sort(a + 1, a + n + 1);
	while (T--) {
		while (!q.empty())q.pop();
		int l, r, j = 1, ans = 0;
		scanf("%d%d", &l, &r);
		for (int i = l; i <= r; i++) {
			for (; j <= n && a[j].first <= i; j++)q.push(a[j].second);
			while (!q.empty() && q.top() < i)q.pop();
			if (!q.empty()) {
				ans++;
				q.pop();
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

 

E. 数列

 

题意：定义数列的喜爱度为满足 2≤i≤n2\leq i\leq n 并且 a[i]=a[i−1]+1a[i]=a[i-1]+1 的 ii 的个数，要求构造出长度为n且所有元素和小于等于m且喜爱度最大的数列。

结论就是，把整个数列中从1开始的连续段分块的话，块的个数越少，喜爱度越大。设每块最大值为 a,b,c,⋯a,b,c,\cdots，因为 a+b+c+⋯=na+b+c+\cdots=n，则喜爱度 (a−1)+(b−1)+(c−1)+⋯(a-1)+(b-1)+(c-1)+\cdots 只与块的个数有关。

第二个结论是，块数固定的情况下，每块应该尽量平均分配，此时的元素总和最小。这就不用证明了，但要注意是在块数确定的情况下。

则从小到大枚举块数，对于每种块数，贪心分配每块的最大值，求出的元素总和如果满足小于等于m，则答案就是当前块数的构造情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int n; ll m;
int main() {
	scanf("%d%lld", &n, &m);
	for (int i = 1; i <= n; i++) {
		int blo = n / i, la = n % i;
		if (1ll * la*(2 + blo)*(1 + blo) / 2 + 1ll * (i - la)*(1 + blo)*blo / 2 <= m) {
			for (int j = 0; j < la; j++)
				for (int k = 1; k <= blo + 1; k++)
					printf("%d ", k);
			for (int j = la; j < i; j++)
				for (int k = 1; k <= blo; k++)
					printf("%d ", k);
			puts("");
			break;
		}
	}
	return 0;
}

 

F. ABCBA

 

题意：给定一棵树，每个节点有一个大写字符，多次询问两点路径上子序列ABCBA的个数。

可持久化线段树

可持久化线段树维护时间轴的信息。每个节点在它的父节点的基础上再建立一棵线段树，维护增加这个节点之后的新的线段树。这样兄弟之间就不会相互影响，因而可以在线段树中以深度作为下标进行区间的查询。这样一来，不用树刨就可以单独查询一条链上的信息了。

线段树的区间合并时就是分类讨论，记录自己区间的各个子序列个数信息，再合并。

对于每次询问，首先找到lca，则分成左右两条链，还要合并这两条链的信息，和线段树里的合并类似，但是要注意这时的其中一条链是反过来的，因为要求的子序列是ABCBA。

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
105
106
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 3e4 + 10;
const int mod = 10007;
int n, q;
char s[N];
vector<int>G[N];
int f[N][20], dep[N], cnt, ls[N << 4], rs[N << 4], rt[N];
struct X {
	int ABCBA, A, AB, ABC, ABCB, B, BC, BCB, BCBA, C, CB, CBA, BA;
	X() { ABCBA = A = AB = ABC = ABCB = B = BC = BCB = BCBA = C = CB = CBA = BA = 0; }
	X operator+(const X &t) const {
		X tmp;
		tmp.ABCBA = (ABCBA + t.ABCBA + A * t.BCBA + AB * t.CBA + ABC * t.BA + ABCB * t.A) % mod;
		tmp.A = (A + t.A) % mod;
		tmp.AB = (AB + t.AB + A * t.B) % mod;
		tmp.ABC = (ABC + t.ABC + A * t.BC + AB * t.C) % mod;
		tmp.ABCB = (ABCB + t.ABCB + A * t.BCB + AB * t.CB + ABC * t.B) % mod;
		tmp.B = (B + t.B) % mod;
		tmp.BC = (BC + t.BC + B * t.C) % mod;
		tmp.BCB = (BCB + t.BCB + B * t.CB + BC * t.B) % mod;
		tmp.BCBA = (BCBA + t.BCBA + B * t.CBA + BC * t.BA + BCB * t.A) % mod;
		tmp.C = (C + t.C) % mod;
		tmp.CB = (CB + t.CB + C * t.B) % mod;
		tmp.CBA = (CBA + t.CBA + C * t.BA + CB * t.A) % mod;
		tmp.BA = (BA + t.BA + B * t.A) % mod;
		return tmp;
	}
}tr[N << 4];
void up(int& o, int pre, int l, int r, int p, char c) {
	o = ++cnt;
	ls[o] = ls[pre];
	rs[o] = rs[pre];
	if (l == r) {
		if (c == 'A')tr[o].A = 1;
		else if (c == 'B')tr[o].B = 1;
		else if (c == 'C')tr[o].C = 1;
		return;
	}
	int mid = ((l + r) >> 1);
	if (p <= mid)up(ls[o], ls[pre], l, mid, p, c);
	else up(rs[o], rs[pre], mid + 1, r, p, c);
	tr[o] = tr[ls[o]] + tr[rs[o]];
}
void dfs(int u, int _fa) {
	f[u][0] = _fa;
	dep[u] = dep[_fa] + 1;
	up(rt[u], rt[_fa], 1, n, dep[u], s[u]);
	for (int i = 1; (1 << i) <= dep[u]; i++)
		f[u][i] = f[f[u][i - 1]][i - 1];
	for (int v : G[u]) {
		if (v != _fa)dfs(v, u);
	}
}
int LCA(int u, int v) {
	if (dep[u] < dep[v])swap(u, v);
	for (int i = 17; i >= 0; i--) {
		if ((1 << i) <= dep[u] - dep[v])
			u = f[u][i];
	}
	if (u == v)return u;
	for (int i = 17; i >= 0; i--) {
		if (f[u][i] != f[v][i]) {
			u = f[u][i];
			v = f[v][i];
		}
	}
	return f[u][0];
}
X query(int o, int l, int r, int ql, int qr) {
	if (ql <= l && qr >= r)return tr[o];
	X ans;
	int mid = ((l + r) >> 1);
	if (ql <= mid)ans = ans + query(ls[o], l, mid, ql, qr);
	if (qr > mid)ans = ans + query(rs[o], mid + 1, r, ql, qr);
	return ans;
}
int main() {
	scanf("%d%d", &n, &q);
	scanf("%s", s + 1);
	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);
	}
	dfs(1, 0);
	while (q--) {
		int u, v;
		scanf("%d%d", &u, &v);
		int lca = LCA(u, v), ans = 0;
		if (u == lca)
			ans = query(rt[v], 1, n, dep[lca], dep[v]).ABCBA;
		else if (v == lca)
			ans = query(rt[u], 1, n, dep[lca], dep[u]).ABCBA;
		else {
			X t1 = query(rt[u], 1, n, dep[lca], dep[u]);
			X t2 = query(rt[v], 1, n, dep[lca] + 1, dep[v]);
			ans = (t1.ABCBA + t2.ABCBA + t1.A*t2.BCBA + t1.BA*t2.CBA + t1.CBA*t2.BA + t1.BCBA*t2.A) % mod;
		}
		printf("%d\n", ans);
	}
	return 0;
}