AtCoder Beginner Contest 418

A I’m a teapot

Takahashi is a teapot.
Since he is a teapot, he will gladly accept tea, but will refuse any other liquid.
Determine whether you can pour a liquid named $S$ into him.

You are given a string $S$ of length $N$ consisting of lowercase English letters.
Determine whether $S$ is a string that ends with tea.

Constraints

• $1\le N\le 20$
• $N$ is an integer.
• $S$ is a string of length $N$ consisting of lowercase English letters.

翻译

高桥是一个茶壶。
既然他是茶壶，他就会欣然接受茶水，而拒绝其他任何液体。
确定能否向它倒入名为 $S$ 的液体。

给你一个长度为 $N$ 的字符串 $S$ ，由小写英文字母组成。
请判断 $S$ 是否是以 tea 结尾的字符串。

约束

• $1\le N\le 20$
• $N$ 是整数。
• $S$ 是长度为 $N$ 的字符串，由小写英文字母组成。

分析：判断字符的结尾是不是 tea 即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;void solve() {int n; string s; cin >> n >> s;bool f = (n > 2 && s.substr(n - 3, 3) == "tea");cout << (f ? "Yes" : "No") << "\n";
}
int main() {// freopen("1.in", "r", stdin);int T = 1; while (T--) solve();return 0;
}

B You’re a teapot

I begin with T and end with T, and I am full of T. What am I?

For a string $t$, define the filling rate as follows:

• If the first and last characters of $t$ are both t and $|t|\ge 3$: Let $x$ be the number of t in $t$. Then the filling rate of $t$ is $\frac{x-2}{|t|-2}$, where $|t|$ denotes the length of $t$.
• Otherwise: the filling rate of $t$ is $0$.

You are given a string $S$. Find the maximum possible filling rate of a substring of $S$.

What is a substring?
A substring of $S$ is a string obtained by removing zero or more characters from the beginning and the end of $S$. For example, ab, bc, and bcd are substrings of abcd, while ac, dc, and e are not substrings of abcd.

Constraints

• $1\le |S|\le 100$
• $S$ is a string consisting of lowercase English letters.

翻译

我是什么？

对于一个字符串 $t$ ，定义填充率如下：

• 如果 $t$ 的第一个字符和最后一个字符都是 "T "和 $|t|\ge 3$ ：设 $x$ 是 $t$ 中 "t "的个数。那么 $t$ 的填充率为 $\frac{x-2}{|t|-2}$ ，其中 $|t|$ 表示 $t$ 的长度。
• 否则： $t$ 的填充率为 $0$ 。

给你一个字符串 $S$ 。求 $S$ 子串的最大填充率。

什么是子串？
$S$ 的子串是指从 $S$ 的开头和结尾删除零个或多个字符后得到的字符串。例如，ab、bc和bcd是abcd的子串，而ac、dc和e不是abcd的子串。

约束

• $1\le |S|\le 100$
• $S$ 是一个由小写英文字母组成的字符串。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;void solve() {string s; cin >> s;int x = 0, n = s.size();double ans = 0;for (int i = 0; i < n; i++)for (int j = i + 1; j < n; j++)if (s[i] == 't' && s[j] == 't') {int x = 0, len = j - i + 1;for (int k = i; k <= j; k++)x += (s[k] == 't');ans = max(ans, (x - 2.0) / (len - 2.0));}cout << fixed << setprecision(12) << ans << "\n";
}
int main() {// freopen("1.in", "r", stdin);int T = 1; while (T--) solve();return 0;
}

C Flush

On the poker table, there are tea bags of $N$ different flavors. The flavors are numbered from 1 through $N$, and there are $A_i$ tea bags of flavor $i$ ($1\le i\le N$).

You will play a game using these tea bags. The game has a parameter called difficulty between 1 and $A_1+\cdots +A_N$, inclusive. A game of difficulty $b$ proceeds as follows:

1. You declare an integer $x$. Here, it must satisfy $b\le x\le A_1+\cdots +A_N$.
2. The dealer chooses exactly $x$ tea bags from among those on the table and gives them to you.
3. You check the flavors of the $x$ tea bags you received, and choose $b$ tea bags from them.
4. If all $b$ tea bags you chose are of the same flavor, you win. Otherwise, you lose.

The dealer will do their best to make you lose.

You are given $Q$ queries, so answer each of them. The $j$-th query is as follows:

• For a game of difficulty $B_j$, report the minimum integer $x$ you must declare at the start to guarantee a win. If it is impossible to win, report $-1$ instead.

