A. Setting up Camp#
有 3 种人需要住帐篷，分别有 ，， 个，第一种人是小波奇只愿意自己住，第二种人是喜多一定要和另外 2 个人一起住，第三种人无所谓。每个帐篷最多住 3 个人，最少需要几个帐篷？
小波奇自己住，喜多尽可能内部配队，第三种人填补喜多的空缺，然后除 3 上取整。
B. Fireworks#
有两种烟火，分别在 和 时刻绽放，每次绽放持续 个单位时间，即分别在 和 时刻是绽放的。对所有时间点，求最大同时有多少个烟火绽放？
显然，看一下第 时刻有多少个绽放即可，答案是 。
C. Left and Right Houses#
有一条街有 个住户，被一条路划分成左右两边，每个住户有一个住在左边或右边的意愿 。现在，你要安排这条路的位置，使得左右两边都必须至少有住户数除 2 上取整个人满意，并且最小化其距离中点的距离，并且最小化道路坐标。
虽然条件很多，但是只需要从左到右枚举道路放在哪即可，前后记一下前缀和，即可快速判断合法性。
D. Seraphim the Owl#
有一排长度为 的队列，你现在站在队列最右边（坐标 ）。假设你当前在位置 ，你每次可以往左边跳到位置 ，花费代价 。你现在目标跳到小于等于 的某个位置，问最小代价。
原问题相当于每个位置选一个代价 或 花费，因为每个位置都只会从中选择其一计算一次，并且最后一次花费的是 ，就能构造出一个合法的跳跃方案。注意，你需要枚举最后一次的落点是在 中的某处，因为可能存在 很小 很大的情况。
E. Binary Search#
给你一个乱序的长度为 的排列，你可以最多 2 次，任意交换 2 个位置，使得对这个排列运行二分查找能找到答案。
乍一看你似乎要构造一个长度为 的序列来让二分查找正确运行，但其实这就想歪了。可以发现，虽然二分的过程是乱的，但是确实实打实的在缩减目标区间到唯一一个。我们其实只需要让它随便运行，然后把答案放到随便运行的目标位置上即可。
我们在二分的过程中标记一下访问过哪些位置，那么剩下的位置都可以随意交换，最后找一个没动过的位置换一下即可。注意，在随便二分的过程中，因为可能半路就找到了答案，这时候需要额外花费一次操作，把答案换到一个别的地方。
反正大概是这么个意思，随便乱写了一通，加了点 assert，但是能过。
F. Kirill and Mushrooms#
给了你 个蘑菇，每个蘑菇有一个权值 。你可以从中选出 个蘑菇，权值是选出的蘑菇的权值最小值乘 。还有一个限制是，有一个排列 ，若你选择的 个蘑菇，则这些 蘑菇的权值清空，无法选择。求最大权值的前提下，最小选择个数。
从 到 （虽然只能大概到一半）枚举选了几个蘑菇，维护剩余蘑菇的前 大，然后清除一下对应的蘑菇。
大概感觉能直接搞个堆就行，但是不想动脑直接贴了个树状数组维护第 大。
G. Cook and Porridge#
有 个人排成一队吃饭，有一堆它们在队列里排序的规则，问前 时刻内能否每人吃过一次，或者报告不行。
没写，大概搞个什么数据结构维护弄一弄，感觉一堆细节不想写。
H. GCD is Greater#
给你一个大小为 的数组，你现在要将他们分成两块，且每块至少有 2 个元素，第一块求他们的 ，第二块求他们的 加上参数 。求是否存在一种分割方案，使得第一块的权值严格大于第二块。
显然，第一块的 的数只需要 2 个就行了，因为数越多 越小；同样， 也是数越多越小，但是是符合目标的。
那么我可以直接枚举 ，然后怎么判一判就行了，然后就没写也没细想了，应该差不多能做。
代码#
A. Setting up Camp#
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int inf = 1e9 + 7;
const int maxn = 300000 + 5;
int n, a[maxn];
int main() {
#ifdef DEBUG
freopen("../assets/in.txt", "r", stdin);
#endif
int T;
scanf("%d", &T);
while (T--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
int cnt = a;
cnt += b / 3;
b %= 3;
if (b > 0 && b + c < 3) {
puts("-1");
continue;
} else {
if (b > 0) {
c -= 3 - b;
cnt++;
}
cnt += (c + 2) / 3;
printf("%d\n", cnt);
}
}
return 0;
}
B. Fireworks#
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int inf = 1e9 + 7;
const int maxn = 300000 + 5;
int main() {
#ifdef DEBUG
freopen("../assets/in.txt", "r", stdin);
#endif
int T;
scanf("%d", &T);
while (T--) {
long long a, b, m;
scanf("%lld%lld%lld", &a, &b, &m);
long long ans = 2 + m / a + m / b;
printf("%lld\n", ans);
}
return 0;
}
C. Left and Right Houses#
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int inf = 1e9 + 7;
const int maxn = 300000 + 5;
int n, pre[maxn], suf[maxn];
char buf[maxn];
int main() {
#ifdef DEBUG
freopen("../assets/in.txt", "r", stdin);
#endif
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%s", &n, buf + 1);
pre[0] = 0; suf[n + 1] = 0;
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + (buf[i] == '0');
}
for (int i = n; i >= 1; i--) {
suf[i] = suf[i + 1] + (buf[i] == '1');
}
pre[n + 1] = pre[n]; suf[0] = suf[1];
auto check = [&](int p) {
int l = pre[p];
int r = suf[p + 1];
return l >= (p + 1) / 2 && r >= (n - p + 1) / 2;
};
int ans = -1;
for (int i = 0; i <= n; i++) {
if (check(i)) {
if (ans == -1 || abs(n - ans - ans) > abs(n - i - i)) {
ans = i;
}
}
}
assert(ans != -1);
printf("%d\n", ans);
}
return 0;
}
D. Seraphim the Owl#
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int inf = 1e9 + 7;
const int maxn = 300000 + 5;
int n, m, a[maxn], b[maxn];
int main() {
#ifdef DEBUG
freopen("../assets/in.txt", "r", stdin);
#endif
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
for (int i = 1; i <= n; i++) {
scanf("%d", b + i);
}
long long ans = 0, mn = a[m], sum = 0;
for (int i = n; i > m; i--) {
ans += min(a[i], b[i]);
}
for (int i = m; i >= 1; i--) {
mn = min(mn, a[i] + sum);
sum += b[i];
}
printf("%lld\n", ans + mn);
}
return 0;
}
E. Binary Search#
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int inf = 1e9 + 7;
const int maxn = 300000 + 5;
int n, x, a[maxn];
void check() {
// for (int i = 1; i <= n; i++) {
// printf("%d%c", a[i], " \n"[i == n]);
// }
int l = 1, r = n + 1;
while (r - l > 1) {
int m = (l + r) / 2;
if (a[m] <= x) {
l = m;
} else {
r = m;
}
}
// printf(": %d %d\n", l, a[l]);
assert(r - l == 1 && a[l] == x);
}
int main() {
#ifdef DEBUG
freopen("../assets/in.txt", "r", stdin);
#endif
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &x);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
vector<pair<int,int>> ans;
int l = 1, r = n + 1;
vector<int> visited(n + 1, 0);
while (r - l > 1) {
int m = (l + r) / 2;
if (a[m] == x && r - l > 1) {
int found = -1;
for (int i = 1; found == -1 && i <= n; i++) {
if (!visited[i]) found = i;
}
assert(found != -1);
ans.push_back({ m, found });
swap(a[m], a[found]);
}
visited[m] = 1;
if (a[m] <= x) {
l = m;
} else {
r = m;
}
}
if (a[l] != x) {
int found = -1;
for (int i = 1; found == -1 && i <= n; i++) {
if (a[i] == x) found = i;
}
assert(found != -1 && !visited[found]);
visited[found] = 1;
ans.push_back({ found, l });
swap(a[found], a[l]);
}
printf("%d\n", (int) ans.size());
for (auto& p: ans) {
printf("%d %d\n", p.first, p.second);
}
check();
}
return 0;
}
F. Kirill and Mushrooms#
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int inf = 1e9 + 7;
const int maxn = 300000 + 5;
struct BIT {
static const int R = 1 << 21;
int a[R];
inline int lowbit(int x) { return x & -x; }
void insert(int i, int v) {
for (; i < R; i += lowbit(i)) a[i] += v;
}
void clear(int i) {
for (; i < R; i += lowbit(i)) a[i] = 0;
}
int findx(int p, int rk) {
// if (p > R) return -1;
if (p & 1) {
// if (p + (a[p] < rk) > R) return -1;
return p + (a[p] < rk);
} else {
if (rk > a[p]) return findx(p + lowbit(p) / 2, rk - a[p]);
else return findx(p - lowbit(p) / 2, rk);
}
}
int findx(int rk) {
return findx(R >> 1, rk);
}
} f;
int n, a[maxn], p[maxn];
int main() {
#ifdef DEBUG
freopen("../assets/in.txt", "r", stdin);
#endif
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
vector<int> lsh;
auto gid = [&](int x) -> int {
return int(lsh.end() - lower_bound(lsh.begin(), lsh.end(), x));
};
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
lsh.push_back(a[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", p + i);
}
sort(lsh.begin(), lsh.end());
lsh.resize(unique(lsh.begin(), lsh.end()) - lsh.begin());
for (int i = 1; i <= n; i++) {
f.insert(gid(a[i]), 1);
}
long long ans = 0;
int cnt = 0;
for (int i = 1; i + i - 1 <= n; i++) {
int id = f.findx(i);
int val = lsh[lsh.size() - id];
// printf("Find: %d %d\n", id, val);
if (1ll * val * i > ans) {
ans = 1ll * val * i;
cnt = i;
}
// Delete
f.insert(gid(a[p[i]]), -1);
}
printf("%lld %d\n", ans, cnt);
for (int i = 1; i <= n; i++) f.clear(gid(a[i]));
}
return 0;
}