 不知道结果是什么样，但是不挣扎的话，就连RP爆炸摸到牌的机会都没有吧。
A.Cooking Competition
题意
给你几种操作，让你根据种类给Kobayashi或者Tohru加分，最后让你输出谁的分高。
解法
水题直接做就好了，其中3、4两种情况可以直接忽略，因为不产生分差所以对最后结果并没有影响。
原题
Time Limit: 1 Second Memory Limit: 65536 KB
“Miss Kobayashi’s Dragon Maid” is a Japanese manga series written and illustrated by Coolkyoushinja. An anime television series produced by Kyoto Animation aired in Japan between January and April 2017.
In episode 8, two main characters, Kobayashi and Tohru, challenged each other to a cookoff to decide who would make a lunchbox for Kanna’s field trip. In order to decide who is the winner, they asked n people to taste their food, and changed their scores according to the feedback given by those people.
There are only four types of feedback. The types of feedback and the changes of score are given in the following table.
Type  Feedback 
Score Change (Kobayashi) 
Score Change (Tohru) 

1  Kobayashi cooks better  +1  0 
2  Tohru cooks better  0  +1 
3  Both of them are good at cooking  +1  +1 
4  Both of them are bad at cooking  1  1 
Given the types of the feedback of these n people, can you find out the winner of the cooking competition (given that the initial score of Kobayashi and Tohru are both 0)?
Input
There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 100), indicating the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 20), its meaning is shown above.
The next line contains n integers a_{1}, a_{2}, … , a_{n} (1 ≤ a_{i} ≤ 4), indicating the types of the feedback given by these n people.
Output
For each test case output one line. If Kobayashi gets a higher score, output “Kobayashi” (without the quotes). If Tohru gets a higher score, output “Tohru” (without the quotes). If Kobayashi’s score is equal to that of Tohru’s, output “Draw” (without the quotes).
Sample Input
2 3 1 2 1 2 3 4
Sample Output
Kobayashi Draw
Hint
For the first test case, Kobayashi gets 1 + 0 + 1 = 2 points, while Tohru gets 0 + 1 + 0 = 1 point. So the winner is Kobayashi.
For the second test case, Kobayashi gets 1  1 = 0 point, while Tohru gets 1  1 = 0 point. So it’s a draw.
代码
1 

B.Problem Preparation
题意
每个查询都给你一个数列让你判断是否合法，要求n在1013，然后难度从两个1开始，后面难度差不能超过2，最难的一道只能有一道，且不受难度梯度的限制
解法
先排序，然后顺序检查即可。
原题
It’s time to prepare the problems for the 14th Zhejiang Provincial Collegiate Programming Contest! Almost all members of Zhejiang University programming contest problem setter team brainstorm and code day and night to catch the deadline, and empty bottles of Marjar Cola litter the floor almost everywhere!
To make matters worse, one of the team member fell ill just before the deadline. So you, a brilliant student, are found by the team leader Dai to help the team check the problems’ arrangement.
Now you are given the difficulty score of all problems. Dai introduces you the rules of the arrangement:
 The number of problems should lie between 10 and 13 (both inclusive).
 The difficulty scores of the easiest problems (that is to say, the problems with the smallest difficulty scores) should be equal to 1.
 At least two problems should have their difficulty scores equal to 1.
 After sorting the problems by their difficulty scores in ascending order, the absolute value of the difference of the difficulty scores between two neighboring problems should be no larger than 2. BUT, if one of the two neighboring problems is the hardest problem, there is no limitation about the difference of the difficulty scores between them. The hardest problem is the problem with the largest difficulty score. It’s guaranteed that there is exactly one hardest problem.
