Streaming#3模拟赛题解

Posted on |
Words count in article: 1.7k | Reading time ≈ 8

Streaming#3NOIp模拟赛Day1题解

A. 数三角形

题意：给出平面上的 $n$ 个点，问能组成的三角形个数。

思路：没什么思路， $n$ 非常小，所以枚举三个顶点并暴力判断是否贡献就行了。

注意：似乎要注意掉精的问题（？）

代码：

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
#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, ans;
struct point
{
	int x, y;
};
point a[N];

int main()
{
#ifndef Wepdekr
	freopen("tri.in", "r", stdin);
	freopen("tri.out", "w", stdout);
#endif
	n = read();
	for (ri i = 1; i <= n; i++)
		a[i].x = read(), a[i].y = read();
	for (ri i = 1; i <= n; i++)
		for (ri j = i + 1; j <= n; j++)
			for (ri k = j + 1; k <= n; k++)
			{
				if ((a[j].x - a[i].x) * (a[k].y - a[j].y) == (a[k].x - a[j].x) * (a[j].y - a[i].y))
					continue;
				ans++;
			}
	printf("%d", ans);
	return 0;
}
/*
5
0 0
1 0
2 0
0 1
1 1
2333 3333

*/

B. 4和7

题意：给出一条线，从 $0$ 开始，每一次可以向正方向走 $4$ 个单位或 $7$ 个单位，走到某一些指定单位上有一定的收益，可以在任意位置停下来，问最大的收益。

思路：表示做过一个类似的题目，不过是改成了在图上跑，然后……

YSJ：这很显然是个思博DP。

没错， $\text{DP}$ 部分确实是比较简单，显然有以下方程：

这样做是 $O(m)$ 的做法，但 $m$ 较大后便不可避免的会超时，所以我们考虑将与 $m$ 有关的状态变成与 $n$ 有关。

我们将有收益的位置排序后设 $f _ i$ 表示进行到第 $i$ 个有收益的位置是的最大收益。

然后考虑 $4$ 和 $7$ 的奇怪限制，由于我们已经做过了 小凯的疑惑 所以我们知道最大不能表示的数为 $17$ ，然后我们只要记录距离为 $17$ 之前的点的最大值就可以转移过来了。

转移的时候暴力处理一下 $17$ 以内的数就行了。

然后我用的是相当暴力的平衡树，所以常数大到天上去了。

注意：输入的位置可能有相同的，要合并一下。

代码：

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
#define int 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, cnt;
int f[N];
bool vis[N];
struct point
{
	int num, pos;
	friend bool operator < (point a1, point a2)
	{
		return a1.pos < a2.pos;
	}
};
point p[N];

il void Get_unable()
{
	for (ri i = 0; i <= 5; i++)
		for (ri j = 0; j <= 3; j++)
			vis[i * 4 + j * 7] = 1;
}

namespace splay
{
	int tot, rt;
	
	struct node
	{
		int fa, ch[2];
		int cnt, num, val, ans;
	};
	node a[N * 2];
	
	il void Pushup(int x)
	{
		a[x].cnt = a[a[x].ch[0]].cnt + a[a[x].ch[1]].cnt + a[x].num;
		a[x].ans = max(max(a[a[x].ch[0]].ans, a[a[x].ch[1]].ans), a[x].val);
	}
	
	il int Search(int x, int w)
	{
		while (a[x].val != w)
		{
			if (w < a[x].val)
			{
				if (!a[x].ch[0])
					break;
				x = a[x].ch[0];
			}
			else if (w > a[x].val)
			{
				if (!a[x].ch[1])
					break;
				x = a[x].ch[1];
			}
		}
		return x;
	}
	
	il void Rotate(int x)
	{
		int y = a[x].fa;
		int z = a[y].fa;
		bool k = (a[y].ch[1] == x);
		int w = a[x].ch[!k];
		if (z)
			a[z].ch[a[z].ch[1] == y] = x;
		a[y].ch[k] = w;
		a[x].ch[!k] = y;
		if (w)
			a[w].fa = y;
		a[x].fa = z;
		a[y].fa = x;
		
		Pushup(y);
		Pushup(x);
	}
	il void Splay(int x)
	{
		while (a[x].fa)
		{
			int y = a[x].fa;
			int z = a[y].fa;
			if (z)
				Rotate(((a[y].ch[0] == x) ^ (a[z].ch[0] == y)) ? x : y);
			Rotate(x);
		}
		rt = x;
	}
	
