这里是关于CodeForce Round 578 Div 2的一些题解
A. Hotelier
Problem
Amugae has a hotel consisting of $10$ rooms. The rooms are numbered from $0$ to $9$ from left to right.
The hotel has two entrances — one from the left end, and another from the right end. When a customer arrives to the hotel through the left entrance, they are assigned to an empty room closest to the left entrance. Similarly, when a customer arrives at the hotel through the right entrance, they are assigned to an empty room closest to the right entrance.
One day, Amugae lost the room assignment list. Thankfully Amugae’s memory is perfect, and he remembers all of the customers: when a customer arrived, from which entrance, and when they left the hotel. Initially the hotel was empty. Write a program that recovers the room assignment list from Amugae’s memory.
Input
The first line consists of an integer $n (1 \leq n \leq 105)$, the number of events in Amugae’s memory.
The second line consists of a string of length $n$ describing the events in chronological order. Each character represents:
‘L’: A customer arrives from the left entrance.
‘R’: A customer arrives from the right entrance.
‘0’, ‘1’, …, ‘9’: The customer in room x (0, 1, …, 9 respectively) leaves.
It is guaranteed that there is at least one empty room when a customer arrives, and there is a customer in the room $x$ when $x (0, 1, …, 9)$is given. Also, all the rooms are initially empty.
Output
In the only line, output the hotel room’s assignment status, from room $0$ to room $9$. Represent an empty room as ‘0’, and an occupied room as ‘1’, without spaces.
Examples
input
8
LLRL1RL1output
1010000011
input
9
L0L0LLRR9output
1100000010
Note
In the first example, hotel room’s assignment status after each action is as follows.
·First of all, all rooms are empty. Assignment status is 0000000000.
·L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000.
·L: one more customer from the left entrance. Assignment status is 1100000000.
·R: one more customer from the right entrance. Assignment status is 1100000001.
·L: one more customer from the left entrance. Assignment status is 1110000001.
·1: the customer in room 1 leaves. Assignment status is 1010000001.
·R: one more customer from the right entrance. Assignment status is 1010000011.
·L: one more customer from the left entrance. Assignment status is 1110000011.
·1: the customer in room 1 leaves. Assignment status is 1010000011.
So after all, hotel room’s final assignment status is 1010000011.
In the second example, hotel room’s assignment status after each action is as follows.
·L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000.
·0: the customer in room 0 leaves. Assignment status is 0000000000.
·L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000 again.
·0: the customer in room 0 leaves. Assignment status is 0000000000.
·L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000.
·L: one more customer from the left entrance. Assignment status is 1100000000.
·R: one more customer from the right entrance. Assignment status is 1100000001.
·R: one more customer from the right entrance. Assignment status is 1100000011.
·9: the customer in room 9 leaves. Assignment status is 1100000010.
So after all, hotel room’s final assignment status is 1100000010.
想法
暴力出奇迹
The Code Of My Program
1  /********************* 
B. Block Adventure
Problem
Gildong is playing a video game called Block Adventure. In Block Adventure, there are n columns of blocks in a row, and the columns are numbered from $1$ to $n$. All blocks have equal heights. The height of the $i^{th}$ column is represented as $h_i$, which is the number of blocks stacked in the $i^{th}$ column.
Gildong plays the game as a character that can stand only on the top of the columns. At the beginning, the character is standing on the top of the $1^{st}$ column. The goal of the game is to move the character to the top of the $n^{th}$ column.
The character also has a bag that can hold infinitely many blocks. When the character is on the top of the $i^{th}$ column, Gildong can take one of the following three actions as many times as he wants:
··if there is at least one block on the column, remove one block from the top of the $i^{th}$ column and put it in the bag;
··if there is at least one block in the bag, take one block out of the bag and place it on the top of the $i^{th}$ column;
··if $i < n$ and $ \left h_i − h_{i + 1} \right \leq k$, move the character to the top of the $(i+1)^{th}$ column. $k$ is a nonnegative integer given at the beginning of the game. Note that it is only possible to move to the next column.
In actions of the first two types the character remains in the $i^{th}$ column, and the value $h_i$ changes.
The character initially has $m$ blocks in the bag. Gildong wants to know if it is possible to win the game. Help Gildong find the answer to his question.
Input
Each test contains one or more test cases. The first line contains the number of test cases $t (1 \leq t \leq 1000)$. Description of the test cases follows.
The first line of each test case contains three integers $n, m, k (1 \leq n \leq 100, 0 \leq m \leq 10^6, 0 \leq k \leq 10^6)$ — the number of columns in the game, the number of blocks in the character’s bag at the beginning, and the nonnegative integer $k$ described in the statement.
The second line of each test case contains $n$ integers. The $i^{th}$ integer is $h_i (0 \leq hi \leq 10^6)$, the initial height of the $i^{th}$ column.
Output
For each test case, print “YES” if it is possible to win the game. Otherwise, print “NO”.
You can print each letter in any case (upper or lower).
Example
input
5
3 0 1
4 3 5
3 1 2
1 4 7
4 10 0
10 20 10 20
2 5 5
0 11
1 9 9
99output
YES
NO
YES
NO
YES
Note
In the first case, Gildong can take one block from the $1^{st}$ column, move to the $2^{nd}$ column, put the block on the $2^{nd}$ column, then move to the $3^{rd}$ column.
In the second case, Gildong has to put the block in his bag on the $1^{st}$ column to get to the $2^{nd}$ column. But it is impossible to get to the $3^{rd}$ column because $ \left h2−h3 \right = 3 > k $and there is no way to decrease the gap.
In the fifth case, the character is already on the $n^{th}$ column from the start so the game is won instantly.
想法
直接贪心拿掉当前所在位置所有的，然后放回去满足条件的最少的，看看手头上的数目是不是小于0即可
The Code Of My Program
1  /********************* 
C. Round Corridor
Problem
Amugae is in a very large round corridor. The corridor consists of two areas. The inner area is equally divided by $n$ sectors, and the outer area is equally divided by $m$ sectors. A wall exists between each pair of sectors of same area (inner or outer), but there is no wall between the inner area and the outer area. A wall always exists at the 12 o’clock position.
The inner area’s sectors are denoted as $(1,1),(1,2),…,(1,n)$ in clockwise direction. The outer area’s sectors are denoted as $(2,1),(2,2),…,(2,m)$ in the same manner. For a clear understanding, see the example image above.
Amugae wants to know if he can move from one sector to another sector. He has $q$ questions.
For each question, check if he can move between two given sectors.
Input
The first line contains three integers $ n , m , q (1 \leq n,m \leq 10^{18}, 1 \leq q \leq 10^4) $— the number of sectors in the inner area, the number of sectors in the outer area and the number of questions.
Each of the next $q$ lines contains four integers $s_x, s_y, e_x, e_y (1 \leq s_x,e_x \leq 2$; if$ s_x=1$, then$ 1 \leq s_y \leq n$, otherwise $1 \leq s_y \leq m$; constraints on $e_y$ are similar). Amague wants to know if it is possible to move from sector$ (s_x,s_y) $to sector$ (e_x,e_y)$.
Output
For each question, print “YES” if Amugae can move from $(sx,sy)$ to $(ex,ey)$, and “NO” otherwise.
You can print each letter in any case (upper or lower).
Example
input
4 6 3
1 1 2 3
2 6 1 2
2 6 2 4output
YES
NO
YES
Note
Example is shown on the picture in the statement.
想法
看到图就想到内圈每隔$x$个，外圈每隔$y$个，形成一个自闭组，那么这有什么关系吗？
有，每隔几个每隔几个，就是gcd的意义啊
那么思路清晰了，计算他们的gcd，就是最大公约数——代表着他们同时分成多少大自闭组，再分别用内外圈总数/自闭组数，就是内外圈每个自闭组包含几个单位范围，再确定询问的位置是否属于同一个自闭组，判断即可
The Code Of My Program
1  /********************* 
D. White Lines
Problem
Gildong has bought a famous painting software cfpaint. The working screen of cfpaint is squareshaped consisting of $n$ rows and $n$ columns of square cells. The rows are numbered from $1$ to $n$, from top to bottom, and the columns are numbered from $1$ to $n$, from left to right. The position of a cell at row $r$ and column $c$ is represented as $(r,c)$. There are only two colors for the cells in cfpaint — black and white.
There is a tool named eraser in cfpaint. The eraser has an integer size $k (1 \leq k \leq n)$. To use the eraser, Gildong needs to click on a cell $(i,j)$ where $1 \leq i,j \leq n−k+1$. When a cell $(i,j)$ is clicked, all of the cells $(i′,j′)$ where $i \leq i′ \leq i+k−1$ and $j \leq j′ \leq j+k−1$ become white. In other words, a square with side equal to $k$ cells and top left corner at $(i,j)$ is colored white.
A white line is a row or a column without any black cells.
Gildong has worked with cfpaint for some time, so some of the cells (possibly zero or all) are currently black. He wants to know the maximum number of white lines after using the eraser exactly once. Help Gildong find the answer to his question.
Input
The first line contains two integers $n$ and $k (1 \leq k \leq n \leq 2000)$ — the number of rows and columns, and the size of the eraser.
The next $n$ lines contain $n$ characters each without spaces. The $j^{th}$ character in the $i^{th}$ line represents the cell at $(i,j)$. Each character is given as either ‘B’ representing a black cell, or ‘W’ representing a white cell.
Output
Print one integer: the maximum number of white lines after using the eraser exactly once.
Examples
input
4 2
BWWW
WBBW
WBBW
WWWBoutput
4
input
3 1
BWB
WWB
BWBoutput
2
input
5 3
BWBBB
BWBBB
BBBBB
BBBBB
WBBBWoutput
2
input
2 2
BW
WBoutput
4
input
2 1
WW
WWoutput
4
Note
In the first example, Gildong can click the cell $(2,2)$, then the working screen becomes:
BWWW
WWWW
WWWW
WWWB
Then there are four white lines — the $2^{nd}$ and $3^{rd}$ row, and the $2^{nd}$ and $3^{rd}$ column.
In the second example, clicking the cell $(2,3)$ makes the $2^{nd}$ row a white line.
In the third example, both the $2^{nd}$ column and $5^{th}$ row become white lines by clicking the cell $(3,2)$.
想法 （官方题解）
Let’s consider a single row that contains at least one black cell. If the first appearance of a black cell is at the $l^{th}$ column and the last appearance of a black cell is at the $r^{th}$ column, we can determine whether it becomes a white line when a certain cell $(i,j)$ is clicked in $O(1)$, after some preprocessing. It becomes a white line if and only if a cell $(i,j)$ is clicked where the row is at $[i,i+k−1]$ and $j \leq l \leq r \leq j+k−1$. We just need to compute $l$ and $r$ in advance.
Now let’s consider all $n$ rows (not columns). First, count all rows that are already white lines before clicking. Then we count the number of white rows when the cell $(1,1)$ is clicked, by applying the above method to all rows from $1$ to $k$. Ignore the alreadywhite rows that we counted before. So far we obtained the number of white rows when the cell $(1,1)$ is clicked. From now, we slide the window. Add the $k+1^{th}$ row and remove the $1^{st}$ row by applying the same method to them, and we obtain the number of white rows when the cell $(2,1)$ is clicked. We can repeat this until we calculate all $n−k+1$ cases for clicking the cells at the $1^{st}$ column. Then we repeat the whole process for all $n−k+1$ columns.
The same process can be done for counting white columns, too. Now we know the number of white rows and white columns when each cell is clicked, so we can find the maximum value among their sums.
Time complexity: $O(n^2)$
配上图，一开始我也是这么想的，但是想出来是个$O(n^2k)$的假算法，T在第12个点，后来看了题解发现其实可以预处理一下，计算橡皮擦擦$(i,j)$到$(i+k1,j+k1)$这个大正方形对行列的贡献的时候可以优化到$O(n^2)$，不需要每次都重复计算K行K列。
The Code Of My Program
1  /********************* 
E. Compress Words
Problem
Amugae has a sentence consisting of $n$ words. He want to compress this sentence into one word. Amugae doesn’t like repetitions, so when he merges two words into one word, he removes the longest prefix of the second word that coincides with a suffix of the first word. For example, he merges “sample” and “please” into “samplease”.
Amugae will merge his sentence left to right (i.e. first merge the first two words, then merge the result with the third word and so on). Write a program that prints the compressed word after the merging process ends.
Input
The first line contains an integer $n (1 \leq n \leq 10^5)$, the number of the words in Amugae’s sentence.
The second line contains $n$ words separated by single space. Each words is nonempty and consists of uppercase and lowercase English letters and digits $(‘A’, ‘B’, …, ‘Z’, ‘a’, ‘b’, …, ‘z’, ‘0’, ‘1’, …, ‘9’)$. The total length of the words does not exceed $10^6$.
Output
In the only line output the compressed word after the merging process ends as described in the problem.
Examples
input
5
I want to order pizzaoutput
Iwantorderpizza
input
5
sample please ease in outoutput
sampleaseinout
想法
先来想两个单词的连接 ， 比如qwer和asdf这两个，没有重复部分，直接变为qwerasdf；qwer和erty有重复的er，则变成qweryt。
两个单词的做完了，那么来考虑多个单词asdf，qwer，erty，则结果是asdfqwerty；
很显然只有相邻的单词会有互相影响，那么这题就把大问题——n个单词连起来——转换为小问题——两两连接
对于短的单词直接BF算法暴力匹配是可以的，但是考虑到这题数据范围，显然要用到KMP（其实字符串哈希也行但是我不会）
计算KMP的时候可以进行优化，只需要比较两个串中短串的长度即可。
比如我有qwertyuiopasdfghjklzxcv和zxcvbnm，长度分别是23和7，那么直接比较长串的后7个和短串；
再比如我有90qwer和qwertyuiopasdfghjklzxcv那么我只要比较长串的前6个和90qwer。
官方题解
Denote the words from left to right as $W_1,W_2,W_3,⋯,W_n$.
If we define string $F(k)$ as the result of merging as described in the problem $k$ times, we can get $F(k+1)$ by the following process:
If length of $F(k)$ $>$ length of $W_{k+1}$
Assume the length of $F(K)$ is $x$, and the length of $W_{k+1}$ is $y$. Construct the string $c=W_{k+1}+F(k) [ x−y…x ] $ ( * $s[x..y]$ for string $s$ is the substring from index $x$ to $y$)
Get the KMP failure function from string c.
We can get maximum overlapped length of $W_{k+1}$’s prefix and $F(k)$’s suffix from this function. Suppose the last element of the failure function smaller than the length of $W_{k+1}$ is $z$. Then the longest overlapped length of $F(k)$’s suffix and $W_{k+1}$’s prefix is $min(z,y)$. Let $L=min(z,y)$.
Then, $F(k+1)=F(k)+W_{k+1}[L+1…y]$
Otherwise
Construct $c$ as $W_{k+1}[1…x]+F(k)$. We can get $F(k+1)$ from the same process described in 1.
In this process, we can get $F(k+1)$ from $F(k)$ in time complexity $O(len(W_{k+1}))$. So, we can get $F(N)$ (the answer of this problem) in $O(len(W_1)+len(W_2)+⋯+len(W_N))$.
The Code Of My Program
1 
