2020牛客暑期多校训练营（第三场）

A. Clam and Fish $\looparrowright$

题目描述

There is a fishing game as following.
The game contains $n$ stages, numbered from $1$ to $n$ .
There are four types of stages (numbered from $0$ to $3$ ). Type $0$ : There are no fish and no clam in this stage. Type $1$ : There are no fish and one clam in this stage. Type $2$ : There are one fish and no clam in this stage. Type $3$ : 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 $n$ 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 $t$ ( $1 \leqslant t \leqslant 2.5 \times 10^5$ ), indicating the number of test cases.
There are two lines in each test. The first line contains one integer $n$ ( $1 \leqslant n \leqslant 2 \times 10^6$ ), indicating the number of stages in this game. The second line contains a string with length $n$ . The $i$ -th character of this string indicates the type of the $i$ -th stage.
The sum of $n$ across the test cases doesn’t exceed $2 \times 10^6$ .

输出描述

For each test case print exactly one integer indicating the maximum number of fish you can catch in the game configuration.

示例1

输入

输出

1
2

2  
0

备注

One possible scenario you can catch two fishes is as follow.
stage $1$ : Do nothing.
stage $2$ : Make a pack of fish bait.
stage $3$ : Catch a fish by a pack of fish bait.
stage $4$ : Catch the fish that appears in the stage.

分析

首先明确，要是当前的状态有鱼，那么直接抓鱼。若当前为状态 $2$ ，那么用鱼饵钓鱼显然不如直接抓鱼实惠；若当前状态为 $3$ ，虽然可以获得鱼饵，但是获得鱼饵也是为了在将来花费这个鱼饵钓到鱼，问题是将来可能不会再有钓鱼的机会（鱼饵多余，已经是最后一天……），不如放弃这个鱼饵，直接抓鱼。
若当前状态没有鱼，那么鱼饵要尽量在没有蛤蜊的时候用掉，有蛤蜊的状态用来获取鱼饵。若当前状态为 $0$ ，什么都没有；那么有鱼饵的话直接用来抓鱼，否则就什么都不做。若当前状态为 $1$ ，如果没有鱼饵，那就不必思考，直接获取鱼饵；如果有鱼饵，再来考虑要不要钓鱼；因为鱼饵是为将来状态为 $0$ 的时候准备的，如果钓鱼后，拥有的鱼饵足够将来状态为 $0$ 的那几天使用，就可以放心地钓鱼，否则就将蛤蜊做成鱼饵。
值得一提的是，需要逆向预处理第 $i$ 天后状态为 $0$ 的天数，再正向进行贪心。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第三场） Problem A
Date: 8/14/2020
Description: Greedy
*******************************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2000005;
int _;
char days[N];
int n;
int leftover[N];
int bait,fish;
inline void init();
int main(){
	for(cin>>_;_;_--){
		scanf("%d%s",&n,days+1);
		init();
		int i;
		for(i=n;i>=1;i--){
			leftover[i]+=days[i]=='0';
			leftover[i]+=leftover[i+1];
		}
		for(i=1;i<=n;i++){
			if(days[i]=='0'){
				//没鱼 没蛤蜊
				if(bait){
					//有鱼饵 可以抓鱼
					bait--;
					fish++;
				}
			}else if(days[i]=='1'){
				//没鱼 有蛤蜊
				if(!bait){
					//没鱼饵 只能将蛤蜊做成鱼饵
					bait++;
				}else{
					//有鱼饵 考虑要不要抓鱼
					if(leftover[i]<bait){
						//当前鱼饵足够在后面没鱼没蛤蜊的情况下抓鱼
						//现在可以抓鱼
						fish++;
						bait--;
					}else{
						//做成鱼饵 在将来没鱼没蛤蜊的情况下抓鱼
						bait++;
					}
				}
			}else{
				//有鱼直接抓 不能错失机会
				fish++;
			}
		}
		printf("%d\n",fish);
	}
	return 0;
}
inline void init(){
	bait=fish=0;
	fill(leftover,leftover+n+2,0);
}

B. Classical String Problem $\looparrowright$

题目描述

Given a string $S$ consists of lower case letters. You’re going to perform $Q$ operations one by one. Each operation can be one of the following two types.
Modify: Given an integer $x$ , you need to modify $S$ according to the value of $x$ . If $x$ is positive, move the leftmost $x$ letters in $S$ to the right side of $S$ ; otherwise, move the rightmost $|x|$ letters in $S$ to the left side of $S$ .
Answer: Given a positive integer $x$ . Please answer what the $x$ -th letter in the current string $S$ is.

输入描述