	il void Insert(int x)
	{
		if (!tot)
		{
			a[++tot].val = x;
			a[tot].ans = x;
			a[tot].cnt = a[tot].num = rt = 1;
			return;
		}
		int k = Search(rt, x);
		if (a[k].val == x)
			a[k].num++;
		else
		{
			a[++tot].val = x;
			a[tot].ans = x;
			a[tot].cnt = a[tot].num = 1;
			a[tot].fa = k;
			a[k].ch[x > a[k].val] = tot;
		}
		int k1 = k;
		while (k1)
		{
			Pushup(k1);
			k1 = a[k1].fa;
		}
		Splay((a[k].val == x) ? k : tot);
	}
	il void Delete(int x)
	{
		int k = Search(rt, x);
		Splay(k);
		if (a[k].val != x)
			return;
		if (a[k].num > 1)
			a[k].cnt--, a[k].num--;
		else
		{
			if (!a[k].ch[0])
			{
				rt = a[k].ch[1];
				a[rt].fa = a[k].ch[1] = a[k].cnt = a[k].num = 0;
				a[k].val = a[k].ans = -inf;
			}
			else
			{
				Splay(Search(a[k].ch[0], inf));
				a[rt].ch[1] = a[k].ch[1];
				Pushup(rt);
				a[a[k].ch[1]].fa = rt;
				a[k].fa = a[k].ch[0] = a[k].ch[1] = a[k].cnt = a[k].num = 0;
				a[k].val = a[k].ans = -inf;
			}
		}
	}
	
	il int Get_max()
	{
		return a[rt].ans;
	}
}

signed main()
{
#ifndef Wepdekr
	freopen("hop.in", "r", stdin);
	freopen("hop.out", "w", stdout);
#endif
	n = read(), m = read();
	Get_unable();
	for (ri i = 1; i <= n; i++)
		p[i].num = read(), p[i].pos = read();
	sort(p + 1, p + 1 + n);
	cnt = n;
	for (ri i = 1; i <= n; i++)
		if (p[i].pos == p[i - 1].pos)
		{
			p[i].num += p[i - 1].num;
			p[i - 1].pos = inf;
			cnt--;
		}
	sort(p + 1, p + 1 + n);
	int foo[20];
	for (ri i = 1; i <= cnt; i++)
	{
		foo[0] = 0;
		for (ri j = i - 1; j >= 0; j--)
		{
			if (p[i].pos - p[j].pos > 17)
				break;
			if (!vis[p[i].pos - p[j].pos])
			{
				splay :: Delete(f[j]);
				foo[++foo[0]] = j;
			}
		}
		f[i] = splay :: Get_max() + p[i].num;
		for (ri j = 1; j <= foo[0]; j++)
			splay :: Insert(f[foo[j]]);
		splay :: Insert(f[i]);
	}
	int ans = 0;
	for (ri i = 1; i <= n; i++)
		ans = max(ans, f[i]);
	printf("%lld", ans);
	return 0;
}
/*
3 13
100 4
10 7
1 11

*/

C. 反射镜

题意：给出坐标平面上的 $n$ 面镜子，它们都与坐标轴成 $45 ^ {\circ}$ 角，一束光从原点向 $x$ 轴正方向射出，走过了 $T$ 个单位后的坐标。

思路：并没有什么特别的思路，就是模拟，将镜子坐标离散出来后按照 $x, y$ 双关键字排序后就可以二分找到下一面镜子的位置，然后就可以很快的处理出来。

但是另外有一个很恶心的问题：环。所以我们需要特殊处理。

首先由于初中光学知识，光路是可逆的，也就是说在这道题的情境下，每面镜子的一面最多经过一次，如果出现第二次经过，则出现了环，那么模一下就可以保证复杂度了。

注意：……

代码： $tan 90 ^ {\circ}$

总结

并不是一场特别难的模拟赛，模拟题放 $\text{T3}$ 实在是太毒瘤了，写到后面心态爆炸。

不过 $\text{B}$ 的平衡树一遍打对了，倒还是不错。

整场比赛 $100 + 100 + 5 = 205pts$ 算是不错的成绩，就是可能需要更耐心一些去打模拟，心态爆炸是不行的Da☆Ze

0%