T1 My Cow Ate My Homework GMOJ 6659
Description
In your bovine history class, you have been given a rather long homework assignment with N questions (3≤N≤100,000), each graded with an integer score in the range 0...10,000. As is often customary, your teacher plans to assign a final grade by discarding a question on which you received the lowest score and then averaging the remaining scores together. Unfortunately, your pet cow Bessie has just eaten your answers to the first K questions! (K could be as small as 1 or as large as N−2). After copious explanation, your teacher finally believes your story, and agrees to grade the remaining non-eaten part of the assignment the same way as before -- by removing the lowest-scoring question (or one such question, in the event of a tie) and averaging the rest.
Please output all values of K which would have earned you the maximum possible score according to this grading scheme, in sorted order.
在你的历史课上，你得到了一个很长的作业。这个作业包含了N个题目（3 ≤ N ≤ 100,000），每个题目的成绩在0~10,000之间。按照惯例，你的老师按照以下方式计算最终成绩：去掉你最低的一个成绩，然后将其余成绩的平均成绩作为最终成绩。但不幸的是，你的宠物牛“贝西”刚刚吃了前K个题目的答案！（1 ≤ K ≤ N-2）
经过你的一番解释，老师终于相信了你的故事，并且同意对你有答案的题目（没有被吃掉答案的题目）像之前一样给分——通过去掉最低的成绩（如果有多个最低成绩，则只去掉其中一个）并取剩余成绩的平均成绩。
根据这一成绩计算方案，请按升序输出所有可以使你最终成绩最高的K的值。
Input
The first line of input contains N, and the next line contains the scores on the N homework questions.
Output
Please output, one value per line, all values of K which would have earned you the maximum possible score.
Sample Input
5 3 1 9 2 7Sample Output
2Data Constraint
暴力st表可过
#include <cstdio>
#include <cmath>
#define ll long long
ll n, m;
ll tot;
ll st[100010][40];
ll a[100010];
ll ans[100010];
long double mx;
inline ll max(ll x, ll y) {
return x > y ? x : y;
}
inline ll min(ll x, ll y) {
return x < y ? x : y;
}
inline ll query(ll l, ll r) {
ll s = log2(r - l + 1);
return min(st[l][s], st[r - (1 << s) + 1][s]);
}
ll cnt;
int main() {
// freopen("homework.in", "r", stdin);
// freopen("homework.out", "w", stdout);
scanf("%lld", &n);
for(ll i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
st[i][0] = a[i];
tot += a[i];
}
for(ll j = 1; j <= 30; j++) {
for(ll i = 1; i <= n; i++) {
if(i + (1 << (j - 1)) > n) continue;
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
for(ll i = 1; i <= n - 2; i++) {
tot -= a[i];
ll res = tot - query(i + 1, n);
long double score = res * 1.0 / (n - i - 1);
if(score > mx) {
mx = score;
cnt = 0;
ans[++cnt] = i;
}
else if(score == mx) {
ans[++cnt] = i;
}
}
for(ll i = 1; i <= cnt; i++) printf("%lld\n", ans[i]);
}
T2 Haybale Feast
Description
Farmer John is preparing a delicious meal for his cows! In his barn, he has N haybales (1≤N≤100,000). The ith haybale has a certain flavor Fi (1≤Fi≤10^9) and a certain spiciness Si (1≤Si≤10^9). The meal will consist of a single course, being a contiguous interval containing one or more consecutive haybales (Farmer John cannot change the order of the haybales). The total flavor of the meal is the sum of the flavors in the interval. The spiciness of the meal is the maximum spiciness of all haybales in the interval.
Farmer John would like to determine the minimum spiciness his single-course meal could achieve, given that it must have a total flavor of at least M (1≤M≤10^18).
Input
The first line contains the integers N and M, the number of haybales and the minimum total flavor the meal must have, respectively. The next N lines describe the N haybales with two integers per line, first the flavor F and then the spiciness S.
Output
Please output the minimum spiciness in a single course meal that satisfies the minimum flavor requirement. There will always be at least one single-course meal that satisfies the flavor requirement.
Sample Input
5 10 4 10 6 15 3 5 4 9 3 6Sample Output
9Data Constraint
最小的最大值用二分！
然后知道要最大值最小肯定区间要尽量小，然后就可以用st表乱搞了。
#include <cstdio>
#include <cmath>
#define ll long long
ll n, m;
ll f[100010];
ll s[100010];
ll st[100010][40];
ll sum[100010], ans = 1e15;
inline ll max(ll x, ll y) {
return x > y ? x : y;
}
inline ll min(ll x, ll y) {
return x < y ? x : y;
}
inline ll query(ll l, ll r) {
ll s = log2(r - l + 1);
return max(st[l][s], st[r - (1 << s) + 1][s]);
}
int main() {
freopen("hayfeast.in", "r", stdin);
freopen("hayfeast.out", "w", stdout);
scanf("%lld %lld", &n, &m);
for(ll i = 1; i <= n; i++) {
scanf("%lld %lld", &f[i], &s[i]);
sum[i] = sum[i - 1] + f[i];
st[i][0] = s[i];
}
for(ll j = 1; j <= 30; j++) {
for(ll i = 1; i <= n; i++) {
if(i + (1 << (j - 1)) > n) continue;
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
for(ll i = 1; i <= n; i++) {
ll l = i, r = n, res = i;
while(l <= r) {
ll mid = (l + r) >> 1;
if(sum[mid] - sum[i - 1] >= m) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if(sum[res] - sum[i - 1] >= m) {
ans = min(ans, query(i, res));
}
}
printf("%lld", ans);
}
T3 A Pie for a Pie GMOJ 6656
Description
Bessie and Elsie have each baked N pies (1≤N≤10^5). Each of the 2N pies has a tastiness value according to Bessie and a (possibly different) tastiness value according to Elsie. Bessie is thinking about giving one of her pies to Elsie. If Elsie receives a pie from Bessie, she will feel obligated to give one of her pies to Bessie. So as to not appear stingy nor flamboyant, Elsie will try to pick a pie that is at least as tasty (in Elsie's eyes) as the pie she received, but no more than D units tastier (0≤D≤10^9). Such a pie may not exist, in which case Elsie will adopt a pseudonym and exile herself to Japan.
But if Elsie does give Bessie a pie in return, Bessie will similarly try to give Elsie a pie which is at least as tasty but no more than D units tastier (in Bessie's eyes) as the pie Elsie just gave her. Should this be impossible, Bessie too will exile herself. Otherwise she will give her chosen pie to Elsie. This cycle will continue until one of the cows is exiled, an unhappy outcome, or one of the cows receives a pie which she accords a tastiness value of 0, in which case the gift exchange will end and both cows will be happy.
Bessie和Elsie各自烤了 N(1≤N≤10^5)个馅饼）。Bessie 会这 2N 个馅饼打分，Elsie 也会。二者的打分均为一个<=10^9的非负整数。由于她们口味不同，每个派的两个分数可能不同。 她们想互赠礼物。开始时，Bessie 送给 Elsie 一个馅饼。她们收到礼物（对方做的馅饼）后都会回赠对方一个自己做的馅饼。 她们选择回礼的方法相同。以 Elsie 为例，Elsie 根据自己的打分来选择回礼。回礼的分数至少要大于等于她收到的馅饼的分数，但两个馅饼的分数差不能大于 D(0≤D≤10^9) 。如果有多个馅饼满足要求，Elsie 可以选择其中的任意一个作为回礼。若没有馅饼满足要求，Elsie 会放弃。Bessie 选择回礼的方法同理。 她们之间的礼物交换将持续到一头牛放弃（Bad End），或一头牛收到一个她自己打分为 00 的馅饼，此时礼物交换愉快结束（Happy End）。 请注意，不能把一个馅饼赠送两次，不能把馅饼送给自己。 Bessie 想知道：对于每个她做的馅饼，如果她将这个馅饼作为最开始送给 Elsie 的礼物，她俩至少要互赠多少次馅饼（Bessie 给 Elsie 算一次，Elsie 回赠 Bessie 又算一次），才能 Happy End 。如果不可能 Happy End，请输出 -1。Input
The first line contains the two integers N and D. The next 2N lines contain two space-separated integers each, respectively denoting the value of a particular pie according to Bessie, and the value of that pie according to Elsie.
The first N lines refer to Bessie's pies, and the remaining N lines refer to Elsie's pies.
It is guaranteed that all tastiness values are in the range [0,10^9].
第一行有两个整数 N, D。
在接下来的 2N行中，每行有两个整数，表示对于某个馅饼，Bessie 的打分和 Elsie 的打分。其中，前 N 行表示 Bessie 做的馅饼，后 N行则是 Elsie 做的馅饼。Output
here should be N lines in the output. Line i should contain a single integer: the minimum number of pies that could be gifted in a happy gift exchange started with Bessie's pie i. If no gift exchange starting with pie i is happy, then line i should contain the single integer −1 instead.
输出共 N 行，每行一个整数。 第 i 行的整数表示：如果 Bessie 将馅饼 i作为最开始送给 Elsie 的礼物，她俩至少要互赠多少次馅饼才能 Happy End 。如果不可能 Happy End，请在该行输出 -1。Sample Input
2 1 1 1 5 0 4 2 1 4Sample Output
3 1Data Constraint
线段树优化连边然后反向跑一遍（甚至不需要优化连边）
但是我还没打出来。
T4 Modern Art 2 GMOJ 6636
Description
Bessie and Elsie have each baked N pies (1≤N≤10^5). Each of the 2N pies has a tastiness value according to Bessie and a (possibly different) tastiness value according to Elsie. Bessie is thinking about giving one of her pies to Elsie. If Elsie receives a pie from Bessie, she will feel obligated to give one of her pies to Bessie. So as to not appear stingy nor flamboyant, Elsie will try to pick a pie that is at least as tasty (in Elsie's eyes) as the pie she received, but no more than D units tastier (0≤D≤10^9). Such a pie may not exist, in which case Elsie will adopt a pseudonym and exile herself to Japan.
But if Elsie does give Bessie a pie in return, Bessie will similarly try to give Elsie a pie which is at least as tasty but no more than D units tastier (in Bessie's eyes) as the pie Elsie just gave her. Should this be impossible, Bessie too will exile herself. Otherwise she will give her chosen pie to Elsie. This cycle will continue until one of the cows is exiled, an unhappy outcome, or one of the cows receives a pie which she accords a tastiness value of 0, in which case the gift exchange will end and both cows will be happy.
Bessie和Elsie各自烤了 N(1≤N≤10^5)个馅饼）。Bessie 会这 2N 个馅饼打分，Elsie 也会。二者的打分均为一个<=10^9的非负整数。由于她们口味不同，每个派的两个分数可能不同。 她们想互赠礼物。开始时，Bessie 送给 Elsie 一个馅饼。她们收到礼物（对方做的馅饼）后都会回赠对方一个自己做的馅饼。 她们选择回礼的方法相同。以 Elsie 为例，Elsie 根据自己的打分来选择回礼。回礼的分数至少要大于等于她收到的馅饼的分数，但两个馅饼的分数差不能大于 D(0≤D≤10^9) 。如果有多个馅饼满足要求，Elsie 可以选择其中的任意一个作为回礼。若没有馅饼满足要求，Elsie 会放弃。Bessie 选择回礼的方法同理。 她们之间的礼物交换将持续到一头牛放弃（Bad End），或一头牛收到一个她自己打分为 00 的馅饼，此时礼物交换愉快结束（Happy End）。 请注意，不能把一个馅饼赠送两次，不能把馅饼送给自己。 Bessie 想知道：对于每个她做的馅饼，如果她将这个馅饼作为最开始送给 Elsie 的礼物，她俩至少要互赠多少次馅饼（Bessie 给 Elsie 算一次，Elsie 回赠 Bessie 又算一次），才能 Happy End 。如果不可能 Happy End，请输出 -1。Input
The first line contains the two integers N and D. The next 2N lines contain two space-separated integers each, respectively denoting the value of a particular pie according to Bessie, and the value of that pie according to Elsie.
The first N lines refer to Bessie's pies, and the remaining N lines refer to Elsie's pies.
It is guaranteed that all tastiness values are in the range [0,10^9].
第一行有两个整数 N, D。
在接下来的 2N行中，每行有两个整数，表示对于某个馅饼，Bessie 的打分和 Elsie 的打分。其中，前 N 行表示 Bessie 做的馅饼，后 N行则是 Elsie 做的馅饼。Output
here should be N lines in the output. Line i should contain a single integer: the minimum number of pies that could be gifted in a happy gift exchange started with Bessie's pie i. If no gift exchange starting with pie i is happy, then line i should contain the single integer −1 instead.
输出共 N 行，每行一个整数。 第 i 行的整数表示：如果 Bessie 将馅饼 i作为最开始送给 Elsie 的礼物，她俩至少要互赠多少次馅饼才能 Happy End 。如果不可能 Happy End，请在该行输出 -1。Sample Input
2 1 1 1 5 0 4 2 1 4Sample Output
3 1Data Constraint
读错题了……
原文“为了快捷，每次涂色可以用一种颜色填充一个区间，同一种颜色只能使用一次”极易让人理解为“每次涂色中，同一种颜色只能用一次”，实际上是“在所有涂色中一种颜色只能用一次”！（当然也很有可能是因为我太菜了才会误解）。
我被翻译问题（姑且这么说吧）卡了半小时……
难受。
没有递归的题解，我来交一发。
我们把输入转换为部分线段：
如图（以下不同符号分别表示不同区间）：
1 2 1 3 1
----- ===
+ _
我们可以转换为：
1~3
2~2
4~4
4~5
请注意，在这里并不是：
1~3
2~2
4~4
3~5 ⭐
代码很容易可得到：
for(ll i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
if(a[i] == 0) continue; // 0不算入区间
if(!t[a[i]]) {
t[a[i]] = i;
}
else {
vis[a[i]] = 1;
s[++cnt] = (side){t[a[i]], i};
t[a[i]] = i + 1;
}
}
for(ll i = 1; i <= n; i++) { // 只出现过一次，需要补上
if(!vis[a[i]] && a[i]) {
s[++cnt] = (side){t[a[i]], t[a[i]]};
vis[a[i]] = 1;
}
}
转换为以上边的线段表示方式，然后很显然就是求线段最深的深度。
我们就可以递归了。
把线段按右端点排序，然后递归。我们会遇到以下情况：
-
在父线段的区间外，说明这个不在我们的递归讨论范围内，如果我们讨论了，返回到父节点时就会多算入父节点之外的最深深度：
----v -----u --------------fa这个在我们的区间外，所以记得跳出，因为我们不能统计在内。
-
在父线段的区间内，但在当前线段的区间外，说明这个在我们的递归讨论范围内，但我们要重置寄存器（我们只能求深度最大值，如果我们不重置，就会导致两个不同区间的深度累加）：
----v -----u --------------------fa -
与当前线段有交点：
----v -----u这个肯定是输出
-1，十分显然。 -
在父线段的区间内，在当前线段的区间内，进去递归，返回深度，累加到寄存器：
---v -----u --------------------fa
ll dfs(ll u, ll fa) {
ll sum = 0, child_sum = 1;
for(ll v = u + 1; v <= cnt; v++) {
if(s[v].x < s[fa].x) { // 下面的情况和题解一一对应
sum = max(sum, child_sum);
return sum;
} else if(s[v].y < s[u].x || s[u].y < s[v].x) {
sum = max(sum, child_sum);
child_sum = 1;
u = v;
} else if(s[v].x < s[u].x) {
printf("-1");
exit(0);
} else {
ll res = dfs(v, u);
child_sum += res;
}
}
sum = max(sum, child_sum);
return sum;
}
但是我们还有：
1 0 1 0 1
所以记得需要特判前缀和。
首先先求出每一位的前缀和，当前节点为 0 时，前缀和加一，连线段时判断如果线段端点前缀和不同，就说明线段内有 0，直接无脑输出 -1。
for(ll i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
sum[i] = sum[i - 1] + (a[i] == 0); // 计算前缀和
if(a[i] == 0) continue; // 0不算入区间
if(!t[a[i]]) {
t[a[i]] = i;
}
else {
vis[a[i]] = 1;
s[++cnt] = (side){t[a[i]], i};
if(sum[t[a[i]] - 1] != sum[i]) { // 区间内有0
printf("-1");
exit(0);
}
t[a[i]] = i + 1;
}
}
聪明的你肯定发现了，这么递归是会超时的，所以我们返回时还要返回当前枚举到的子节点 v。然后把递归完成后记得更新 for 的位置。因为里面的已经计算过了。
node dfs(ll u, ll fa) {
ll sum = 0, child_sum = 1;
for(ll v = u + 1; v <= cnt; v++) {
if(s[v].x < s[fa].x) { // 下面的情况和题解一一对应
sum = max(sum, child_sum);
return (node){sum, v};
} else if(s[v].y < s[u].x || s[u].y < s[v].x) {
sum = max(sum, child_sum);
child_sum = 1;
u = v;
} else if(s[v].x < s[u].x) {
printf("-1");
exit(0);
} else {
node res = dfs(v, u);
child_sum += res.w;
v = res.i - 1; // 不这么做会超时，因为里面的都计算过了，再计算肯定没有那么深。
}
}
sum = max(sum, child_sum);
return (node){sum, n + 1};
}
全部代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
ll n;
ll a[100010];
ll t[100010];
ll sum[100010];
struct side {
ll x, y;
} s[100010], g[100010];
struct node {
ll w, i;
};
ll cnt;
bool vis[100010];
node dfs(ll u, ll fa) {
ll sum = 0, child_sum = 1;
for(ll v = u + 1; v <= cnt; v++) {
if(s[v].x < s[fa].x) { // 下面的情况和题解一一对应
sum = max(sum, child_sum);
return (node){sum, v};
} else if(s[v].y < s[u].x || s[u].y < s[v].x) {
sum = max(sum, child_sum);
child_sum = 1;
u = v;
} else if(s[v].x < s[u].x) {
printf("-1");
exit(0);
} else {
node res = dfs(v, u);
child_sum += res.w;
v = res.i - 1; // 不这么做会超时，因为里面的都计算过了，再计算肯定没有那么深。
}
}
sum = max(sum, child_sum);
return (node){sum, n + 1};
}
void solve(ll l, ll r) {
if(l == r) return;
ll mid = (l + r) >> 1;
solve(l, mid);
solve(mid + 1, r);
ll pos1 = l, pos2 = mid + 1;
for(ll i = l; i <= r; i++) {
if(pos2 > r || (pos1 <= mid && s[pos1].y > s[pos2].y)) {
g[i] = s[pos1++];
} else {
g[i] = s[pos2++];
}
}
for(ll i = l; i <= r; i++) s[i] = g[i];
}
int main() {
scanf("%lld", &n);
for(ll i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
sum[i] = sum[i - 1] + (a[i] == 0); // 计算前缀和
if(a[i] == 0) continue; // 0不算入区间
if(!t[a[i]]) {
t[a[i]] = i;
}
else {
vis[a[i]] = 1;
s[++cnt] = (side){t[a[i]], i};
if(sum[t[a[i]] - 1] != sum[i]) { // 区间内有0
printf("-1");
exit(0);
}
t[a[i]] = i + 1;
}
}
for(ll i = 1; i <= n; i++) { // 只出现过一次，需要补上
if(!vis[a[i]] && a[i]) {
s[++cnt] = (side){t[a[i]], t[a[i]]};
vis[a[i]] = 1;
}
}
if(cnt == 0) {
printf("0");
exit(0);
}
s[0].x = 0;
s[0].y = n + 1;
solve(1, cnt);
node res = dfs(1, 0);
printf("%lld", res.w);
}