## BestCoder Round #65 (4/5)

maksyuki 发表于 比赛 分类，标签:

# A ZYB's Biology

Problem Description

After getting 600 scores in NOIP ZYB(ZJ-267) begins to work with biological questions.Now he give you a simple biological questions: he gives you a DNA sequence and a RNA sequence,then he asks you whether the DNA sequence and the RNA sequence are
matched.

The DNA sequence is a string consisted of A,C,G,T;The RNA sequence is a string consisted of A,C,G,U.

DNA sequence and RNA sequence are matched if and only if A matches U,T matches A,C matches G,G matches C on each position.

Input

In the first line there is the testcase T.

For each teatcase:

In the first line there is one number N.

In the next line there is a string of length N,describe the DNA sequence.

In the third line there is a string of length N,describe the RNA sequence.

1 \leq T \leq 10,1 \leq N \leq 100

Output

For each testcase,print YES or NO,describe whether the two arrays are matched.

Sample Input

2
4
ACGT
UGCA
4
ACGT
ACGU

Sample Output

YES

NO

Source

BestCoder Round #65

# B ZYB's Game

Problem Description

ZYB played a game named NumberBomb with his classmates in hiking:a host keeps a number in [1,N] in mind,then
players guess a number in turns,the player who exactly guesses X loses,or the host will tell all the players that
the number now is bigger or smaller than X.After that,the range players can guess will decrease.The range is [1,N] at first,each player should guess in the legal range.

Now if only two players are play the game,and both of two players know the X,if two persons all use the best strategy,and the first player guesses first.You are asked to find the number of X that the second player
will win when X is in [1,N].

Input

In the first line there is the number of testcases T.

For each teatcase:

the first line there is one number N.

1≤T≤100000,1≤N≤10000000

Output

For each testcase,print the ans.

Sample Input

13

Sample Output

1

Source

BestCoder Round #65

# C ZYB's Premutation

Problem Description

ZYB has a premutation P,but he only remeber the reverse log of each prefix of the premutation,now he ask you to
restore the premutation.

Pair (i,j)(i<j) is considered as a reverse log if Ai>Aj is matched.

Input

In the first line there is the number of testcases T.

For each teatcase:

In the first line there is one number N.

In the next line there are N numbers Ai,describe the number of the reverse logs of each prefix,

The input is correct.

1≤T≤5,1≤N≤50000

Output

For each testcase,print the ans.

Sample Input

130 1 2

Sample Output

3 1 2

Source

BestCoder Round #65

# D ZYB's Tree

Problem Description

ZYB has a tree with N nodes,now he wants you to solve the numbers of nodes distanced no more than K for each node.
the distance between two nodes(x,y) is defined the number of edges on their shortest path in the tree.

To save the time of reading and printing,we use the following way:

For reading:we have two numbers A and B,let fai be the father of node i,fa1=0,fai=(A∗i+B)%(i−1)+1 for i∈[2,N] .

For printing:let ansi be the answer of node i,you only need to print the xor sum of all ansi.

Input

In the first line there is the number of testcases T.

For each teatcase:

In the first line there are four numbers N,K,A,B

1≤T≤5,1≤N≤500000,1≤K≤10,1≤A,B≤1000000

Output

For T lines,each line print the ans.

Please open the stack by yourself.

N≥100000 are only for two tests finally.

Sample Input

1

3 1 1 1

Sample Output

3

Source

BestCoder Round #65