CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
A - Jagged Swaps
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> n;
rep (i, 1, n) cin >> a[i];
while (true) {
bool f = 0;
rep (i, 2, n - 1) if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
swap(a[i], a[i + 1]);
f = 1;
}
if (!f) break;
}
bool f = 1;
rep (i, 1, n) if (i != a[i]) {
f = 0;
break;
}
cout << (f ? "YES\n" : "NO\n");
}
return 0;
}
B - AB Flipping
正反各来一次
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> n >> s + 1;
int ans = 0;
rep (i, 1, n) f[i] = 1;
per (i, n - 1, 1) {
if (s[i] == 'A' && s[i + 1] == 'B') {
++ans;
swap(s[i], s[i + 1]);
f[i] = 0;
}
}
rep (i, 1, n - 1) {
if (s[i] == 'A' && s[i + 1] == 'B' && f[i]) {
++ans;
swap(s[i], s[i + 1]);
f[i] = 0;
}
}
cout << ans << '\n';
}
return 0;
}
C - Matching Arrays
每次以贪心地增加/减少匹配项
const int N = 2e5 + 5;
int n, m, _, k, cas;
int a[N], b[N], c[N], d[N];
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> n >> m;
rep (i, 1, n) cin >> a[i], c[i] = i;
rep (i, 1, n) cin >> b[i];
sort(c + 1, c + 1 + n, [&](int x, int y) { return a[x] < a[y]; });
sort(b + 1, b + 1 + n);
int cnt = 0;
rep (i, 1, n) cnt += a[c[i]] > b[i];
if (cnt < m) {
set<PII> q;
rep (i, 1, n) if (a[c[i]] <= b[i]) {
if (!q.empty() && q.begin()->fi < a[c[i]]) {
int pp = q.begin()->se;
swap(b[i], b[pp]);
++cnt;
if (cnt == m) break;
q.erase(q.begin());
q.emplace(b[pp], pp);
} else {
q.emplace(b[i], i);
}
}
} else if (cnt > m) {
set<PII> q;
rep (i, 1, n) if (a[c[i]] > b[i]) {
if (!q.empty() && b[i] >= q.begin()->fi) {
int pp = q.begin()->se;
swap(b[i], b[pp]);
--cnt;
if (cnt == m) break;
q.erase(q.begin());
}
q.emplace(a[c[i]], i);
}
}
if (cnt == m) {
rep (i, 1, n) d[c[i]] = b[i];
cout << "YES\n";
rep (i, 1, n) cout << d[i] << ' ';
cout << '\n';
} else {
cout << "NO\n";
}
}
return 0;
}
D - Ones and Twos
考察奇偶性，考虑从头/尾丢弃 item 来使得剩余的子数组和等于所求
-
当头尾丢弃的 item 和是偶数时，必定有解，每次也偶数的从头/尾丢弃偶数即可（或者头尾一起各丢一个 1）
-
当头尾丢弃的 item 和是奇数是，先从数组头 or 尾贪心的选一个方向丢一个 1, 就可以转成情况 1 了（前提剩余 sum 可以凑出所求和）
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> n >> m;
int s = 0;
set<int> st;
rep (i, 1, n) {
cin >> a[i], s += a[i];
if (a[i] == 1) st.emplace(i);
}
rep (i, 1, m) {
int op; cin >> op;
if (op == 2) {
int x, y; cin >> x >> y;
if (a[x] == 1) st.erase(x);
s -= a[x]; a[x] = y;
if (a[x] == 1) st.emplace(x);
s += a[x];
} else {
int x; cin >> x;
if (s < x) cout << "NO\n";
else if (s == x) cout << "YES\n";
else {
int z = s - x;
if (!(z & 1)) cout << "YES\n";
else if (!st.empty() && z >= (min(*st.begin() - 1, n - *st.rbegin()) << 1) + 1) cout << "YES\n";
else cout << "NO\n";
}
}
}
}
return 0;
}
E - Permutation Sorting
每个数字移动的距离不会超过 n, 为了方便计算，选择拆环，让 a[n + 1 ~ n * 2] = a[1 ~ n]
每个位置移动的绝对距离是 \(s_i\), 即 \((i + h_i − 1) % n =a_i - 1\)
然后就是考虑路径上哪些点 j 可以跳过，即 \(i < j < i + h_i \ and \ (i < a_j < i + h_i \ or \ i < a_j + n < i + h_i)\)
或者说对于点 i 的移动路径是 [l, r] (l = i, (r - 1) mod n + 1 = \(a_i\)), 他路径上可以跳过的点就是路径被 [l, r] 包含的路径
然后就是找个数据结构维护单点修改，区间查询路径上可以跳过的点数就好了
const int N = 1e6 + 5;
int n, m, _, cas;
int a[N], c[N << 1], ans[N];
void add(int x, int k) { for (; x <= n << 1; x += -x & x) c[x] += k; }
int ask(int x) { int ans = 0; for (; x; x -= x & -x) ans += c[x]; return ans; }
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> n;
memset(c, 0, sizeof(int) * n << 1);
vector<PII> e;
rep (i, 1, n) {
cin >> a[i];
if (i <= a[i]) {
e.pb(i, a[i]);
e.pb(i + n, a[i] + n);
}
else e.pb(i, a[i] + n);
}
sort(e.begin(), e.end(), greater<PII>());
for (auto [l, r]: e) {
if (l <= n) {
ans[a[l]] = r - l - ask(r) + ask(l - 1);
}
add(r, 1);
}
rep (i, 1, n) cout << ans[i] << ' ';
cout << '\n';
}
return 0;
}