Desorting
定义一次操作为选定一个 \(i\) ，令 \(a_{1 \sim i}\) 自增， \(a_{i + 1 \sim n}\) ，自减，求使得整个序列无序的最小操作次数
若序列一开始就无序，输出 \(0\)
否则找到相邻两数差值最小的位置，在这个位置不断使用操作，可以证明这是最优方案
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 5e2 + 7;
int a[N];
int T, n;
inline bool check() {
for (int i = 2; i <= n; ++i)
if (a[i] < a[i - 1])
return true;
return false;
}
signed main() {
scanf("%d", &T);
for (; T; --T) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
if (check()) {
puts("0");
continue;
}
int minn = inf;
for (int i = 2; i <= n; ++i)
minn = min(minn, a[i] - a[i - 1]);
printf("%d\n", minn / 2 + 1);
}
return 0;
}
Fibonaccharsis
给定斐波那契数列的第 \(k\) 项 \(n\) ，求 \(f_1, f_2\) 有多少种可能性
注意到斐波那契数列的增长速度十分快，且知道相邻两项之后就能快速推出 \(f_1, f_2\) ，考虑枚举第 \(k - 1\) 项，暴力递推到 \(f_1, f_2\) 即可
时间复杂度 \(O(n \log n)\)
#include <bits/stdc++.h>
using namespace std;
int T, n, K;
inline bool check(int f1, int f2, int pos) {
int f0;
while (pos--) {
f0 = f2 - f1;
if (f0 < 0)
return false;
f2 = f1, f1 = f0;
}
return f1 <= f2;
}
signed main() {
scanf("%d", &T);
for (; T; --T) {
scanf("%d%d", &n, &K);
int ans = 0;
for (int i = 1; i <= n; ++i)
ans += check(i, n, K - 2);
printf("%d\n", ans);
}
return 0;
}
Ntarsis' Set
对于一个无限长的序列 \(1, 2, 3, \cdots\) ，每次删除前 \(a_1, a_2, \cdots, a_n\) 小的数字， \(k\) 次操作后求序列最小值
注意到对于任何一个数，只有删除比它小的数才会使得它更进一步被删掉，二分答案判断是否会被删掉即可
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 7;
int a[N];
int T, n, K;
inline bool check(int k, ll mid) {
while (k--)
mid -= upper_bound(a + 1, a + 1 + n, mid) - a - 1;
return mid < 1;
}
signed main() {
scanf("%d", &T);
for (; T; --T) {
scanf("%d%d", &n, &K);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
ll l = 1, r = 1e12, ans = 1;
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(K, mid))
l = mid + 1;
else
ans = mid, r = mid - 1;
}
printf("%lld\n", ans);
}
return 0;
}
Imbalanced Arrays
给定一个序列 \(a_{1 \sim n}\) ，构造一个序列 \(b_{1 \sim n}\) 满足
- \(-n \leq b_i \leq n, b_i \not = 0\)
- \(\forall i, j \in [1, n], b_i + b_j \not = 0\)
- 满足有 \(a_i\) 个 \(j\) 满足 \(b_i + b_j > 0\) （\(i, j\) 可以相等）
若不存在这个序列输出
NO
首先可以注意到若序列中同时出现或同时不出现 \(0\) 和 \(n\) ，则无解
于是我们可以从极端情况入手，用左右两个指针维护即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
struct Node {
int a, b, id;
inline bool operator < (const Node &rhs) const {
return a < rhs.a;
}
} a[N];
int ans[N];
int T, n;
inline bool solve() {
for (int i = n, l = 1, r = n, tmp = 0; i; --i) {
if (a[l].a == tmp && a[r].a - i == tmp)
return false;
if (a[l].a != tmp && a[r].a - i != tmp)
return false;
if (a[l].a == tmp)
a[l].b = -i, ++l;
else
a[r].b = i, ++tmp, --r;
}
for (int i = 1; i <= n; ++i)
ans[a[i].id] = a[i].b;
return true;
}
signed main() {
scanf("%d", &T);
for (; T; --T) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i].a);
a[i].id = i;
}
sort(a + 1, a + 1 + n);
if (solve()) {
puts("YES");
for (int i = 1; i <= n; ++i)
printf("%d ", ans[i]);
puts("");
} else
puts("NO");
}
return 0;
}
Ina of the Mountain
定义一次操作为选定 \(l, r\) ，将 \(a_{l \sim r}\) 自减，操作过程中若 \(a_i = 0\) 则 \(a_i \leftarrow k\) ，求使得所有 \(a_i\) 均等于 \(k\) 的最小操作次数
令 \(c_i\) 为 \(a_i\) 被区间覆盖的次数，则 \(\forall i \in [1, n], a_i \equiv c_i \pmod{k}\)
令 \(b_i = a_i - a_{i - 1}, d_i = c_i - c_{i - 1}\) ，则 \(\forall i \in [1, n], b_i \equiv d_i \pmod{k}\) ，可以证明存在一组最优解满足所有 \(d_i \in (-k, k)\)
这样一来，每个 \(d_i\) 只有两种取值，设为 \(A_i < 0, B_i > 0\) 。选 \(A_i\) 不会产生代价，选 \(B_i\) 会产生 \(B_i\) 的代价，且各段前缀中选的数的和要非负
使用小根堆维护反悔贪心即可，时间复杂度 \(O(n \log n)\)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 7;
int a[N];
int T, n, K;
signed main() {
scanf("%d", &T);
for (; T; --T) {
scanf("%d%d", &n, &K);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
ll ans = 0;
priority_queue<int, vector<int>, greater<int> > Q;
for (int i = 1, sum = 0; i <= n; ++i) {
int b = (a[i] - a[i - 1] + K) % K;
if (!b)
continue;
int x = b - K;
if (sum + x >= 0)
sum += x, Q.push(b);
else {
int num = Q.empty() ? inf : Q.top();
if (num < b)
ans += num, Q.pop(), Q.push(b), sum += x + K;
else
ans += b, sum += b;
}
}
printf("%lld\n", ans);
}
return 0;
}
Miriany and Matchstick
用 \(A, B\) 填充一个 \(2 \times n\) 的矩阵，第一行已填好，求使得相邻两格相同的格子对数量为 \(k\) 的填的方案数
设 \(f_{i, c, j}\) 表示填了第二行的前 \(i\) 个位置，\(i\) 处的字符为 \(c \in \{ \texttt{A}, \texttt{B} \}\) （用 \(0, 1\) 表示 \(\texttt{A}, \texttt{B}\) ，填有不同字符的相邻位置是否能有 \(j\) 对
打表发现 \(\forall i \in [1, n], c \in \{ 0, 1 \}\) ，有 \(f_{i, c, 0}, f_{i, c, 1}, \cdots\) 构成的 \(01\) 串中所有 \(1\) 构成一个极长连续段或构成两个极长连续段且中间最多一个 \(0\)
令三元组 \((p, l, r)\) 表示一个状态，其中 \(p\) 为空缺位置， \(l, r\) 表示最左或最右的 \(1\) 的位置，转移即可
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
struct Node {
int p, l, r;
inline bool check(int x) const {
return l <= x && x <= r && x != p;
}
inline Node getnxt(int d) const {
return Node{~p ? p + d : -1, l + d, r + d};
}
} f[N][2];
int a[N], b[N];
char s[N];
int T, n, k;
inline Node merge(const Node &lhs, const Node &rhs) {
int L = min(lhs.l, rhs.l), R = max(lhs.r, rhs.r);
if (L <= lhs.p && lhs.p <= R && !rhs.check(lhs.p))
return (Node) {lhs.p, L, R};
else if (L <= rhs.p && rhs.p <= R && !lhs.check(rhs.p))
return (Node) {rhs.p, L, R};
else if (lhs.r + 2 == rhs.l)
return (Node) {lhs.r + 1, L, R};
else if (rhs.r + 2 == lhs.l)
return (Node) {rhs.r + 1, L, R};
else
return (Node) {-1, L, R};
}
signed main() {
scanf("%d", &T);
for (; T; --T) {
scanf("%d%d%s", &n, &k, s + 1);
for (int i = 1; i <= n; ++i)
a[i] = s[i] == 'B';
for (int i = 2; i <= n; ++i)
k -= a[i] != a[i - 1];
if (k < 0) {
puts("NO");
continue;
}
f[1][0] = Node{-1, 0, 0}, f[1][1] = Node{-1, 1, 1};
for (int i = 2; i <= n; ++i)
if (a[i - 1] == a[i]) {
f[i][0] = merge(f[i - 1][1].getnxt(1), f[i - 1][0]);
f[i][1] = merge(f[i - 1][0].getnxt(2), f[i - 1][1].getnxt(1));
} else {
f[i][0] = merge(f[i - 1][0].getnxt(1), f[i - 1][1]);
f[i][1] = merge(f[i - 1][1].getnxt(2), f[i - 1][0].getnxt(1));
}
int p = k, cnt;
if (f[n][0].check(k))
cnt = 0;
else if (f[n][1].check(k))
cnt = 1;
else {
puts("NO");
continue;
}
for (int i = n; i; --i) {
b[i] = a[i] ^ cnt;
if (i > 1)
if (a[i - 1] == a[i]) {
if (cnt) {
if (f[i - 1][0].check(p - 2))
p -= 2, cnt = 0;
else
--p;
} else {
if (f[i - 1][1].check(p - 1))
--p, cnt = 1;
}
} else {
if (cnt) {
if (f[i - 1][1].check(p - 2))
p -= 2;
else
--p, cnt = 0;
} else {
if (f[i - 1][0].check(p - 1))
--p;
else
cnt = 1;
}
}
}
puts("YES");
for (int i = 1; i <= n; ++i)
putchar(b[i] ? 'B' : 'A');
puts("");
}
return 0;
}