The team members have given you lots of possible arrangements. Please check whether these arrangements obey the rules or not.
Input
There are multiple test cases. The first line of the input is an integer T (1 ≤ T ≤ 10^{4}), indicating the number of test cases. Then T test cases follow.
The first line of each test case contains one integer n (1 ≤ n ≤ 100), indicating the number of problems.
The next line contains n integers s_{1}, s_{2}, … , s_{n} (1000 ≤ s_{i} ≤ 1000), indicating the difficulty score of each problem.
We kindly remind you that this problem contains large I/O file, so it’s recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.
Output
For each test case, output “Yes” (without the quotes) if the arrangement follows the rules, otherwise output “No” (without the quotes).
Sample Input
8 9 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 999 1 1 2 3 4 5 6 7 8 9 11 999 1 3 5 7 9 11 13 17 19 21 10 15 1 13 17 1 7 9 5 3 11 13 1 1 1 1 1 1 1 1 1 1 1 1 2 10 2 3 4 5 6 7 8 9 10 11 10 15 1 13 3 6 5 4 7 1 14
Sample Output
No No Yes No Yes Yes No No
Hint
The first arrangement has 9 problems only, which violates the first rule.
Only one problem in the second and the fourth arrangement has a difficulty score of 1, which violates the third rule.
The easiest problem in the seventh arrangement is a problem with a difficulty score of 2, which violates the second rule.
After sorting the problems of the eighth arrangement by their difficulty scores in ascending order, we can get the sequence 1, 1, 3, 4, 5, 6, 7, 13, 14, 15. We can easily discover that 13  7 = 6 > 2. As the problem with a difficulty score of 13 is not the hardest problem (the hardest problem in this arrangement is the problem with a difficulty score of 15), it violates the fourth rule.
代码
1 

C.What Kind of Friends Are You?
题意
有c种friend的类型，q个询问，n个回答询问的人，询问是一个列表，每个人都回答所有询问，如果这个人的类型在list里边他就会回答yes，否则回答no，让你判断能否判断这个人的friend类型，如果可以那就输出他的friend类型，否则输出Let’s go to the library!!
解法
一开始脑洞太大了以为这里要考虑排除法的情况，但是实际上这道题还是有点漏洞，还好样例还是比较强，基本只要过了样例应该就没问题了，对所有yes的情况做一个集合交，然后从中间删去被no否定的情况，如果只剩下一个了，那么就可以确定，否则不行。 除非我读错题意了，否则我觉得这道题应该把可以排除法确定的情况考虑进去。
另外，我这里用了一个vis数组来处理每个询问之间的关系，这道题据说可以用set强行维护交集。
原题
Time Limit: 1 Second Memory Limit: 65536 KB
Japari Park is a large zoo home to extant species, endangered species, extinct species, cryptids and some legendary creatures. Due to a mysterious substance known as Sandstar, all the animals have become anthropomorphized into girls known as Friends.
Kaban is a young girl who finds herself in Japari Park with no memory of who she was or where she came from. Shy yet resourceful, she travels through Japari Park along with Serval to find out her identity while encountering more Friends along the way, and eventually discovers that she is a human.
However, Kaban soon finds that it’s also important to identify other Friends. Her friend, Serval, enlightens Kaban that she can use some questions whose expected answers are either “yes” or “no” to identitfy a kind of Friends.
To be more specific, there are n Friends need to be identified. Kaban will ask each of them q same questions and collect their answers. For each question, she also gets a full list of animals’ names that will give a “yes” answer to that question (and those animals who are not in the list will give a “no” answer to that question), so it’s possible to determine the name of a Friends by combining the answers and the lists together.
But the work is too heavy for Kaban. Can you help her to finish it?
Input
There are multiple test cases. The first line of the input is an integer T (1 ≤ T ≤ 100), indicating the number of test cases. Then T test cases follow.
The first line of each test case contains two integers n (1 ≤ n ≤ 100) and q (1 ≤ q ≤ 21), indicating the number of Friends need to be identified and the number of questions.
The next line contains an integer c (1 ≤ c ≤ 200) followed by c strings p_{1}, p_{2}, … , p_{c} (1 ≤ p_{i} ≤ 20), indicating all known names of Friends.
For the next q lines, the ith line contains an integer m_{i} (0 ≤ m_{i} ≤ c) followed by m_{i} strings s_{i, 1}, s_{i, 2}, … , s_{i, mi} (1 ≤ s_{i, j} ≤ 20), indicating the number of Friends and their names, who will give a “yes” answer to the ith question. It’s guaranteed that all the names appear in the known names of Friends.
For the following n lines, the ith line contains q integers a_{i, 1}, a_{i, 2}, … , a_{i, q} (0 ≤ a_{i, j} ≤ 1), indicating the answer (0 means “no”, and 1 means “yes”) to the jth question given by the ith Friends need to be identified.
It’s guaranteed that all the names in the input consist of only uppercase and lowercase English letters.
Output
For each test case output n lines. If Kaban can determine the name of the ith Friends need to be identified, print the name on the ith line. Otherwise, print “Let’s go to the library!!” (without quotes) on the ith line instead.
Sample Input
2 3 4 5 Serval Raccoon Fennec Alpaca Moose 4 Serval Raccoon Alpaca Moose 1 Serval 1 Fennec 1 Serval 1 1 0 1 0 0 0 0 1 0 0 0 5 5 11 A B C D E F G H I J K 3 A B K 4 A B D E 5 A B K D E 10 A B K D E F G H I J 4 B D E K 0 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 1
Sample Output
Serval Let's go to the library!! Let's go to the library!! Let's go to the library!! Let's go to the library!! B Let's go to the library!! K
Hint
The explanation for the first sample test case is given as follows:
As Serval is the only known animal who gives a “yes” answer to the 1st, 2nd and 4th question, and gives a “no” answer to the 3rd question, we output “Serval” (without quotes) on the first line.
As no animal is known to give a “no” answer to all the questions, we output “Let’s go to the library!!” (without quotes) on the second line.
Both Alpaca and Moose give a “yes” answer to the 1st question, and a “no” answer to the 2nd, 3rd and 4th question. So we can’t determine the name of the third Friends need to be identified, and output “Let’s go to the library!!” (without quotes) on the third line.
代码
1 

