AtCoder Beginner Contest 360
A - A Healthy Breakfast (abc360 A)
题目大意
给定一个字符串包含RMS，问R是否在S的左边。
解题思路
比较R和S的下标，谁小即谁在左边。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
cout << (s.find('R') < s.find('M') ? "Yes" : "No") << '\n';
return 0;
}
B - Vertical Reading (abc360 B)
题目大意
给定两个字符串\(s,t\)，找到一个 \(1 \leq c \leq w < |s|\)，使得将 \(s\)拆开，每个子串有\(w\)个字母， 对每个子串取第\(c\)位字母出来（不存在则不取），使其组成 \(t\)。
解题思路
由于\(|s| \leq 100\)，直接花 \(O(|s|^2)\)枚举 \(c,w\)，然后拆开子串、拼接、比较即可。时间复杂度是 \(O(n^3)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s, t;
cin >> s >> t;
bool ok = false;
for (int i = 1; i < s.size(); i++) {
vector<string> sub;
for (int j = 0; j < s.size(); j += i) {
sub.push_back(s.substr(j, i));
}
for (int j = 0; j < i; ++j) {
string ans;
for (auto& x : sub) {
if (j < x.size())
ans += x[j];
}
if (ans == t) {
ok = true;
}
}
}
if (ok)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
C - Move It (abc360 C)
题目大意
给定 \(n\)个箱子。再给定\(n\)个球所在的箱子位置，球有重量。
移动球到其他箱子里，代价是球的重量。
求最小的代价，使得每个箱子各有一个球。
解题思路
对于一个有多个球的盒子，因为最终会有一个球留在盒子里，为了最小代价，那最重的球不移动，而移动其他的球。
因此最终的代价就是每个盒子除最重球的球重量的和。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<vector<int>> box(n);
vector<int> pos(n);
for (auto& i : pos)
cin >> i;
for (int i = 0; i < n; ++i) {
int w;
cin >> w;
box[pos[i] - 1].push_back(w);
}
int ans = 0;
for (auto& i : box) {
if (i.empty())
continue;
sort(i.begin(), i.end(), greater<int>());
ans += accumulate(i.begin(), i.end(), 0) - i[0];
}
cout << ans << '\n';
return 0;
}
D - Ghost Ants (abc360 D)
题目大意
一维数轴，蚂蚁移动，有方向，速度一样。碰撞时不改变方向，继续保持原方向行走。
经过\(t\)时刻后，问碰撞的蚂蚁对数。
解题思路
同方向的蚂蚁不会碰撞，因此仅考虑不同向的。
考虑往右的蚂蚁会与哪些往左的蚂蚁碰撞。
由于所有蚂蚁速度一样，因此由相向运动得知，假设当前往右的蚂蚁位置为\(x\)，那么所有往左的位于\([x, x + 2t]\)的蚂蚁都会与其相撞。
根据蚂蚁前进方向对坐标排序，二分一下就能找到往左的位于 \([x, x + 2t]\)的蚂蚁数量。
所有数量累加即为答案。时间复杂度是 \(O(n \log n)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, t;
string dir;
cin >> n >> t >> dir;
array<vector<int>, 2> pos;
for (int i = 0; i < n; ++i) {
int p;
cin >> p;
pos[dir[i] - '0'].push_back(p);
}
for (auto& x : pos)
sort(x.begin(), x.end());
LL ans = 0;
for (int i = 1; i < 2; ++i) {
auto& cur = pos[i];
auto& nxt = pos[i ^ 1];
for (auto x : cur) {
LL l = x;
LL r = x + t * (i == 1 ? 1 : -1) * 2ll;
if (l > r)
swap(l, r);
auto ll = lower_bound(nxt.begin(), nxt.end(), l);
auto rr = upper_bound(nxt.begin(), nxt.end(), r);
ans += rr - ll;
}
}
cout << ans << '\n';
return 0;
}
E - Random Swaps of Balls (abc360 E)
题目大意
\(n\)个球，其中第一个是黑球，其余是白球。
进行以下操作 \(k\)次：
- 随机两次独立选取 \(i,j\)，交换第 \(i\)个球和第 \(j\)个球。
问黑球位置的期望值。
解题思路
假设最终黑球位于第\(i\)个球的概率是\(p_i\)，根据期望定义，答案就是 \(\sum_{i=1}^{n} i p_i\)。考虑如何求\(p_i\)。
容易发现第 \(2,3,...,n\)个球没有本质区别，其概率都是一样的，因此最终我们需要求的就两个数
- \(p_1\)即位于第一个球的概率
- \(p_2\)即位于非第一个球的概率
容易发现经过第\(k\)次操作的概率，仅依赖于第 \(k-1\)次的情况，因此可以迭代球，即设 \(dp[k][0/1]\)表示经过 \(k\)次操作后，球位于第一个球/不位于第一个球的概率。
转移就考虑本次操作是否将球移动到第一个球或非第一个球。设移动概率\(move = 2\frac{1}{n}\frac{n-1}{n}\)，不移动概率\(stay = 1 - move\)，移动到某一个位置的概率为 \(move1 = \frac{move}{n-1} = \frac{2}{n^2}\)
\(dp[i][0] = dp[i - 1][0] \times stay + dp[i - 1][1] \times move1\)，不动或者从非一球移动到一球。
\(dp[i][1] = dp[i - 1][0] \times move + dp[i - 1][1] \times (1 - move1)\)，从一球移动或者从非一球移动到非移动（全概率-移动到一球的概率）
最后\(p_1 = dp[k][0],p_2 = p_3 = ... = p_n = \frac{dp[k][1]}{n-1}\)，答案就是\(\sum_{i=1}^{n} i p_i = dp[k][0] + \frac{(n+2)(n-1)}{2} \frac{dp[k][1]}{n-1}\)。
时间复杂度为\(O(k)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
long long qpower(long long a, long long b) {
long long qwq = 1;
while (b) {
if (b & 1)
qwq = qwq * a % mo;
a = a * a % mo;
b >>= 1;
}
return qwq;
}
long long inv(long long x) { return qpower(x, mo - 2); }
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
int invn = inv(n);
int invn1 = inv(n - 1);
int move = 2ll * invn * (n - 1) % mo * invn % mo;
int stay = (1ll - move + mo) % mo;
int move1 = 1ll * move * invn1 % mo;
array<int, 2> dp{};
dp[0] = 1;
for (int i = 0; i < k; i++) {
array<int, 2> dp2{};
dp2[0] = (1ll * dp[0] * stay % mo + 1ll * dp[1] * move1 % mo) % mo;
dp2[1] = (1ll * dp[0] * move % mo +
1ll * dp[1] * ((1 - move1 + mo) % mo) % mo) %
mo;
dp.swap(dp2);
}
int ans =
(dp[0] + 1ll * (n + 2) * (n - 1) / 2 % mo * dp[1] % mo * invn1 % mo) %
mo;
cout << ans << '\n';
return 0;
}
F - InterSections (abc360 F)
题目大意
给定\(n\)个区间，若俩区间\([l_a, r_a],[l_b,r_b]\)有交叉 ，则有\(l_a < l_b < r_a < r_b\)。
设 \(f(l,r)\)表示与 \([l,r]\)有交叉的区间数。
求最大值。
解题思路
<++>
神奇的代码
G - Suitable Edit for LIS (abc360 G)
题目大意
给定一个数组，进行一次操作，使得最长上升子序列的长度最大。
操作为，将任意一个数改为任意一个数。
解题思路
这种有一次修改的，可以从修改处考虑，其修改处左右两边是一个正常的最长上升子序列问题。
因此事先求出\(pre[i]\)表示从左到右，选了第 \(i\)个数字的最长上升子序列长度，\(suf[i]\)表示从右到左，选了第 \(i\)个数字的最长下降子序列长度，需要使用\(O(n\log n)\)的方法。考虑如何将 \(pre\)和 \(suf\)组合。
注意到是严格上升，如果枚举 \(suf_i\)，思考 \(\max(pre_j + suf_i + 1)\)有什么条件，以及 \(j\)如何找。
枚举 \(i\)，考虑 \(j\)，则有 \(k \in (j, i), a_k\)需要修改，因此 \(j < i - 1\)，同时由于严格递增， \(a_i > a_j + 1\) ，这样\(a_k\)才能更改成对应的数，使得 \(pre_j\)和 \(suf_i\)拼接起来得到一个更长的最长上升子序列。
即需要解决这么一个问题\(\max_{j < i - 1 \& a_i > a_j + 1} (pre_j + suf_i + 1)\)。容易发现这就是一个朴素的二维偏序问题，用线段树求解即可。注意需要对\(a_i\)离散化。
\(O(n \log n)\)的一种最长上升子序列的求法，即\(pos[i]\)表示最长上升子序列长度为 \(i\)的末尾数字（最大数字）的最小值。注意到 \(pos\)是一个递增的数组，因此对于当前数字\(a_i\) ，可以二分找到它可以接在哪个数字\(a_j\)的后面，进而知道了当前的\(dp[i]\)，然后更新 \(pos\)数组。或者朴素的 \(O(n^2)\)的 \(dp\)，分析转移式可以注意到也是一个二维偏序问题，也可以用线段树解决。
用线段树解二维偏序，下标是\(a_j\)，值是\(dp[j]\)。即当前\(dp[j]\)求出来后，将 \(dp[j - 1]\)插入到线段树里，即将 \(a_j\)位置的值赋予 \(dp[j]\)。
这样在求\(dp[i]\)时，线段树里的值都是 \(j < i - 1\)的 \(dp[j]\)的值，自然满足第一个 \(j < i - 1\)的条件，因为线段树的下标是 \(a_j\)，而 \(a_i > a_j + 1\)相当于一个区间 \([1, a_i - 2]\)，要求的就是这个区间的\(dp\)最大值，因为线段树维护的就是\(dp[j]\)，故区间查询最大值、单点修改即可。而由于\(a_i\)很大，为作为线段树的下标，需要离散化。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9 + 8;
const int N = 2e5 + 8;
class segment {
#define lson (root << 1)
#define rson (root << 1 | 1)
public:
int maxx[N << 2];
void build(int root, int l, int r) {
if (l == r) {
maxx[root] = 0;
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
maxx[root] = max(maxx[lson], maxx[rson]);
}
void update(int root, int l, int r, int pos, int val) {
if (l == r) {
maxx[root] = max(maxx[root], val);
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
update(lson, l, mid, pos, val);
else
update(rson, mid + 1, r, pos, val);
maxx[root] = max(maxx[lson], maxx[rson]);
}
LL query(int root, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return maxx[root];
}
int mid = (l + r) >> 1;
int resl = -inf, resr = -inf;
if (L <= mid)
resl = query(lson, l, mid, L, R);
if (R > mid)
resr = query(rson, mid + 1, r, L, R);
return max(resl, resr);
}
} sg;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a)
cin >> x;
auto solve = [&](vector<int>& a) -> vector<int> {
vector<int> dp(n, 1);
vector<int> pos(n + 1, inf);
pos[0] = -inf;
for (int i = 0; i < n; i++) {
auto it = lower_bound(pos.begin(), pos.end(), a[i]) - pos.begin();
dp[i] = it;
pos[it] = min(pos[it], a[i]);
}
return dp;
};
auto pre = solve(a);
reverse(a.begin(), a.end());
transform(a.begin(), a.end(), a.begin(), [](int x) { return -x; });
auto suf = solve(a);
reverse(suf.begin(), suf.end());
reverse(a.begin(), a.end());
transform(a.begin(), a.end(), a.begin(), [](int x) { return -x; });
vector<int> b(a.begin(), a.end());
b.push_back(-inf);
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
auto rank = [&](int x) {
return lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
};
int ans = 0;
int m = b.size();
sg.build(1, 1, m);
for (int i = 0; i < n; ++i) {
int cnt = sg.query(1, 1, m, 1, rank(a[i] - 1) - 1);
ans = max(ans, suf[i] + cnt + (i != 0));
if (i > 0)
sg.update(1, 1, m, rank(a[i - 1]), pre[i - 1]);
}
cout << ans << '\n';
return 0;
}