OrzCC杯模拟赛NOIp模拟赛Day1题解

Posted on | In |
Words count in article: 1.9k | Reading time ≈ 9

OrzCC杯模拟赛NOIp模拟赛Day1题解

A. 队爷的新书

题意：给出 $n$ 个区间，可以选择一个数 $p$，对于每个区间，如果 $p$ 在区间内则获得 $p$ 的收益，问总收益的最大值。

思路：很显然是一个思博贪心（甚至做过原题），首先很容易看出的一点就是只有区间的端点对于答案是有意义的，所以把端点弄出来离散化一下，然后看每个点左边有几个左端点几个右端点然后暴力乘一下就行了。

注意：思博题，随便打都能 $\text{A}$ 。

代码：

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>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n;
int a[N];

il bool cmp(int x, int y)
{
	return abs(x) == abs(y) ? x < y : abs(x) < abs(y);
}

int main()
{
#ifndef Wepdekr
	freopen("book.in", "r", stdin);
	freopen("book.out", "w", stdout);
#endif
	n = read();
	for (ri i = 1; i <= n; i++)
		a[2 * i - 1] = -1 * read(), a[2 * i] = read();
	sort(a + 1, a + 1 + 2 * n, cmp);
	ll num = 0, ans = -inf;
	for (ri i = 1; i <= 2 * n; i++)
	{
		if (a[i] < 0)
			num++;
		else
		{
			ans = max(ans, a[i] * num);
			num--;
		}
	}
	printf("%lld", ans);
	return 0;
}
/*
4
1 3
2 4
3 5
4 7

*/

B. 队爷的AU Plan

题意：

给出两个长度为 $n$ 的任务，第 $i$ 个任务难度为 $hard_i$ ，完成的收益为 $s_i​$ 。

初始有一个价值 $m​$ ，可以一次完成难度不超过 $m​$ 的所有任务，只扣除最大的 $hard_i​$ 的价值，可获得这些任务的全部收益，问完成所有任务后的总价值最大是多少。

思路：很显然作为 $\text{DP}$ ，我们可以设 $f _ i$ 表示完成到第 $i$ 个任务时的最大价值，很显然有以下转移：

但是这样是 $O(n ^ 2)$ 级别的复杂度，很显然会 $\color {darkblue} {\text {TLE}}$ ，所以我们考虑优化。

整理一下我们会发现一个事实：最优的转移状态 $j$ 一定满足以下式子值最大即可：

然后我们不妨用 $sum _ i$ 表示前 $i$ 个任务的收益之和。

我们假设对于状态 $i$ 可以由 $j$ 和 $k$ 两种状态转移过来，且 $j < k$ ，首先若 $j$ 和 $k$ 不由前面同一个状态转移得到，则很显然 $k$ 的决策层数更大，消耗更多，则 $j$ 优于 $k$ ；若 $j$ 和 $k$ 由前面同一个状态 $l$ 转移得到，则有：

两式相减得

则很显然有

则由 $j$ 转移过来显然比由 $k$ 转移过来更优。由此推广可得对于每一个状态 $i$ ，最小的能转移到 $i$ 的状态一定是最优的，所以找到第一个能转移的状态就 break 掉就行了。

但是这样并不能 $\color {green} {\text{AC}}$ ，所以还有另一个优化：假设状态 $i - 1$ 由状态 $j$ 转移过来，那么 $j$ 之前的状态肯定不能转移到 $i$ ，所以就可以省掉无用的枚举。

注意：似乎也没什么要注意的。

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, m;
int hard[N], s[N];
int dp[N], pre[N];

int main()
{
#ifndef Wepdekr
	freopen("plan.in", "r", stdin);
	freopen("plan.out", "w", stdout);
#endif
	n = read(), m = read();
	for (ri i = 1; i <= n; i++)
		hard[i] = read();
	for (ri i = 1; i <= n; i++)
		s[i] = read(), pre[i] = pre[i - 1] + s[i];
	memset(dp, 0xc0, sizeof(dp));
	dp[0] = m;
	int last = 0;
	for (ri i = 1; i <= n; i++)
		for (ri j = last; j < i; j++)
		{
			if (dp[j] < hard[i])
				continue;
			dp[i] = max(dp[i], dp[j] - hard[i] + pre[i] - pre[j]);
			last = j;
			break;
		}
	printf("%d", dp[n]);
	return 0;
}
/*
5 5
2 4 5 7 9
4 4 3 6 5

*/

