A - ?UPC
题意：给你一个字符串，把他的第一个字符和"UPC"输出。
输出即可。
点击查看代码
void solve() {
std::string s;
std::cin >> s;
std::cout << s[0] << "UPC\n";
}
B - Heavy Snake
题意：n条蛇由厚度和长度，重量为厚度乘长度，问长度加上1~k时，最大的蛇的重量分别是多少。
直接模拟即可。
点击查看代码
void solve() {
int n, d;
std::cin >> n >> d;
std::vector<int> a(n), b(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i] >> b[i];
}
for (int i = 1; i <= d; ++ i) {
int ans = 0;
for (int j = 1; j < n; ++ j) {
if (a[j] * (b[j] + i) > a[ans] * (b[ans] + i)) {
ans = j;
}
}
std::cout << a[ans] * (b[ans] + i) << "\n";
}
}
**C - Various Kagamimochi **
题意：给你升序的n个数，一个数可以放在大于等于它的两倍的数上面，问有多少匹配的数。
从后往前双指针找可以匹配的最大的，那么前面的所有数都可以匹配。
也可以二分。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
i64 ans = 0;
for (int i = n - 1, j = n - 1; i >= 0; -- i) {
while (j >= 0 && a[j] > a[i] / 2) {
-- j;
}
ans += j + 1;
}
std::cout << ans << "\n";
}
D - Coming of Age Celebration8
题意：n个人，每个人有一些石头，每个人第i年会向前面的人要一个石头（如果有），问最后每个人手上的石头数。
第i个人要加上前面的石头，然后给后面连续的min(n - i, a[i])个人一个石头，加石头可以差分做，循环过去判断就行。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
}
std::vector<int> d(n + 2);
for (int i = 1; i <= n; ++ i) {
d[i] += d[i - 1];
a[i] += d[i];
if (a[i]) {
d[i + 1] += 1;
d[std::min(n + 1, i + a[i] + 1)] -= 1;
}
a[i] = std::max(0, a[i] - (n - i));
}
for (int i = 1; i <= n; ++ i) {
std::cout << a[i] << " \n"[i == n];
}
}
E - Simultaneous Kagamimochi
题意：给你升序的n个数，一个数可以放在大于等于它的两倍的数上面，问最多匹配多少个。
刚开始想着贪心匹配wa了两发，然后二分写挂一发。。。
我们肯定要选前面最小的几个和后面最大的匹配，二分这个匹配数，看对应的数能否匹配上就行。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
auto check = [&](int p) -> bool {
for (int i = n - 1; p >= 0 ; -- i, -- p) {
if (a[p] * 2 > a[i]) {
return false;
}
}
return true;
};
int l = 0, r = n / 2 - (n % 2 == 0);
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
if (!check(l)) {
std::cout << 0 << "\n";
} else {
std::cout << l + 1 << "\n";
}
}
F - Dangerous Sugoroku
看了一发感觉会又不会，然后看g过的多就去看g了
待补。
G - Simultaneous Kagamimochi 2
题意：e的加强版，改为q个询问，每次问一个区间的匹配数
想半天写了个线段树二分没搞出来。
待补。