省流版
A - 123233 (abc380 A)
题目大意
给了\(6\)个数字，问是否
- \(1\)的数字出现 \(1\)次
- \(2\)的数字出现 \(2\)次
- \(3\)的数字出现 \(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;
cin >> s;
bool ok = true;
for (int i = 1; i <= 3; ++i)
ok &= count(s.begin(), s.end(), i + '0') == i;
if (ok)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
B - Hurdle Parsing (abc380 B)
题目大意
给定一个包含-|的字符串。统计每两个|之间有多少个-。
解题思路
找到连续的两个|的下标，然后其差即为答案。Python可以一行。
神奇的代码
print(' '.join([str(len(s)) for s in input()[1:-1].split('|')]))
C - Move Segment (abc380 C)
题目大意
给定一个01子串。
连续的1视为一个块。
现将第\(k\)个块移动到第 \(k-1\)个块前面。
解题思路
按照题意，找到第\(k\)个块的下标，然后复制即可。下述是Python代码，split('0')可以轻易找到第\(k\)个块，然后移动即可。
神奇的代码
n, k = map(int, input().split())
k -= 1
s = input().split('0')
one = [pos for pos, i in enumerate(s) if i]
kk = s[one[k]]
s.pop(one[k])
s[one[k - 1]] += kk + '0'
print('0'.join(s))
D - Strange Mirroring (abc380 D)
题目大意
给定一个字符串\(s\)，重复下述操作 无数次：
- 将 \(s\)的字母大小写反转成 \(t\)，加到 \(s\)后面
给定 \(q\)个询问，每个询问问第 \(k\)个字符是什么。
解题思路
每进行一次操作，字符串\(s\)的长度会翻倍。
容易发现其字符串形如\(s_0\overline{s_0}\overline{s_0\overline{s_0}}\overline{s_0\overline{s_0}\overline{s_0\overline{s_0}}}\overline{s_0\overline{s_0}\overline{s_0\overline{s_0}}\overline{s_0\overline{s_0}\overline{s_0\overline{s_0}}}}\)
我们从大往小的看，左右两边长度一样，区别就是反转。我们找到第一个\(s_i\)，使得\(k\)在右半边，那我们就记录一次反转操作，然后递归的考虑右边横线下方的字符串，直到 \(k < |s|\)，我们就得到对应的字符和反转的次数，就得知最后的字符是多少了。
即先找到第一个 \(s_i = s_{i-1}t_{i-1}\)，其中 \(k\)位于 \(t_{i-1}\)里，这里\(s_{i-1}\)和 \(t_{i-1}\)只是大小写反了。此时就需要反转一次了，然后令\(k = k - |s_{i-1}|\)，递归的考虑重复考虑相同的情况即可。
神奇的代码
#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;
int q;
cin >> s >> q;
vector<LL> round{int(s.size())};
auto dfs = [&](auto dfs, LL k, int sign) -> char {
if (k < s.size()) {
if (sign) {
if (isupper(s[k])) {
return tolower(s[k]);
} else {
return toupper(s[k]);
}
} else {
return s[k];
}
}
auto pos = upper_bound(round.begin(), round.end(), k);
LL len = *pos / 2;
return dfs(dfs, k - len, sign ^ 1);
};
while (q--) {
LL k;
cin >> k;
--k;
while (round.back() <= k) {
round.push_back(round.back() * 2);
}
cout << dfs(dfs, k, 0) << ' ';
}
cout << '\n';
return 0;
}
E - 1D Bucket Tool (abc380 E)
题目大意
从左到右\(n\) 个格子，第 \(1\) 个格子颜色为\(i\) 。
维护 \(q\) 个查询，分两种：
1 x c：将第\(x\)个格子连同周围与其同色的格子涂成颜色\(c\)2 c：问颜色\(c\)的格子数
解题思路
如果一个格子颜色与周围相同，则它们就会连通，成为一个整体，我们可以用并查集维护这个连通性。
对于操作\(1\)，从并查集就很方便的修改一个整体的颜色，进而维护每种颜色的格子数。但修改颜色后，需要看看这个整体与左右两个格子的颜色是否相同，能否合并成新的整体。
为了能找到这个整体的左右相邻格子，并查集需要维护该整体的最左和最右的格子，然后根据颜色决定是否合并。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
class dsu {
public:
vector<int> p;
vector<int> l;
vector<int> r;
vector<int> sz;
vector<int> col;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
col.resize(n);
sz.resize(n);
l.resize(n);
r.resize(n);
iota(l.begin(), l.end(), 0);
iota(r.begin(), r.end(), 0);
iota(p.begin(), p.end(), 0);
iota(col.begin(), col.end(), 0);
fill(sz.begin(), sz.end(), 1);
}
inline int get(int x) { return (x == p[x] ? x : (p[x] = get(p[x]))); }
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
sz[y] += sz[x];
l[y] = min(l[y], l[x]);
r[y] = max(r[y], r[x]);
return true;
}
return false;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
dsu d(n);
vector<int> cnt(n, 1);
while (q--) {
int op;
cin >> op;
if (op == 1) {
int x, c;
cin >> x >> c;
x--;
--c;
int fx = d.get(x);
cnt[d.col[fx]] -= d.sz[fx];
d.col[fx] = c;
cnt[d.col[fx]] += d.sz[fx];
for (auto& nei : {d.l[fx] - 1, d.r[fx] + 1}) {
if (nei >= 0 && nei < n) {
int fnei = d.get(nei);
if (fnei != fx && d.col[fnei] == c) {
d.unite(fx, fnei);
}
}
}
} else {
int c;
cin >> c;
--c;
cout << cnt[c] << '\n';
}
}
return 0;
}
F - Exchange Game (abc380 F)
题目大意
高桥和青木手里各有\(n,m\)张牌，桌子上有 \(l\)张牌。牌上写了数字。
高桥和青木轮流操作，直到无法操作的人输。
操作为，将手里的一张牌 \(a\)放到桌子上，如果桌上有数字小于 \(a\)的牌，他可以拿一张到自己手上，当然也可以选择不拿。
高桥先手，问最优策略下谁赢。
解题思路
博弈\(dp\)，从卡牌在谁手中的角度思考状态数，只有 \(O(3^{n+m+l}) = O(3^12) = 5e5\)，因此直接搜索即可。
即设 \(dp[i][j]=1/0\)表示当前 \(i\)先手，局面是 \(j\)（即一个描述\(n+m+l\)张牌在谁手中的状态，可以是一个数组，\(0/1/2\)分别表示在高桥、青木或者桌子上，也可以是一个三进制的压缩状态），此时先手必赢/必输。
转移则枚举当前手的策略，即先花\(O(n+m+l)\)枚举将手里的哪张牌放到桌子上，再花 \(O(n+m+l)\)枚举 拿桌子上的哪张牌，然后更新局面状态，转移到下一个局面即可。
而当前局是先手必赢/必输，取决于下一个局面（注意下一个局面的先手是当前局面的后手）。因为是最优策略，因此下一个局面如果有（当前局面的后手）必输局面，那先手必赢，否则如果下一个局面全是（当前局面的后手）必赢局面，则先手必输。
因此求解是一个递归的过程。总的时间复杂度是\(O((n+m+l)^2 3^{n+m+l})\)
vector状态1700ms
#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, m, l;
cin >> n >> m >> l;
vector<int> c(n + m + l);
for (auto& x : c)
cin >> x;
array<map<vector<int>, int>, 2> dp;
vector<int> st(n + m + l);
fill(st.begin(), st.begin() + n, 0);
fill(st.begin() + n, st.begin() + n + m, 1);
fill(st.begin() + n + m, st.end(), 2);
auto dfs = [&](auto dfs, vector<int>& st, int p) -> bool {
if (count(st.begin(), st.end(), p) == 0) {
return dp[p][st] = 0;
}
if (dp[p].count(st))
return dp[p][st];
bool ok = true;
for (int i = 0; i < n + m + l; i++) {
if (st[i] == p) {
st[i] = 2;
for (int j = 0; j < n + m + l; j++) {
if (st[j] == 2 && c[j] < c[i]) {
st[j] = p;
ok &= dfs(dfs, st, p ^ 1);
st[j] = 2;
}
}
ok &= dfs(dfs, st, p ^ 1);
st[i] = p;
}
}
return dp[p][st] = (ok ^ 1);
};
if (dfs(dfs, st, 0))
cout << "Takahashi" << '\n';
else
cout << "Aoki" << '\n';
return 0;
}
三进制压缩状态200ms
#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, m, l;
cin >> n >> m >> l;
vector<int> c(n + m + l);
for (auto& x : c)
cin >> x;
vector<int> base(n + m + l, 1);
for (int i = 1; i < n + m + l; ++i) {
base[i] = base[i - 1] * 3;
}
array<vector<int>, 2> dp{vector<int>(base.back() * 3, -1),
vector<int>(base.back() * 3, -1)};
auto get_bit = [&](int x, int y) { return x / base[y] % 3; };
auto tr = [&](int& cur, int pos, int v) {
cur -= get_bit(cur, pos) * base[pos];
cur += v * base[pos];
};
auto final = [&](int st, int p) {
for (int i = 0; i < n + m + l; i++) {
if (get_bit(st, i) == p)
return false;
}
return true;
};
auto dfs = [&](auto dfs, int st, int p) -> bool {
if (final(st, p)) {
return dp[p][st] = 0;
}
if (dp[p][st] != -1)
return dp[p][st];
bool ok = true;
for (int i = 0; i < n + m + l; i++) {
if (get_bit(st, i) == p) {
tr(st, i, 2);
for (int j = 0; j < n + m + l; j++) {
if (get_bit(st, j) == 2 && c[j] < c[i]) {
tr(st, j, p);
ok &= dfs(dfs, st, p ^ 1);
tr(st, j, 2);
}
}
ok &= dfs(dfs, st, p ^ 1);
tr(st, i, p);
}
}
return dp[p][st] = (ok ^ 1);
};
int st = 0;
for (int i = 0; i < n + m + l; i++) {
tr(st, i, (i >= n) + (i >= n + m));
}
if (dfs(dfs, st, 0))
cout << "Takahashi" << '\n';
else
cout << "Aoki" << '\n';
return 0;
}
G - Another Shuffle Window (abc380 G)
题目大意
给定一个关于\(n\)的全排列\(p\)和一个数字 \(k\)。进行如下操作一次。
- 第一步，从\([1, n - k + 1]\)随机选一个数\(i\)
- 第二部，将 \(p_{i, i + k - 1}\)随机打乱
问进行操作后的逆序对的期望值。
解题思路
期望的求法就是该情况的逆序对数$\times $发生该情况的概率，对所有情况求和。因此我们先考虑所有情况怎么来的。
首先第一步，枚举\(i\)，它数量只有 \(O(n)\)，可以枚举。
枚举了 \(i\)后，排列 \(p\)就分成了三部分： \(l,m,r\)，其中 \(m\)就是将会随机打乱的\(k\)个数，然后\(l,r\)就是左右两部分的数。
再然后就是第二部，将中间部分\(m\)打乱，但这情况数有\(O(k!)\)，显然不能枚举，我们考虑能否综合第二步的所有情况来求。
考虑逆序对\((i,j)\)的来源，根据\(i,j\)的值，有这几部分：
- \(ll\)部分
- \(lr\)部分
- \(lm\)部分
- \(rr\)部分
- \(mr\)部分
- \(mm\)部分
除了最后一个，前\(5\)个的逆序对的数量不会随着第二步的操作而改变。当第一个的\(i\)变化时，我们可以实时维护前 \(5\)部分的逆序对数量的变化。
而第六部分的 \(mm\)，考虑里面的任意两个数 \((i,j)\)，综合所有的随机打乱情况 ，谁前谁后其实各占一半，也就是说，任意一对数只有一半的概率会产生逆序对，而\(k\)个数一共有 \(\frac{k(k-1)}{2}\)对数，每对形成逆序对的概率都是 \(\frac{1}{2}\)，因此第六部分的期望逆序对数量始终是 \(\frac{k(k-1}}{2} \frac{1}{2} = \frac{k(k-1)}{4}\)。
而前 \(5\)部分的维护，即 \(m\)最左边少一个数， \(l\)最右边多一个数， \(m\) 最右边多一个数，\(r\)最左边少一个数，依次计算这些数所产生的逆序对数量，然后更新即可。
而产生逆序对的数量，即对于数\(i\) ，我们想知道大于\(i\)或小于 \(i\)的数量，可以通过维护 \(l,m,r\)部分的桶（即\(cnt_{i}\)表示数字\(i\)出现的次数 ），加以树状数组或线段树的单点修改和区间求和，从而在 \(O(\log n)\)的时间得到。即权值线段树或权值树状数组。
总的时间复杂度为\(O(n \log n)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
// starting from 1
template <typename T> class fenwick {
public:
vector<T> fenw;
int n;
int tot;
fenwick(int _n) : n(_n) {
fenw.resize(n);
tot = 0;
}
inline int lowbit(int x) { return x & -x; }
void modify(int x, T v) {
tot += v;
for (int i = x; i < n; i += lowbit(i)) {
fenw[i] += v;
}
}
T get(int x) {
T v{};
for (int i = x; i > 0; i -= lowbit(i)) {
v += fenw[i];
}
return v;
}
};
const LL 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;
vector<int> p(n);
fenwick<int> l(n + 1), mid(n + 1), r(n + 1);
for (auto& x : p) {
cin >> x;
}
LL llc = 0, lmc = 0, mrc = 0, rrc = 0, lrc = 0;
LL mmc = 1ll * k * (k - 1) % mo * inv(4) % mo;
const int large = 1;
const int small = 0;
auto get_cnt = [&](fenwick<int>& f, int p, int large) {
if (!large)
return f.get(p - 1);
else
return f.tot - f.get(p);
};
auto update_l = [&](int num, int v) { // the right of l
l.modify(num, v);
llc += get_cnt(l, num, large) * v;
lmc += get_cnt(mid, num, small) * v;
lrc += get_cnt(r, num, small) * v;
};
auto update_m = [&](int num, int v) {
mid.modify(num, v);
lmc += get_cnt(l, num, large) * v;
mrc += get_cnt(r, num, small) * v;
};
auto update_r = [&](int num, int v) { // the left of r
r.modify(num, v);
lrc += get_cnt(l, num, large) * v;
mrc += get_cnt(mid, num, large) * v;
rrc += get_cnt(r, num, small) * v;
};
for (int i = 0; i < k; ++i)
update_m(p[i], 1);
for (int i = n - 1; i >= k; --i)
update_r(p[i], 1);
LL ans = (llc + lmc + mrc + rrc + lrc + mmc) % mo;
for (int i = 0; i < n - k; ++i) {
update_m(p[i], -1);
update_l(p[i], 1);
update_r(p[i + k], -1);
update_m(p[i + k], 1);
ans = (ans + llc + lmc + mrc + rrc + lrc + mmc) % mo;
}
ans = ans * inv(n - k + 1) % mo;
cout << ans << '\n';
return 0;
}
标签：AtCoder,return,Beginner,get,int,long,st,380,dfs From： https://www.cnblogs.com/Lanly/p/18550426