Solved 9 of 13.退役老登来凑个热闹
A. 一起奏响历史之音！
题意
给定 \(7\) 个数，判断是否由 \(1, 2, 3, 5, 6\) 组成。
思路
如题，模拟即可。
时间复杂度：\(O(n)\)
对应AC代码
void solve() {
int n = 7;
bool ok = true;
while(n --) {
int x;
cin >> x;
if(x == 4 || x == 7) ok = false;
}
cout << (ok ? "YES" : "NO") << '\n';
}主打一个手速
B. 能去你家蹭口饭吃吗
题意
给定长为 \(n\) 的序列 \(a\)。记 \(x\) 小于序列 \(a\) 中至少 \(\lfloor \frac{n}{2} \rfloor + 1\) 个数字，求 \(x\) 的最大值。
思路
只需小于序列 \(a\) 中的第 \(\lfloor \frac{n}{2} \rfloor + 1\) 大即可。
记序列 \(a\) 中的第 \(\lfloor \frac{n}{2} \rfloor + 1\) 大的下标为 \(p\)，则答案为 \(a_p - 1\)。
时间复杂度：\(O(nm)\)
对应AC代码
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
sort(a.begin(), a.end());
cout << a[n / 2 + 1] - 1 << '\n';
}简单排个序
C. 字符串外串
题意
对于一个字符串，定义其可爱度为满足 至少存在一个长为 \(k\) 的连续子串 \(a\) 和一个长为 \(k\) 的非连续子序列（非空）\(b\)、且 \(a=b\) 的 \(k\) 的最大值。
给定两个整数 \(n, m\)，构造一个长为 \(n\) 且可爱度为 \(m\) 的小写字母字符串。
思路
首先我们来考虑一下如何求一个字符串的可爱度，这同时也是 \(D\) 题要完成的任务。
举例来说，有这样一个字符串 \(abacbac\)，钦定其为 \(s\)。第一眼想到的可能是这种取法：\(a=s_1s_2s_3s_4, b=s_1s_5s_6s_7\)。此时我们有一个有趣的发现：\(b\) 中的 \(s_5\) 完全可以替换为 \(a\) 中的 \(s_2\)，同时 \(b\) 中的 \(s_6\) 也可以替换为 \(a\) 中的 \(s_3\)，做完这些后，\(a\) 与 \(b\) 只有最后一个字符不在同一位置。
更复杂的字符串也是一样的，因为 \(a\) 和 \(b\) 都是按照同样的顺序从字符串取出的。
所以我们有一个很明显的贪心思路：假设 \(a\) 和 \(b\) 的最后一个字符为 \(x\)，那么从右往左取第一个 \(x\) 作为 \(b\) 的最后一个字符，第二个 \(x\) 作为 \(a\) 的最后一个字符，并将第二个 \(x\) 左侧的所有字符拼接在 \(a, b\) 前面。
同时我们需要翻转一下字符串，求出反向的最大值，最后两者取最大值即可求出可爱度。
现在我们回过头来看看 \(C\) 题。
让我们先从左往右看。首先，作为最后一个不同的字符 \(x\)，其出现次数至少为 \(2\)，且可爱度应该取倒数第二个 \(x\) 出现的位置。
那么无论以哪种字符结尾，其倒数第二个字符的下标需满足 \(p \leq m\)。换句话说，我们希望构造出的字符串应该类似于下面的样子：
\(...x...x\)，最后两个 \(x\) 之间既不包含 \(x\)，也没有重复出现的字符。
最简单的构造自然是 \(xx \ldots x ?? \ldots ?x\)，可惜从右往左看时，可爱度过大了。所以我们需要一个对称的或者有周期性的构造。
不妨考虑周期性的构造。如果要满足上面的条件，那么周期至少为 \(n - m\)，否则两个 \(x\) 间会出现重复的字符。
那么我们只需在 \(a \sim z\) 中取出 \(n - m\) 个字符，然后一直重复即可。
如上，当 \(n < m + 1\) 或者 \(n > m + 26\) 时，判定无解，否则不难证明构造的正确性。
时间复杂度：\(O(n)\)
对应AC代码
void solve() {
int n, m;
cin >> n >> m;
if(n < m + 1 || n > m + 26) {
cout << "NO\n";
return;
}
cout << "YES\n";
for(int i=0;i<n;i++) {
cout << (char)('a' + i % (n - m));
}
cout << '\n';
}没对上脑电波
D. 字符串里串
题意
在 \(C\) 题的定义下，给定字符串，求可爱度。
思路
详见 \(C\) 题题解。
需要注意的是，这种做法可能会出现 \(b\) 包含空串的情况，比如说 \(aba\)。此时需要特判一下。
时间复杂度：\(O(n)\)
对应AC代码
void solve() {
int n;
cin >> n;
string s;
cin >> s;
s = " " + s;
vector<vector<int>> idx(26);
for(int i=1;i<=n;i++) {
idx[s[i] - 'a'].pb(i);
}
int ans = 0;
for(auto &vec : idx) {
if(vec.size() <= 1) continue;
if(vec[1] != n) ans = max(ans, n - vec[1] + 1);
if(vec[vec.size() - 2] != 1) ans = max(ans, vec[vec.size() - 2]);
}
cout << ans << '\n';
}观察可得
E. 一起走很长的路！
题意
给定一个长为 \(n\) 的序列 \(a\)，对于一个区间 \([l, r]\)，若对于所有 \(i \in [l, r)\)，均有 \(a_l + a_{l + 1} + \ldots + a_i \geq a_{i + 1}\)，则该区间为完美的。
给定 \(q\) 次独立询问，每次询问给定一个区间 \([l, r]\)，定义一次操作为选定一个元素并将其 \(+1\) 或 \(-1\)，确定使得区间完美需要的最小操作数。
思路
首先，我们只需增大 \(a_l\) 即可，因为增大 \(a_l\) 会影响到后面所有的条件。
那么我们只需求出 \(\max(a_{i + 1} - (a_l + a_{l + 1} + \ldots + a_i))\)，并对 \(0\) 取 \(\max\) 即可。
考虑前缀和，我们只需求出 \(\max_{i \in [l+1,r]}(a_i - pre_i) + pre_l\)，然后对 \(0\) 取 \(\max\)。
因为不存在修改，所以简单的 ST 表即可解决。
时间复杂度：\(O(n \log n)\)
对应AC代码
template<class Info>
struct SparseTable {
int n;
vector<vector<Info>> info;
vector<int> lg;
SparseTable() : n(0) {}
void initLg() {
lg = vector<int>(n + 1, -1);
for(int i=1;i<=n;i++) lg[i] = lg[i / 2] + 1;
}
explicit SparseTable(int _n, vector<Info> _info) : n(_n) {
initLg();
info = vector<vector<Info>>(n + 1, vector<Info>(lg[n] + 1));
for(int i=1;i<=n;i++) info[i][0] = _info[i];
for(int i=1;i<=lg[n];i++){
for(int j=1;j+(1ll<<(i-1))<=n;j++){
info[j][i] = info[j][i - 1] + info[j + (1ll << (i - 1))][i - 1];
}
}
}
Info rangeQuery(int l, int r) {
int len = lg[r - l + 1];
return info[l][len] + info[r - (1ll << len) + 1][len];
}
};
struct Info{
int val = 0;
};
Info operator+(const Info &a, const Info &b) {
Info c;
c.val = max(a.val, b.val); //RMQ
return c;
}
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
vector<int> pre(n + 1);
vector<Info> info(n + 1);
pre[1] = a[1];
info[1].val = -inf;
for(int i=2;i<=n;i++) {
info[i].val = a[i] - pre[i - 1];
pre[i] = pre[i - 1] + a[i];
}
SparseTable<Info> st(n + 1, info);
while(q --) {
int l, r;
cin >> l >> r;
if(l == r) {
cout << 0 << '\n';
continue;
}
cout << max(0ll, st.rangeQuery(l + 1, r).val + pre[l - 1]) << '\n';
}
}如果反着减可能就懵逼了（
F. 一起找神秘的数！
题意
给定区间 \([l,r]\)，求满足 \(l \leq x,y \leq r\) 以及 \(x+y = (x~\text{or}~y) + (x~\text{and}~y) + (x~\text{xor}~y)\) 的二元组 \((x, y)\) 数量。
思路
首先，显然可以发现当 \(x=y\) 时等式成立，不妨大胆猜想，大胆乱交，小心求证。
我们不妨按位考虑，先无视异或，可以得到下面的真值表：
| \(x\) | \(y\) | \(x~\text{or}~y\) | \(x~\text{and}~y\) | \((x~\text{or}~y) + (x~\text{and}~y)\) | \(x+y\) |
|---|---|---|---|---|---|
| \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) | \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) | \(0\) | \(1\) | \(1\) |
| \(1\) | \(1\) | \(1\) | \(1\) | \(2\) | \(2\) |
可以发现，\(x + y = (x~\text{or}~y) + (x~\text{and}~y)\)，换句话说，\((x~\text{xor}~y) = 0\)。从而得到 \(x = y\)，证明了我们的猜想。
那么答案就是区间内数字的个数，也就是 \(r - l + 1\)。
时间复杂度：\(O(n \log n)\)
对应AC代码
void solve() {
int l, r;
cin >> l >> r;
cout << r - l + 1 << '\n';
}乱猜就完事了！（
G. 一起铸最好的剑！
题意
给定两个整数 \(n, m\)，求出使得 \(|m ^ k - n|\) 最小的 \(k\) 的值。
思路
暴力，打到第一次超过 \(n\) 时即可，特判 \(m = 1\)。
时间复杂度：\(O(\log_mn)\)
对应AC代码
void solve() {
int n, m;
cin >> n >> m;
long long x = m;
pair<long long, int> ans = {abs(x - n), 1};
if(m != 1) {
for(int i=2;x<n;i++) {
x *= m;
ans = min(ans, {abs(x - n), i});
}
}
cout << ans.second << '\n';
}人均挂一发（
H. 一起画很大的圆！
题意
给定四个整数 \(a, b, c, d\)，分别代表直线 \(x = a, x = b, y = c, y = d\)，且满足 \(a \leq b, c \leq d\)。
在直线所围得的矩形的边上取三个不同的整点，使得外接圆面积最大，并给出方案。
思路
不妨从曲率的角度考虑，如果三点共线的话，那么面积将为无穷大，所以我们只需让三点尽可能贴近一条直线。
同时，由正弦定理可知，外接圆半径和边长也有关系，所以我们考虑让斜边尽可能长。
于是我们只需用类似于样例的方法，先取长边的一端作为点 \(A\)，然后在长边上取离 \(A\) 最近的点 \(B\)，最后取在短边且距离长边另一端最近的点 \(C\)，即可得到最大面积。
时间复杂度：\(O(1)\)
对应AC代码
void solve() {
int a, b, c, d;
cin >> a >> b >> c >> d;
if (b - a <= d - c) {
cout << a << ' ' << c << '\n';
cout << a << ' ' << c + 1 << '\n';
cout << a + 1 << ' ' << d << '\n';
} else {
cout << a << ' ' << d << '\n';
cout << a + 1 << ' ' << d << '\n';
cout << b << ' ' << d - 1 << '\n';
}
}差点取对角线去了，显然不如这种方案来的共线
I. 一起看很美的日落！
待补充
J. 数据时间？
待补充
K. 可以分开吗？
题意
给定一个 \(n \times m\) 的 \(01\) 矩阵，若两个格子有至少一条公共边，则视为在同一连通块中。当连通块中全为 \(1\) 时，该连通块将掉落。
定义一次操作为将矩阵中的 \(0\) 抹除，输出使得至少一块连通块掉落需要的最小操作数。
思路
不妨考虑使用并查集维护所有全 \(1\) 连通块，从而快速确定每个为 \(1\) 的格子属于哪个连通块。
然后我们只需求出每个连通块需要多少次操作使其能掉落，然后取最小值即可。
不妨枚举所有为 \(0\) 的格子，并判断与其相邻的最多 \(4\) 个为 \(1\) 的格子各属于哪个连通块，并得到一个连通块的不可重集合，然后给集合中的每个连通块的答案累加 \(1\) 即可。
时间复杂度：\(O(nm)\)
对应AC代码
struct DSU {
vector<int> pa, siz;
void init(int n) { pa = vector<int>(n + 1), siz = vector<int>(n + 1, 1), iota(all(pa), 0); }
int find(int x) { while(x != pa[x]) x = pa[x] = pa[pa[x]]; return x; }
bool unite(int u, int v) {
int f1 = find(u), f2 = find(v);
if (f1 == f2) return false;
siz[f1] += siz[f2];
pa[f2] = f1;
return true;
}
int size(int x){ return siz[find(x)]; }
}dsu;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n + 1, vector<int>(m + 1));
for(int i=1;i<=n;i++) {
string s;
cin >> s;
for(int j=1;j<=m;j++) a[i][j] = s[j - 1] - '0';
}
auto p = [&](int x, int y) { return (x - 1) * m + y; };
dsu.init(n * m);
for(int x=1;x<=n;x++) {
for(int y=1;y<=m;y++) {
if(a[x][y] == 0) continue;
for(auto [dx, dy] : {pii{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
int tx = x + dx, ty = y + dy;
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && a[tx][ty] == 1) {
dsu.unite(p(x, y), p(tx, ty));
}
}
}
}
vector<int> cnt(n * m + 1);
for(int x=1;x<=n;x++) {
for(int y=1;y<=m;y++) {
if(a[x][y] == 1) continue;
set<int> adj;
for(auto [dx, dy] : {pii{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
int tx = x + dx, ty = y + dy;
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && a[tx][ty] == 1) {
adj.ep(dsu.find(p(tx, ty)));
}
}
for(auto &it : adj) cnt[it] ++;
}
}
int ans = inf;
for(int i=1;i<=n*m;i++) {
if(cnt[i] == 0) continue;
ans = min(ans, cnt[i]);
}
if(ans == inf) cout << 0 << '\n'; // 全是蓝的
else cout << ans << '\n';
}写搜索好像有点麻烦（
L. 还会再见吗？
待补充
M. 那是我们的影子
待补充