2020牛客暑期多校训练营(第三场)
A. Clam and Fish
题目描述
There is a fishing game as following.
The game contains stages, numbered from to .
There are four types of stages (numbered from to ). Type : There are no fish and no clam in this stage. Type : There are no fish and one clam in this stage. Type : There are one fish and no clam in this stage. Type : There are one fish and one clam in this stage.
In each stage, you can do exactly one of the following four actions.
If there is a clam in the stage, you can use this clam to make one pack of fish bait. And the number of packs of fish bait you have is increased by one. You can use this pack of fish bait to catch fish after this stage.
If there is one fish in the stage, you can catch this fish without any fish bait. After this stage, the number of packs of fish bait you have is not changed.
If you have at least one pack of fish bait. You can always catch one fish by using exactly one pack of fish bait even if there are no fish in this stage. After this stage, the number of packs of fish bait you have is decreased by one.
You can do nothing.
Now, you are given and the type of each stage. Please calculate the largest number of fish you can get in the fishing game.
输入描述
The first line contains one integer (), indicating the number of test cases.
There are two lines in each test. The first line contains one integer (), indicating the number of stages in this game. The second line contains a string with length . The -th character of this string indicates the type of the -th stage.
The sum of across the test cases doesn’t exceed .
输出描述
For each test case print exactly one integer indicating the maximum number of fish you can catch in the game configuration.
示例1
输入
1 | 2 |
输出
1 | 2 |
备注
One possible scenario you can catch two fishes is as follow.
stage : Do nothing.
stage : Make a pack of fish bait.
stage : Catch a fish by a pack of fish bait.
stage : Catch the fish that appears in the stage.
分析
首先明确,要是当前的状态有鱼,那么直接抓鱼。若当前为状态 ,那么用鱼饵钓鱼显然不如直接抓鱼实惠;若当前状态为 ,虽然可以获得鱼饵,但是获得鱼饵也是为了在将来花费这个鱼饵钓到鱼,问题是将来可能不会再有钓鱼的机会(鱼饵多余,已经是最后一天……),不如放弃这个鱼饵,直接抓鱼。
若当前状态没有鱼,那么鱼饵要尽量在没有蛤蜊的时候用掉,有蛤蜊的状态用来获取鱼饵。若当前状态为 ,什么都没有;那么有鱼饵的话直接用来抓鱼,否则就什么都不做。若当前状态为 ,如果没有鱼饵,那就不必思考,直接获取鱼饵;如果有鱼饵,再来考虑要不要钓鱼;因为鱼饵是为将来状态为 的时候准备的,如果钓鱼后,拥有的鱼饵足够将来状态为 的那几天使用,就可以放心地钓鱼,否则就将蛤蜊做成鱼饵。
值得一提的是,需要逆向预处理第 天后状态为 的天数,再正向进行贪心。
代码
1 | /****************************************************************** |
B. Classical String Problem
题目描述
Given a string consists of lower case letters. You’re going to perform operations one by one. Each operation can be one of the following two types.
Modify: Given an integer , you need to modify according to the value of . If is positive, move the leftmost letters in to the right side of ; otherwise, move the rightmost letters in to the left side of .
Answer: Given a positive integer . Please answer what the -th letter in the current string is.
输入描述
There are lines in the input. The first line of the input contains the string . The second line contains the integer . The following lines each denotes an operation. You need to follow the order in the input when performing those operations.
Each operation in the input is represented by a character and an integer . If c=='M'
, this operation is a modify operation, that is, to rearrange according to the value of ; if c=='A'
, this operation is an answer operation, to answer what the -th letter in the current string is.
( stands for the length of the string ).
consists of lower case letters.
.
or . If , . If , .
There is at least one operation in the input satisfies .
输出描述
For each answer operation, please output a letter in a separate line representing the answer to the operation. The order of the output should match the order of the operations in the input.
示例1
输入
1 | nowcoder |
输出
1 | n |
备注
Initially, is “nowcoder”, six operations follow.
The -st operation is asking what the -st letter is. The answer is ‘n’.
The -nd operation is to move the leftmost letters to the rightmost side, so is modified to “odernowc”.
The -rd operation is asking what the -th letter is. The answer is ‘o’.
The -th operation is to move the rightmost letters to the leftmost side, so is modified to “owcodern”.
The -th operation is to move the leftmost letter to the rightmost side, so is modified to “wcoderno”.
The -th operation is asking what the -st letter is. The answer is ‘w’.
分析
将字符串看作一个环,定义一个指针 指向字符串的起点,从起点开始逆时针遍历整个环,得到的就是当前字符串;不论如何更改,环的结构是不会变的。查询时,从起点开始,逆时针经过 个点,最终到达的点即为询问的答案;更新时,若 ,要将字符串末尾的某个字符作为起点,将指针顺时针移动 次;否则,将指针逆时针移动 次。环上的移动,通过对字符串长度 取模来体现。
代码
1 | /****************************************************************** |
F. Fraction Construction Problem
题目描述
There are queries.
In each query, you are given two positive integers and .
Please print a line consists of four positive integers c,d,e,f satisfying the following constraints: , and , .
If there are multiple solutions, you can print anyone.
If there are no solution, please print -1 -1 -1 -1
in this line.
输入描述
The first line contains one integer , the number of test cases.
The only line of each test case contains two integers and .
输出描述
For each test case print four integers . If there are no solution, should all be .
示例1
输入
1 | 3 |
输出
1 | -1 -1 -1 -1 |
分析
若 ,代表分数 可以约分为 。简便起见,直接令 ,那么就有 ,有一组解为 ,。
若 ,那么 已经是最简分式,将等式左边通分后,可得 。首先,当 为质数的幂时,无解(文末给出证明)。接下来考虑 有多个不相同质因子的情况。根据算数基本定理,可以将 写成有限个质数的乘积,。方便起见,直接令 ,。 是一个裴蜀方程,当且仅当 时方程有整数解。若能构造得到的 使得 ,那么方程一定有整数解。显然这样的构造方案是存在的,令 ,,就有 。可以用扩展欧几里得算法求出 的特解 ,为了满足条件 ,不妨让 尽量向 靠近。令 ,求一个不等式组即可得到 的上界。有不等式组 $\begin{cases}c_0+kd\leqslant top\\e_0+kf\leqslant top\end{cases}$,解得 。
接下来给出证明:当 且 为质数的幂次时,无解。
设 ,,。由于 是质数的幂次,可设 ,,其中 ,。那么有 且 。很显然, 式的左边分式可以上下同除以 进行约分;又 ,故 ,这样一来, 就是一个可约分的分式,与事实矛盾。证毕。
代码
1 | /****************************************************************** |
L. Problem L is the Only Lovely Problem
题目描述
Dreamoon loves lovely things, like lovely girls, lovely bed sheets, lovely clothes…
So he thinks a string is lovely if and only if it begins with the word “lovely”(case insensitive). You are given a string. Please tell us whether Dreamoon thinks that string is lovely.
输入描述
The input contains only one line.
This line contains a string . The length of is between and .
consists of only the English alphabet. It can be lower case or upper case.
输出描述
If a string is lovely, please output “lovely”, Otherwise, output “ugly”. (The output is case sensitive).
示例1
输入
1 | LovelyAA |
输出
1 | lovely |
示例2
输入
1 | lovelymoon |
输出
1 | lovely |
示例3
输入
1 | NOWCOWDER |
输出
1 | ugly |
示例4
输入
1 | LoveLive |
输出
1 | ugly |
分析
要求字符串开头为 “lovely”,只需要依次比较字符串开头的六位即可,只需要注意比较是不区分大小写的。
代码
1 | /****************************************************************** |