Description
题目描述
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.