D.Let’s Chat
题意
A和B连续互发消息m天为就擦出火花，友♂情♂值++，给你每个人给对面发消息的一些区间，求出两人最终的友♂情♂值。
解法
由于x, y的范围只有100，至多会搞出来400个区间，那么把这些区间离散化，然后根据数据给的区间，维护这些离散化区间是否被覆盖，最后找出两人互动的时间区间，然后每个分离的区间，对答案的贡献是max{区间长度m+1,0}
原题
ACM (ACMers’ Chatting Messenger) is a famous instant messaging software developed by Marjar Technology Company. To attract more users, Edward, the boss of Marjar Company, has recently added a new feature to the software. The new feature can be described as follows:
If two users, A and B, have been sending messages to each other on the last m consecutive days, the “friendship point” between them will be increased by 1 point.
More formally, if user A sent messages to user B on each day between the (i  m + 1)th day and the ith day (both inclusive), and user B also sent messages to user A on each day between the (i  m + 1)th day and the ith day (also both inclusive), the “friendship point” between A and B will be increased by 1 at the end of the ith day.
Given the chatting logs of two users A and B during n consecutive days, what’s the number of the friendship points between them at the end of the nth day (given that the initial friendship point between them is 0)?
Input
There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 10), indicating the number of test cases. For each test case:
The first line contains 4 integers n (1 ≤ n ≤ 10^{9}), m (1 ≤ m ≤ n), x and y (1 ≤ x, y ≤ 100). The meanings of n and m are described above, while x indicates the number of chatting logs about the messages sent by A to B, and y indicates the number of chatting logs about the messages sent by B to A.
For the following x lines, the ith line contains 2 integers l_{a, i} and r_{a, i} (1 ≤ l_{a, i} ≤ r_{a, i} ≤ n), indicating that A sent messages to B on each day between the l_{a, i}th day and the r_{a, i}th day (both inclusive).
For the following y lines, the ith line contains 2 integers l_{b, i} and r_{b, i} (1 ≤ l_{b, i} ≤ r_{b, i} ≤ n), indicating that B sent messages to A on each day between the l_{b, i}th day and the r_{b, i}th day (both inclusive).
It is guaranteed that for all 1 ≤ i < x, r_{a, i} + 1 < l_{a, i + 1} and for all 1 ≤ i < y, r_{b, i} + 1 < l_{b, i + 1}.
Output
For each test case, output one line containing one integer, indicating the number of friendship points between A and B at the end of the nth day.
Sample Input
2 10 3 3 2 1 3 5 8 10 10 1 8 10 10 5 3 1 1 1 2 4 5
Sample Output
3 0
Hint
For the first test case, user A and user B send messages to each other on the 1st, 2nd, 3rd, 5th, 6th, 7th, 8th and 10th day. As m = 3, the friendship points between them will be increased by 1 at the end of the 3rd, 7th and 8th day. So the answer is 3.
代码
1 

