2017/10/12 NOIp模拟赛

发表于 更新于 阅读次数： 本文字数： 4.4k 阅读时长 ≈ 4 分钟

概述

我从未写过模拟赛的题解，但是这次模拟赛全部是原题，因此写公开题解也不会有版权问题。所有题目2s,512MB。

prmq

来源

codechef June17 Chef and Prime Queries

题意

给定$N$($N\le10^5$)个数$A_{1\dots N}$($2\le A_i\le 10^6$)，$Q$($Q\le10^5$)个询问$L,R,X,Y$($1\le L\le R\le N,1\le X\le Y\le 10^6$)，求$A_{L\dots R}$中的数包含$X\dots Y$中的质因数的总数。

样例

1
2
3
4
5
4 
2 3 4 5
2
1 3 2 3
1 4 2 5
1
2
4
5

子任务

  • 30%:$N,Q\le100,X,Y,A_i\le1,000$
  • 50%:$N,Q\le1,000,X,Y,A_i\le10,000$
  • 100%:$N,Q\le10^5$

题解

30%

在原题和模拟赛中都提供了一个代码片段，将其实现加上$O(\sqrt V)$的质数判断即可得到30%。时间复杂度$O(QVN\log V)$

50%

可以发现每个数的不同质因数的数量是相当有限的，具体的，对于$A_i\le10^6$，最多只有7个不同的质因数(2*3*5*7*11*13*17=510,510)。因此对每个数分解质因数，每次扫描$A_{L\dots R}$统计合法的质因数个数。时间复杂度$O(N\sqrt V+QN)$，当然第二项要*7。

100%

进一步，这其实就是一个二维数点问题，一维是$L\dots R$，另一维是$X\dots Y$。这两维范围并不大，所以不需要离散化，可以用树套树，也可以用主席树^ptree。模拟赛时，我还想到了莫队，但好像难以实现；有人写了，但只有暴力分。我用了半个多小时写完了好久没写的主席树，还写了欧拉筛，调到一个小时过了样例。然后又很快写了一下对拍，没有错误。时间复杂度$O(V+N(\sqrt V+\log V)+Q\log V)$，空间复杂度$O(N\log V)$。实际上，不需要$O(V)$欧拉筛，直接质因数分解也可以。

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
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("prmq.in");
ofstream fout("prmq.out");
const int N = 100005, V = 1e6;
int a[N], p[N], cc, root[N * 8], tr[N];
bool bl[V + 5];
struct node
{
	int sum, ls, rs;
} tree[N * 150];
void modify(int &id, int pred, int l, int r, int x, int val)
{
	id = ++cc;
	tree[id] = tree[pred];
	if (l == r)
		tree[id].sum += val;
	else
	{
		int mid = (l + r) / 2;
		if (x <= mid)
			modify(tree[id].ls, tree[pred].ls, l, mid, x, val);
		else
			modify(tree[id].rs, tree[pred].rs, mid + 1, r, x, val);
		tree[id].sum = tree[tree[id].ls].sum + tree[tree[id].rs].sum;
	}
}
int query(int rl, int rr, int l, int r, int L, int R)
{
	if (L <= l && R >= r)
		return tree[rr].sum - tree[rl].sum;
	int mid = (l + r) / 2, sum = 0;
	if (L <= mid)
		sum += query(tree[rl].ls, tree[rr].ls, l, mid, L, R);
	if (R > mid)
		sum += query(tree[rl].rs, tree[rr].rs, mid + 1, r, L, R);
	return sum;
}
int main()
{
	int pn = 0;
	for (int i = 2; i <= V; i++)
	{
		if (!bl[i])
			p[++pn] = i;
		for (int j = 1; j <= pn && i * p[j] <= V; j++)
		{
			bl[i * p[j]] = true;
			if (i % p[j] == 0)
				break;
		}
	}
	int n;
	fin >> n;
	int rn = 0;
	for (int i = 1; i <= n; i++)
	{
		int x;
		fin >> x;
		for (int j = 1; p[j] * p[j] <= x && x > 1; j++)
			if (x % p[j] == 0)
			{
				int cnt = 0;
				for (; x % p[j] == 0; x /= p[j])
					cnt++;
				rn++;
				modify(root[rn], root[rn - 1], 1, pn, j, cnt);
			}
		if (x > 1)
		{
			rn++;
			modify(root[rn], root[rn - 1], 1, pn, lower_bound(p + 1, p + pn + 1, x) - p, 1);
		}
		tr[i] = rn;
	}
	int q;
	fin >> q;
	while (q--)
	{
		int l, r, x, y;
		fin >> l >> r >> x >> y;
		x = lower_bound(p + 1, p + pn + 1, x) - p;
		y = upper_bound(p + 1, p + pn + 1, y) - p - 1;
		fout << query(root[tr[l - 1]], root[tr[r]], 1, pn, x, y) << endl;
	}
	return 0;
}

