题目名称 2036. [ZJOI2007]捉迷藏
输入输出 hide.in/out
难度等级 ★★★★
时间限制 10000 ms (10 s)
内存限制 512 MB
测试数据 10 简单对比
题目来源 2015-09-15
开放分组 全部用户
提交状态
分类标签
树分治 线段树
通过:63, 提交:318, 通过率:19.81%
GravatarKZNS 100 0.971 s C++
GravatarPSI 100 0.994 s C++
Gravatarfye 100 1.025 s C++
GravatarPSI 100 1.104 s C++
GravatarceerRep 100 1.152 s C++
GravatarTenderRun 100 1.175 s C++
Gravatar张灵犀不和我一般见识真可怕呢(笑 100 1.176 s C++
Gravatarmikumikumi 100 1.350 s C++
Gravatarlcomyn 100 1.391 s C++
Gravatarthomount 100 1.443 s C++
关于 捉迷藏 的讨论
跑的快的那个是某大神写的,
已换成官方数据
Gravatarmikumikumi
2015-09-17 16:13 1楼
回复 @mikumikumi :
你BZOJ上过了?
Gravatarcstdio
2015-09-16 20:43 2楼
回复 @cstdio :
木有,我的代码太丑了,有两个点w了。最后用了从网上找的一份代码,打算有时间再重写一遍
Gravatarmikumikumi
2015-09-20 12:07 3楼
回复 @cstdio :
我在tyvj上评测的
Gravatarmikumikumi
2015-09-16 23:20 4楼
回复 @mikumikumi :
%%%%%
Gravatarcstdio
2015-09-20 09:06 5楼
multiset好慢。。
Gravatarlyxin65
2016-01-09 23:58 6楼
O(m*logm*logn)的算法强行撸过,感觉亵渎了神题……
居然在BZOJ上卡过了……COGS上最慢点到了4s
GravatarFoolMike
2017-06-03 21:20 7楼
想知道 AAAWAAAAAA 的是怎么改的。。。
Gravatarxzz_666
2018-01-17 09:40 8楼
这题对拍的时候n要小一点才能拍出WA。。。然后修改完了立刻查询。。。
n太大了因为最长链很多条,根本拍不出错。。。
给个我拍出错几率较高的生成器([tab]换成\t):

import random
import os
def sys(s):return os.system(s)
def rand(l,r):return int(random.uniform(l,r+1))
cnt=0
while True:
[tab]fout=open("hide.in","w")
[tab]n,m=10,10
[tab]orz=[i+1 for i in range(0,n)]
[tab]random.shuffle(orz)
[tab]print(n,file=fout)
[tab]for i in range(2,n+1):print(rand(1,i-1),i,file=fout)
[tab]print(m*2,file=fout)
[tab]for tjj in range(0,m):
[tab][tab]print('C',orz[tjj],file=fout)
[tab][tab]print('G',file=fout)
[tab]fout.close()
[tab]sys("./hide && ./std")
[tab]cnt+=1;print(cnt,end=' ')
[tab]if sys("diff hide.out hide.ans"):break
[tab]print("AC")
print("WA")
Gravatarxzz_666
2018-01-17 21:54 9楼
GravatarHyoi_Turkey
2018-03-14 17:17 10楼

2036. [ZJOI2007]捉迷藏

★★★★   输入文件:hide.in   输出文件:hide.out   简单对比
时间限制:10 s   内存限制:512 MB

【题目描述】

Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋子都互相可达。

游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia希望知道可能的最远的两个孩子的距离(即最远的两个关灯房间的距离)。

我们将以如下形式定义每一种操作:

C(hange) i 改变第i个房间的照明状态,若原来打开,则关闭;若原来关闭,则打开。

G(ame)     开始一次游戏,查询最远的两个关灯房间的距离。

【输入格式】

第一行包含一个整数N,表示房间的个数,房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b,表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q,表示操作次数。接着Q行,每行一个操作,如上文所示。

【输出格式】

对于每一个操作Game,输出一个非负整数到hide.out,表示最远的两个关灯房间的距离。若只有一个房间是关着灯的,输出0;若所有房间的灯都开着,输出-1。

【样例输入】

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G

【样例输出】

4
3
3
4

【提示】

对于20%的数据, N ≤50, M ≤100;

对于60%的数据, N ≤3000, M ≤10000;

对于100%的数据, N ≤100000, M ≤500000。

【来源】

http://www.tyvj.cn

曹钦翔 《数据结构的提炼与压缩》