There are $Q+2$ lines in the input. The first line of the input contains the string $S$ . The second line contains the integer $Q$ . The following $Q$ 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 $c$ and an integer $x$ . If c=='M', this operation is a modify operation, that is, to rearrange $S$ according to the value of $x$ ; if c=='A', this operation is an answer operation, to answer what the $x$ -th letter in the current string $S$ is.
$2 \leqslant |S| \leqslant 2 \times 10^6$ ( $|S|$ stands for the length of the string $S$ ).
$S$ consists of lower case letters.
$1 \leqslant Q \leqslant 8 \times 10^5$ .
$c = 'M'$ or $'A'$ . If $c = 'M'$ , $1 \leqslant |x| < |S|$ . If $c = 'A'$ , $1 \leqslant x \leqslant |S|$ .
There is at least one operation in the input satisfies $c = 'A'$ .

输出描述

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

输入

nowcoder
6
A 1
M 4
A 6
M -3
M 1
A 1

输出

1
2
3

n
o
w

备注

Initially, $S$ is “nowcoder”, six operations follow.
The $1$ -st operation is asking what the $1$ -st letter is. The answer is ‘n’.
The $2$ -nd operation is to move the leftmost $4$ letters to the rightmost side, so $S$ is modified to “odernowc”.
The $3$ -rd operation is asking what the $6$ -th letter is. The answer is ‘o’.
The $4$ -th operation is to move the rightmost $3$ letters to the leftmost side, so $S$ is modified to “owcodern”.
The $5$ -th operation is to move the leftmost $1$ letter to the rightmost side, so $S$ is modified to “wcoderno”.
The $6$ -th operation is asking what the $1$ -st letter is. The answer is ‘w’.

分析

将字符串看作一个环，定义一个指针 $pointer$ 指向字符串的起点，从起点开始逆时针遍历整个环，得到的就是当前字符串；不论如何更改，环的结构是不会变的。查询时，从起点开始，逆时针经过 $x$ 个点，最终到达的点即为询问的答案；更新时，若 $x<0$ ，要将字符串末尾的某个字符作为起点，将指针顺时针移动 $-x$ 次；否则，将指针逆时针移动 $x$ 次。环上的移动，通过对字符串长度 $len$ 取模来体现。
2020牛客多校第三场.png

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第三场） Problem B
Date: 8/14/2020
Description: Pointer Simulation
*******************************************************************/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=2000005;
int _;
char s[N];
int q;
int len;
int main(){
	scanf("%s%d",s,&q);
	len=strlen(s);
	int pointer=0;
	while(q--){
		char c;
		int x;
		getchar();
		scanf("%c%d",&c,&x);
		if(c=='M'){
			//取模体现环上移动的性质
			pointer=(pointer+x+len)%len;
		}else{
			printf("%c\n",s[(pointer+x-1)%len]);
		}
	}
	return 0;
}

F. Fraction Construction Problem $\looparrowright$

题目描述

There are $t$ queries.
In each query, you are given two positive integers $a$ and $b$ $(a, b \leqslant 2 \times 10^6)$ .
Please print a line consists of four positive integers c,d,e,f satisfying the following constraints: $\frac{c}{d} - \frac{e}{f} = \frac{a}{b}$ , $d < b$ and $f < b$ , $1 \leqslant c,e \leqslant 4 \times 10^{12}$ .
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 $t$ $(1 \leqslant t \leqslant 10^5)$ , the number of test cases.
The only line of each test case contains two integers $a$ and $b$ $(1 \leqslant a, b \leqslant 2 \times 10^6)$ .

输出描述

For each test case print four integers $c,d,e,f$ . If there are no solution, $c,d,e,f$ should all be $-1$ .

示例1

输入

输出

1
2
3

-1 -1 -1 -1
1 2 1 3
145 87 104 78

分析