Constraints

• $1\le N\le 3\times 10^5$
• $1\le Q\le 3\times 10^5$
• $1\le A_i\le 10^6$ ($1\le i\le N$)
• $1\le B_j\le \min (10^9,A_1+\cdots +A_N)$ ($1\le j\le Q$)
• All input values are integers.

翻译：
在扑克桌上，有不同口味的茶包。口味从 $1$ 到 $N$ 编号，有 $A_i$ 个茶包口味 $i$（$1\le i\le N$）。
你将用这些茶包玩游戏。游戏有一个名为难度的参数，介于 $1$ 和 $a_1+\cdots +a_N$ 之间。难度游戏 $b$ 的收益如下：

1. 声明一个整数 $x$。这里，它必须满足 $b\le x\le A_1+\cdots +A_N$。
2. 经销商从桌上的茶包中准确地选择 $x$ 个茶包，并将其送给您。
3. 您检查收到的 $x$ 个茶包，并从中选择 $b$ 个茶包。
4. 如果你选择的 $b$ 个茶包都是相同的味道，你就赢了。否则，你输了。

经销商会尽最大努力让你输。

您会收到 $Q$ 的查询，请逐一回答。第 $j$ 个查询如下：

• 对于难度为 $B_j$ 的游戏，报告您必须在开始时声明的最小整数 $x$，以确保获胜。如果不可能获胜，则报告 $-1$。

约束条件

• $1\le N\le 3\times 10^5$
• $1\le Q\le 3\times 10^5$
• $1\le A_i\le 10^6$ ($1\le i\le N$)
• $1\le B_j\le \min (10^9,A_1+\cdots +A_N)$ ($1\le j\le Q$)
• 所有输入值都是整数。

分析：

本题目要模拟样例，找到题目所求：当相同元素的数量至少为 $b$ 的需要最少有解数量 $x$。

解法：考虑对原数组 $a_i$ 排序，求出前缀和 $s_i$，二分查询第一个$\ge b$ 的元素位置 $id$，如果答案存在，则 $ans=s_{id-1}+(b-1)\times (n-id+1)+1$；否则 $ans=-1$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n, q, a[N], b;
ll s[N];void solve() {cin >> n >> q;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];while (q--) {cin >> b;int id = lower_bound(a + 1, a + 1 + n, b) - a;ll ans = -1;if (id <= n && a[id] >= b)ans = s[id - 1] + 1ll * (b - 1) * (n - id + 1) + 1;cout << ans << "\n";}
}
int main() {// freopen("1.in", "r", stdin);int T = 1; while (T--) solve();return 0;
}

D XNOR Operation

This problem is a subproblem of Problem G.

A non-empty string $S$ consisting of 0 and 1 is called a beautiful string when it satisfies the following condition:

• (Condition) You can perform the following sequence of operations until the length of $S$ becomes $1$ and make the only character remaining in $S$ be 1.
  1. Choose any integer $i$ satisfying $1\le i\le |S|-1$.
  2. Define an integer $x$ as follows:
     • If $S_i=$ 0 and $S_{i+1}=$ 0, let $x=1$.
     • If $S_i=$ 0 and $S_{i+1}=$ 1, let $x=0$.
     • If $S_i=$ 1 and $S_{i+1}=$ 0, let $x=0$.
     • If $S_i=$ 1 and $S_{i+1}=$ 1, let $x=1$.
  3. Remove $S_i$ and $S_{i+1}$, and insert the digit corresponding to $x$ in their place.
     For example, if $S=$ 10101 and you choose $i=2$, the string after the operation is 1001.

You are given a string $T$ of length $N$ consisting of 0 and 1.
Find the number of beautiful strings that are substrings of $T$. Even if two substrings are identical as strings, count them separately if they are taken from different positions.

What are substrings? A substring of $S$ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$.
For example, 10 is a substring of 101, but 11 is not a substring of 101.

Constraints

• $1\le N\le 2\times 10^5$
• $N$ is an integer.
• $T$ is a string of length $N$ consisting of 0 and 1.

翻译：

本问题是问题 G 的子问题。

由 0 和 1 组成的非空字符串 $S$ 满足以下条件时，称为优美字符串：

