2017/10/12 NOIp模拟赛

概述

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

prmq

来源

codechef June17 Chef and Prime Queries

题意

给定NN(N105N\le10^5)个数 (2Ai1062\le A_i\le 10^6),QQ(Q105Q\le10^5)个询问L,R,X,YL,R,X,Y(1LRN,1XY1061\le L\le R\le N,1\le X\le Y\le 10^6),求 中的数包含 中的质因数的总数。

样例

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,Q100,X,Y,Ai1,000N,Q\le100,X,Y,A_i\le1,000
  • 50%:N,Q1,000,X,Y,Ai10,000N,Q\le1,000,X,Y,A_i\le10,000
  • 100%:N,Q105N,Q\le10^5

题解

30%

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

50%

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

100%

进一步,这其实就是一个二维数点问题,一维是 ,另一维是 。这两维范围并不大,所以不需要离散化,可以用树套树,也可以用主席树^ptree。模拟赛时,我还想到了莫队,但好像难以实现;有人写了,但只有暴力分。我用了半个多小时写完了好久没写的主席树,还写了欧拉筛,调到一个小时过了样例。然后又很快写了一下对拍,没有错误。时间复杂度O(V+N(V+logV)+QlogV)O(V+N(\sqrt V+\log V)+Q\log V),空间复杂度O(NlogV)O(N\log V)。实际上,不需要O(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)(L1,X,Y)(R,X,Y)-(L-1,X,Y),排序,用树状数组维护每个质因数出现的次数即可。时间复杂度O(N(V+logV)+QlogV)O(N(\sqrt V+\log V)+Q\log V),空间复杂度O(V+Q)O(V+Q),比主席树更简单。

得分

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

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

ants

来源

AtCoder Grand Contest 013C Ants on a Circle

题意

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

样例

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

子任务

  • 30%:T100T\le100
  • 另30%:X1T0,XN+T<LX_1-T\ge0,X_N+T<L
  • 100%:

题解

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

30%

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

另30%

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

100%

如果蚂蚁可以绕圈,会发生什么呢?只要确定排名为1的蚂蚁在最终位置中的编号。如果一只蚂蚁顺时针穿过了X=0X=0,可以发现排名为1的蚂蚁在最终编号中+1,就是样例的情况;反之亦然。因此,我们可以根据每只蚂蚁穿过X=0X=0的次数计算出排名为1的蚂蚁在最终位置中的标号。时间复杂度O(NlogN)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

题意

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

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

样例

1
2 3
1
56

子任务

  • 30%:N,M5N,M\le5
  • 50%:N,M100N,M\le100
  • 100%:1N,M3,0001\le N,M\le3,000

题解