E.Seven Segment Display
题意
有一个8位的7段液晶数字显示器（总之就是计算器上那种显示方式来表示一个16进制数），每个数位的显示要根据组成它的段的多少每秒付出能量，输入秒数n和初始值，每秒这个数字自增1，如果到了FFFFFFFF下一秒会变00000000，问你n秒后消耗了多少能量。
做法
很显然，数字的递增是有规律的，第0位 \(16\) s一循环，第1位 \(16^2\) s一循环，以此类推，因此就根据这个逐位运算就可以了。把n逐次减去16的幂次就可以顺推出cost了。我的代码里为了减少变数用了先尽可能把低位变0的办法来简化思考的复杂度。由于保证低位全是0，每次第i位自增一个数，要经过 \(16^i\) s，在不断减1s的过程当中，高位数位全部不变，低位数位走循环，当前位数字根据n的大小和数位当前字改变一定周期，根据上面这些条件我们可以在常数时间内算出每一位增加到0所花的时间和需要的cost。然后我的做法是先从低位推到高位，然后高位推回低位，这样保证低于当前位的数位全是0，如果不这样做的话需要考虑的因素可能会多一点，虽然队友用直接从高位搞到低位的方法没有AC，但是我觉得应该也是能做的。
原题
A seven segment display, or seven segment indicator, is a form of electronic display device for displaying decimal numerals that is an alternative to the more complex dot matrix displays. Seven segment displays are widely used in digital clocks, electronic meters, basic calculators, and other electronic devices that display numerical information.
Edward, a student in Marjar University, is studying the course “Logic and Computer Design Fundamentals” this semester. He bought an eightdigit seven segment display component to make a hexadecimal counter for his course project.
In order to display a hexadecimal number, the seven segment display component needs to consume some electrical energy. The total energy cost for display a hexadecimal number on the component is the sum of the energy cost for displaying each digit of the number. Edward found the following table on the Internet, which describes the energy cost for display each kind of digit.


For example, in order to display the hexadecimal number “5A8BEF67” on the component for one second, 5 + 6 + 7 + 5 + 5 + 4 + 6 + 3 = 41 units of energy will be consumed.
Edward’s hexadecimal counter works as follows:
 The counter will only work for n seconds. After n seconds the counter will stop displaying.
 At the beginning of the 1st second, the counter will begin to display a previously configured eightdigit hexadecimal number m.
 At the end of the ith second (1 ≤ i < n), the number displayed will be increased by 1. If the number displayed will be larger than the hexadecimal number “FFFFFFFF” after increasing, the counter will set the number to 0 and continue displaying.