• 条件）你可以执行以下一系列操作，直到 $S$ 的长度变为 $1$ ，并使 $S$ 中唯一剩下的字符是 1。
  1. 选择满足 $1\le i\le |S|-1$ 的任意整数 $i$ 。
  2. 定义整数 $x$ 如下：
     • 如果 $S_i=$ 0 且 {98421818}0和 $S_{i+1} =$ 0，设 $x=1$ .
     • 若 $S_i=$ 0 且 {56774510} 0, 则设 $x=1$ .0和 $S_{i+1} =$ 1，则 $x=0$ .
     • 若 $S_i=$ 1，且 $S_{i+1}=$ 0，则让 {12243413}.0"，则 $x=0$ .
     • 如果 $S_i=$ 1 和 {1848987} 0, 让 {297737}.1且 $S_{i+1} =$ 1`，则设 $x=1$ 。
  3. 删除 $S_i$ 和 $S_{i+1}$ ，并插入与 $x$ 相对应的数字。
     例如，如果 $S=$ 10101"，而您选择了 $i=2$ ，则操作后的字符串为 “1001”。

给定长度为 $N$ 的字符串 $T$ 由 0 和 1 组成。
求作为 $T$ 的子串的美丽字符串的个数。即使两个子串是相同的字符串，如果它们取自不同的位置，也要分别计算。

什么是子串？ $S$ 的子串是删除 $S$ 开头的零个或多个字符和结尾的零个或多个字符后得到的字符串。
例如，10是101的子串，但11不是101的子串。

约束

• $1\le N\le 2\times 10^5$
• $N$ 是整数。
• $T$ 是长度为 $N$ 的字符串，由 0 和 1 组成。

分析：

E Trapezium

There are $N$ points on a two-dimensional plane, with the $i$-th point at coordinates $(X_i,Y_i)$. It is guaranteed that no two points are at the same position, and no three points are collinear.

Among the combinations of four points from these points, how many combinations can form a trapezoid as a polygon with those four points as vertices?

Constraints

• $4\le N\le 2000$
• $0\le X_i,Y_i\le 10^7$ ($1\le i\le N$)
• No two points are at the same location.
• No three points are collinear.
• All input values are integers.

翻译：
在一个二维平面上有 $N$ 个点，其中第 $i$ 个点的坐标为 $(X_i,Y_i)$ 。保证没有两个点在同一位置，也没有三个点是共线的。

在这些点的四点组合中，以这四点为顶点能组成梯形多边形的组合有多少种？

约束

• $4\le N\le 2000$
• $0\le X_i,Y_i\le 10^7$ ( $1\le i\le N$ )
• 没有两个点在同一位置。
• 没有三个点是相邻的。
• 所有输入值均为整数。

分析：

F We’re teapots

There are $N$ teapots arranged in a row, numbered from $1$ to $N$ from left to right.

There is a sequence of integers $(a_1,\dots ,a_N)$, initially with values $a_1=\cdots =a_N=-1$.

You will fill each teapot with either tea or coffee so that the following conditions are all satisfied:

• For any two adjacent teapots, at least one of them contains tea.
• For any integer $i$ satisfying $1\le i\le N$, if $a_i\ne -1$, then exactly $a_i$ of teapots $1,\dots ,i$ contain coffee.

You are given $Q$ queries, which you should process in the given order.

The $j$-th query ($1\le j\le Q$) is as follows:

• Change the value of $a_{X_j}$ to $Y_j$. Then, print the number, modulo $998244353$, of ways to fill the teapots satisfying the conditions.

Constraints

• $2\le N\le 2\times 10^5$
• $1\le Q\le 2\times 10^5$
• $1\le X_j\le N$ ($1\le j\le Q$)
• $-1\le Y_j\le X_j$ ($1\le j\le Q$)
• All input values are integers.

翻译

有 $N$ 个茶壶排成一排，从左到右依次编号为 $1$ 至 $N$ 。

有一串整数 $(a_1,\dots ,a_N)$ ，最初的值为 $a_1=\cdots =a_N=-1$ 。

你要在每个茶壶中注入茶或咖啡，以满足以下所有条件：

• 对于任意两个相邻的茶壶，其中至少有一个装有茶叶。
• 对于满足 $1\le i\le N$ 的任意整数 $i$ ，如果有 $a_i\ne -1$ ，那么在 $1,\dots ,i$ 的茶壶中，正好有 $a_i$ 个茶壶装有咖啡。

给你 $Q$ 个查询，你应按给定的顺序处理这些查询。

$j$ -th 查询（ $1\le j\le Q$ ）如下：

• 将 $a_{X_j}$ 的值改为 $Y_j$ 。然后，打印出满足条件的茶壶的装水方式的数量，模数为 $998244353$ 。

限制因素

• $2\le N\le 2\times 10^5$
• $1\le Q\le 2\times 10^5$
• $1\le X_j\le N$ ( $1\le j\le Q$ )
• $-1\le Y_j\le X_j$ ( $1\le j\le Q$ )
• 所有输入值均为整数。

分析：

G Binary Operation

There are $16$ integer tuples $(A,B,C,D)$ satisfying A,B,C,D∈{0,1}A, B, C, D \in \lbrace 0, 1 \rbraceA,B,C,D∈{0,1}. For each of them, solve the following problem.

A non-empty string $S$ consisting of 0 and 1 is called a beautiful string when it satisfies the following condition:

• (Condition) You can perform the following sequence of operations until the length of $S$ becomes $1$ and make the only character remaining in $S$ be 1.
  1. Choose any integer $i$ satisfying $1\le i\le |S|-1$.
  2. Define an integer $x$ as follows:
     • If $S_i=$ 0 and $S_{i+1}=$ 0, let $x=A$.
     • If $S_i=$ 0 and $S_{i+1}=$ 1, let $x=B$.
     • If $S_i=$ 1 and $S_{i+1}=$ 0, let $x=C$.
     • If $S_i=$ 1 and $S_{i+1}=$ 1, let $x=D$.
  3. Remove $S_i$ and $S_{i+1}$, and insert the digit corresponding to $x$ in their place.
     For example, if $S=$ 10101 and you choose $i=2$, the string after the operation is 1001 if $B=0$, and 1101 if $B=1$.

You are given a string $T$ of length $N$ consisting of 0 and 1.

• Let $L$ be the length of the longest beautiful string that is a substring of $T$ (if no substring of $T$ is a beautiful string, let $L=-1$),
• Let $M$ be the number of beautiful strings that are substrings of $T$.

Find $L$ and $M$. Even if two substrings are identical as strings, count them separately if they are taken from different positions.

What are substrings?
A substring of $S$ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$.
For example, 10 is a substring of 101, but 11 is not a substring of 101.

Constraints

• $1\le N\le 2\times 10^5$
• $N$ is an integer.
• $T$ is a string of length $N$ consisting of 0 and 1.

翻译

有 $16$ 个整数元组 $(A,B,C,D)$ 满足 A,B,C,D∈{0,1}A, B, C, D \in \lbrace 0, 1 \rbraceA,B,C,D∈{0,1} 。请分别求解下列问题。

由 "0 "和 "1 "组成的非空字符串 $S$ 满足以下条件时，称为优美字符串：

• （条件）你可以执行下面的操作序列，直到 $S$ 的长度变为 $1$ ，并使 $S$ 中唯一剩下的字符是 1。

1. 选择满足 $1\le i\le |S|-1$ 的任意整数 $i$ 。
2. 定义整数 $x$ 如下：

• 如果 $S_i=$ 0 和 {53892861} 0 。0和 $S_{i+1} =$ 0，则设 $x=A$ .
• 如果 $S_i=$ 0 且 {346645525} 0, 则让 $x=A$ .0 "和 $S_{i+1}=$ “1”，设为 $x=B$ 。
• 如果 $S_i=$ 1 和 {3676760} 1，令 $x=B$ .1 “和 $S_{i+1}=$ 0”，则 $x=C$ .
• 如果 $S_i=$ 1和 {66227549} 0，让 $x=C$ .1和 $S_{i+1} =$ 1.如果 $S_i =$ 1和 $S_{i+1} =$1`, 则让 $x=D$ .

3. 删除 $S_i$ 和 $S_{i+1}$ ，并插入与 $x$ 相对应的数字。
   例如，如果 $S=$ 10101"，并选择 $i=2$ ，则操作后的字符串如果是 $B=0$ 则为 “1001”，如果是 $B=1$ 则为 “1101”。

给出长度为 $N$ 的字符串 $T$ ，它由 0 和 1 组成。

• 设 $L$ 是长度为 $T$ 的子串的最长优美字符串（如果 $T$ 的子串都不是优美字符串，则设为 $L=-1$ ）、
• 设 $M$ 是作为 $T$ 子串的优美字符串的个数。

找出 $L$ 和 $M$ 。即使两个子串是相同的字符串，如果它们取自不同的位置，也要分别计算。

什么是子串？
$S$ 的子串是删除 $S$ 开头的零个或多个字符和结尾的零个或多个字符后得到的字符串。
例如，10是101的子串，但11不是101的子串。

约束

• $1\le N\le 2\times 10^5$
• $N$ 是整数。
• $T$ 是长度为 $N$ 的字符串，由 0 和 1 组成。
  分析：