C. 队爷的讲学计划

题意：给出一张有向带权图，从一号结点出发，每个 $\text{SCC}$ 内的点互相到达时边权为 $1$ ，问经过最大结点数时经过的最小边权是多少。

思路：很显然需要使用 $\text{Tarjan}$ 将 $\text{SCC}$ 缩点，缩点后形成了一个 $\text{DAG}$ ，然后在 $\text{DAG}$ 上跑 $\text{SPFA}$ 就行了。

注意：题目中要求数量最大优先，所以在跑 $\text{SPFA}$ 的时候应该注意这个问题。

代码：

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, m, num, top, id;
int dfn[N], low[N], st[N], bel[N], siz[N], fa[N], dis[N], foo[N];
bool instk[N], vis[N];

struct Graph
{
	int cnt, head[N];
	
	struct edge
	{
		int fr, to, nxt, weight;
	};
	edge e[N];
	
	il void add_edge(int u, int v, int w)
	{
		e[++cnt] = (edge) {u, v, head[u], w};
		head[u] = cnt;
	}
};
Graph G, T;

il void Clear_Stack(int x)
{
	num++;
	do {
		int u = st[top];
		bel[u] = num;
		instk[u] = 0;
		siz[num]++;
	} while (st[top--] != x);
}

il void Tarjan(int x)
{
	st[++top] = x;
	instk[x] = 1;
	dfn[x] = low[x] = ++id;
	for (ri i = G.head[x]; i; i = G.e[i].nxt)
	{
		int v = G.e[i].to;
		if (!dfn[v])
		{
			Tarjan(v);
			low[x] = min(low[x], low[v]);
		}
		else if (instk[v])
			low[x] = min(low[x], low[v]);
	}
	if (low[x] == dfn[x])
		Clear_Stack(x);
}

queue <int> q;
il void SPFA(int s)
{
	for (ri i = 1; i <= num; i++)
		vis[i] = 0, dis[i] = -inf;
	q.push(s);
	vis[s] = 1;
	foo[s] = siz[s];
	dis[s] = siz[s] - 1;
	while (!q.empty())
	{
		int u = q.front();
		vis[u] = 0;
		q.pop();
		for (ri i = T.head[u]; i; i = T.e[i].nxt)
		{
			int v = T.e[i].to;
			if (foo[u] + siz[v] > foo[v])
			{
				foo[v] = foo[u] + siz[v];
				dis[v] = dis[u] + T.e[i].weight + siz[v] - 1;
				q.push(v);
			}
			else if (foo[u] + siz[v] == foo[v] && dis[u] + T.e[i].weight + siz[v] - 1 < dis[v])
			{
				dis[v] = dis[u] + T.e[i].weight + siz[v] - 1;
				q.push(v);
			}
		}
	}
}

int main()
{
#ifndef Wepdekr
	freopen("teach.in", "r", stdin);
	freopen("teach.out", "w", stdout);
#endif
	n = read(), m = read();
	int sum = 0;
	for (ri i = 1; i <= m; i++)
	{
		int u = read(), v = read(), w = read();
		G.add_edge(u, v, w);
		sum += w;
	}
	Tarjan(1);
	for (ri i = 1; i <= n; i++)
	{
		if (!dfn[i])
			continue;
		for (ri j = G.head[i]; j; j = G.e[j].nxt)
		{
			int v = G.e[j].to;
			if (bel[i] != bel[v])
				T.add_edge(bel[i], bel[v], G.e[j].weight);
		}
	}
	SPFA(bel[1]);
	int mx = -inf, mn = inf;
	for (ri i = 1; i <= num; i++)
	{
		if (foo[i] > mx)
		{
			mx = foo[i];
			mn = dis[i];
		}
		else if (foo[i] == mx)
			mn = min(mn, dis[i]);
	}
	printf("%d %d", mx, mn);
	return 0;
}
/*
6 6
1 2 3
2 3 7
2 6 4
3 4 5
4 5 4
5 2 3

*/

总结

其实是一场还不错的比赛，但是很可惜没有完全发挥出实力来，因为 $\text{Tarjan}$ 忘了导致 $\text{C}$ 题只有 $10$ 分，然后 $\text{B}$ 题的优化也没有想出来，然后就只有 $160pts$ ，被各路神仙吊打。

或许真的快退役了吧……

0%