Problem 1537 --跳蚤国王的游戏

1537: 跳蚤国王的游戏

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $2$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
跳蚤国王和蛐蛐国王在玩一个游戏。
他们在一个n行m列的网格上排兵布阵。其中的c个格子中(0<=2c<=nm-3), 每个格子有一只跳蚤,另有c个格子,每个格子中有一只蛐蛐,剩下的nm-2c个格子 是空的。
我们定义跳蚤国王获胜,当某个时刻,网格中存在连续的k个格子,每个格子中 都是跳蚤。连续的k个格子是指,选定某个格子,选定某个方向(上,右,上左,上 右),从这个格子开始在这个方向上连续的k个格子。同理我们可以定义蛐蛐国王获 胜。
在一开始的网格上,保证不存在一方己经获胜,保证至少有3个空格子。
接下来跳蚤国王和蛐蛐国王轮流行动,跳蚤国王先手。跳蚤国王行动的时候,可 以在网格的任意一个空格子里放一只跳蚤;蛐蛐国王行动的时候,可以在网格的任意 一个空格子里放一只蛐蛐。如果某时刻某一方己经获胜,则游戏结束。
现在跳蚤国王想知道,网格中有多少个空格子,使得跳蚤国王第一步在该格子中 放一只跳蚤之后,可以在一步之内获胜。
跳蚤国王在一步之内获胜的意思是,跳蚤国王己经获胜,或者,不论蛐蛐国王下 一步如何行动,蛐蛐国王都不能获胜,且跳蚤国王在接下来的一步中都存在一种获胜 的方案。
跳蚤国王当然知道怎么做啦!但是他想考考你。
put
包含多组测试数据。
输入的第一行只有一个整数T,表示数据的组数。保证1<=T<= 100。
接下来依次输入T组数据,每组数据的第一行包含四个整数n,m,k,c。保证 1<=n,m<=109,5<=k<=105,0<=2c<=min(nm−3,2∗105)。
接下来c行,每行包含两个整数x,y,表示第x行,第y列的格子被一只跳蚤占 据。保证1 <= x <= n,1 <= y <= m;每一组数据当中,同一只跳蚤不会被多次描述。
接下来c行,每行包含两个整数x,y,表示第x行,第y列的格子被一只蛐蛐占 据。保证1 <= x <= n,1 <= y <= m;每一组数据当中,同一只蛐蛐不会被多次描述。
同一行相邻的整数之间由一个空格隔开。
我们记 ∑ c为T组输入数据的所有c的总和,保证 ∑c<=105。 

对于每一组数据依次输出一行一个整数,表示网格中有多少个格子,使得跳蚤国 王第一步在该格子中放一只跳蚤之后,可以在一步之内获胜。
4
12 12 9 7
3 3
4 4
5 5
6 6
7 7
8 8
9 9
12 1
12 2
12 3
11 1
11 2
11 3
1 12
8 8 5 4
3 3
3 4
3 5
3 7
7 3
7 4
8 3
8 4
8 8 5 4
3 3
3 4
3 5
3 6
7 3
7 4
7 5
7 6
8 8 5 4
3 3
3 4
3 5
1 1
7 3
7 4
7 5
7 6
2
3
2
0

推荐代码 查看1537 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战 AOJ大管家 435570 2019-05-31 00:15:27

赛题来源/所属竞赛 2016年中国大学生程序设计竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