但是，上课曾经讲过二维数点可以离线解决。这题最方便的写法是将询问拆成$(R,X,Y)-(L-1,X,Y)$，排序，用树状数组维护每个质因数出现的次数即可。时间复杂度$O(N(\sqrt V+\log V)+Q\log V)$，空间复杂度$O(V+Q)$，比主席树更简单。

得分

0 20 30 50 100 平均分
7 4 2 12 8 47

这题的思路比较简单，只要写数据结构，是平均分最高的一题。

ants

来源

AtCoder Grand Contest 013C Ants on a Circle

题意

在一个周长为$L$($L\le10^9$)的圆上有$N$($N\le10^5$)只蚂蚁，每只蚂蚁初始位置为$X_i$($X_i\in\mathbb{N},0\le X_i<L$)，方向$W_i$($W_i\in{1,2}$,1为顺时针，2为逆时针)。每只蚂蚁在单位时间内移动单位距离，两只蚂蚁相撞会立即掉头，求$T$($T\le10^9$)时刻每只蚂蚁对应的位置。

样例

1
2
3
4
3 8 3
0 1
3 2
6 1
1
2
3
1
3
0

子任务

  • 30%:$T\le100$
  • 另30%:$X_1-T\ge0,X_N+T<L$
  • 100%:$0\le X_1<X_2\dots<X_N<L$

题解

很容易发现，我们可以计算出所有蚂蚁的最终位置，因为两只蚂蚁相撞可以看作直接对穿而过。因此只要确定每只蚂蚁最终位置的对应关系。

30%

找不到对应关系，但还是可以直接模拟这个过程的。简单起见，把坐标乘以2，这样只会在整数时刻相撞，模拟$2T$时间，一直保持坐标的有序性。这样模拟是比较难写的，时间复杂度$O(NT)$。在模拟赛中，我在这题上花了很多时间，写了一个$O(TN\log N)$的模拟，但最终0分。

另30%

这种情况下不会绕圈，可以发现蚂蚁相撞后，其排名没有改变。只要把最终位置排序，就与初始位置是一一对应的。这里的30%比上述简单多了，时间复杂度$O(N\log N)$。这个问题很经典，可以在洛谷P1367交，注意不同的是蚂蚁没有排序，需要先进行排序。

100%

如果蚂蚁可以绕圈，会发生什么呢？只要确定排名为1的蚂蚁在最终位置中的编号。如果一只蚂蚁顺时针穿过了$X=0$，可以发现排名为1的蚂蚁在最终编号中+1，就是样例的情况；反之亦然。因此，我们可以根据每只蚂蚁穿过$X=0$的次数计算出排名为1的蚂蚁在最终位置中的标号。时间复杂度$O(N\log 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
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("ants.in");
ofstream fout("ants.out");
const int N = 1e5;
int a[N];
int main()
{
	int n, l, t;
	fin >> n >> l >> t;
	int start = 0;
	for (int i = 0; i < n; i++)
	{
		int x, dir;
		fin >> x >> dir;
		if (dir == 1)
		{
			a[i] = (x + t) % l;
			start = (start + (x + t - a[i]) / l) % n;
		}
		else
		{
			a[i] = ((x - t) % l + l) % l;
			start = (start + (x - t - a[i]) / l) % n;
		}
	}
	sort(a, a + n);
	start = (start % n + n) % n;
	rotate(a, a + start, a + n);
	for (int i = 0; i < n; i++)
		fout << a[i] << endl;
	return 0;
}

得分

0 30 60 100 平均分
24 5 2 2 14

这题的思路比较巧妙，而模拟比较难写，是得分最低的。

piling

来源

AtCoder Grand Contest 013D Piling Up

题意

盒子里有无限多的红色和蓝色积木，先任意取出$N$($N\le3,000$)块，再进行$M$($M\le3,000$)次以下操作来搭$2M$高的塔：

  • 将任意一块积木放在塔上
  • 取出一块红色积木和一块蓝色积木
  • 将任意一块积木放在塔上

样例

1
2 3
1
56

子任务

  • 30%:$N,M\le5$
  • 50%:$N,M\le100$
  • 100%:$1\le N,M\le3,000$

题解