AtCoder Beginner Contest 418

AtCoder Beginner Contest 418

A I’m a teapot

#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

#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

E Trapezium

F We’re teapots

G Binary Operation