Solved 8 of 13.难度偏大场
A. 智乃的博弈游戏
题意
给定 \(n\) 个石子。对于两个人的博弈，每轮可拿走与当前石子个数互质数量的石子，剩余 \(1\) 个石子时玩家获胜。判断先手是否必胜。
思路
经典猜猜题，不过也是一个比较经典的博弈。
可以发现，\(1\) 和所有数都互质，那么我们从必胜态往后推。
首先，显然 \(1\) 为必胜态，\(2\) 因为可以拿走 \(1\) 个石子所以成为必败态。对于 \(3\) 来说，可以拿走 \(1\) 或 \(2\) 个石子，显然当拿走 \(1\) 个石子时可以达到必败态，所以 \(3\) 也是一个必胜态。
如上进行递推，可以归纳总结出：奇数时必胜，偶数时必败。
时间复杂度：\(O(1)\)
对应AC代码
void solve() {
int x;
cin >> x;
cout << (x % 2 == 0 ? "No" : "Yes") << '\n';
}主打一个手速
B. 能去你家蹭口饭吃吗
待补充
C. 智乃的Notepad(Easy version)
题意
给定 \(n\) 个字符串，定义一次操作为删除最后一个字符，或者添加任意一个字符。输出使得所有给定字符串都能在操作过程中出现至少一次需要的最小操作数。
思路
为了降低操作数量，我们需要尽可能避免相同的前缀被重复删除然后添加。最简单的方法是将字符串数组直接排序，这样可以让相同前缀的字符串靠在一起，然后我们只需模拟整个过程即可。
可是需要注意的是，我们最后不需要清空，而这就导致了最后留下来的字符串长度会对答案产生影响，就像样例所给那样。
可以发现的是，如果我们将相同前缀视为一个连通块，那么对于一个固定的前缀，其各个子连通块在操作中的顺序是可以任意调整的，这不影响前面第一段话所提到的结论。于是，通过一些交换，我们可以把长度最长的字符串换为最后留下来的字符串，从而最小化操作数。
因此答案即为 数组排序后包含清空操作的整个过程需要的操作数 \(-\) 最长字符串的长度。
结合字典树可以更好地理解上面的思考过程。当然这题也可以使用字典树实现，有点大材小用罢了。
时间复杂度：\(O(n \log n)\)
对应AC代码
void solve() {
int n, _;
cin >> n >> _;
vector<string> s(n);
for(auto &it : s) cin >> it;
sort(s.begin(), s.end());
cin >> _ >> _;
int ans = s[0].size() + s[n - 1].size();
for(int i=1;i<n;i++) {
int c = 0;
for(int j=0;j<min(s[i - 1].size(), s[i].size());j++) {
if(s[i - 1][j] == s[i][j]) c ++;
else break;
}
ans += s[i - 1].size() + s[i].size() - 2 * c;
}
int mx_len = 0;
for(auto &it : s) mx_len = max(mx_len, (int) it.size());
cout << ans - mx_len << '\n';
}本来还以为排个序就好了（
D. 智乃的Notepad(Hard version)
待补充
E. 智乃的小球
题意
给定水平光滑平面上的 \(n\) 个小球，每个小球具有一个初速度 \(1\) 或 \(-1\)，规定小球间的碰撞为弹性碰撞，即交换速度，输出第 \(k\) 次碰撞的时刻。
思路
首先，因为交换速度，我们可以无视碰撞，视为小球相互可以穿过，这样就可以把问题简化很多，变成了我们熟知的相遇问题。
可以发现，时间越早，相碰的小球数量也越少，反之亦然。也就是说，两者具有单调的关系，因而我们不妨考虑二分答案。
我们现在需要一种 \(n \log n\) 的复杂度来计算指定时刻及以前，有多少小球会相遇。因为速度大小是 \(1\)，所以我们可以把时间当作距离来看。
显然只有相向而行的小球才会相遇，所以我们可以将向左运动的小球的位置存下来，然后枚举每一个向右运动的小球，二分出指定距离以内的小球的个数，从而计算出答案。
时间复杂度：\(O(n \log^2 n)\)
对应AC代码
void solve() {
int n, k;
cin >> n >> k;
vector<pair<int, int>> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i].first >> a[i].second;
sort(a.begin() + 1, a.end());
vector<int> p, q;
for(int i=1;i<=n;i++) {
if(a[i].second == -1) {
p.emplace_back(i);
q.emplace_back(a[i].first);
}
}
bool ok = false;
auto check = [&](double x) -> bool {
int cnt = 0;
for(int i=1;i<=n;i++) {
if(a[i].second == -1) continue;
//(y-x)/2<=mid
//y<=mid*2+x
double dist = a[i].first + 2 * x;
auto it = upper_bound(p.begin(), p.end(), i);
if(it == p.end()) continue;
int L = it - p.begin();
int R = upper_bound(q.begin() + L, q.end(), dist) - q.begin();
cnt += R - L;
if(cnt > k) break;
}
return cnt >= k;
};
double l = 0, r = 1e18, mid;
for(int _=0;_<100;_++) {
mid = (l + r) / 2;
if(check(mid)) {
r = mid;
ok = true;
}else l = mid;
}
if(ok) cout << "Yes" << '\n' << fixed << setprecision(6) << r << '\n';
else cout << "No" << '\n';
}比较经典的题
F. 智乃的捉迷藏
题意
对于 \(6\) 个编号为 \(1 \sim 6\) 的位置，\(A\) 能看到 \(1, 2, 3\)，\(B\) 能看到 \(3, 4, 5\)，\(C\) 能看到 \(1, 6, 5\)。给定 \(n\) 个物品，将其任意放入 \(6\) 个位置中，判断是否能让 \(A, B, C\) 分别看到 \(a, b, c\) 个物品。
思路
首先，任意两个人都能看到一个相同的位置，而每个人都能看到一个其他人看不到的位置。所以我们可以将物品分摊到这个位置，从而连续地改变两个人看到的物品数量。
钦定 \(a \leq b \leq c\)，那么我们可以考虑将 \(a\) 和 \(b\) 分摊给 \(c\)，最后可以分摊出去 \(\min(a+b, c)\)，扣掉这些可得 \(a+b+c-\min(a+b,c)\)。
那么我们只需满足 \(a+b+c - \min(a+b, c) \leq n\) 即可。当 \(a + b = c\) 时，取到 \(a + b + c - \min(a+b, c)\) 的最小值 \(\frac{a +b + c}{2}\)，即 \(a + b + c \leq 2n\)。
而如果我们将物品放在只能被一个人看到的位置，就可以让 \(n\) 最大化，得到 \(n \leq a + b + c\)。
因而有 \(n \leq a + b + c \leq 2n\)，满足条件即可。
\(n\) 给的很小，也许暴力也行，但不如这样一行。
时间复杂度：\(O(1)\)
对应AC代码
void solve() {
int n, a, b, c;
cin >> n >> a >> b >> c;
cout << (n <= a + b + c && a + b + c <= 2 * n ? "Yes" : "No") << '\n';
}感觉 \(20\) 的 \(n\) 纯诈骗
G. 智乃与模数
题意
给定两个整数 \(n, k\)，遍历 \(j \in [1, n]\)，记 \(a_i\) 为由 \(n \bmod j\) 所形成的序列的第 \(i\) 大元素的值，求数组 \(a\) 的前 \(k\) 项和。
思路
根据取模的定义，\(x \bmod y = z\) 即 \(z = x - \lfloor \frac{x}{y} \rfloor \cdot y\)。我们要求 \(z\) 的前 \(k\) 大和，也就是要求 \(\lfloor \frac{x}{y} \rfloor \cdot y\) 的前 \(k\) 小和。
根据数论分块的知识，\(\lfloor \frac{x}{y} \rfloor\) 总共有根号种。当 \(\lfloor \frac{x}{y} \rfloor\) 一致时，\(y\) 的取值为一个连续的区间，那么 \(\lfloor \frac{x}{y} \rfloor \cdot y\) 构成一个等差数列。
不妨对第 \(k\) 小的值 \(V\) 进行二分。对于每一个 \(\lfloor \frac{x}{y} \rfloor\)，记 \(y\) 对应的区间为 \([l, r]\)，那么等差数列的首项 \(a_1 = \lfloor \frac{n}{l} \rfloor \cdot l\)，公差 \(d = \lfloor \frac{n}{l} \rfloor\)，通项公式为 \(a_1 + (p - 1) \cdot d\)。所以最后一项应该小于 \(V\)，化简不等式可得 \(\lfloor \frac{V - a_1}{d} \rfloor + 1\)，不过当然需要对 \(r - l + 1\) 取最小值。累加数量后即可完成二分的检查。
求出 \(V\) 后，我们用类似的思想，计算出小于 \(V\) 的 \(\lfloor \frac{x}{y} \rfloor \cdot y\) 的总和，最后再用若干个 \(p\) 补全个数即可。当然，答案需要用 \(kn\) 扣掉。
时间复杂度：\(O(\sqrt n \log n)\)
对应AC代码
void solve() {
int n, k;
cin >> n >> k;
auto check = [&](int x) -> bool {
int cnt = 0;
for(int l=1,r;l<=n;l=r+1) {
r = n / (n / l);
int a1 = n / l * l, d = n / l;
if(x - a1 < 0) continue;
cnt += min(r - l + 1, (x - a1) / d + 1);
}
return cnt >= k;
};
int L = 1, R = n, mid;
while(L < R) {
mid = (L + R) >> 1ll;
if(check(mid)) R = mid;
else L = mid + 1;
}
int ans = k * L;
for(int l=1,r;l<=n;l=r+1) {
r = n / (n / l);
int a1 = n / l * l, d = n / l;
if(L - a1 < 0) continue;
int p = (L - a1) / d;
ans -= (p + 1) * L;
ans += (a1 + a1 + p * d) * (p + 1) / 2;
}
cout << k * n - ans << '\n';
}做数学糕手
H. 智乃与黑白树
待补充
I. 智乃的兔子跳
待补充
J. 智乃画二叉树
待补充
K. 智乃的逆序数
题意
给定 \(n\) 个互不包含相同元素的序列，且假设序列的值域为 \([l, r]\)，则该序列为值域内 \(r - l + 1\) 个数字的排列。
将序列拼接在一起，在不打乱原本在同一序列的任意两个数字的相对顺序的条件下，任意打乱拼接后的序列，使得逆序对个数为给定的整数 \(k\)。
思路
因为值域不相交，所以如果我们按照值域将序列数组升序排序，拼接后的逆序对个数就是各个序列的逆序对个数总和。而最大即为按照规定完整排序后的结果。
逆序对和冒泡排序联系很大，而有趣的是本题的数据范围小到可以跑冒泡排序。因为降序的冒泡排序中，每交换一次就会使得逆序对个数增大 \(1\)，所以我们可以利用这一点，根据规则进行冒泡排序，从而将逆序对个数增大到 \(k\)。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
void solve() {
int n, k;
cin >> n >> k;
vector<vector<int>> a(n);
vector<pair<int, int>> b;
for(int i=0;i<n;i++) {
int l;
cin >> l;
a[i] = vector<int>(l);
for(int j=0;j<l;j++) {
cin >> a[i][j];
for(int p=0;p<l;p++) {
if(a[i][p] > a[i][j]) k --;
}
}
}
if(k < 0) {
cout << "No\n";
return;
}
sort(a.begin(), a.end(), [&](vector<int> &x, vector<int> &y) {
return x[0] < y[0];
});
for (int i=0;i<n;i++) {
for(auto &it : a[i]) b.emplace_back(it, i);
}
n = b.size();
for(int i=0;i<n;i++) {
for(int j=n-1;j>i;j--) {
if(b[j].second == b[j - 1].second) continue;
if(k > 0 && b[j - 1].first < b[j].first) {
swap(b[j], b[j - 1]);
k --;
}
}
}
if(k != 0) {
cout << "No\n";
return;
}
cout << "Yes\n";
for(int i=0;i<n;i++) cout << b[i].first << ' ';
cout << '\n';
}怎么感觉这题的过题率不该这么低（
L. 智乃的三角遍历
题意
给定一个整数 \(n\)，一笔画出 \(n\) 层正三角形组成的图形，输出方案。
思路
手玩一下可以发现很多解法，最易于书写的方法为先从顶点往左下角走，然后从左下角往右下角走，然后将最底下一层的斜边都走了，走到最左边时往右沿着横线走，走到最右边，然后重复上述步骤即可。
当然也可以打表或直接欧拉回路。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
void solve() {
int n;
cin >> n;
n ++;
vector<int> l(n + 1, 1), r(n + 1);
for(int i=1;i<=n;i++) {
l[i] = l[i - 1] + i - 1;
r[i] = l[i] + i - 1;
}
cout << "Yes\n";
for(int i=1;i<=n;i++) cout << l[i] << ' ';
for(int i=n;i>=2;i--) {
for(int j=l[i]+1;j<=r[i];j++) cout << j << ' ';
int now = r[i], p = -i;
while(now != l[i - 1]) {
now += p;
if(p == -i) p = i - 1;
else p = -i;
cout << now << ' ';
}
}
cout << '\n';
}大学生怎么能忍住不玩一下的（
M. 智乃的牛题
题意
给定一个长为 \(8\) 的字符串，判断是否可以任意调整顺序以组成 \(\mathtt{nowcoder}\)。
思路
根据题意模拟即可。
时间复杂度：\(O(n)\)
对应AC代码
void solve() {
string s;
cin >> s;
vector<int> cnt(26);
for(auto &it : s) cnt[it - 'a'] ++;
if (
cnt['c' - 'a'] == 1 &&
cnt['d' - 'a'] == 1 &&
cnt['e' - 'a'] == 1 &&
cnt['n' - 'a'] == 1 &&
cnt['o' - 'a'] == 2 &&
cnt['r' - 'a'] == 1 &&
cnt['w' - 'a'] == 1
) {
cout << "happy new year\n";
} else {
cout << "I AK IOI\n";
}
}IOI AK ME