ABC388(A-G)
A - ?UPC¶
题目大意
给你一个字符串 \(S\)，输出 \(S\) 的第一个字符，然后输出 UPC。
参考代码
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
cin >> s;
cout << s[0] << "UPC" << endl;
return 0;
}
B - Heavy Snake¶
题目大意
有 \(N\) 条蛇，第 \(i\) 条蛇的厚度是 \(T_i\)，长度是 \(L_i\)，一条蛇的重量定义为厚度和长度的乘积，对于 \(k = 1, 2, ..., D\)，你需要回答当所有蛇的长度都增长 \(k\) 后，最重的蛇的重量是多少？
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, d;
cin >> n >> d;
vector<int> t(n), l(n);
for(int i = 0; i < n; i++)
cin >> t[i] >> l[i];
for(int k = 1; k <= d; k++)
{
int m = 0;
for(int i = 0; i < n; i++)
m = max(m, t[i] * (l[i] + k));
cout << m << endl;
}
return 0;
}
C - Various Kagamimochi¶
题目大意
有 \(N(2 \le N \le 5 \times 10 ^ 5)\) 个饼，第 \(i\) 个饼的大小为 \(A_i(1 \le A_i \le 10 ^ 9)\)，其中 \(A_i \le A_{i+1}(1 \le i < N)\)。
如果有两个饼的大小分别为 \(a\) 和 \(b\)，且满足 \(2 \times a \le b\)，就可以将大小为 \(a\) 的饼放在大小为 \(b\) 的饼的上面构成“双层饼”。
问：有多少个数对 \((i, j)\) 满足可以将第 \(i\) 个饼放在第 \(j\) 个饼的上面构成“双层饼”？
解题思路
因为 \(A_i\) 已经有序，双指针统计答案就好。
参考代码
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a)
cin >> x;
LL ans = 0;
for(int l = 0, r = 0; r < n; r++)
{
while(a[l] * 2 <= a[r])
l++;
ans += l;
}
cout << ans << endl;
return 0;
}
D - Coming of Age Celebration¶
题目大意
在一个外星球上有 \(N(1 \le N \le 5 \times 10^5)\) 个外星人，每个外星人都未成年。第 \(i\) 个外星人会在 \(i\) 年后成年。初始的时候第 \(i\) 个外星人有 \(A_i(1 \le A_i \le 5 \times 10^5)\) 个石头。这个星球有一个规矩，当有人成年时，所有（还有石头的）成年人都会给他 \(1\) 个石头作为成人礼。问：在 \(N\) 年之后，每个外星人分别有多少个石头？
解题思路
第 \(i\) 个人成年之后需要为后续的所有外星人发 \(1\) 个石头，直到手中没有石头为止。显然，在第 \(i\) 个人成年时统计出他还有多少个石头，一次性扣除掉后续的石头数量，就是他最终剩下的石头数量。而扣除的石头相当于对后续做了一次区间加，可以用树状数组，也可以直接修改差分数组，时间复杂度 \(O(N)\)。
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n + 2);
vector<int> b(n + 2);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
b[i] += b[i-1];
a[i] += b[i];
int k = min(a[i], n - i);
b[i + 1]++;
b[i + k + 1]--;
a[i] -= k;
cout << a[i] << ' ';
}
return 0;
}
E - Simultaneous Kagamimochi¶
题目大意
有 \(N(2 \le N \le 5 \times 10 ^ 5)\) 个饼，第 \(i\) 个饼的大小为 \(A_i(1 \le A_i \le 10 ^ 9)\)，其中 \(A_i \le A_{i+1}(1 \le i < N)\)。
如果有两个饼的大小分别为 \(a\) 和 \(b\)，且满足 \(2 \times a \le b\)，就可以将大小为 \(a\) 的饼放在大小为 \(b\) 的饼的上面构成“双层饼”。
问：这 \(N\) 个饼最多可以同时做成多少个“双层饼”？
解题思路
二分答案，对于某个答案 \(X\)，一定是最小的前 \(X\) 个饼和最大的后 \(X\) 个饼依次配对成 \((A_1, A_{N-X+1}), (A_2, A_{N-X+2}), ..., (A_X, A_N)\)，中间的饼一定不会被选用（因为中间的饼无论放在上面或者下面都不会更好）。至多枚举 \(O(\log N)\) 个答案，每个答案需要 \(O(N)\) 时间判断，时间复杂度为 \(O(N\log N)\)
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a)
cin >> x;
auto check = [&a, n](int k) -> bool
{
for (int i = 0, j = n - k; i < k; i++, j++)
if (a[i] * 2 > a[j])
return false;
return true;
};
int l = 0, r = n / 2;
while (l < r)
{
int mid = (l + r + 1) / 2;
if(check(mid))
l = mid;
else
r = mid - 1;
}
cout << l << endl;
return 0;
}
F - Dangerous Sugoroku¶
题目大意
有 \(N(2 \le N \le 10 ^ {12})\) 个格子排成一行，有 \(M(1 \le M \le 2 \times 10 ^ 4)\) 个禁止进入的格子区间，第 \(i\) 个区间是 \([L_i, R_i]\)，其中 \(1 \le L_i \le R_i < N\) 且 \(R_i < L_{i+1}(1 \le i \le M-1)\)。
给你两个整数 \(A\) 和 \(B\)，其中 \(1 \le A \le B \le 20\)。初始的时候你在第 \(1\) 个格子，你的目的地是第 \(N\) 个格子。你可以进行多次移动，每一次移动选择一个整数 \(x \in [A, B]\)，然后向右移动 \(x\) 格。你不能进入被任意一个区间 \([L_i, R_i]\) 所标记的格子。问：你能否到达第 \(N\) 个格子？
解题思路
先考虑朴素的 dp，用 \(dp[i] = 1/0\) 表示能否到达第 \(i\) 个格子，用 \(b[i] = 1/0\) 表示第 \(i\) 个格子是否被标记过。转移如下：
这样算出 \(dp[N]\) 的时间复杂度是 \(O(N)\)，还是会超时。
注意到 \(B \le 20\)，那么 \(\bigvee\limits_{j=A}^{j=B} dp[i-j]\) 这个转移方式实际可以用一个 \(B \times B\) 的布尔矩阵的方式表达出来，布尔矩阵的乘法使用与操作代替乘法，或操作代替加法。
例如对于样例的 \(A = 3\)，\(B = 5\)，可以构造出：
这样就可以矩阵快速幂了。不过直接从 \(1\) 算到 \(N\) 是不行的，中间会有很多禁区没有考虑到。我们可以依次跳到每个禁区的右端点 \(R_i\)，这样我们当前的向量就是 \(\begin{bmatrix}dp_{R_i} & \cdots & dp_{L_i} & \cdots & dp_{R_i-B+1}\end{bmatrix}\)，然后手动的将向量的 \(\begin{bmatrix}dp_{R_i} & \cdots & dp_{L_i} \end{bmatrix}\) 部分设置为 \(0\)，反复的跳 \(M\) 次，时间复杂度就是 \(M\log N\)，可以通过。
参考代码还用了 bitset 加速。
参考代码
#include <array>
#include <bitset>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
using LL = long long;
const int N = 20;
using RowVec = bitset<N>;
class Matrix
{
public:
RowVec &operator[](int i) { return a[i]; }
const RowVec &operator[](int i) const { return a[i]; }
Matrix operator*(const Matrix &y) const;
private:
array<RowVec, N> a;
};
RowVec operator*(const RowVec &v, const Matrix &m)
{
RowVec res;
for (int j = 0; j < N; j++)
if (v[j])
res |= m[j];
return res;
}
Matrix Matrix::operator*(const Matrix &y) const
{
Matrix res;
for (int i = 0; i < N; i++)
res[i] = a[i] * y;
return res;
}
Matrix qpow(Matrix a, LL b)
{
Matrix res;
for (int i = 0; i < N; i++)
res[i][i] = 1;
while (b)
{
if (b & 1)
res = res * a;
b >>= 1;
a = a * a;
}
return res;
}
int main()
{
LL n;
int m, a, b;
cin >> n >> m >> a >> b;
vector<pair<LL, LL>> ranges(m + 1);
ranges[0] = {1, 1};
for (int i = 1; i <= m; i++)
cin >> ranges[i].first >> ranges[i].second;
RowVec V;
V[0] = 1;
Matrix A;
for (int i = 1; i < N; i++)
A[i - 1][i] = 1;
for (int i = a; i <= b; i++)
A[i - 1][0] = 1;
for (int i = 1; i <= m; i++)
{
V = V * qpow(A, ranges[i].second - ranges[i - 1].second);
for (LL x = ranges[i].second, j = 0; x >= ranges[i].first && j < N; j++, x--)
V[j] = 0;
}
V = V * qpow(A, n - ranges[m].second);
cout << (V[0] ? "Yes" : "No");
return 0;
}
G - Simultaneous Kagamimochi 2¶
题目大意
有 \(N(2 \le N \le 5 \times 10 ^ 5)\) 个饼，第 \(i\) 个饼的大小为 \(A_i(1 \le A_i \le 10 ^ 9)\)，其中 \(A_i \le A_{i+1}(1 \le i < N)\)。
如果有两个饼的大小分别为 \(a\) 和 \(b\)，且满足 \(2 \times a \le b\)，就可以将大小为 \(a\) 的饼放在大小为 \(b\) 的饼的上面构成“双层饼”。
给你 \(Q(2 \le Q \le 5 \times 10 ^ 5)\) 个询问，每个询问包含一个区间 \([L_i, R_i]\)，你需要回答出使用下标为区间 \([L_i, R_i]\) 的饼可以同时做多少个“双层饼”。
解题思路
我们可以发现，对于某个询问的 \([L_i, R_i]\)，当我们每个询问二分一个 \(X\)，仍然是取区间 \([L_i, R_i]\) 的前 \(X\) 个和后 \(X\) 个来对比，而且每个位置都是对应的，例如将第 \(A_t\) 个饼放在上面，则下面的饼就是 \(A_{R_i-L_i + 1 + t - X}\)，也就是需要 \(2 \times A_t \le A_{R_i-L_i + 1 + t - X}\) 才行，如果一个一个对比最坏仍然是 \(O(N)\) 的，这样总的时间复杂度就是 \(O(QN\log N)\)，肯定超时。
考虑一下 C 题的做法，C 题的时候使用了双指针，求出了每个饼从右边开始的第一个满足条件的可以放在下面的饼的位置，而这个位置是全局固定的，所以我们用同样的方法预处理出一个数组， \(f[t]\) 表示第 \(t\) 个饼作为上面的饼时，第一个可以放在其下面的饼的位置。
于是对于 \(2 \times A_t \le A_{R_i-L_i + 1 + t - X}\) 这个式子就不用直接判断值，只需要比较下标大小就可以了，即 \(f[t] \le R_i-L_i + 1 + t - X\)，这个式子的变量只有 \(t\)，移到同侧就是 \(f[t] - t \le R_i-L_i + 1 - X\)，现在我们需要对于 \(t = L_i, L_i+1, ... L_i + X-1\) 都满足这个式子才是 check 成功。对于这个变量求出最大的那一个和右侧进行比较即可。于是我们可以在做出一个 \(g[t] = f[t] - [t]\)，同时处理出 \(g\) 的 ST 表，就能 \(O(1)\) 的查出 \(t = L_i, L_i+1, ... L_i + X-1\) 在 \(g\) 上的最大值，用这个值和右侧的常量比较就可以了。
于是 check 的时间复杂度就是 \(O(1)\)，处理所有的询问的复杂度就是 \(O(Q\log N)\)， 预处理出 ST 表的时间复杂度是 \(O(N\log N)\)，总的复杂度就是 \(O(Q\log N +N\log N)\)。此外，如果 \(N\) 比较大会导致 \(O(N\log N)\) 超时的话，只需要把 ST 表换成线段树，这样总的时间复杂度就是 \(O(Q \log N + N)\)
参考代码
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
struct SparseTable
{
int n;
vector<vector<int>> M;
vector<int> log2val;
SparseTable(const vector<int> &a) : n(a.size()), M(n), log2val(n + 1)
{
for (int i = 2; i <= n; i++)
log2val[i] = log2val[i / 2] + 1;
for (int i = 0; i < n; i++)
M[i].push_back(a[i]);
for (int j = 1, len1 = 1, len2 = 2; len2 <= n; j++, len1 <<= 1, len2 <<= 1)
for (int i = 0; i + len2 < n; i++)
M[i].push_back(max(M[i][j - 1], M[i + len1][j - 1]));
}
int ask(int l, int r) const
{
int len = r - l + 1, k = log2val[len];
return max(M[l][k], M[r - (1 << k) + 1][k]);
}
};
int main()
{
int n;
cin >> n;
vector<int> a(n+1), f(n+1);
for(int i = 1; i <= n; i++)
cin >> a[i];
for (int l = 1, r = 1; l <= n; l++)
{
while (r <= n && a[l] * 2 > a[r])
r++;
f[l] = r - l;
}
SparseTable t(f);
auto check = [&t](int l, int r, int k) -> bool
{ return t.ask(l, l + k - 1) <= r - l + 1 - k; };
int q;
cin >> q;
while (q--)
{
int l, r;
cin >> l >> r;
int lb = 0, ub = (r - l + 1) / 2;
while (lb < ub)
{
int mid = (lb + ub + 1) / 2;
if (check(l, r, mid))
lb = mid;
else
ub = mid - 1;
}
cout << lb << endl;
}
return 0;
}
创建日期: 2025-06-01