15 分钟 读完 (大约 2204 个字)

2018-10-17考试

这里是简介

T1

题面

智者奥尔曼曾说过： 有缘的人即使相隔海角天涯， 也会在梦境中相遇。

IcePrince_1968 和 IcePrincess_1968 便是如此。 有一天 IcePrincess_1968 突发奇想： 为什么不用梦境操控仪器来增加她和 IcePrince_1968 的缘分呢？

IcePrincess_1968 的梦境可以用 n 个区间来表示，第 i 个区间[li,ri]表示她的第 i 个梦境会在 li 时刻开始， 在 ri 时刻结束（ 包含 li 和 ri 两个时刻） 。 因为IcePrincess_1968 经常做白日梦， 所以 n 可能很大。

两个人的梦境不是什么时候都能融合的。只有在一些关键的与另一个人相关的梦境转折点两个人的梦境相遇， 才能完成融合， 形成浪漫的梦境。

IcePrincess_1968 探测到IcePrince_1968 近期的 m 个与 IcePrincess_1968 相关的梦境转折点， 第 i 个转折点 ti 表示他的第 i 个梦境转折点会在 ti 时刻出现。 因为 IcePrince_1968 和 IcePrincess_1968 很有缘，IcePrince_1968 经常梦到 IcePrincess_1968， 所以 m 可能会很大。

当 IcePrincess_1968 的一个梦境包含了 IcePrince_1968 的一个梦境转折点时，两个人的这两段梦境就能得到融合。 但要注意 IcePrincess_1968 的每段梦境只能和 IcePrince_1968 的一个梦境转折点融合， 类似的， IcePrince_1968 的每个梦境转折点只能和 IcePrincess_1968的一段梦境融合， 否则会引发时空混乱。

IcePrincess_1968 很喜欢做和 IcePrince_1968 相关的梦。 所以她想算出她的这些梦境最多能和 IcePrince_1968 的梦境转折点融合出多少个浪漫的梦境。

IcePrincess_1968 擅长文学但不擅长计算机， 所以只能找你帮忙。

题解

…

考虑贪心，将区间按右端点排序，找到离左端点最近的一个转折点，用$multiset$维护即可

代码

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<cstdio>
#include<algorithm>
#include<set>
#define RG register

inline int read()
{
	int data = 0, w = 1;
	char ch = getchar();
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data*w;
}

const int maxn(200010);
struct node { int l, r; } d[maxn];
inline bool cmp(const node &lhs, const node &rhs) { return lhs.r < rhs.r || (lhs.r == rhs.r && lhs.l < rhs.l); }
int t[maxn], n, m;
std::multiset<int> s;

int main()
{
	n = read(); m = read();
	for(RG int i = 1; i <= n; i++) d[i] = (node) {read(), read()};
	for(RG int i = 1; i <= m; i++) s.insert(t[i] = read());

	std::sort(d + 1, d + n + 1, cmp);
	int ans = 0;
	std::multiset<int>::iterator it;
	for(RG int i = 1; i <= m; i++)
	{
		it = s.lower_bound(d[i].l);
		if(it == s.end() || *it > d[i].r) continue;
		++ans; s.erase(it);
	}
	printf("%d\n", ans);
	return 0;
}

T2

题面

给定一棵有$n$个节点的树，求它树高的期望

题解

妙啊

预处理$dp[i][j]$表示$i$个点的森林,有$j$个点在第一棵树的概率,转移考虑第$i$个点是否在第一棵子树中,我们有状态转移方程
$$
dp[i][j] = dp[i − 1][j − 1] ∗ (j − 1) ∗ inv[i] + dp[i − 1][j] ∗ (i − j) ∗ inv[i]
$$
考虑修改算法三中状态的含义,令$f[i][j]$表示有$i$个点的树,深度不超过$j$的概率,$g[i][j]$表示有$i$个点的森林,深度不超过$j$的概率,$f[i][j]$直接从$g[i-1][j-1]$转移来;$g[i][j]$考虑枚举第一棵树的大小$k$,从一棵树和一个森林转移来,同时还要乘上第一棵子树大小为$k$的概率,我们有状态转移方程:
$$
g[i][j] = \sum_{k = 1} ^ i f[k][j] g[i - k][j] dp[i][k]
$$
具体的细节可以看标程。最后只要用$f[n][j]-f[n][j-1]$就可以得到深度为$j$的树的概率
时间复杂度: $O(n^3)$

代码

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
#include<cstdio>
#include<cstring>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));

inline int read()
{
	int data = 0, w = 1;
	char ch = getchar();
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data*w;
}

const int maxn(210);
int n, p, inv[maxn];
inline int Inv(int x)
{
	static int ans, y; ans = 1; y = p - 2; x %= p;
	while(y)
	{
		if(y & 1) ans = 1ll * ans * x % p;
		x = 1ll * x * x % p; y >>= 1;
	}
	return ans;
}

int dp[maxn][maxn], f[maxn][maxn], g[maxn][maxn], ans[maxn];

inline int F(int i, int j);
inline int G(int i, int j)
{
	if(j < 0) return 0;
	if(i == 0) return 1;
	if(~g[i][j]) return g[i][j];
	g[i][j] = 0;
	for(RG int k = 1; k <= i; k++)
		g[i][j] = (g[i][j] + (1ll * (1ll * F(k, j) * G(i - k, j) % p) * dp[i][k]) % p) % p;
	return g[i][j];
}

