月度归档:2017年03月

Codeforces 455B. A Lot of Games(字典树上博弈)

Andrew, Fedor and Alex are inventive guys. Now they invent the game with strings for two players.

Given a group of n non-empty strings. During the game two players build the word together, initially the word is empty. The players move in turns. On his step player must add a single letter in the end of the word, the resulting word must be prefix of at least one string from the group. A player loses if he cannot move.

Andrew and Alex decided to play this game k times. The player who is the loser of the i-th game makes the first move in the (i + 1)-th game. Guys decided that the winner of all games is the player who wins the last (k-th) game. Andrew and Alex already started the game. Fedor wants to know who wins the game if both players will play optimally. Help him.

Input

The first line contains two integers, n and k (1 ≤ n ≤ 105; 1 ≤ k ≤ 109).

Each of the next n lines contains a single non-empty string from the given group. The total length of all strings from the group doesn’t exceed 105. Each string of the group consists only of lowercase English letters.

Output

If the player who moves first wins, print “First“, otherwise print “Second” (without the quotes).

Examples
input

output

input

output

input

output

题意:给出n个字符串,要求两人轮流对一个空串进行操作,每次在末尾添加一个字符要求添加完后字符串必须是这n个字符串中的某个字符串的前缀。当某个人无法操作视为输。假如某个人在第i轮输掉,那么它在第i+1轮就是先手,那么问在第k轮的时候是第一轮的先手还是后手胜利。

假如只有一轮,我们只需要建立字典树,然后dfs推出来必胜必败态就可以了。但是现在是第k轮的胜败。所以我们必须要考虑在这一轮赢是否是真正优的决策。

假如先手只能输的话,那么他将会一直输,所以导致第k轮也是输。即第一轮的先手必败。

假如先手只能赢的话,那么他们有任何可以选择的余地,所以第k轮的胜负和k的奇偶性有关。

假如先手可以自己决定胜利还是输的话,那么他可以输掉前k-1轮,保证第k轮自己的先手然后获胜就行了。所以是还是第一轮先手必胜。

假如先手无法决定自己胜利还是输的话,那么就相当于后手可以决定胜负,那么先手必败。因为后手一定可以做出对自己有利的决策。

现在考虑状态如何转移:假如一个状态的后继都是只能输的状态,那么这个就是只能赢的状态。

假如一个状态的后继都是只能赢的状态,那么这个就是只能输的状态。

假如一个状态的后继中存在只能输和只能赢的后继,或者是他的后继中有无法自己决策输赢的情况,那么他就是可以自己决定胜负的状态。

同理自己无法决定胜负的状态一定是后继中只有可以自己决定胜负的状态。

然后dfs一下,可以求出字典树root的状态,然后讨论一下就好了。

 

BZOJ 1941: [Sdoi2010]Hide and Seek(K-Dtree查询平面最近点最远点)

Description

小猪iPig在PKU刚上完了无聊的猪性代数课,天资聪慧的iPig被这门对他来说无比简单的课弄得非常寂寞,为了消除寂寞感,他决定和他的好朋友giPi(鸡皮)玩一个更加寂寞的游戏—捉迷藏。 但是,他们觉得,玩普通的捉迷藏没什么意思,还是不够寂寞,于是,他们决定玩寂寞无比的螃蟹版捉迷藏,顾名思义,就是说他们在玩游戏的时候只能沿水平或垂直方向走。一番寂寞的剪刀石头布后,他们决定iPig去捉giPi。由于他们都很熟悉PKU的地形了,所以giPi只会躲在PKU内n个隐秘地点,显然iPig也只会在那n个地点内找giPi。游戏一开始,他们选定一个地点,iPig保持不动,然后giPi用30秒的时间逃离现场(显然,giPi不会呆在原地)。然后iPig会随机地去找giPi,直到找到为止。由于iPig很懒,所以他到总是走最短的路径,而且,他选择起始点不是随便选的,他想找一个地点,使得该地点到最远的地点和最近的地点的距离差最小。iPig现在想知道这个距离差最小是多少。 由于iPig现在手上没有电脑,所以不能编程解决这个如此简单的问题,所以他马上打了个电话,要求你帮他解决这个问题。iPig告诉了你PKU的n个隐秘地点的坐标,请你编程求出iPig的问题。

Input

第一行输入一个整数N 第2~N+1行,每行两个整数X,Y,表示第i个地点的坐标

Output

一个整数,为距离差的最小值。

Sample Input

4
0 0
1 0
0 1
1 1

Sample Output

1

 

HINT

对于30%的数据,N<=1000 对于100%的数据,N<=500000,0<=X,Y<=10^8 保证数据没有重点保证N>=2

还是对K-Dtree的估价函数了解不深啊,我以为最远点的估价函数和最近点的是一样的,结果样例都调不出来。但是我并不知道,这个最近点和最远点的估价函数该怎么证啊QAQ、、、

但是这次居然不用卡常啦,跑的还行,撒花~

 

BZOJ 2850: 巧克力王国(K-Dtree维护矩形中的点和)

Description

巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎,因为大家都不喜
欢过于甜的巧克力。对于每一块巧克力,我们设x和y为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的
评判标准,所以每个人都有两个参数a和b,分别为他自己为牛奶和可可定义的权重,因此牛奶和可可含量分别为x
和y的巧克力对于他的甜味程度即为ax + by。而每个人又有一个甜味限度c,所有甜味程度大于等于c的巧克力他都
无法接受。每块巧克力都有一个美味值h。现在我们想知道对于每个人,他所能接受的巧克力的美味值之和为多少

Input

第一行两个正整数n和m,分别表示巧克力个数和询问个数。接下来n行,每行三个整数x,y,h,含义如题目所示。再
接下来m行,每行三个整数a,b,c,含义如题目所示。

Output

输出m行,其中第i行表示第i个人所能接受的巧克力的美味值之和。

Sample Input

3 3
1 2 5
3 1 4
2 2 1
2 1 6
1 3 5
1 3 7

Sample Output

5
0
4

HINT

1 <= n, m <= 50000,1 <= 10^9,-10^9 <= a, b, x, y <= 10^9。

知道这个题考的是K-Dtree,就想怎么维护出来答案,发现没有动态插入点,那么就不需要替罪羊重建了,直接建树查询即可。K-Dtree每个节点都可以代表了一个矩形区域,我们知道这个节点所代表的矩形边界后,判断一下这个节点的矩形区域是否在ax+by=c这条直线以下,如果是的话直接返回节点维护的和,否则的话分别递归下去。但是不知道为什么我的查询一直T,不断卡常后还是卡不过去,于是就去看别人的写法,改成别人那样查询居然快了10倍??

感觉对这个东西还是不够熟练,每写一次就有很大的常数问题,所以需要进一步研究。