赛时过了 ABCD，rank 15270，我嘞个豆啊，虽然菜成 shi 了，但是打得很开心，凌晨一点多还兴奋得不得了。
就是网络好差，比赛开始好几分钟了还被关在外边。
A - Creating Words
B - Maximum Multiple Sum
签到题，略
C - Good Prefixes
想到用前缀和，一开始写成每次往后一位后缀，只对最后一位数字考察，显然每次拓展一位要重新考察整个数列是否存在 Good Prefixes
但即使用了前缀和，这样直接暴力枚举做，复杂度也要 \(O(n^2)\)
后来又拿起样例想了想，发现一个很重要的性质：对于一个数列，是否存在 Good Prefixes 有且仅有 其中的最大值可能满足，
这是显然的，一个数要满足刚好等于数列中其他数的和。
所以每次考察一个新的数列，只要考察其最大值即可，
我用了 priority_queue 实现，复杂度就降到了 \(O(n\log n)\)
code
#include <bits/stdc++.h>
#define re register int
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int T, n;
LL a[N], sum[N];
priority_queue<LL> q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while (T --)
{
cin >> n;
while (!q.empty()) q.pop();
for (re i = 1; i <= n; i ++)
{
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
int res = 0;
for (re i = 1; i <= n; i ++)
{
q.push(a[i]);
LL t = q.top();
if (sum[i] - t == t)
{
res ++;
}
}
cout << res << '\n';
}
return 0;
}
D - Manhattan Circle
题目屁话好像有点多，根据样例就能推出做法了
找到两条对角线（也就是最长的）所在的坐标，就是这什么 manhattan circle 的圆心坐标
code
#include <bits/stdc++.h>
#define re register int
using namespace std;
const int N = 2e5 + 10;
int T, n, m, num_x[N], num_y[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while (T --)
{
cin >> n >> m;
for (re i = 1; i <= n; i ++) num_x[i] = 0;
for (re i = 1; i <= m; i ++) num_y[i] = 0;
int max_x = -1, max_y = -1, x, y;
for(re i = 1; i <= n; i ++)
for (re j = 1; j <= m; j ++)
{
char c; cin >> c;
if (c == '#')
{
num_x[i] ++;
num_y[j] ++;
if (num_x[i] > max_x)
max_x = num_x[i], x = i;
if (num_y[j] > max_y)
max_y = num_y[j], y = j;
}
}
cout << x << ' ' << y << '\n';
}
return 0;
}
E - Secret Box
首先对于任意长方体 (a, b, c)，在空间 (x, y, z) 中可能存在的不同的摆放位置数量是：\((x-a+1)(y-b+1)(z-c+1)\)
主要是选 (a, b, c) 且满足 a * b * c = k 的最优策略
赛时我只能想到暴力枚举三维取 max，赛后才发现居然可以只用枚举两维就够了？
我去，我真的是个傻缺，k 知道了，a，b知道了，干嘛还去枚举 c 啊，解个一元一次方程就行了呀，哎
code
#include <bits/stdc++.h>
#define re register int
#define max(x, y) (x > y ? x : y)
using namespace std;
typedef long long LL;
int T, x, y, z;
LL k;
inline LL solve(int a, int b, LL c)
{
return (LL)((x - a + 1) * (y - b + 1) * (z - c + 1));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while (T --)
{
cin >> x >> y >> z >> k;
LL res = 0;
for (re a = 1; a <= x; a ++)
for (re b = 1; b <= y; b ++)
{
LL c = k / a / b;
if (a * b * c != k || c > z) continue;
res = max(res, solve(a, b, c));
}
cout << res << '\n';
}
return 0;
}
F - Final Boss
直接模拟会超时，那么可取的复杂度一般是 \(O(n)\)、\(O(n\log n)\) 等线性做法（这也是一种技巧，综合考虑复杂度选择合适的算法 link）
发现轮数越多，击败的可能性是不降的
也就是说，如果当前轮数为 x，满足可以击败 boss，那么 [x, r] 越多的轮数则一定可以击败 boss
满足单调性，可以对轮数进行 二分，每个技能的贡献就是 \(\large\lceil \frac{mid}{c[i]} \rceil * a[i]\)
新学的小技巧：向上取证可以写做 ceil((double)a/b) 等价于 (a+b-1)/b
#include <bits/stdc++.h>
#define re register int
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int T, h, n, a[N], c[N];
inline bool check(LL mid)
{
LL res = 0;
for (re i = 1; i <= n; i ++)
{
res += ceil((double)mid / c[i]) * a[i];
// res += ((mid + c[i] - 1) / c[i]) * a[i];
if (res >= h) return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while (T --)
{
cin >> h >> n;
for (re i = 1; i <= n; i ++) cin >> a[i];
for (re i = 1; i <= n; i ++) cin >> c[i];
LL l = 0, r = 1e11;
while (l < r)
{
LL mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << '\n';
}
return 0;
}