Given n and m, Edward is interested in the total units of energy consumed by the seven segment display component. Can you help him by working out this problem?
Input
There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 10^{5}), indicating the number of test cases. For each test case:
The first and only line contains an integer n (1 ≤ n ≤ 10^{9}) and a capitalized eightdigit hexadecimal number m (00000000 ≤ m ≤ FFFFFFFF), their meanings are described above.
We kindly remind you that this problem contains large I/O file, so it’s recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.
Output
For each test case output one line, indicating the total units of energy consumed by the eightdigit seven segment display component.
Sample Input
3 5 89ABCDEF 3 FFFFFFFF 7 00000000
Sample Output
208 124 327
Hint
For the first test case, the counter will display 5 hexadecimal numbers (89ABCDEF, 89ABCDF0, 89ABCDF1, 89ABCDF2, 89ABCDF3) in 5 seconds. The total units of energy cost is (7 + 6 + 6 + 5 + 4 + 5 + 5 + 4) + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 6) + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 2) + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 5) + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 5) = 208.
For the second test case, the counter will display 3 hexadecimal numbers (FFFFFFFF, 00000000, 00000001) in 3 seconds. The total units of energy cost is (4 + 4 + 4 + 4 + 4 + 4 + 4 + 4) + (6 + 6 + 6 + 6 + 6 + 6 + 6 + 6) + (6 + 6 + 6 + 6 + 6 + 6 + 6 + 2) = 124.
代码
1 

F.Heap Partition
题意
要求把序列S分成尽可能少的子序列，使得这个子序列能够组成一个二叉树，满足 \(j为i的父结点时\) \(s_j ≤ s_i\) 且 \(j < i\) 成立，并且输出这些子序列
解法
关键是要想到贪心的方法：对于每一个序列，下标i最小的那个结点一定是作为根出现，因此直接从左到右把第一个未被加入树的点作为根，然后尽可能的把之后的结点加到二叉树里面去，用multiset来维护二叉树的叶子结点的可行性（因为只有大于等于 \(s_i\) 的结点可以作为 \(i\) 结点的儿子）。
代码
1 

G.Yet Another Game of Stones
本题ref: http://blog.csdn.net/dormousenone/article/details/70599659
题意
Alice 和 Bob玩一个nim游戏的变种，Alice受到的限制比Bob多，最关键要想到Bob必胜的两种情况，也就是把b_i == 2的堆变成只有一个，那么Bob只要不管怎么取都只在最后取b_i == 2那一堆就必胜。所以Alice在这种情况下的唯一策略就是取走全部，取不走就输了，取走的话变成bob先手的nim游戏 有一堆b_i == 1且a_i > 1 的情况下，Alice取这堆不一定能够使nim平衡，那么bob只要构造高位必须选这一堆才能平衡，最低位不能平衡的情况就可以了（想得不严谨）
原题
Alice and Bob are playing yet another game of stones. The rules of this game are as follow:
 The game starts with n piles of stones indexed from 1 to n. The ith pile contains a_{i} stones and a special constraint indicated as b_{i}.
 The players make their moves alternatively. The allowable moves for the two players are different.
 An allowable move of Bob is considered as removal of some positive number of stones from a pile.

An allowable move of Alice is also considered as removal of some positive number of stones from a pile, but is limited by the constraint b_{i} of that pile.
 If b_{i} = 0, there are no constraints.
 If b_{i} = 1, Alice can only remove some odd number of stones from that pile.
 If b_{i} = 2, Alice can only remove some even number of stones from that pile.
 The player who is unable to make an allowable move loses.