若 $\gcd(a,b)>1$ ，代表分数 $\frac{a}{b}$ 可以约分为 $\frac {a/\gcd(a,b)}{b/\gcd(a,b)}$ 。简便起见，直接令 $d=f=\frac{b}{\gcd(a,b)}$ ，那么就有 $c-e=\frac{a}{\gcd(a,b)}$ ，有一组解为 $c=\frac{a}{\gcd(a,b)}$ ， $e=1$ 。
若 $a\bot b$ ，那么 $\frac{a}{b}$ 已经是最简分式，将等式左边通分后，可得 $\frac{fc-de}{df}=\frac{a}{b}$ 。首先，当 $b$ 为质数的幂时，无解（文末给出证明）。接下来考虑 $b$ 有多个不相同质因子的情况。根据算数基本定理，可以将 $b$ 写成有限个质数的乘积， $b=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$ 。方便起见，直接令 $df=b$ ， $fc-de=a$ 。 $fc-de=a$ 是一个裴蜀方程，当且仅当 $\gcd(f,d)\mid a$ 时方程有整数解。若能构造得到的 $f,d$ 使得 $\gcd(f,d)=1$ ，那么方程一定有整数解。显然这样的构造方案是存在的，令 $d=p_1^{k_1}$ ， $f=p_2^{k_2}\cdots p_m^{k_m}=\frac{b}{p_1^{k_1}}$ ，就有 $\gcd(d,f)=1$ 。可以用扩展欧几里得算法求出 $c,e$ 的特解 $c_0,e_0$ ，为了满足条件 $1\leqslant c,e\leqslant 4\times 10^{12}$ ，不妨让 $c,e$ 尽量向 $4\times 10^{12}$ 靠近。令 $top=4\times 10^{12}$ ，求一个不等式组即可得到 $c,e$ 的上界。有不等式组 $\begin{cases}c_0+kd\leqslant top\\e_0+kf\leqslant top\end{cases}$，解得 $k\leqslant \min\left(\left\lfloor\frac{top-c_0}{d}\right\rfloor,\left\lfloor\frac{top-e_0}{f}\right\rfloor\right)$ 。
接下来给出证明：当 $a\bot b$ 且 $b$ 为质数的幂次时，无解。
设 $df=kb$ ， $fc-de=ka$ ， $b=p^t$ 。由于 $b$ 是质数的幂次，可设 $d=k_1p^x$ ， $f=k_2p^y$ ，其中 $k_1k_2=k$ ， $x+y=t$ 。那么有 $\frac{k_2p^yc-k_1p^xd}{kp^t}=\frac{a}{b}(\ast)$ 且 $kp^t=b$ 。很显然， $(\ast)$ 式的左边分式可以上下同除以 $\mathrm{lcm}(p^x,p^y)$ 进行约分；又 $kp^t=b$ ，故 $k_2p^yc-k_1p^xd=a$ ，这样一来， $\frac{a}{b}$ 就是一个可约分的分式，与事实矛盾。证毕。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第三场）Problem F
Date: 8/15/2020
Description: Number Theory, Construction, Extend Euclid Algorithm
*******************************************************************/
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const ll top=4000000000000;
void ex_gcd(ll,ll,ll&,ll&);
vector<int> divide(int);
int main(){
	int _;
	for(cin>>_;_;_--){
		int a,b;
		ll c,d,e,f;
		scanf("%d%d",&a,&b);
		int gcd=__gcd(a,b);
		if(gcd==1){
			vector<int>prime_factor=divide(b);
			if(prime_factor.size()<=1){
				puts("-1 -1 -1 -1");
			}else{
				ll p=1;
				while(b%p==0){
					p=p*prime_factor.front();
				}
				p/=prime_factor.front();
				d=p;
				f=b/p;
				ex_gcd(f,d,c,e);
				c=c*a;
				e=-e*a;
				ll k=min((top-c)/d,(top-e)/f);
				c+=k*d;
				e+=k*f;
				printf("%lld %lld %lld %lld\n",c,d,e,f);
			}
		}else{
			d=f=b/gcd;
			e=1;
			c=a/gcd+1;
			printf("%lld %lld %lld %lld\n",c,d,e,f);
		}
	}
	return 0;
}
void ex_gcd(ll a,ll b,ll& x,ll& y){
	if(!b){
		x=1;
		y=0;
		return;
	}else{
		ex_gcd(b,a%b,x,y);
		ll temp=x;
		x=y;
		y=temp-a/b*y;
	}
}
vector<int> divide(int x){
	vector<int>prime_factor;
	for(register int i=2;i*i<=x;i++){
		if(x%i==0){
			prime_factor.push_back(i);
			while(x%i==0) x/=i;
		}
	}
	if(x>1) prime_factor.push_back(x);
	return prime_factor;
}

L. Problem L is the Only Lovely Problem $\looparrowright$

题目描述

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 $s$ . The length of $s$ is between $8$ and $10$ .
$s$ 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

输入

LovelyAA

输出

lovely

示例2

输入

1	lovelymoon

输出

lovely

示例3

输入

NOWCOWDER

输出

ugly

示例4

输入

LoveLive

输出

ugly

分析

要求字符串开头为 “lovely”，只需要依次比较字符串开头的六位即可，只需要注意比较是不区分大小写的。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第三场） Problem L
Date: 8/14/2020
Description: Easy String Problem
*******************************************************************/
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
int main(){
	string s;
	cin>>s;
	//依次比较6位
	//不区分大小写
	if((s[0]=='l'||s[0]=='L')&&
	(s[1]=='o'||s[1]=='O')&&
	(s[2]=='v'||s[2]=='V')&&
	(s[3]=='e'||s[3]=='E')&&
	(s[4]=='l'||s[4]=='L')&&
	(s[5]=='y'||s[5]=='Y')){
		puts("lovely");
	}else{
		puts("ugly");
	}
	return 0;
}