A – Sanitize Hands (abc357 A)
题目大意
给定(m)个物品。
依次来 (n)个人,每个人拿(a_i)个物品。
问有几个人可以拿走所需物品。
解题思路
求一遍前缀和然后upper_bound
一下,或者直接累计求和。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector a(n);
for (auto& x : a)
cin >> x;
partial_sum(a.begin(), a.end(), a.begin());
auto ans = upper_bound(a.begin(), a.end(), m) - a.begin();
cout
B – Uppercase and Lowercase (abc357 B)
题目大意
给定一个字符串,若大写字母占多数,则全部字母变成大写字母,否则变成小写字母。
问最终的字符串。
解题思路
按照题意统计一下大小写字母的数量,然后按照规则变换即可。
神奇的代码
#include
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;
int lower = count_if(s.begin(), s.end(), [](char c) { return islower(c); });
int upper = s.size() - lower;
if (lower >= upper) {
transform(s.begin(), s.end(), s.begin(), ::tolower);
} else {
transform(s.begin(), s.end(), s.begin(), ::toupper);
}
cout
C – Sierpinski carpet (abc357 C)
题目大意
给定(n),输出一个 (3^{n} times 3^{n})的图形 (g_n),其中有 (9 times 9)格,中间格子是全 .
,其余(8)格的图案是 (g_{n-1})。
(g_0)的图形是 #
。
解题思路
按照题意递归构造。
枚举(3^{n} times 3^{n})的每个位置((i,j)),设(sz=3^{n-1})。然后通过((frac{i}{sz}, frac{j}{sz}))判断其属于 (9)个方格中的哪个,如果是中间,则就是 .
,否则就进入子问题((i % sz, j % sz, n – 1)),即 (g_{n-1})的图案,位置 ((i % sz, j % sz))的图形。
神奇的代码
#include
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;
auto ns = [&](int i) {
int sz = 1;
for (int j = 0; j char {
if (n == 0)
return '#';
int small = ns(n - 1);
int x = i / small, y = j / small;
if (x == 1 && y == 1) {
return '.';
} else
return solve(solve, i % small, j % small, n - 1);
};
for (int i = 0; i
D – 88888888 (abc357 D)
题目大意
给定(n),定义 (f(n))表示 (n)个 (n)的拼接得到的数字。
求 (f(n) % 998244353)。
解题思路
设(a_1)表示 (1)个 (n), (a_2)表示(2)个 (n)。
容易得到(a_1 = n, a_2 = xa_1 + n = xn + n = n(x + 1), a_3 = xa_2 + n = n(x^2 + x + 1)),其中 (x=10^k), (k)是 (n)的位数。
展开得到通项公式(a_n = xa_{n-1} + n = n(x^{n-1} + x^{n-2} + cdots + x + 1) = n frac{x^n – 1}{x – 1})
通过费马小定理知 (frac{1}{x-1} equiv (x-1)^{mo-2} mod mo,mo=998244353)。
因此最终答案就是(n (x^n – 1)(x – 1)^{mo-2}) ,用快速幂计算即可。时间复杂度是(O(log n))
神奇的代码
#include
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);
LL n;
cin >> n;
__int128 ten = 1;
while (ten
E – Reachability in Functional Graph (abc357 E)
题目大意
给定一张基环内向森林(有向图,每个点出度为(1)),问点对数量 ((i,j)),满足从点 (i)出发可以到达点 (j)。
解题思路
考虑朴素做法,显而易见的(O(n^2)):从每个点出发,进行 (DFS)。
分析朴素做法,会发现操作重复的地方:假想一条链 (1 to 2 to 3 to 4 cdots),从 (1)出发 (DFS),从 (2)出发 (DFS),会发现非常冗余,当从 (1)出发时,它能到达的点, (2)也能到达,也就是说可以利用 (2)节点的信息,以避免重复搜索。
我们想通过后继节点的答案来得到当前点的答案,那得先计算后继节点答案,然后再考虑当前节点。这其实非常像拓扑排序:把边方向,然后我们处理入度为 (0)的点(这意味着原图中的后继节点已经计算完毕了)。
然而拓扑排序适用于 (DAG)(有向无环图),这里有环,因此得事先找到环。环上的节点是处处到达的。
如何找到环呢?考虑这是一张基环内向森林,它有个性质,即从任何点出发,最终一定会走到环内。
注意到答案分两类,一类是环上的点的贡献,其贡献值即为环大小。另一类是非环上的点的贡献,由于从它出发最终会走到环内,因此其贡献值为环大小(+)沿途的点数,我们从环上的点出发,就能一路更新沿途的点数及贡献了。
首先从任意点进行(DFS),直到重复访问到某个点时,这个点就是环上的点,标记一下。
然后从标记的点进行(DFS),遍历环上的点,统计环大小和标记环上的点。同时统计环上的点对答案的贡献(即环大小)。
最后从环上的点往非环上的点进行 (DFS),统计非环点对答案的贡献。
(3)次 (DFS)即可,时间复杂度是 (O(n))。
神奇的代码
#include
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> edge(n), inv(n);
for (int i = 0; i > p;
--p;
edge[i].push_back(p);
inv[p].push_back(i);
}
vector cnt(n), cir(n), visit(n);
int tt = 0;
auto dfs1 = [&](auto dfs1, int u) -> void {
visit[u] = tt;
for (auto v : edge[u]) {
if (!visit[v]) {
dfs1(dfs1, v);
} else if (visit[v] == tt) {
cir[v] = 1;
}
}
};
for (int i = 0; i void {
visit[u] = 1;
cir[u] = 1;
++cur;
for (auto v : edge[u]) {
if (!visit[v]) {
dfs2(dfs2, v);
}
}
cnt[u] = cur;
};
for (int i = 0; i void {
for (auto& v : inv[u]) {
if (!cir[v]) {
ans += cc + 1;
dfs3(dfs3, v, cc + 1);
}
}
};
for (int i = 0; i
F – Two Sequence Queries (abc357 F)
题目大意
给定两个数组(a,b), 维护一下三种操作:
-
1 l r x
,给(a_l, a_{l+1}, cdots, a_r)都加上 (x) -
2 l r x
,给(b_l, b_{l+1}, cdots, b_r)都加上 (x) -
3 l r
,求(sum_{i=l}^{r} a_i times b_i mod 998244353)
解题思路
区间操作,考虑线段树,维护的信息是什么。
首先肯定有(sum a_i b_i),考虑对它修改后,要额外维护什么信息,才能得到新的 (sum a_i b_i)。
对它修改,即变为 (sum (a_i + x)(b_i + y) = sum a_i b_i + ysum a_i + xsum b_i + sum xy)。
因此我们还需维护(sum a_i)和 (sum b_i),而它们的更新则需要自己的信息即可。
由于是区间操作, (lazy)信息就维护 (x,y)。
神奇的代码
#include
using namespace std;
using LL = long long;
const int N = 2e5 + 8;
const int mo = 998244353;
class segment {
#define lson (root & a, vector& b) {
if (l == r) {
sab[root] = 1ll * a[l - 1] * b[l - 1] % mo;
sum[root][0] = a[l - 1];
sum[root][1] = b[l - 1];
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid, a, b);
build(rson, mid + 1, r, a, b);
pushup(root);
}
void pushdown(int root, int l, int mid, int r) {
if (lazy[root][0] || lazy[root][1]) {
sab[lson] =
(sab[lson] + lazy[root][0] * sum[lson][1] % mo +
lazy[root][1] * sum[lson][0] % mo +
lazy[root][0] * lazy[root][1] % mo * (mid - l + 1) % mo) %
mo;
sum[lson][0] =
(sum[lson][0] + lazy[root][0] * (mid - l + 1) % mo) % mo;
sum[lson][1] =
(sum[lson][1] + lazy[root][1] * (mid - l + 1) % mo) % mo;
sab[rson] = (sab[rson] + lazy[root][0] * sum[rson][1] % mo +
lazy[root][1] * sum[rson][0] % mo +
lazy[root][0] * lazy[root][1] % mo * (r - mid) % mo) %
mo;
sum[rson][0] = (sum[rson][0] + lazy[root][0] * (r - mid) % mo) % mo;
sum[rson][1] = (sum[rson][1] + lazy[root][1] * (r - mid) % mo) % mo;
lazy[lson][0] = (lazy[lson][0] + lazy[root][0]) % mo;
lazy[lson][1] = (lazy[lson][1] + lazy[root][1]) % mo;
lazy[rson][0] = (lazy[rson][0] + lazy[root][0]) % mo;
lazy[rson][1] = (lazy[rson][1] + lazy[root][1]) % mo;
lazy[root][0] = lazy[root][1] = 0;
}
}
void update(int root, int l, int r, int L, int R, LL val, int op) {
if (L > 1;
pushdown(root, l, mid, r);
if (L mid)
update(rson, mid + 1, r, L, R, val, op);
pushup(root);
}
LL query(int root, int l, int r, int L, int R) {
if (L > 1;
pushdown(root, l, mid, r);
LL ans = 0;
if (L mid)
ans += query(rson, mid + 1, r, L, R);
ans %= mo;
return ans;
}
} sg;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
vector a(n), b(n);
for (auto& i : a)
cin >> i;
for (auto& i : b)
cin >> i;
sg.build(1, 1, n, a, b);
while (q--) {
int op;
cin >> op;
if (op == 3) {
int l, r;
cin >> l >> r;
int ans = sg.query(1, 1, n, l, r);
cout > l >> r >> x;
sg.update(1, 1, n, l, r, x, op - 1);
}
}
return 0;
}
G – Stair-like Grid (abc357 G)
题目大意
给定(n),定义一个网格,前两行有 (4)个格子,接着两行有 (6)个格子,接着两行有 (8)个格子 (…)。
其中有 (m)个格子不可走。
从左上到右下,只能往下走和往右走。问方案数。
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net