Codeforces Round #567 Div.2 D. Irrigation总结(Treap)


本来为了节省时间,决定之后不再写CF比赛的总结(要不然得写到天荒地老),但是这道题折磨了我一天多的时间,最后甚至连对拍器都写出来了,所以值得一写,顺便也总结一下Treap……

题目链接:https://codeforces.com/contest/1181/problem/D

题意

m个城市要轮流举办奥运会,按举办次数从小到大且编号从小到大的顺序,之前奥运会已经举办过了n次。给定q个询问,问这些年份分别是哪些城市举办奥运会。

分析

解法1:名次树

考虑一下实际举办的情况,很容易想到一种这样的算法:首先把所有城市按举办次数为第一关键字,编号为第二关键字排序,然后每次取第一个城市为下一年举办奥运会的城市,取完之后更新举办次数,重新排序;等到各城市举办次数都一样之后,就只是按编号顺序继续举办了。当然,直接这么做肯定会超时。

继续观察可以发现,如果前面有几个城市的举办次数都相同,那么它们会轮流举办,直到每个城市的举办次数都达到之后的举办次数更多的城市为止。下面是题解里的图:

顺序示意图

首先城市3会举办一次。之后,2、3、5的举办次数就相等了,会按2、3、5的顺序各举办一次。这之后,1、2、3、5、8的举办次数就相等了,会按1、2、3、5、8的顺序举办两次……

这样解题思路就很清楚了。首先把城市排序,查询也排序;然后对于每个查询,判断它位于哪两个举办次数的区间中,然后把之前的年份都加到一个名次树中,根据查询的具体大小计算它应该轮到第几个城市,最后在名次树里查询就可以了。

结果问题出在了名次树上。我从网上找了一个Treap模板,结果总是在Test 15超时,最后把这个Treap模板和其他模板对比,发现这个模板的插入操作写挂了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insert(Node* &o,int v)
{
if (!o) {
o = new Node(v);
return;
} else {
int d = o -> cmp(v);
if(d == -1) o -> w++;
else {
insert(o -> ch[d], v);
// 这里变成指针比较了,而不是rank比较
if(o -> ch[d] > o) rotate(o, d^1);
}
}
o->maintain();
}

然而,经过我漫长的对拍,似乎这个写法并不是错的,只会影响效率(大概这也是为什么原作者没发现)。但是查了半天,都说这样的指针比较是未被定义的,所以如果不认真看看代码,恐怕并不知道为什么这样不是错的……

解法2:一种不需要名次树的方法

这种方法的思路是这样的:想象一个宽度为M,高度无限的矩形,每年在矩形中的一个格子上着色,按从左到右,从下向上的顺序。着色的列表示当年举办奥运会的城市,即在第T年,会对第T % M列染色。现在的问题是,已经有N个城市举办过比赛了;在这种情况下,仍然可以顺序染色,只要把举办过比赛的城市跳过去就行。

把这种方法和上一种对比,会发现实际效果是相同的:在举办次数较少的城市的举办次数没有超过举办次数更多的城市之前,一直在那些举办次数较少的城市之间轮流举行。问题是怎么确定跳过哪些城市。以题目中的Example 1为例,第7到16年的奥运会是这样举办的:

1
2
3
4
5
6
7
8
9
10
11
...
+----+----+----+----+
| 13 | 14 | 15 | 16 |
+----+----+----+----+
| * | 10 | 11 | 12 |
+----+----+----+----+
| * | * | 8 | 9 |
+----+----+----+----+
| * | * | * | 7 |
+----+----+----+----+
1 2 3 4

为了快速找到年份对应的格子,不妨在为*号的格子里也填上数字,具体的数字是下一个年份-1:

1
2
3
4
5
6
7
8
9
10
+----+----+----+----+
| 13 | 14 | 15 | 16 |
+----+----+----+----+
| 9 | 10 | 11 | 12 |
+----+----+----+----+
| 7 | 7 | 8 | 9 |
+----+----+----+----+
| 6 | 6 | 6 | 7 |
+----+----+----+----+
1 2 3 4

填上的数字为[6, 6, 6, 7, 7, 9]。于是,对于每一个查询的年份,只要二分查找一共有多少个填充的数字比它小,就可以知道一共跳过了多少个城市,然后就可以计算出这一年应该在哪个城市举办奥运会了。

代码

解法1:https://codeforces.com/contest/1181/submission/55874889

解法2:https://codeforces.com/contest/1181/submission/55650482

对拍器

这里为了方便起见,干脆把Windows版的脚本对拍器贴出来。当然,如果有朝一日非得对拍而又没有网的话,写个管道+C++对拍器可能更简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
@echo off
:loop
gen
echo New data generated
std < a.in > std.out
echo Std executed
a < a.in > a.out
echo Program executed
fc /a a.out std.out
if errorlevel 1 pause
echo test finished
goto loop
pause

 评论