Alice is always the first to make a move. Do you know who will win the game if they both play optimally?
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 10^{5}), indicating the number of piles.
The second line contains n integers a_{1}, a_{2}, …, a_{n} (1 ≤ a_{i} ≤ 10^{9}), indicating the number of stones in each pile.
The third line of each test case contains n integers b_{1}, b_{2}, …, b_{n} (0 ≤ b_{i} ≤ 2), indicating the special constraint of each pile.
It is guaranteed that the sum of n over all test cases does not exceed 10^{6}.
We kindly remind you that this problem contains large I/O file, so it’s recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.
Output
For each test case, output “Alice” (without the quotes) if Alice will win the game. Otherwise, output “Bob” (without the quotes).
Sample Input
3 2 4 1 1 0 1 3 2 1 1 2
Sample Output
Alice Bob Bob
Hint
For the first test case, Alice can remove 3 stones from the first pile, and then she will win the game.
For the second test case, as Alice can only remove some even number of stones, she is unable to remove all the stones in the first move. So Bob can remove all the remaining stones in his move and win the game.
For the third test case, Alice is unable to remove any number of stones at the beginning of the game, so Bob wins.
代码
1 

H. Binary Tree Restoring
题意
给你两个dfs序列，不一定先访问哪个儿子，让你还原出符合这两个dfs序列的二叉树
解法
ref：https://www.cnblogs.com/weeping/p/6777603.html
和上文解法有细微差别，但是基本思想就那样。
首先同一个子树，dfs序的长度是一定的，那么：如果同一对兄弟，ab用了不同的dfs顺序，取a[i], b[i]在另一个dfs序上的下标就可以得出两个子树分别有多大了，那么dfs序里除掉两个子树之外还剩下的部分，大概就是之前ab用了相同dfs序的兄弟的另外一个子树的部分，可是位置怎么取呢？其实可以做下移，也就是说，在没有冲突的情况下尽量往儿子上放，这样如果子树根的左右儿子发生了反转的顺序，确定这个子树的范围，后面的部分只要继续接在父亲结点上就可以啦。
因此我的做法是递归返回被加入二叉树的结点的数量，如果对p的一个儿子，做完一次搜索之后返回的结点数量比区间内有的结点数量少，就说明下一步搜索的时候出现了p的儿子出现了左右儿子反转的情况，而这种情况下又发现左右儿子反转之后还有一些结点既不在左儿子又不在右儿子，那么我们把这部分放到p的另一个儿子上来处理： 若可以处理全部结点，那么就结束，返回结点数量，如果不能处理，即p的另一个儿子也出现左右儿子反转，返回已经处理的结点数量，由上一层来处理这些未被处理的结点。 同时，由于未被处理的结点一定在我们传下去的区间的末尾，因此区间应该是从L+ processed到R
原题
Time Limit: 1 Second Memory Limit: 65536 KB
Given two depthfirstsearch (DFS) sequences of a binary tree, can you find a binary tree which satisfies both of the DFS sequences?
Recall that a binary tree is a tree in which each vertex has at most two children, and the depthfirst search is a tree traversing method which starts at the root and explores as far as possible along each branch before backtracking.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 10^{5}), indicating the number of vertices in the binary tree.
The second line contains n integers a_{1}, a_{2}, …, a_{n} (1 ≤ a_{i} ≤ n, ∀ 1 ≤ i < j ≤ n, a_{i} ≠ a_{j}), indicating the first DFS sequence of the binary tree.
The third line of each test case contains n integers b_{1}, b_{2}, …, b_{n} (1 ≤ b_{i} ≤ n, ∀ 1 ≤ i < j ≤ n, b_{i} ≠ b_{j}), indicating the second DFS sequence of the binary tree.
It is guaranteed that the sum of n over all test cases does not exceed 10^{6}, and there always exists at least one possible binary tree.
We kindly remind you that this problem contains large I/O file, so it’s recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.
Output
For each test case, output one line which contains n integers seperated by one space. The ith integer indicates the father of the ith vertex in the binary tree which satisfies both of the DFS sequence. If the ith vertex is the root of the binary tree, output 0 as its father. If there are multiple valid answers, you can output any of them.
Please, DO NOT print extra spaces at the end of each line, or your program may get a “wrong answer” verdict as this problem is special judged.
Sample Input
2 6 3 4 2 5 1 6 3 4 5 2 1 6 3 1 2 3 1 2 3
Sample Output
3 4 0 3 4 1 0 1 2
代码
1 
