C/C++教程
AtCoder Grand Contest 058 部分题目不简要题解
从这里开始
- 比赛目录
Problem A Make it Zigzag
考虑使 $1, 3, 5, 7, \cdots, 2n - 3$ 这些位置后三个中的最大值在中间，最后再处理一下最后两个位置就行了。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
int a[N];
vector<int> ans;
int maxp(int a, int b, int c) {
if (c > max(a, b)) return 2;
if (b > max(a, c)) return 1;
return 0;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= (n << 1); i++) {
scanf("%d", a + i);
}
for (int i = 1; i <= (n << 1) - 2; i += 2) {
int d = maxp(a[i], a[i + 1], a[i + 2]);
if (d != 1) {
ans.push_back(min(i + d, i + 1));
swap(a[i + d], a[i + 1]);
}
}
int n2 = n << 1;
if (a[n2 - 1] > a[n2]) {
ans.push_back(n2 - 1);
}
printf("%d\n", (signed) ans.size());
for (auto x : ans) {
printf("%d ", x);
}
return 0;
}
Problem B Adjacent Chmax
考虑其实问题相当于一个较大数可以把较小数覆盖掉。
依次考虑原序列每个数在最终序列中占了多长一段。容易发现只需要满足占的那一段里没有比它大的数就可以。
然后就是个简单 dp。
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void exgcd(int a, int b, int& x, int& y) {
if (!b) {
x = 1, y = 0;
} else {
exgcd(b, a % b, y, x);
y -= (a / b) * x;
}
}
int inv(int a, int n) {
int x, y;
exgcd(a, n, x, y);
return (x < 0) ? (x + n) : (x);
}
const int Mod = 998244353;
template <const int Mod = :: Mod>
class Z {
public:
int v;
Z() : v(0) { }
Z(int x) : v(x){ }
Z(ll x) : v(x % Mod) { }
friend Z operator + (const Z& a, const Z& b) {
int x;
return Z(((x = a.v + b.v) >= Mod) ? (x - Mod) : (x));
}
friend Z operator - (const Z& a, const Z& b) {
int x;
return Z(((x = a.v - b.v) < 0) ? (x + Mod) : (x));
}
friend Z operator * (const Z& a, const Z& b) {
return Z(a.v * 1ll * b.v);
}
friend Z operator ~(const Z& a) {
return inv(a.v, Mod);
}
friend Z operator - (const Z& a) {
return Z(0) - a;
}
Z& operator += (Z b) {
return *this = *this + b;
}
Z& operator -= (Z b) {
return *this = *this - b;
}
Z& operator *= (Z b) {
return *this = *this * b;
}
friend bool operator == (const Z& a, const Z& b) {
return a.v == b.v;
}
};
Z<> qpow(Z<> a, int p) {
Z<> rt = Z<>(1), pa = a;
for ( ; p; p >>= 1, pa = pa * pa) {
if (p & 1) {
rt = rt * pa;
}
}
return rt;
}
typedef Z<> Zi;
const int N = 5005;
template <typename T>
bool vmax(T& a, T b) {
return a < b ? (a = b, true) : false;
}
int n;
int vis[N];
int a[N], fa[N];
Zi f[N], g[N];
void build(int l, int r, int v) {
if (l > r) {
return;
}
int mx = -1, mxp = 0;
for (int i = l; i <= r; i++) {
if (vmax(mx, a[i])) {
mxp = i;
}
}
fa[mxp] = v;
build(l, mxp - 1, mxp);
build(mxp + 1, r, mxp);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
a[0] = N, a[n + 1] = N;
f[0] = 1;
for (int i = 1; i <= n; i++) {
int l = i, r = i;
while (a[l - 1] < a[i]) l--;
while (a[r + 1] < a[i]) r++;
Zi s = 0;
for (int j = l; j <= r; j++) {
g[j] += (s += f[j - 1]);
}
for (int j = 0; j <= n; j++) {
g[j] += f[j];
f[j] = g[j];
g[j] = 0;
}
}
printf("%d\n", f[n].v);
return 0;
}
Problem C Planar Tree
差点不会这题，感觉好毒瘤啊。
如果只有 1, 2 这个题瞎做就好了。
注意到如果奇数和偶数都能连，就是只有 1, 2 的情况，可是 1, 4 不能连。考虑先把这两个烦人的东西干掉。
考虑 $(1, 2)$，$(3, 4)$ 相邻的时候直接连起来，然后分别当做只有一个点 2 或者 3。假如原问题有解且不存在这条边，那么显然这条边可以加上去，然后环上随便删一条边就行了。因此原问题和新问题有解性等价。
注意到如果有连续两个数是相同的，那么可以在其中 1 个连边的时候，两个一起连。考虑把这两个缩一起。和上面同样的方法证明两个问题有解性等价，只是可以加边的原因略有不同。
现在问题变成 1 不和 2 相邻，4 不和 3 相邻，相邻的数不同，目标把所有的 1, 4 连到别的点上。可以发现，树上不跨过 4 的 $(1, 2)$ 相连会导致至少 1 个 $3$ 不能继续和 4 相连。（如果有跨过 4 的话就考虑这个 $(3, 4)$，这样处理下去可能会得到不跨过 2 的 $(3, 4)$ 相连，但和这个情形是相似的）这样的情况一定是 $(1, 3, 2)$，考虑把这个缩成 $2$，继续这个操作。所以每消去一个 1 就会减少一个 3，每消去一个 4 就会减少一个 2。
如果不存在 $(1, 3, 2)$ 也不存 $(4, 2, 3)$，那么说明不存在 $(2, 3)$ 相邻的情况，此时可以得到 $4$ 的数量大于等于 $2$ 的数量， $3$ 的数量大于等于 $1$ 的数量（等于是因为可能都没有），此时显然不可能。
相反如果满足 $2$ 的数量加上 $3$ 的数量大于 $1$ 的数量加上 $4$ 的数量，同时 1 的数量大于等于 3 的数量，4 的数量大于等于 2 的数量，因为每次两个数量和同时减少，所以不可能出现不存在 $(2, 3)$ 相邻的情形。因此只用处理一下，然后数数量就可以了。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int T, n;
int a[N], stk[N], cnt[5];
int merge(int x, int y) {
if (x > y) swap(x, y);
if (x == y) {
return x;
}
if (x + 1 == y && x != 2) {
return x == 1 ? y : x;
}
return 0;
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
int pos = 1, top = 1;
while (a[pos] == a[1]) pos++;
rotate(a + 1, a + pos, a + n + 1);
stk[top] = a[1];
for (int i = 2, x; i <= n; i++) {
x = merge(stk[top], a[i]);
if (x) {
stk[top] = x;
} else {
stk[++top] = a[i];
}
}
int frt = 1, tmp;
while (frt < top && (tmp = merge(stk[frt], stk[top]))) {
stk[top] = tmp;
frt++;
}
memset(cnt, 0, sizeof(cnt));
for (int i = frt; i <= top; i++) {
cnt[stk[i]]++;
}
if (cnt[4] <= cnt[2] && cnt[1] <= cnt[3] && cnt[1] + cnt[4] < cnt[2] + cnt[3]) {
puts("Yes");
} else {
puts("No");
}
}
int main() {
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
Problem D Yet Another ABC String
这种题比那种无聊的猜结论题有意思多了。
朴素容斥的话相当于硬点若干个位置，然后这个位置起始长度为 3 的子串不合法。有重叠的话不好处理，主要因为 3 种字符的数量有限制。
考虑让硬点的位置后面一定不和它相连。就是 ABC 后面不是 A。相当于就是对每个这样连续的 ABCABCAB 末做一个子集容斥。
然后就是个简单组合计数。
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void exgcd(int a, int b, int& x, int& y) {
if (!b) {
x = 1, y = 0;
} else {
exgcd(b, a % b, y, x);
y -= (a / b) * x;
}
}
int inv(int a, int n) {
int x, y;
exgcd(a, n, x, y);
return (x < 0) ? (x + n) : (x);
}
const int Mod = 998244353;
template <const int Mod = :: Mod>
class Z {
public:
int v;
Z() : v(0) { }
Z(int x) : v(x){ }
Z(ll x) : v(x % Mod) { }
friend Z operator + (const Z& a, const Z& b) {
int x;
return Z(((x = a.v + b.v) >= Mod) ? (x - Mod) : (x));
}
friend Z operator - (const Z& a, const Z& b) {
int x;
return Z(((x = a.v - b.v) < 0) ? (x + Mod) : (x));
}
friend Z operator * (const Z& a, const Z& b) {
return Z(a.v * 1ll * b.v);
}
friend Z operator ~(const Z& a) {
return inv(a.v, Mod);
}
friend Z operator - (const Z& a) {
return Z(0) - a;
}
Z& operator += (Z b) {
return *this = *this + b;
}
Z& operator -= (Z b) {
return *this = *this - b;
}
Z& operator *= (Z b) {
return *this = *this * b;
}
friend bool operator == (const Z& a, const Z& b) {
return a.v == b.v;
}
};
Z<> qpow(Z<> a, int p) {
Z<> rt = Z<>(1), pa = a;
for ( ; p; p >>= 1, pa = pa * pa) {
if (p & 1) {
rt = rt * pa;
}
}
return rt;
}
typedef Z<> Zi;
const int N = 3e6 + 5;
int A, B, C, S;
Zi fac[N], _fac[N], pw2[N];
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i;
}
_fac[n] = ~fac[n];
for (int i = n; i; i--) {
_fac[i - 1] = _fac[i] * i;
}
pw2[0] = 1;
for (int i = 1; i <= n; i++) {
pw2[i] = pw2[i - 1] * 2;
}
}
void cswap(int& a, int& b) {
if (a > b) {
swap(a, b);
}
}
Zi comb(int n, int m) {
return n < m ? 0 : fac[n] * _fac[m] * _fac[n - m];
}
int main() {
scanf("%d%d%d", &A, &B, &C);
S = A + B + C;
cswap(B, C), cswap(A, B), cswap(B, C);
init(S);
Zi ans = 0, tmp;
for (int i = 0; i <= A; i++) {
// the last one isn't included
int rest = S - 3 * i;
tmp = comb(rest + i - 1, i) * pw2[i] * fac[rest] * _fac[A - i] * _fac[B - i] * _fac[C - i];
// the last one is included
if (i) {
tmp += comb(rest + i - 1, i - 1) * pw2[i - 1] * 3 * fac[rest] * _fac[A - i] * _fac[B - i] * _fac[C - i];
}
if (i & 1) {
ans -= tmp;
} else {
ans += tmp;
}
}
printf("%d\n", ans.v);
return 0;
}
Problem E Nearer Permutation
感觉这种题和码农题一样无聊，反正顺着思路做就完了，每步难度不大，就是思考的过程特别长。虽然也有可能是因为我菜。
考虑怎么找出 $z$。
首先考虑怎么算 $d(x, z)$，相当于将 $x$ 第一个位置上的数，在 $z$ 中改为 $1$，第二位置上的数，在 $z$ 中改为 $2$，然后求 $z'$ 的逆序对数。
这个显然相当于 $i$ 在两个排列中出现的位置构成的有序二元组的逆序对数。
那么现在有 2 列二元组，每列二元组只知道其中 1 个数，从小到大把 $1$ 到 $n$ 填进去，每次尽可能填较小的数对应的二元组。
现在问题变成判定把剩下的填进来其中 1 列的逆序对数是否不超过另一列的逆序对数。
可以发现，只有每对 $i$ 在 $x$ 和 $y$ 中出现的位置构成的有序二元组的逆序对会对差有贡献，并且贡献为 $+1$ 或者 $-1$。（其实这个逆序对其实就是 $i$ 在 $x$ 中出现的位置 $p_i$ 的逆序对）如果 $p_i > p_j (i < j)$ 并且 $(p_i, ?)$ 被先填上数，那么会产生 $+1$ 的差。（最终需要差小于等于 0）我们下面称违反一个逆序对 $(i, j) (i < j, p_i > p_j)$ 指先在 $(p_i, ?)$ 填数。
因此我们可以至多违反逆序对总数除以 $2$ 向下取整个逆序对。
然后很容易得到一个明确的求 $z$ 的做法：假设当前在确定第 $i$ 个位置上的数，找尽量小的 $j$ 满足上一条限制，然后填上 $(p_j, i)$。
现在回到原问题。
现在我们要填 $p_1, \cdots, p_n$，题目指定了上面做法填 $(p_i, ?)$ 的顺序。
当我们填了一个 $(p_i, ?)$ 且前面有没有填的 $(p_j, ?)$ 时相当于限制此时能违反的数量小于填 $(p_j, ?)$ 会违反的数量。考虑每次填的过程，允许违反的数量每次单调不增，后者至多减少 1。所以如果下一次填的位置 $(p_k, ?)$ 满足 $k < i$，那么意味着上面这个差是刚好变为 $0$，所以填完 $(p_k, ?)$ 后不能再违反任何逆序对。这之后只能每次填 $p$ 最小的没填的位置。
我们将 $p_i$ 分为 4 类：
- 第一类位置：满足 $i = z_i$
- 第三类位置：第一个满足 $z_i > z_{i + 1}$ 的 $z_{i + 1}$
- 第二类位置：设第三类位置为 $z_t$，那么在 $z_1, \cdots, z_{t - 1}$ 中满足 $z_i > i$ 的为第二类位置
- 第四类位置：剩下的
容易发现对于第一类位置没有限制。如果一个现在要填的位置 $p_i$，之前还有没有填的位置 $p_j$，那么一定满足 $p_i < p_j$，否则能违反的限制数一定满足能先填 $p_j$。因此在不考虑第三类位置的情况下，第二类位置的限制在处理出第四类位置的 $p$ 的相对顺序后就已知了。
我们希望使得逆序对数减去 2 倍被违反的逆序对数为 $0$ 或者 $1$。我们先考虑这个东西的最小值。注意到每产生一个被违反的逆序对的时候对这个值的贡献为 $-1$。
在不考虑第三类位置的时候，最优方案为第一类位置依次填 $n, n - 1, \cdots$，第一个第二类位置填能填最大的数（能违反的逆序对数到这里的时候最大值就是这个位置上的限制）剩下按顺序填最小的数。
注意到你可以连续地把这个值加上 1，所以如果第三类位置在第一个第二类位置的后面就做完了。
考虑第三类位置在所有第二类位置之前的情形。
如果第三类位置填上后后面有 $x$ 个数比它小，那么到这个位置的时候允许违反的逆序对数也是 $x$。第三类位置对于倒数第 $i$ 个被填上的第二类位置有一个限制：这后面至多有 $i - 1$ 个数比它小（注意求 $z$ 的过程运行到这里的时候允许违反的逆序对数是 $x$）。此时显然最优的话把第一个第二类位置填能填的最大的，剩下的没填的按顺序填能填的最小的。因此我们只用求一下最大可能的 $x$ 即可。（注意这里所有的第二类位置都对这个第三类位置有限制，因为经过第一个第二类位置后，允许违反的逆序对数是 $x$ 不是 $0$）。
Code
#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool vmin(T& a, T b) {
return a > b ? (a = b, true) : false;
}
const int N = 3e5 + 5;
typedef class Fenwick {
public:
int n;
int a[N];
void init(int n) {
this->n = n;
fill(a, a + n + 1, 0);
}
#define lowbit(_) ((_) & -(_))
void add(int idx, int val) {
for ( ; idx <= n; idx += lowbit(idx)) {
a[idx] += val;
}
}
int query(int idx) {
int ret = 0;
for ( ; idx; idx -= lowbit(idx)) {
ret += a[idx];
}
return ret;
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
} Fenwick;
int T, n;
Fenwick fen;
int a[N], les[N];
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
int p1, p2;
for (p1 = 1; p1 <= n && a[p1] == p1; p1++);
if (p1 >= n) {
puts("Yes");
return;
}
for (p2 = p1 + 1; p2 <= n && a[p2] > a[p2 - 1]; p2++);
long long dif = -1ll * (n + n - p1) * (p1 - 1) / 2;
fen.init(n);
for (int i = n; i >= p1; i--) {
int p = a[i];
dif += fen.query(p);
fen.add(p, 1);
}
for (int i = 1; i <= n; i++) {
les[i] = n + 1;
}
fen.init(n);
for (int i = p2; i <= n; i++) {
int p = a[i];
if (i != p2) {
les[p] = fen.query(p, n);
}
fen.add(p, 1);
}
if (a[p2] > a[p1]) {
int lim = n + 1;
for (int i = p1; i <= a[p1]; i++) {
vmin(lim, les[i]);
}
dif -= lim + (p2 - p1 - 1);
} else {
int lim = n - a[p2] - (p2 - p1);
for (int i = 2; i <= n; i++) {
vmin(les[i], les[i - 1]);
}
for (int i = p1; i < p2; i++) {
vmin(lim, les[a[i]] + p2 - i - 1);
}
vmin(lim, les[a[p2]] - 1);
dif -= lim + p2 - p1 - 1;
}
puts((dif < 2) ? "Yes" : "No");
}
int main() {
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
Problem F Authentic Tree DP
别催了，在路上了.jpg
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
-
在Mac系统上将图片中的文字提取出来有哪些方法？-icode9专业技术文章分享11-22
-
excel 表格中怎么固定一行显示不滚动？-icode9专业技术文章分享11-22
-
怎么将 -rwxr-xr-x 修改为 drwxr-xr-x？-icode9专业技术文章分享11-22
-
在Excel中怎么将小数向上取整到最接近的整数？-icode9专业技术文章分享11-22
-
Excel中常见的取整函数有哪些？-icode9专业技术文章分享11-22
-
错误信息：does not match the actual quantity supplied 提示是什么意思？-icode9专业技术文章分享11-22
-
WebSocket学习：初学者的简单指南11-21
-
获取apk的md5值有哪些方法？-icode9专业技术文章分享11-20
-
xml报文没有传 IdentCode ，为什么正常解析没报错呢？-icode9专业技术文章分享11-20
