| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12568 | Reverse Linked List ver 2 |
|
| 13572 | String Operations 1 |
|
| 14558 | The Final Magical Corridor |
|
| 14559 | My Final String |
|
Description
Given several operations, push x, pop, print, reverse, create a linked list dynamicly.
- push x: Add one Node (with data = x) at the front of linked list.
- pop: Delete the Node at the front of linked list.
- reverse: reverse the current linked list
- print: output the linked list in given format.
You have to implement 3 functions:
1. void Push(Node** ptr_head,int x)
2. void Pop(Node** ptr_head)
3. void Reverse_List(Node** ptr_head)
Note: Modify the Node* head by Node** ptr_head
Input
There’re operations on several lines.
All operations are one of push x, pop, print, reverse.
It’s guaranteed that:
- Number of operations is less than 5,000,000
- Integer x is in [−1000,1000]
- The maximum length of linked list is less than 10,000.
Output
Output the linked list for every print.
Sample Input Download
Sample Output Download
Partial Judge Code
12568.cPartial Judge Header
12568.hTags
Discuss
Description
Input
The first line contains a string s, which consists of only lowercase Latin characters. The second line contains a integer Q. The next Q lines, each contains two characters A and B.
Constraints
- 1≤|s|≤106
- 1≤Q≤105
- A,B∈[a−z]
for testcases 1~3, 1≤|s|≤1000.
for testcases 4~6, there’s no additional constraints.
Output
Print the resulting string in one line after applying the Q operations.
(remember to print a new line character)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
After narrowly escaping the second trial, you step into the third and final part of the Magical Corridor. The air feels heavier, and the shimmering walls seem to mock your every step.
This time, the corridor presents a new challenge: not only must you gather gems as before, but now you must also deal with the mysterious shopkeepers stationed along the path.
In this corridor, every position contains either a gem or a shop:
- Gems: You can collect them as usual when you pass by.
- Shops: You can trade any one gem you already have for a new one. The shopkeeper will give you one gem of any color you choose, with a weight of Wi . However, the shopkeepers are very evil: the weight Wi of the gems you get from shops will always be smaller than the weight of the gems you can collect directly (see Constraints for details).
Thanks to your clever mind, you already know exactly where every gem and shop is in the corridor. With this knowledge, you must plan your path carefully.
Your ultimate goal remains the same:
- For a given position m, collect the maximum number of different gem colors.
- If there are multiple ways to collect the most colors, maximize the total weight of the gems you collect.
The magical movement rules are still in effect:
- If you are at position i, you can only move to positions that are multiples of i. For example, if you are at position 1, you can move to positions 2,3,…,N. From position 2, you can only move to positions 4,6,…
Can you outsmart this new challenge and finally escape?
Input
The first line contains two integers N and Q: the length of the corridor and the number of queries.
The second line contains N integers C1,C2,…,CN , where Ci is:
- 0 : A shop is at position i.
- 1 ≤ Ci ≤ 7 : A gem of color Ci is at position i.
The third line contains N integers W1,W2,…,WN, where Wi is:
- The weight of the gem at position i (if Ci ≠ 0).
- The weight of the gems offered by the shop at position i (if Ci = 0).
The next Q lines each contain a single integer m, the endpoint for each query.
Constraints
- 1 ≤ N ≤ 3 × 104
- 1 ≤ Q ≤ 105
- 0 ≤ Ci ≤ 7
- if Ci = 0, 1 ≤ Wi ≤ 99
- if Ci ≠ 0, 100 ≤ Wi ≤ 105
- 1 ≤ m ≤ N
Subtasks
- Testcases 1~3: 1 ≤ Ci ≤ 7
- Testcases 4~5:
- 1 ≤ Ci ≤ 7 for all i ≤ N / 2
(In other words, the shops can only appear in the second half of the corridor, and can only be the endpoint of each query.) - if Ci ≠ 0, Wi = 100 (the weights of all gems are the same).
- It is guaranteed that for each query, making at most a single trade will result in the optimal solution.
- 1 ≤ Ci ≤ 7 for all i ≤ N / 2
- Testcases 6~7:
- 1 ≤ Ci ≤ 7 for all i ≤ N / 2
(In other words, the shops can only appear in the second half of the corridor, and can only be the endpoint of each query.) - if Ci ≠ 0, Wi = 100 (the weights of all gems are the same).
- 1 ≤ Ci ≤ 7 for all i ≤ N / 2
- Testcases 8~9: No additional restrictions.
Output
For each query, output two integers in a single line:
- The maximum number of distinct gem colors you can collect up to position m.
- The maximum total weight of the gems you can collect, with the maximum number of distinct gem colors, up to position m.
Please remember to print "\n" at the end of each line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are interesting string operations there.
- a + b: Concatenate the string b after the string a.
- a - b: If string b has appeared in string a, delete the first appearance of b in a, otherwise output "error".
- a [b]: Output the b-th character after sorting a in lexicographical order. If b exceeds the length of a, output "error".
- a @ b1_b2_b3_...bk: For all strings bi concatenated with '_', if a has appeared in string bi, add bi to a list, output the list in this order:
- If fx > fy: x is listed before y (fi is the number of occurrences of a in the string i )
- If |x| > |y|: x is listed before y
- If |x| = |y|: follows the lexicographical order
- a ? b1_b2_b3_...bk: You will receive the following T - 1 operations, output the result sorted according to the @ sorting rule in the end
- 1 i p q: represents bi = bp + bq
- 2 i p q: represents bi = bp - bq （If bq cannot be found in bp , ignore this operation.)
Input
The first line contains an integer T, representing the number of string operations.
The following T lines each contain a string Si , representing the string operation in the i-th round.
Subtasks
- Testcase 1: 1 ≤ T ≤ 1000, 1 ≤ |S | ≤ 104, only "+" operation, a and b are guaranteed to consist of lowercase letters
- Testcases 2 ~ 3: 1 ≤ T ≤ 1000, 1 ≤ |S | ≤ 104, only "-" operation, a and b are guaranteed to consist of lowercase letters
- Testcases 4 ~ 5: 1 ≤ T ≤ 1000, 1 ≤ |S | ≤ 105, only "[ ]" operation, a is guaranteed to consist of lowercase letters, and b is guaranteed to consist of digits
- Testcases 6: 1 ≤ T ≤ 1000, 1 ≤ |S | ≤ 104, only "@" operation, a and b are guaranteed to consist of lowercase letters and "_"
- Testcases 7: 1 ≤ T ≤ 1000, 1 ≤ |S | ≤ 105, only "@" operation, a and b are guaranteed to consist of lowercase letters and "_"
- Testcases 8: 1 ≤ T ≤ 10, 1 ≤ |S | ≤ 104, 1 ≤ i, p, q ≤ k, only "?" operation, a and b are guaranteed to consist of lowercase letters and "_"
- Testcases 9: 1 ≤ T ≤ 1000, 1 ≤ |S | ≤ 105, 1 ≤ i, p, q ≤ k, only "?" operation, a and b are guaranteed to consist of lowercase letters and "_"
Output
Output T lines, each containing a string Si after operation.
Please remember to print "\n" at the end.
Aftermath, a student in NTHU, is very good at programming. Today, as usual, she comes up with a programming problem but felt bored to solve it by herself(it’s too easy for her!). Thus, she left the problem to you, that is:
Given a string that consists of only lowercase Latin characters, there are Q operations to apply on this string. Each operation is represented by two characters, let’s say A and B, and you have to turn every A in the given string to B. After the Q operations, you should print the resulting string in one line(remember to print a new line character).