A. tb的区间问题
题意
tb 给了 fc 一个长度为 n 的数组 A , fc 对 A 进行 k 次如下操作：
删除数组第一个元素或者删除数组最后一个元素。
求最后得到的数组和的最大值。
大概思路
滑动窗口秒了
参考代码
void solve() {
int n, k;
std::cin >> n >> k;
int l = n - k;
i64 ans = 0;
std::vector<i64> a(n);
for (auto &i : a) std::cin >> i;
i64 tmp = 0;
for (int i = 0; i < n; i++) {
tmp += a[i];
if (i - l >= 0) {
tmp -= a[i - l];
}
ans = std::max(ans, tmp);
}
std::cout << ans;
}
B. tb的字符串问题
题意
tb 给了 fc 一个字符串。
fc 对字符串可以进行若干次 （可能是0） 次如下操作：
选择子串 ‘‘fc’’ 或者子串 ‘’tb’’ ，将其从字符串中删去。
求最后剩下字符串的最短长度。
子串：原字符串中下标连续的一段字符串。
大概思路
直接用栈贪心地匹配fc和tb就行
参考代码
void solve() {
int n;
std::cin >> n;
std::string s;
std::cin >> s;
std::stack<char> stk;
for (auto &c : s) {
if (stk.size() && (stk.top() == 'f' && c == 'c' || stk.top() == 't' && c == 'b')) {
stk.pop();
} else {
stk.push(c);
}
}
std::cout << stk.size();
}
C. tb的路径问题
题意
tb 给了 fc 一张有 n×n 个格点的图。
图上每个格点都写着一个数。第 i 行第 j 列的格点上写着的数字为 i 和 j 的最大公约数。
现在 fc 需要从第 1 行第 1 列出发，去往第 n 行第 n 列处的格点，fc 可以消耗一点能量移向相邻的格点。
在任何时候，设 fc 所位于的格点上所写的数字为 x ，如果 x 不为 1 ，他可以使用传送阵传送到任何数字为 x 的格点，此操作不消耗能量。
求 fc 到达第 n 行第 n 列所消耗的最少能量。
相邻：如果用 (x,y) 表示第 x 行第 y 列的位置，(x,y) 与 (x+1,y),(x,y+1),(x−1,y),(x,y−1) 相邻。
大概思路
手玩一下样例，取n为10左右，把除1以外的格子标出来，容易发现gcd为2的格子实在是太多了。
| 行/列 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | ||||||||
| 2 | 2 | 2 | 2 | 2 | |||||
| 3 | 3 | 3 | 3 | ||||||
| 4 | 2 | 4 | 2 | 2 | |||||
| 5 | 5 | ||||||||
| 6 | 2 | 3 | 2 | 6 | 2 | 3 | |||
| 7 | 7 | ||||||||
| 8 | 2 | 2 | 2 | 8 | |||||
| 9 | 3 | 3 | 9 |
我们当 $n$ 很大时，我们不妨先花两步走到 $(2,2)$，然后分类讨论：
- 当 $n$ 为偶数时，$\gcd(n, n - 2) = 2$，我们只需要再花费2步，就能从 $(n - 2,n)$ 转移到 $(n, n)$
- 当 $n$ 为奇数时，$n - 1$为偶数，我们可以先转移到 $(n-1,n-1)$，再花2步转移到 $(n,n)$
然后注意特判 $n$ 很小的情况（$n = 1, 2, 3$）就可以了。
参考代码
void solve() {
int n;
std::cin >> n;
if (n == 1) {
std::cout << 0;
return;
} else if (n == 2) {
std::cout << 2;
return;
} else if (n == 3) {
std::cout << 4;
return;
} else {
if (n % 2 == 0) {
std::cout << 4;
} else {
std::cout << 6;
}
return;
}
}
D. tb的平方问题
题意
tb 给了 fc 一个数组 A 。
随后， tb 对 fc 进行了 q 次询问，每次询问 tb 给 fc 一个 x ，需要 fc 给出包含了 x 位置且区间和为完全平方数的连续子数组个数。
大概思路
注意到n比较小，为1e3，完全可以$O(n^2)$暴力预处理出所有元素和为完全平方数的区间。然后用差分进行快速区间修改，最后前缀和统计即可。
不知道为什么没想到前缀和，直接上的树状数组
参考代码
template<typename T>
struct BIT {
std::vector<T> a;
int n;
BIT(int n_) {//下标从1开始
a.clear();
a.resize(n_ + 1);
n = n_;
}
BIT() {}
BIT(const BIT& bit) {//[可选] 复制bit（很少用）
n = bit.n;
a = bit.a;
}
T getsum(int x) {//获取[1, x]的和 O(logn)
T s = 0;
while (x) {
s += a[x];
x -= (x &- x);
}
return s;
}
void add(int x, T val) {//单点增加x处的值 O(logn)
while (x <= n) {
a[x] += val;
x += (x &- x);
}
}
};
//附：想区间修改，区间查询的话，可以用这个维护差分数组（不过都只支持加减）
//区间推平，区间加乘，等操作，请换线段树
void solve() {
int n, q;
std::vector<i64> a(n + 1), pre(n + 1);
for (int i = 1; i <= n; i++) std::cin >> a[i];
for (int i = 1; i <= n; i++) {
pre[i] = a[i] + pre[i - 1];
}
auto ck = [&](i64 x) {
i64 x_ = std::sqrt(x);
return ((x_ - 1) * (x_ - 1) == x) || ((x_) * (x_) == x) || ((x_ + 1) * (x_ + 1) == x);
};
BIT<i64> bit(n + 1);
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j <= n) {
if (ck(pre[j] - pre[i - 1])) {
bit.add(i, 1);
bit.add(j + 1, -1);
}
}
}
while (q--) {
int x;
std::cin >> x;
std::cout << bit.getsum(x) << "\n";
}
}
E. tb的数数问题
题意
tb 给了 fc 一个包含若干个数字的可重集合 $A$ ，如果我们说一个数字 $x$ 是好的当且仅当 $\forall d∣x$ ，有 $d∈A$。
现在，fc 想知道有多少个不同的正整数是好的，请你告诉他吧。
$d∣x$ : 表示 $d$ 为 $x$ 的约数。
$∀ d∣x$ ，有 d∈Ad∈A ： $x$ 的任何约数都至少在 $A$ 中出现一次。
大概思路
一个很像dp的东西，设 $P_i$ 为 $a_i$ 的所有质因数构成的集合，那么转移方程如下：
$$ dp[a_i] = \underset{p \in P_i}{{\LARGE\mathrm \&}} dp[\frac{a_i}{p}]$$
然后统计dp[i]即可，复杂度应该是$O(n\log\max(a_i))$的。
参考代码
struct Sieve {
std::vector<int> mpf; // minimum prime factor
std::vector<int> prime;
Sieve(int n) : mpf(n) {
for (int i = 2; i < n; i++) {
if (mpf[i] == 0) {
prime.push_back(i);
mpf[i] = i;
}
for (int j = 0; j < prime.size() and i * prime[j] < n; j++) {
mpf[i * prime[j]] = prime[j];
if (prime[j] == mpf[i])
break;
}
}
}
// get all factors
std::vector<int> getDiv(int x) const {
std::vector<int> _div(1, 1);
while (x > 1) {
int d = mpf[x];
int l = 0, r = _div.size();
while (x % d == 0) {
for (int k = l; k < r; k++) {
_div.push_back(_div[k] * d);
}
x /= d;
l = r, r = _div.size();
}
}
return _div;
}
};
Sieve si(1e6 + 1);
void solve() {
int n;
std::cin >> n;
std::set<int> s;
while (n--) {
int x;
std::cin >> x;
s.insert(x);
}
if (!s.count(1)) {
std::cout << 0;
return;
}
std::vector<bool> dp(*s.rbegin() + 1, 0);
int ans = 0;
for (auto &i : s) {
std::set<int> p;
int z = i;
while (z != 1) {
p.insert(si.mpf[z]);
z /= si.mpf[z];
}
dp[i] = 1;
for (auto &j : p) {
dp[i] = dp[i] & dp[i / j];
}
ans += dp[i];
}
std::cout << ans;
}
F. tb的排列问题
题意
tb 给了 fc 一个长度为 $n$ 的排列 $A$ ，fc 想要更改一下此排列，他选择了一个幸运数字 $w$ ,依照如下方式操作了 $n$ 次:
第 $i$ 次操作中，选择两个整数 $x,y$，满足 $i≤x≤y≤min(i+w,n)$ ，交换 $A_x$ 与 $A_y$ 的值，$x = y$ 时数组不变。
经过这 $n$ 次操作后，他得到了新的排列 $B$。
由于 fc 的记忆只有七秒，他很快就忘记了 $A$ 排列是什么样子，只记得一部分 $A$ 排列中的元素以及其对应位置。现在他将 $B$ 排列以及残缺的 $A$ 排列给出，请你帮他计算一下一共有多少种可能的 $A$ 排列。（可能存在 fc 记忆错乱了，没有符合条件的 $A$ 。）
由于答案过大，输出方案数模以 $998244353$ 即可。
大概思路
直接正序遍历A数组模拟，一个个换B数组中各个数的位置。然后根据"当前遍历到的位置之前的数是无法再改变的"，分情况讨论。
考虑两种情况：
- 当前遍历到的数，在A数组中出现过
- 当前遍历到的数，在A数组中没有出现过
那么对于出现的情况，我们可以这样考虑：
- 如果出现的数的下标大于 $i + w$，那么显然不存在合法的原排列，因为你没法把那个数移动到当前位置。
- 如果出现的数的下标小于 $i + w$，那么显然存在一种方式，将那个数移动到该位置：若其下标在 $i$ 到 $i + w$ 之间，可以直接换；若下标小于 $i$，那根据“当前遍历到的位置之前的数是无法再改变的”可知，这个数早在前面的步骤就被丢到后面来了。
对于没出现的情况，显然是要拿$-1$来顶，可以这样考虑：
- 对于下标大于 $i + w$ 的 $-1$，我们不予考虑，因为类比之前的分析，我们知道这些 $-1$ 没法换过来。
- 对于下标小于 $i + w$ 的 $-1$，显然是都有机会被放到当前位置的，我们只需要让答案乘上 “小于$i + w$的$-1$的个数 $-$ 已经使用过的 $-1$ 的个数”即可。
参考代码
constexpr int M = 998244353;
void solve() {
int n, w;
std::cin >> n >> w;
std::vector<int> a(n), p = a, idx(n + 1, -1);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
if (a[i] != -1) {
idx[a[i]] = i;
}
}
for (auto &i : p) std::cin >> i;
i64 ans = 1;
int used = 0;
std::vector<int> pre(n);
pre[0] = (a[0] == -1);
for (int i = 1; i < n; i++) {
pre[i] = pre[i - 1] + (a[i] == -1);
}
for (int i = 0; i < n && ans != 0; i++) {
if (idx[p[i]] != -1) {
if (idx[p[i]] > i + w) {
ans = 0;
}
} else {
(ans *= (pre[std::min(n - 1, i + w)] - used)) %= M;
used++;
}
}
std::cout << ans << "\n";
}