问题 A: a lanran problem

题目描述







Today lanran finds that his name can be found in both string “lanran2001” and “20lanran01”, now lanran will give you T(T<=1000) strings (string.length() <= 100). For a given string, you can remove any substring of them to make it become “lanran”, if you can do it, print a “YES” in one line, or print “NO”.




输入







The first line will be an integer T(T<=1000), which is the number of given string. For each test data, there will be one line contains a string of lowercase characters(‘a’ – ‘z’) and 0-9 digits.




输出







For each given string, print the answer of lanran’s question.




样例输入










6




lanran




lanran2001




20lan0r1an




lanan




nanla




larann




样例输出










YES




YES




YES




NO




NO




NO

问题 B: Brackets matching







题目描述







There are n brackets. And you want to know whether they are match to each other. The brackets will only contain {, }, (, ), [, ]. The matching rules are the same as in Math. For example, {{[}]} is not matching, and [{{}} ()] is matching. Please write a program to check whether the given brackets string is matching or not.




输入







The first line will be an integer T, which is the number of test cases. (1 <= T <= 10) For each test case, the first line will be an integer n ( 1 <= n <= 30000) Then there is a line with n brackets.




输出







For each test case, print YES if the test case is a matching case. Otherwise, print NO.




样例输入










7




1




(




2




()




2




{]




6




[(){}]




4




(])[




8




[[{{}}]]




6




[][{]]




样例输出










NO




YES




NO




YES




NO




YES




N

问题 C: Counting







题目描述







Give you an increasing sequence A of length n, find the number of ordered tuples (i, j, k) such that the maximum element in {A[i], A[j], A[k]} minus the minimum element in {A[i], A[j], A[k]} <= m.




输入







The first line of the input is T (T <= 5), which is the number of test cases. For each test cases, the first line is n, m, the next line contains n integers which is the given sequence A. (1 ≤ n ≤ 100000 ; 1 ≤ m≤  1000000000) abs(A[i] <= 1000000000).




输出







For each test cases, print the number required in one line.




样例输入










2




4 3




1 2 3 4




5 19




1 10 20 30 50




样例输出










4




1










问题 D: Dash to Vince







题目描述

Yee_172 is in a maze of n row and m columns. He is in position S and he want to go to position V to find his friend Vince, Vince has told Yee_172 how to find position E by giving Yee_172 a sequence of direction: 01123321……. It confused Yee_172 because Vince has only told him that 0123 means up, left, right, or down




but he forgot to actually assign the directions to digits... Yee_172 want to meet Vince, you need to calculate the number of mappings of digits to directions that will lead Yee_172 to Vince.




输入







The first line is T, which is the number of test cases, (T <= 10); For each test case, the first line will be to integer n, m, and then follows n lines, each line contains m characters (‘#’ means a beautiful girl, if Yee_172 go to ‘#’, he will stop finding Vince, ‘S’ is the start point and ‘E’ is Vince point.) N, m <= 50; After the n lines, there will be one line contains 0, 1, 2, 3 only, means the sequence Yee have, which has a length no more than 100.




输出







For each test case, print a single integer, the number of mappings of digits to directions that will lead the Yee_172 to the Vince.




样例输入










2




6



.....# S....#

.#....




.#....




...E.. 333300012

3



...




.S.




###




.E.




...




3




样例输出










1




0

问题 E: Exciting Spider







题目描述







Ancient Spider was once a very popular card game, and Vince really liked to play it after he got tired of minesweeping. Today Vince wants to play Ancient Spider again, and he changes the rule to make it more boring exciting. At the beginning of the game, Vince has an empty slot on the table. There are n different cards numbered from 1 to n, and Vince will receive them one by one in a given order and put the card onto top of the slot. At any time, Vince can pick up a card from the top of slot and discard it. If Vince has discarded all the n cards, the game ends. Vince wants you to help him find the smallest lexicographical order among all possible discarding orders at the end of the game, which is considered to be most exciting. If you don't know what is lexicographical order, you can see the reference in the following link:https://en.wik ipedia.org/wiki/Lexicographical_order




输入







The first line is an integer T, which is the number of test cases.




Each test case contains two line. The first line has an integer, n.




The second line contains a sequence A of length n, which is a permutation of 1 to n, representing the order Vince receives the cards.




(1<=T<=5, 1<=n<=300000)




输出







For each test case, print n integers in a line, which is the order discarding the card with the smallest lexicographical order.




样例输入










2




3




1 3 2




4




3 4 1 2




样例输出










1 2 3




1 2 4 3

问题 F: Failed in Linear Algebra







题目描述







One day, Wavator is studying his Linear algebra course. He hates calculating the expression of matrix so he wants to develop a calculator to help him. But, he gets 59 in last years’ DSAA course, so he asks you for help; Formally, you are given n matrixes of size m, and an operation just like “(1+2)1” which means the first matrix + the second matrix and then multiply matrix 1. He only wants to calculate “+” and “-” and “”; Wavator denotes that “+” and “-” means A + B = C where C[i][j] = A[i][j] + B[i][j] and similar with “-”; Notice that ab and ba is so different. Wavator thinks the number may be too large finally, so each step you should mod 1000000007, that is, a %= mod when a = 0, a = (a % mod + mod) % mod for a negative a.




输入







The first line contains T, means there will be T (T<=10) test cases. For each test cases, the first line is n and m (n <= 10 and m <= 50), then there will be n part, each part is a m * m matrix a, 0<=a[i][j] <= 10000, matrixes are numbered from 1 to n, then there will be a string s, the length of s is not greater than 50, and it is valid. (contains only 1~n numbers (index of matrixes) and “+”, “-”, “*” only)




输出







For each test case, print m lines, each line should contain m integers, means the value of the final matrix at this line and this column.




样例输入










1




2 2




2



2 1




2 2




3 3




(1+2)*1




样例输出










10



14



提示
















Codes of mod in c++ lang. similar using java.




const int MOD = 1000000007;










inline int add(int x, int y) { return (x + y) % MOD; }










inline int sub(int x, int y) { return (x - y + MOD) % MOD; }










inline int mul(int x, int y) { return static_cast((long long) x * y % MOD); }










问题 G: Greatest difference







题目描述







There are T test cases, for each test case, you will be given n (1<=n<=400000) operations for a stack.




Two possible operations:




\1. push x




\2. pop




for operation 1 you are asked to push x(1<=x<=100000000) in to the stack.




for operation 2 you are asked to pop out the top element of the stack and print the maximum number of the stack - minimum number in the stack.




输入







the first line is T(1<=T<=5).




for each case, the first line is n(1<=n<=400000) , which is the number of operations, then follows n line contains either operation 1 or operation 2.




It is not guaranteed that if the stack is empty , you still need to pop the element.In this situation, you can just ignore the operation, but still need to print the answer.




输出







for each pop operation, print the (MAX - MIN) value in the remains stack, if the stack is empty, print 0.




For each test case, print each answer in a line.

样例输入










1




6




push 387




pop




push 278




push 416




push 111




pop




样例输出










0




138




提示







Hint: 0 is because the stack is empty after the first pop.




138 is calculated by 416 - 278 = 138.