inline int F(int i, int j)
{
	if(~f[i][j]) return f[i][j];
	return f[i][j] = G(i - 1, j - 1);
}

int main()
{
	n = read(); p = read(); inv[1] = 1;
	for(RG int i = 2; i <= n; i++) inv[i] = Inv(i);
	if(n == 0) return puts("0") & 0;
	dp[1][1] = 1;
	for(RG int i = 2; i <= n; i++)
		for(RG int j = 1; j <= i; j++)
			dp[i][j] = ((1ll * (1ll * dp[i - 1][j - 1] * (j - 1) % p) * inv[i] % p) + (1ll * (1ll * dp[i - 1][j] * (i - j) % p) * inv[i] % p)) % p;
	clear(f, -1); clear(g, -1);
	for(RG int i = 2; i <= n; i++) ans[i] = F(n, i);
	ans[1] = 0; int ANS = 0;
	for(RG int i = 2; i <= n; i++) ANS = (ANS + (1ll * ((ans[i] - ans[i - 1]) % p) * i) % p) % p;
	printf("%d\n", (ANS - 1 + p) % p);
	return 0;
}

T3

题面

IcePrincess_1968 和 IcePrince_1968 长大了， 他们开始协助国王 IceKing_1968 管理国内事物。

IcePrincess_1968 和 IcePrince_1968 住在一个宁静悠远的王国： IceKingdom —— 飘雪圣域。 飘雪圣域有 n 个城镇， 编号 1,2,3…n。 有些城镇之间有道路， 且满足任意两点之间有且仅有一条路径。 飘雪圣域风景优美， 但气候并不是太好。 根据 IcePrince_1968 的气候探测仪，将来会发生 q 场暴风雪。 每场暴风雪可以用两个整数 li,ri 刻画， 表示这场暴风雪之后， 只有编号属于[li,ri]的城市没有受到暴风雪的影响。

在暴风雪的影响下迅速确定王国的农业生产方案是非常重要的事情。IceKing_1968 认为， 一个农业生产地域应该是一个极大连通块， 满足每个节点都没有被暴风雪影响。 这里极大连通块的定义是： 不存在一个不属于该点集的未被暴风雪影响的点与该连通块连通。

IcePrincess_1968 要负责算出每次暴风雪后， 王国能拥有多少个农业生产地域。 注意这里每次暴风雪是独立的， 即每次暴风雪过后， 直到每个城镇重新焕发生机， 下一次暴风雪才会到来。

正如上文所述， IcePrincess_1968 擅长文学但不擅长计算机， 于是请你帮忙。

题解

其实，对于一个询问$[l_i,r_i]$，我们只要知道有多少条边的两个端点都没有被暴风雪影响，就可以$O(1)$算联通块的个数。

记$num$为没有被暴风雪影响的边的个数，答案就是$r_i-l_i+1-num$。

我们可以离线做，将原树中所有的边按照编号较大的点从大到小排序,再将询问按右端点从大到小排序。

用一个树状数组来维护所有区间的左端点,刚开始将所有区间的左端点加入$BIT$,随着询问区间右端点的左移,必然会有一些新的右端点在区间右端点之左的边变得不合法,将这些边从$BIT$里删除,即$BIT$实时维护右端点在当前查询区间右端点左边的所有树边的左端点。

因为左端点一定在右端点左边,所以只要一条树边的左端点在查询区间的左端点右边,这条边就一定合法,所以将每个询问在$BIT$里面查询一下即可

代码

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
#include<cstdio>
#include<vector>
#define RG register

inline int read()
{
	int data = 0, w = 1;
	char ch = getchar();
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data*w;
}

const int maxn(200010);
struct edge { int next, to; } e[maxn << 1];
int head[maxn], e_num, n, q, fa[maxn];
inline void add_edge(int from, int to) { e[++e_num] = (edge) {head[from], to}; head[from] = e_num; }

void dfs(int x)
{
	for(RG int i = head[x]; i; i = e[i].next)
	{
		int to = e[i].to; if(to == fa[x]) continue;
		fa[to] = x; dfs(to);
	}
}

struct qry { int l, r, opt, id; } p[maxn << 1];
std::vector<int> Q[maxn];
int ans[maxn], c[maxn], cnt;
inline void add(int x, int v) { while(x <= n) c[x] += v, x += x & -x; }
inline int query(int x) { int ans = 0; while(x) ans += c[x], x -= x & -x; return ans; }
inline int query(int l, int r) { return query(r) - query(l - 1); }

int main()
{
	n = read(); q = read();
	for(RG int i = 1, a, b; i < n; i++) a = read(), b = read(), add_edge(a, b), add_edge(b, a);
	dfs(1);
	for(RG int i = 1, l, r; i <= q; i++)
	{
		l = read(); r = read(); ans[i] = r - l + 1;
		if(l > 2) p[++cnt] = (qry) {l, r, 1, i}, Q[l - 1].push_back(cnt);
		p[++cnt] = (qry) {l, r, -1, i}; Q[r].push_back(cnt);
	}

	std::vector<int>::iterator it;
	for(RG int i = 1; i <= n; i++)
	{
		if(fa[i]) add(fa[i], 1);
		for(it = Q[i].begin(); it != Q[i].end(); ++it)
			ans[p[*it].id] += p[*it].opt * (query(p[*it].l, p[*it].r));
	}

	for(RG int i = 1; i <= q; i++) printf("%d\n", ans[i]);
	return 0;
}
Source --- 考试
【HNOI2015】接水果
【CTSC2008】网络管理
关注我

标签

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×