codeforces_777
不能只会做数据结构裸题啊……想多刷codeforces，训练一下思维啥的。
昨晚的codeforces好像很水的感觉。然而我比较菜……虽然还是涨了rating……
A. Shell Game
原题：https://codeforces.com/problemset/problem/777/A
time limit per test0.5 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Bomboslav likes to look out of the window in his room and watch lads outside playing famous shell game. The game is played by two persons: operator and player. Operator takes three similar opaque shells and places a ball beneath one of them. Then he shuffles the shells by swapping some pairs and the player has to guess the current position of the ball.
Bomboslav noticed that guys are not very inventive, so the operator always swaps the left shell with the middle one during odd moves (first, third, fifth, etc.) and always swaps the middle shell with the right one during even moves (second, fourth, etc.).
Let's number shells from 0 to 2 from left to right. Thus the left shell is assigned number 0, the middle shell is 1 and the right shell is 2. Bomboslav has missed the moment when the ball was placed beneath the shell, but he knows that exactly n movements were made by the operator and the ball was under shell x at the end. Now he wonders, what was the initial position of the ball?
Input
The first line of the input contains an integer n (1 ≤ n ≤ 2·109) — the number of movements made by the operator.
The second line contains a single integer x (0 ≤ x ≤ 2) — the index of the shell where the ball was found after n movements.
Output
Print one integer from 0 to 2 — the index of the shell where the ball was initially placed.
Examples
input
4
2
output
1
input
1
1
output
0
Note
In the first sample, the ball was initially placed beneath the middle shell and the operator completed four movements.
During the first move operator swapped the left shell and the middle shell. The ball is now under the left shell.
During the second move operator swapped the middle shell and the right one. The ball is still under the left shell.
During the third move operator swapped the left shell and the middle shell again. The ball is again in the middle.
Finally, the operators swapped the middle shell and the right shell. The ball is now beneath the right shell.
题目大意：
给出三个碗，编号0~2。碗下面扣着一个小球。第奇数次操作会交换0号碗和1号碗，第偶数次操作会交换1号碗和2号碗。
给出操作次数与操作之后小球的位置，求初始的小球的位置。
个人解法：
写一下交换的情况：
1 2 3 -> 2 1 3 -> 2 3 1 ->3 2 1。
发现3步顺序调换，所以6步是循环节。于是把操作次数mod6，之后操作即可。
代码如下：
https://codeforces.com/contest/777/submission/24961629
B. Game of Credit Cards
原题：https://codeforces.com/problemset/problem/777/B
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
After the fourth season Sherlock and Moriary have realized the whole foolishness of the battle between them and decided to continue their competitions in peaceful game of Credit Cards.
Rules of this game are simple: each player bring his favourite n-digit credit card. Then both players name the digits written on their cards one by one. If two digits are not equal, then the player, whose digit is smaller gets a flick (knock in the forehead usually made with a forefinger) from the other player. For example, if n = 3, Sherlock's card is 123 and Moriarty's card has number 321, first Sherlock names 1 and Moriarty names 3 so Sherlock gets a flick. Then they both digit 2 so no one gets a flick. Finally, Sherlock names 3, while Moriarty names 1 and gets a flick.
Of course, Sherlock will play honestly naming digits one by one in the order they are given, while Moriary, as a true villain, plans to cheat. He is going to name his digits in some other order (however, he is not going to change the overall number of occurences of each digit). For example, in case above Moriarty could name 1, 2, 3 and get no flicks at all, or he can name 2, 3 and 1 to give Sherlock two flicks.
Your goal is to find out the minimum possible number of flicks Moriarty will get (no one likes flicks) and the maximum possible number of flicks Sherlock can get from Moriarty. Note, that these two goals are different and the optimal result may be obtained by using different strategies.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the number of digits in the cards Sherlock and Moriarty are going to use.
The second line contains n digits — Sherlock's credit card number.
The third line contains n digits — Moriarty's credit card number.
Output
First print the minimum possible number of flicks Moriarty will get. Then print the maximum possible number of flicks that Sherlock can get from Moriarty.
Examples
input
3
123
321
output
0
2
input
2
88
00
output
2
0
Note
First sample is elaborated in the problem statement. In the second sample, there is no way Moriarty can avoid getting two flicks.
题目大意：
两人都有一个n位数字的数，然后对每一位进行比对，每次大的那一方可以打对方一下。
比如123和321，第一位B打A，第二位两人都不打，第三位A打B。
现在A是诚实的，会按照顺序报数。B不诚实，他会把一些数字调换顺序（但不能全部换顺序）。
比如321的时候B报231，那样就可以打A两下。
现在你作为B要求两个数：
要求B被打的次数最少，这个数是多少
要求打A的次数最多，这个数是多少
个人解法：
田忌赛马……之前和点bie讨论一下觉得可做，然而写到后面没有时间了，叫开黑的点bie搞了一份代码，结果点bie桶没有清零（还过了pretest），于是最终FST。
贪心的思想，对第一问讨论，对于当前第i位，如果可以不被打，就出不被打的，否则出最小的。
第二位是类似的。
代码如下：
https://codeforces.com/contest/777/submission/24998693
C. Alyona and Spreadsheet
原题：https://codeforces.com/problemset/problem/777/C
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
During the lesson small girl Alyona works with one famous spreadsheet computer program and learns how to edit tables.
Now she has a table filled with integers. The table consists of n rows and m columns. By ai, j we will denote the integer located at the i-th row and the j-th column. We say that the table is sorted in non-decreasing order in the column j if ai, j ≤ ai + 1, j for all i from 1 to n - 1.
Teacher gave Alyona k tasks. For each of the tasks two integers l and r are given and Alyona has to answer the following question: if one keeps the rows from l to r inclusive and deletes all others, will the table be sorted in non-decreasing order in at least one column? Formally, does there exist such j that ai, j ≤ ai + 1, j for all i from l to r - 1 inclusive.
Alyona is too small to deal with this task and asks you to help!
Input
The first line of the input contains two positive integers n and m (1 ≤ n·m ≤ 100 000) — the number of rows and the number of columns in the table respectively. Note that your are given a constraint that bound the product of these two integers, i.e. the number of elements in the table.
Each of the following n lines contains m integers. The j-th integers in the i of these lines stands for ai, j (1 ≤ ai, j ≤ 109).
The next line of the input contains an integer k (1 ≤ k ≤ 100 000) — the number of task that teacher gave to Alyona.
The i-th of the next k lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n).
Output
Print "Yes" to the i-th line of the output if the table consisting of rows from li to ri inclusive is sorted in non-decreasing order in at least one column. Otherwise, print "No".
Example
input
5 4
1 2 3 5
3 1 3 2
4 5 2 3
5 5 3 2
4 4 3 4
6
1 1
2 5
4 5
3 5
1 3
1 5
output
Yes
No
Yes
Yes
Yes
No
Note
In the sample, the whole table is not sorted in any column. However, rows 1–3 are sorted in column 1, while rows 4–5 are sorted in column 3.
题目大意：
给出一个矩阵，要求查询在[li..ri]行中，是否存在一列，使得这一列上的数字从上往下是非递减的。
个人解法：
我们预处理出每个数字，往上的合法序列最长延伸到的位置。这个很容易得到，我们记为F数组。
接下来我们处理出每一行的F最小值。
考虑对于[li..ri]的询问，如果ri这一行的F最小值比li大，意味着每一列的最长的非递减序列都没有达到li，即不存在合法的列。反之，则说明最长的非递减序列达到了li或者更高，那么自然存在合法的列。
代码如下：
https://codeforces.com/contest/777/submission/24998509
D. Cloud of Hashtags
原题：https://codeforces.com/problemset/problem/777/D
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Vasya is an administrator of a public page of organization "Mouse and keyboard" and his everyday duty is to publish news from the world of competitive programming. For each news he also creates a list of hashtags to make searching for a particular topic more comfortable. For the purpose of this problem we define hashtag as a string consisting of lowercase English letters and exactly one symbol '#' located at the beginning of the string. The length of the hashtag is defined as the number of symbols in it without the symbol '#'.
The head administrator of the page told Vasya that hashtags should go in lexicographical order (take a look at the notes section for the definition).
Vasya is lazy so he doesn't want to actually change the order of hashtags in already published news. Instead, he decided to delete some suffixes (consecutive characters at the end of the string) of some of the hashtags. He is allowed to delete any number of characters, even the whole string except for the symbol '#'. Vasya wants to pick such a way to delete suffixes that the total number of deleted symbols is minimum possible. If there are several optimal solutions, he is fine with any of them.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 500 000) — the number of hashtags being edited now.
Each of the next n lines contains exactly one hashtag of positive length.
It is guaranteed that the total length of all hashtags (i.e. the total length of the string except for characters '#') won't exceed 500 000.
Output
Print the resulting hashtags in any of the optimal solutions.
Examples
input
3
#book
#bigtown
#big
output
#b
#big
#big
input
3
#book
#cool
#cold
output
#book
#co
#cold
input
4
#car
#cart
#art
#at
output
#
#
#art
#at
input
3
#apple
#apple
#fruit
output
#apple
#apple
#fruit
Note
Word a1, a2, ..., am of length m is lexicographically not greater than word b1, b2, ..., bk of length k, if one of two conditions hold:
at first position i, such that ai ≠ bi, the character ai goes earlier in the alphabet than character bi, i.e. a has smaller character than b in the first position where they differ;
if there is no such position i and m ≤ k, i.e. the first word is a prefix of the second or two words are equal.
The sequence of words is said to be sorted in lexicographical order if each word (except the last one) is lexicographically not greater than the next word.
For the words consisting of lowercase English letters the lexicographical order coincides with the alphabet word order in the dictionary.
According to the above definition, if a hashtag consisting of one character '#' it is lexicographically not greater than any other valid hashtag. That's why in the third sample we can't keep first two hashtags unchanged and shorten the other two.
题目大意：
给出n个字符串，选择删除若干字符串的某一个后缀（不能删除“#”），使得所有的字符串按照字典序排列。要求最小化删除的字母的个数。
个人解法：
某锟和我说可以贪心。后来感觉的确是这样。
我们从最底下开始，和上面的字符串，从前往后一个一个比较，比较到第一个不同的字母。如果发现上面那一个字符串的当前位比较大，那么说明就要删去当前字符串从这一位开始往后的所有字符。否则这两个串就是满足条件的，返回即可。
代码如下：
https://codeforces.com/contest/777/submission/24998494
（我发现可以直接erase(p,len)……结果还for一遍erase(p,1)了……好蠢）
E. Hanoi Factory
原题：https://codeforces.com/problemset/problem/777/E
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Of course you have heard the famous task about Hanoi Towers, but did you know that there is a special factory producing the rings for this wonderful game? Once upon a time, the ruler of the ancient Egypt ordered the workers of Hanoi Factory to create as high tower as possible. They were not ready to serve such a strange order so they had to create this new tower using already produced rings.
There are n rings in factory's stock. The i-th ring has inner radius ai, outer radius bi and height hi. The goal is to select some subset of rings and arrange them such that the following conditions are satisfied:
Outer radiuses form a non-increasing sequence, i.e. one can put the j-th ring on the i-th ring only if bj ≤ bi.
Rings should not fall one into the the other. That means one can place ring j on the ring i only if bj > ai.
The total height of all rings used should be maximum possible.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of rings in factory's stock.
The i-th of the next n lines contains three integers ai, bi and hi (1 ≤ ai, bi, hi ≤ 109, bi > ai) — inner radius, outer radius and the height of the i-th ring respectively.
Output
Print one integer — the maximum height of the tower that can be obtained.
Examples
input
3
1 5 1
2 6 2
3 7 3
output
6
input
4
1 2 1
1 3 3
4 6 2
5 7 1
output
4
Note
In the first sample, the optimal solution is to take all the rings and put them on each other in order 3, 2, 1.
In the second sample, one can put the ring 3 on the ring 4 and get the tower of height 3, or put the ring 1 on the ring 2 and get the tower of height 4.
题目大意：
给出n个环，每个环有内径与外径以及高度。要求搭一座塔，要求下面的环的外径不小于上面的环的外径，上面环的外径严格大于下面环的内径。
求最高的高度。
个人解法：
我们按照外径从大到小的顺序排序。
之后我们就可以得到一个DP方程，F[i]=max{F[j]}，i的外径大于j的内径。
于是我们用一个树状数组，下标为内径，维护F最大值即可。
考场上树状数组边界打错WAon5到死最后还是没有改出来……
代码如下：