Solved 9 of 12.坑一堆（
A. 小L的三则运算
题意
给定一个大于 \(1\) 的正整数 \(x\) 和一个二元运算符（加减乘之一），输出两个正整数，满足使用该二元运算符计算得到的结果为 \(x\)。
思路
钦定其中一个正整数为 \(1\) 即可。
时间复杂度：\(O(1)\)
对应AC代码
void solve() {
int x;
string op;
cin >> x >> op;
if(op == "*") cout << x << ' ' << 1 << '\n';
else if(op == "+") cout << x - 1 << ' ' << 1 << '\n';
else cout << x + 1 << ' ' << 1 << '\n';
}签到
B. 小L出师了
题意
给定三个正整数 \(n, t, k\)，删去长度为 \(n\) 的数组中的 \(k\) 个不同的位置对应的元素，分割得到若干段，输出长度大于等于 \(t\) 的最多段落数量。
思路
因为我们可以随意选择删除的位置，所以我们可以先全都放在最后，求出段数后再把要删除的位置往前挪，那么显然我们最多可以得到 \(\lfloor \frac{n - k}{t} \rfloor\) 个长度为 \(t\) 的段落。
可是需要注意我们最多只能分得 \(k + 1\) 个段落，需要跟边界取最小值。
时间复杂度：\(O(1)\)
对应AC代码
void solve() {
int n, t, k;
cin >> n >> t >> k;
cout << min(k + 1, (n - k) / t) << '\n';
}简化了一下题意
C. 小L的位运算
题意
给定三个 \(n\) 位二进制数 \(a, b, c\)，定义一次操作为下面四种操作任选其一：
花费 \(x\) 元，反置二进制数 \(a\) 的任意一位；
花费 \(x\) 元，反置二进制数 \(b\) 的任意一位；
花费 \(y\) 元，交换二进制数 \(a\) 的任意两个数位；
花费 \(y\) 元，交换二进制数 \(b\) 的任意两个数位。
在可以进行任意次操作的情况下，输出使得 \(a \oplus b = c\) 需要的最小花费。
思路
我们先不考虑花费，那么不难发现 \(a \oplus b\) 和 \(c\) 的任意一位不对应时，\(a\) 和 \(b\) 在该位的值只有四种可能，分别为 \(00, 01, 10, 11\)。而有趣的是任意一对都有至少一个元素不同，所以我们只需配对交换即可。通过一些贪心策略可以发现，当四种可能的数量中的最大值超过总和的一半时，多余的将无法配对，那么我们将多余的反置即可。
那么如果要考虑花费呢？因为我们上面的操作本质上是两两配对交换，那么这其实等价于分别反置需要交换的两位。所以我们可以比较一下两次反置和一次交换的大小关系，如果前者更小那么全都反置即可，否则采取前面的策略是最优的。
时间复杂度：\(O(n)\)
对应AC代码
void solve() {
int n, x, y;
cin >> n >> x >> y;
string a, b, c;
cin >> a >> b >> c;
vector<int> cnt(4);
for(int i=0;i<n;i++) {
int p = a[i] - '0', q = b[i] - '0', r = c[i] - '0';
if(!(p ^ q ^ r)) continue;
cnt[p * 2 + q] ++;
}
int sum = accumulate(cnt.begin(), cnt.end(), 0ll), mx = *max_element(cnt.begin(), cnt.end());
cout << min(x * sum, x * ((mx % 2 == 0 && sum % 2 == 1) + max(0ll, mx - sum / 2)) + y * (sum / 2)) << '\n';
}要输出方案就头大了
D. 小L的字符串翻转
题意
给定一个长为 \(n\) 的二进制串，将其按照 \(k\) 个元素一段从左到右依次分段，最后一段元素个数可能小于 \(k\)。定义一次操作为选定一段，对整段执行反置或重排列。
在可以任意次操作的情况下，操作完成后将段落重新拼接，并将得到的二进制串中连续的 \(0\) 替换为一个 \(0\)，连续的 \(1\) 替换为一个 \(1\)，记 \(ans_k\) 为替换完成后的长度。输出下式的值：
\(\displaystyle \bigoplus_{k=1}^{n} ans_k\)
思路
首先，\(ans\) 即为拼接完成后 \(01, 10\) 的个数 \(+ 1\)。
如果我们只有一段，那么显然将 \(0\) 和 \(1\) 分开放在两端是最合适的。所以说在一个段落内，最多只会有一个 \(01, 10\)，这取决于段落内是否同时包含 \(0\) 和 \(1\)。
那么答案如果段落变多，那么我们会希望拼接的时候两端都是 \(0\) 或都是 \(1\)。但显然这个是可控的，钦定第一段的右端点为 \(1\)，第二段的左端点完全可以通过反置和重排列变为 \(1\)，而后面也是一样的。
所以说，拼接对我们来说毫无影响，我们只需累加每一段的答案即可。
至于如何检查段落内是否同时包含 \(0\) 和 \(1\)，这可以用前缀和实现，因为我们完全可以做到枚举每一段的左端点，复杂度是调和级数。
时间复杂度：\(O(n \log n)\)
对应AC代码
void solve() {
int n;
cin >> n;
string s;
cin >> s;
s = " " + s;
vector<int> pre(n + 1);
for(int i=1;i<=n;i++) pre[i] = pre[i - 1] + (s[i] - '0');
int ans = 0;
for(int k=1;k<=n;k++) {
int now = 1;
for(int l=1;l<=n;l+=k) {
if(pre[min(n, l + k - 1)] - pre[l - 1] == 0 || pre[min(n, l + k - 1)] - pre[l - 1] == min(n, l + k - 1) - l + 1) continue;
now ++;
}
ans ^= now;
}
cout << ans << '\n';
}差点以为复杂度是平方（
E. 小L的井字棋
题意
给定一个井字棋残局，约定残局合法且双方落子数量相同，在残局基础上，先手当前可以连下两个棋，然后继续正常比赛。在两人足够聪明的条件下，判断先手是否有必胜策略。
思路
首先我们无法找出一个通用的解法，比较无脑的是写搜索，但是没必要。
我们对落子数量进行分讨：
数量为 \(0\)，此时下在中央和任意位置，先手必胜，可以手动模拟验证先手的必胜策略。
数量为 \(2\)，此时先手的棋子只有一条线被封锁，任选一条没被封锁的线填满即可，先手必胜。
数量为 \(4\)，此时先手的棋子最多只有一个被完全封锁，任选一条没被封锁的线填满即可，先手必胜。
而剩下的我们只需暴力填充，因为要么先手只能填入一个，要么后手只能填入一个。
时间复杂度：\(O(能过)\)
对应AC代码
void solve() {
vector<string> s(3);
for(auto &it : s) cin >> it;
vector<vector<pii>> ls = {
{{0, 0}, {1, 0}, {2, 0}},
{{0, 1}, {1, 1}, {2, 1}},
{{0, 2}, {1, 2}, {2, 2}},
{{0, 0}, {0, 1}, {0, 2}},
{{1, 0}, {1, 1}, {1, 2}},
{{2, 0}, {2, 1}, {2, 2}},
{{0, 0}, {1, 1}, {2, 2}},
{{0, 2}, {1, 1}, {2, 0}}
};
int cnt = 0;
for(auto &it : s) cnt += count(it.begin(), it.end(), 'G');
cnt = 9 - cnt;
if(cnt <= 4) {
cout << "Yes\n";
return;
}
for(int i1=0;i1<3;i1++) {
for(int j1=0;j1<3;j1++) {
if(s[i1][j1] != 'G') continue;
for(int i2=0;i2<3;i2++) {
for(int j2=0;j2<3;j2++) {
if(s[i2][j2] != 'G') continue;
auto ss = s;
ss[i1][j1] = ss[i2][j2] = 'X';
bool ok = false;
for(auto &l : ls) {
bool now = true;
for(auto &[x, y] : l) {
if(ss[x][y] != 'X') now = false;
}
ok |= now;
}
if(ok) {
cout << "Yes\n";
return;
}
}
}
}
}
cout << "No\n";
}如果去找规律这题就完蛋了（x
F. 小L的抽卡
待补充
G. 小L的三元组
待补充
H. 小L的min-max问题
题意
给定一个长为 \(n\) 的数组，将其切成 \(k\) 段，切法的权值为所有段落最小值与最大值之积的总和。输出所有切法的权值总和。
思路
首先，我们可以单独计算每一段的权值，并计算这一段会出现多少次，相乘累加即可得到题目所求。
因而我们只需考虑每一段会出现多少次。假设本段左边有 \(x\) 个元素，右侧有 \(y\) 个元素，那么我们可以枚举左边分割为 \(i\) 段，右侧即为 \(k - 1 - i\) 段。
将 \(n\) 个元素分成 \(m\) 段，且每段内至少有一个元素，这相当于在 \(n\) 个元素之间插板，也就是 \(n - 1\) 个空隙中选择 \(m - 1\) 个，用组合数表示即为：
\(\displaystyle \binom{n - 1}{m - 1}\)
那么如果 \(x = 0\) 或 \(y = 0\)，用这个组合数即可得到答案，否则我们可以将出现次数表示为：
\(\displaystyle \sum_{i=1}^{k-2} \binom{x - 1}{i - 1} \binom{y - 1}{k - i - 2}\)
我们稍微变一下式子，将 \(i - 1\) 整体替换：
\(\displaystyle \sum_{i=0}^{k-3} \binom{x - 1}{i} \binom{y - 1}{k - 3 - i}\)
这是经典的范德蒙德卷积，我们可以直接得出答案：
\(\displaystyle \sum_{i=0}^{k-3} \binom{x - 1}{i} \binom{y - 1}{k - 3 - i} = \binom{x + y - 2}{k - 3}\)
至于权值，在遍历的时候顺便更新区间最小最大即可，不过用 ST 表自然也是可以的。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
constexpr int P = 998244353;
using Z = MInt<P>;
//线性求阶乘，逆元，阶乘逆元
static void get_fact_inv(const int n, int fac[], int inv[], int fac_inv[], const int p = mod) {
fac[0] = fac_inv[0] = inv[0] = fac[1] = fac_inv[1] = inv[1] = 1;
for (int i = 2; i <= n; i++) {
fac[i] = fac[i - 1] * i % p;
inv[i] = (p - p / i * inv[p % i] % p) % p; //线性求逆元
fac_inv[i] = fac_inv[i - 1] * inv[i] % p;
}
}
int fac[N], inv[N], fac_inv[N];
void init() {
get_fact_inv(1e4, fac, inv, fac_inv);
}
Z C(int n, int m) {
if(n < m) return {0};
return Z{fac[n]} * fac_inv[m] * fac_inv[n - m];
}
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
Z ans = 0;
for(int l=1;l<=n;l++) {
int mx = -inf, mn = inf;
for(int r=l;r<=n;r++) {
if(n - (r - l + 1) < k - 1) break;
mx = max(mx, a[r]);
mn = min(mn, a[r]);
Z now = 1;
if(l > 1 && r < n) now = C(l - 1 + n - r - 2, k - 3);
if(l == 1 && r < n) now = C(n - r - 1, k - 2);
if(l > 1 && r == n) now = C(l - 2, k - 2);
ans += now * mx * mn;
}
}
cout << ans << '\n';
}怎么感觉老是能在牛客看到范德蒙德卷积
I. 小L的数学题
题意
给定两个整数 \(n, m\)，定义一次操作为下面二者任选其一：
将数字乘 \(2\)；
将数字开平方根后下取整
判断能否经过任意次操作，将 \(n\) 变为 \(m\)。
思路
我们先处理 \(0\) 的情况，因为正整数不可能开平方根到 \(0\)，所以如果两者其一为 \(0\)，其一非 \(0\)，就是无解。而显然相等有解。
接下来考虑正整数之间的变化。首先任何正整数经过有限次开平方根操作后都会变成 \(1\)，我们来考虑怎么从 \(1\) 通过上述操作到达任意数字。
首先，显然存在 \(x, k\)，满足 \(k^{2^j} \leq x < (k + 1)^{2^j}\)，那么我们可以通过开 \(j\) 次平方根从 \(x\) 变成 \(k\)。
我们将式子两边取以 \(2\) 为底的对数，有 \(2^j \log_2 k \leq \log_2 x < 2^j \log_2 (k + 1)\)。
我们将左右两端点作差，得到 \(2^j \log_2 \frac{k + 1}{k}\)，显然只要 \(j\) 足够大，结果就会大于等于 \(1\)。所以一定存在整数 \(p\) 满足 \(2^j \log_2 k \leq p < 2^j \log_2 (k + 1)\)。回到原式，可得 \(k^{2^j} \leq 2^p < (k + 1)^{2^j}\)。
所以我们只需将 \(n\) 先开平方根到 \(1\)，然后一定可以找出整数 \(p, j\) 满足 \(2^j \log_2 m \leq p < 2^j \log_2 (m + 1)\)，乘 \(p\) 次 \(2\) 之后，开 \(j\) 次平方根得到 \(m\)。
所以当且仅当两者其一为 \(0\)，其一非 \(0\)，就是无解。否则一定有解。
时间复杂度：\(O(1)\)
对应AC代码
void solve() {
int n, m;
cin >> n >> m;
cout << ((n != m && (n == 0 || m == 0)) ? "No\n" : "Yes\n");
}证明参考了出题人题解
J. 小L的汽车行驶问题
题意
给定一个整数 \(n\)，在 \(n\) 秒内，每秒的时刻初可以进行三种操作：
踩油门，速度瞬间增大 \(10\)；
踩刹车，速度瞬间降低 \(5\)；
踩离合，当前时刻速度降低 \(10\)，时刻末恢复原速度
在速度不低于 \(0\) 的前提下，给定每秒的操作，计算位移。
思路
模拟即可。
时间复杂度：\(O(n)\)
对应AC代码
void solve() {
int n;
cin >> n;
string s;
cin >> s;
int ans = 0, v = 0;
for(auto &it : s) {
if(it == '0') {
v += 10;
ans += v;
}else if(it == '1') {
v = max(0ll, v - 5);
ans += v;
}else {
ans += max(0ll, v - 10);
}
}
cout << ans << '\n';
}好直白
K. 小L的几何
待补充
L. 小L的构造
题意
给定一个整数 \(n\)，在每个数最多可以使用一次的情况下，输出最多能构造的三元组 \((x, y, z)\) 数量，满足刚好有两对数互质。
思路
首先，注意到存在下面的周期为 \(6\) 的构造方案：
\((i, i + 1, i + 3), (i + 2, i + 4, i + 5)\)
因为周期为偶数，所以奇偶性不变，而由于偶数一定不互质，所以 \((i + 1, i + 3)\) 不互质。
其次，相邻数一定互质，所以 \((i, i + 1), (i + 4, i + 5)\) 互质。
接着，相邻奇数一定互质，因为最小的奇质数大于 \(2\)，所以 \((i + 2, i + 4)\) 互质。
然后，根据辗转相除法可知，两个数的最大公因数如果不是其中的某个数，就一定小于两个数的差的绝对值。而由于 \(i\) 和 \(i + 3\) 相差为 \(3\)，且 \(i\) 模 \(6\) 为 \(1\)，所以两者的最大公因数只能小于 \(3\)，即 \(2\) 或互质。由于 \(i\) 为奇数，所以不可能出现偶数因子，所以 \((i, i + 3)\) 互质。同理可得 \((i + 2, i + 5)\) 不互质，因为 \(i + 2\) 为 \(3\) 的倍数。
但是当 \(n \bmod 6 \geq 3\) 时，可能存在漏解。我们考虑构造 \(n = 9\) 的情况，如下：
\((1, 2, 4), (3, 5, 9), (6, 7, 8)\)
因为为固定数字，可以通过注意力得出正确性。
而后续的方案需要换成下面的样子（不唯一）：
\((i, i + 1, i + 4), (i + 2, i + 3, i + 5)\)
通过类似的方法可以证明正确性。
时间复杂度：\(O(n)\)
对应AC代码
void solve() {
int n;
cin >> n;
if(n <= 3) {
cout << 0 << '\n';
return;
}
if(n <= 5) {
cout << 1 << '\n' << 2 << ' ' << 3 << ' ' << 4 << '\n';
return;
}
cout << n / 3 << '\n';
int i = 1;
if(n % 6 >= 3) {
cout << i << ' ' << i + 1 << ' ' << i + 3 << '\n';
cout << i + 2 << ' ' << i + 4 << ' ' << i + 8 << '\n';
cout << i + 5 << ' ' << i + 6 << ' ' << i + 7 << '\n';
i += 9;
for(;i+5<=n;i+=6) {
cout << i << ' ' << i + 1 << ' ' << i + 4 << '\n';
cout << i + 2 << ' ' << i + 3 << ' ' << i + 5 << '\n';
}
}else {
for(;i+5<=n;i+=6) {
cout << i << ' ' << i + 1 << ' ' << i + 3 << '\n';
cout << i + 2 << ' ' << i + 4 << ' ' << i + 5 << '\n';
}
}
}全是注意力