最近感觉自己又行了。就很想重新开始打 Codeforces,这里罗列一下从 2020/05/16 开始提交的(不是特别水的)AC代码。想有生之年上一次黄,先定个小目标上个1900!菜鸡茶茶白加油!

优雅的代码极大的避免了低级错误,边界处理至少占三分之一的工作量!

不要急着写代码,不要急着写代码,不要急着写代码,重要的事情说三遍!!!

Codeforces 比赛规则:每题有基础分数,每题的分数根据时间线性递减到一半(所以有些大佬先做CD,再做AB),在最后一次提交前每次提交减50分,然后按照分数排名,有hack,但是只有你过了初例并且锁定题目才能hack

Educational Codeforces:跟ICPC一致,不过一次非AC提交罚时为10分钟(ICPC 20分钟)

Codeforces Gobal Round:目前实力不支持做这个,容易掉分! 正常发挥都是能加分的!

查看Codeforces 上的过题数查看比赛rating折线,开始使用 cf-tool + WSL 打比赛(真香)。

技巧:

  • 比赛链接后面加/problems可以一个界面看所有题目。
  • 每道题思考时间不得超过15分钟,防止卡题!!!(常备闹钟,不骄不躁!)
  • AC的代码一般过几秒会弹出Accept对话框,所以可以值得等2~5s,没弹再刷新(cf-tool 真香)。
  • 先打开所有题目,大致扫一眼!只做:数论+DP+图论
  • 不要急着写代码!!!不是每一把都要打,不适合自己的强做没意思!!!
  • 计算式要列的清晰,并且最好是好输入的。
  • 仔细读完题目有明显思路赶紧写,然后要细心把公式列出来不要跳,再去写代码,过了再看别的题
  • caseInput.cpp, nocaseinput.cpp模板先建好 (cf-tool 真香)
  • codeforces.com 打不开的时候可以换成.ml或者.es (这个网址就很机智!)
  • A~F.cpp先创建好,用好 fopen 但是记得关 (cf-tool 真香)
  • 推荐在submit界面交题目(不推荐选择文件,有时候网慢,很可能没交上题 (cf-tool 真香)。
  • 另外一个浏览器(或另一个主界面)看一下关注Standing,不要把简单问题想复杂了
  • 不要写这样的代码if(a[j++]),while(a[j++]) 这种数列下标自加,特别容易出问题还不好查,特别在判断语句中。
  • 在高效和细心中找到一个均衡
  • $N=10^{18}$ 一般会有公式, $N = 2 \cdot 10^5$ 一般会用到排序、树状数组,线段树,等一系列$O(n\log n)$ 算法,$N=1000$ 一般会用到$dp$。模$998244353$可能会用到NFT。

题集

1399D: 01序列分组,使得各组相邻元素不同(主要考察复杂度,超级容易TLE)

可以存储当前10的个数,然后一直跑,就是$O(n)$ 复杂度了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int cas;
std::cin >> cas;
while (cas--) {
int n;
std::string s;
std::cin >> n >> s;
int k = 0, r[n];
std::stack<int> id[2];
for (int i = 0; i < n; ++i) {
int t = ('0' == s[i]);
if (id[t].size()) {
r[i] = id[t].top();
id[t].pop();
} else {
r[i] = ++k;
}
id[1 - t].push(r[i]);
}
print(k);
for (int i = 0; i < n; ++i) std::cout << r[i] << " ";
std::cout << std::endl;
}
return 0;
}

1399E1:dfs建树,然后就知道每条边的权重,然后有限队列贪心即可,注意是所有叶子节点到根的距离和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
using LL = long long;
class LinkStar {
public:
std::vector<int> head, nxt, to;
std::vector<LL> w;
LinkStar(int n) {
nxt.clear();
to.clear();
head = std::vector<int>(n + 1, -1);
}
void addedge(int u, int v, LL val) {
nxt.emplace_back(head[u]);
head[u] = to.size();
to.emplace_back(v);
w.emplace_back(val);
}
};
struct Node {
int d;
LL v;
Node(int _d, LL _v) : d(_d), v(_v) {}
bool operator<(const Node &A) const {
return (v + 1) / 2 * d < (A.v + 1) / 2 * A.d;
}
};
int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int cas;
std::cin >> cas;
while (cas--) {
int n;
LL s;
std::cin >> n >> s;
LinkStar diag(n);
for (int i = 1, u, v; i < n; ++i) {
LL w;
std::cin >> u >> v >> w;
diag.addedge(u, v, w);
diag.addedge(v, u, w);
}
std::priority_queue<Node> a;
bool vis[n + 1] = {};
std::function<int(int, LL)> dfs = [&](int u, LL val) -> int {
vis[u] = true;
int cnt = 0;
for (int i = diag.head[u]; ~i; i = diag.nxt[i]) {
int v = diag.to[i];
if (!vis[v]) cnt += dfs(v, diag.w[i]);
}
cnt = std::max(cnt, 1);
s -= val * cnt;
a.push({cnt, val});
return cnt;
};
dfs(1, 0);
int r = 0;
while (s < 0) {
auto [cnt, val] = a.top();
s += (val + 1) / 2 * cnt;
if(val > 1) a.push({cnt, val / 2});
a.pop();
++r;
}
print(r);
}
return 0;
}

1399E2: 同E1,只是贪心的时候,枚举费用为2的边的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
using LL = long long;
class LinkStar {
public:
std::vector<int> head, nxt, to, c;
std::vector<LL> w;
LinkStar(int n) {
nxt.clear();
to.clear();
head = std::vector<int>(n + 1, -1);
}
void addedge(int u, int v, LL val, int cost) {
nxt.emplace_back(head[u]);
head[u] = to.size();
to.emplace_back(v);
w.emplace_back(val);
c.emplace_back(cost);
}
};
int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int cas;
std::cin >> cas;
while (cas--) {
int n;
LL s;
std::cin >> n >> s;
LinkStar diag(n);
for (int i = 1, u, v, c; i < n; ++i) {
LL w;
std::cin >> u >> v >> w >> c;
diag.addedge(u, v, w, c - 1);
diag.addedge(v, u, w, c - 1);
}
std::vector<std::tuple<int, int, LL>> a;
bool vis[n + 1] = {};
std::function<int(int, LL, int)> dfs = [&](int u, LL val, int cost) -> int {
vis[u] = true;
int cnt = 0;
for (int i = diag.head[u]; ~i; i = diag.nxt[i]) {
int v = diag.to[i];
if (!vis[v]) cnt += dfs(v, diag.w[i], diag.c[i]);
}
cnt = std::max(cnt, 1);
s -= val * cnt;
a.push_back({cost, cnt, val});
return cnt;
};
dfs(1, 0, 0);
std::vector<LL> q[2];
for (auto [cost, cnt, val] : a) {
while (val) {
q[cost].emplace_back((val + 1) / 2 * cnt);
val >>= 1;
}
}
std::sort(q[0].begin(), q[0].end(), std::greater<>());
std::sort(q[1].begin(), q[1].end(), std::greater<>());
int r = 1e9;
for (auto &x : q[0]) s += x;
for (int i = 0, j = q[0].size(); i <= q[1].size(); ++i) {
while (j > 0 && s - q[0][j - 1] >= 0) {
s -= q[0][--j];
}
if (s >= 0) r = std::min(r, 2 * i + j);
if (i != q[1].size()) s += q[1][i];
}
print(r);
}
return 0;
}

1399F : 区间dp问题

f[m] 表示从a[i]的左边界到,m的区间个数(是被一个大的覆盖了的区间,size一般不为1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// follow the idea of Jiangly
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int cas;
std::cin >> cas;
while (cas--) {
int n;
std::cin >> n;
std::vector<std::pair<int, int>> a(n);
std::vector<int> v;
for (auto &[l, r] : a) std::cin >> l >> r;
a.push_back({1, 2e5});
for (auto &[l, r] : a) {
v.emplace_back(l);
v.emplace_back(r);
}
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
for (auto &[l, r] : a) {
l = std::lower_bound(v.begin(), v.end(), l) - v.begin();
r = std::lower_bound(v.begin(), v.end(), r) - v.begin();
}
std::sort(a.begin(), a.end(), [](const auto &lhs, const auto &rhs) {
if (lhs.first == rhs.first) return lhs.second < rhs.second;
return lhs.first > rhs.first;
});
int dp[n + 1] = {};
for (int i = 0; i <= n; ++i) {
std::vector<int> f(a[i].second + 1);
int mx = 0, x = a[i].first - 1;
for (int j = i - 1; j >= 0; --j) {
if (a[j].second > a[i].second) continue;
while (x + 1 < a[j].first) mx = std::max(mx, f[++x]);
f[a[j].second] = std::max(f[a[j].second], dp[j] + mx);
}
for (auto &t : f) mx = std::max(mx, t);
dp[i] = 1 + mx;
}
print(dp[n] - 1);
}
return 0;
}

1389F:二分图

emorgan5289大佬的代码以及解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

multiset<array<int, 3>> a;
multiset<int> s;

int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
for (int i = 0; i < n; i++) {
int l, r, t; cin >> l >> r >> t;
a.insert(t-1 ? array{r, 1, -l} : array{l, 0, -r});
}
for (auto& [_, t, x] : a) {
if (t && s.upper_bound(x) != s.begin())
s.erase(--s.upper_bound(x)), n--;
if (!t) s.insert(x);
}
cout << n << "\n";
}

1384D:两个人轮流取$n$个数,比较它们取的数的异或值,较大的赢

记s为n个数的异或值,如果$s = 0$,那么显然平局,否则看与$s$ 的最高位 异或不为0的数的人数 cnt,显然这个个数是奇数,所以为$1 \mod 4$ ,那么先手赢,否则,我们看 $n - cnt$ 是否为奇数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int cas;
std::cin >> cas;
while (cas--) {
int n;
std::cin >> n;
std::vector<int> a(n);
for (auto &x : a) std::cin >> x;
int sum = 0;
for (auto &x : a) sum ^= x;
if (sum == 0) {
std::cout << "DRAW\n";
} else {
int k = std::__lg(sum);
int cnt = 0;
for (auto &x : a) if((x >> k) & 1) ++cnt;
if (cnt % 4 == 1 || (n - cnt) % 2 == 1) {
std::cout << "WIN\n";
} else {
std::cout << "LOSE\n";
}
}
}
return 0;
}

1384B:很有意思的一道模拟题,我也不知道为什么我要想这么久,太菜了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int cas;
std::cin >> cas;
while (cas--) {
int n, k, len;
std::cin >> n >> k >> len;
int d[n];
bool flag = false;
for (int i = 0; i < n; ++i) {
std::cin >> d[i];
if (d[i] > len) flag = true;
else d[i] = len - d[i];
}
if (flag) {
std::cout << "No\n";
continue;
}
int l = 0, r = k;
for (int i = 0; i < n; ++ i){
int li = std::min(k, d[i]);
int ri = std::max(k, 2 * k - d[i]);
if (r < 2 * k) {
l = 0;
r = std::max(r + 1, ri);
} else if (++l > li) flag = true;
l = std::min(l, k);
if (d[i] >= k) r = k;
}
std::cout << (flag ? "No" : "Yes") << std::endl;
}
return 0;
}

洛谷U122053 选择题经典问题:每个人说另一个人是不是好人, 好人只说真话,坏人只说慌话,输出有多少种可能的情况,并输出可能的情况下,最多的好人和最少的好人数。

val[i] 表示第$i$ 个人是否为好人, w[i,j] 表示$i$ 说$j$ 是好人还是坏人,或 $j$ 说$i$ 是好人还是坏人,那么必然 val[i] ^ val[j] = !w[i,j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// https://www.luogu.com.cn/problem/U122053?contestId=31675
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;
const LL M = 998244353;
const int N = 1e6 + 2;
int head[N], val[N], cnt, nxt[2 * N], to[2 * N];
bool w[2 * N];
void init() {
cnt = -1;
memset(head, -1, sizeof (head));
memset(val, -1, sizeof (val));
}
void addedge(int u, int v, bool flag) {
nxt[++cnt] = head[u];
head[u] = cnt;
to[cnt] = v;
w[cnt] = flag;
}

// 此题BFS更好,不过DFS也能过
std::pair<int, int> dfs(int u, int flag) {
val[u] = flag;
int r1 = 1, r2 = flag;
for (int i = head[u]; ~i; i = nxt[i]) {
int v = to[i];
if (val[v] != -1) {
if (val[v] != (val[u] ^ w[i])) return {-1, 0};
} else {
auto [vr1, vr2] = dfs(v, val[u] ^ w[i]);
if (vr1 == -1) return {-1, 0};
r1 += vr1;
r2 += vr2;
}
}
return {r1, r2};
}

std::pair<int, int> bfs(int iu, int iflag) {
std::queue<std::pair<int, int>> q;
q.push({iu, iflag});
int r1 = 0, r2 = 0;
while (!q.empty()) {
auto [u, flag] = q.front();
q.pop();
if (val[u] != -1) continue;
val[u] = flag;
++r1;
r2 += flag;
for (int i = head[u]; ~i; i = nxt[i]) {
int v = to[i];
if (val[v] != -1) {
if (val[v] != (val[u] ^ w[i])) return {-1, 0};
} else q.push({v, val[u] ^ w[i]});
}
}
return {r1, r2};
}

LL powMod(int n) {
LL r = 1, x = 2;
while (n) {
if (n & 1) r = r * x % M;
n >>= 1; x = x * x % M;
}
return r;
}

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
init();
int n;
std::cin >> n;
for (int i = 1, x; i <= n; ++i) {
bool flag;
std::cin >> x >> flag;
addedge(i, x, !flag);
addedge(x, i, !flag);
}
int now = 0, mx = 0, mi = 0;
for (int i = 1; i <= n; ++i) if (val[i] == -1) {
// auto [r1, r2] = dfs(i, 1);
auto [r1, r2] = bfs(i, 1);
if (r1 == -1) {
std::cout << "No answer\n";
return 0;
}
++now;
mx += std::max(r2, r1 - r2);
mi += std::min(r2, r1 - r2);
}
std::cout << powMod(now) << std::endl;
std::cout << mx << std::endl;
std::cout << mi << std::endl;
return 0;
}

洛谷U122055 出生点 :简单包容排斥

仅考虑 $x$-轴

当$k=0$ 时,那么距离之和就是

然后我们减去 $k$ 个障碍点和其它所有点之间的距离

再加上$k$个障碍点之间的距离

不妨按照$x$-轴排序,然后把前缀和sa[i]求一下,再依次计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;
const LL M = 1e9 + 7;
const LL inv2 = (M + 1)/2;
const LL inv6 = (M + 1)/6;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
LL n, m;
int k;
std::cin >> n >> m >> k;
LL a[k], b[k];
for (int i = 0; i < k; ++i) {
std::cin >> a[i] >> b[i];
}
std::sort(a, a + k);
std::sort(b, b + k);
LL sa[k] = {a[0]}, sb[k] = {b[0]};
for (int i = 1; i < k; ++ i) {
sa[i] = sa[i - 1] + a[i];
sb[i] = sb[i - 1] + b[i];
}

auto f = [](LL m, LL n) -> LL {
return m * m % M * (n - 1) % M * n % M * (n + 1) % M;
};
LL r0 = (f(m, n) + f(n, m)) * inv6 % M;

LL r1 = 0;
for (int i = 0; i < k; ++ i) {
r1 += ((a[i] - 1) * a[i] + (n - a[i] + 1) * (n - a[i])) % M;
}
r1 = r1 % M * m % M * inv2 % M;

LL r2 = 0;
for (int i = 0; i < k; ++ i) {
r2 += ((b[i] - 1) * b[i] + (m - b[i] + 1) * (m - b[i])) % M;
}
r2 = r2 % M * n % M * inv2 % M;

LL r3 = 0;
for (int i = 0; i < k; ++i) {
r3 += (sa[k - 1] - sa[i] - a[i] * (k - 1 - i)) % M;
r3 += (sb[k - 1] - sb[i] - b[i] * (k - 1 - i)) % M;
}
r3 %= M;

LL r = (r0 - r1 - r2 + r3) % M;
if(r < 0) r += M;
std::cout << r << std::endl;

return 0;
}

洛谷U122054 强迫症 : 圆上n个点构成的无交错边的图的个数 $f_n$

$f_0 = 1, f_1 = 1, f_2 = 2, f_3 = 8$,考虑$n+1$个点,如果第$n+1$点与其他点没有边相连有$f_n$ 种,如果相连,设最小的数为$i$, 那么一边有$f_i$ 种(注意到$n+1$这个节点可以不管,因为它不跟小于$i$的节点相连),另一边有$\frac{f_{n+2-i}}{2}$,即

化简一下,可知

我们令 $g_n = f_{n+1}$,则 $g_n = 2g_{n-1} + \sum_{i=2} ^ n g_{i-1} g_{n+1-i} = 2 g_{n-1} + \sum_{i=1} ^{n-1} g_i g_{n-i}$,所以 $g_n = \frac{2}{3} g_{n-1} + \frac{1}{3} \sum_{i=0} ^n g_i g_{n-i}$。考虑$g_n$ 的生成函数$g(z)$:

因此$\frac{1}{3} g^2(z) + (\frac{2}{3} z - 1) g(z) + \frac{2}{3} = 0$,从而 $g(z) = \frac{3-2z \pm \sqrt{1 - 12 z + 4z^2}}{2}$, 由$g_1 = 2$ 知 $g(z) = \frac{3-2z - \sqrt{1 - 12 z + 4z^2}}{2}$,从而$f(z) = f_0 + z g(z) = 1 + \frac{3}{2} z - z^2 - \frac{z}{2} \sqrt{1 - 12 z + 4 z^2}$。

因此 $(n + 1)g_{n+1} - 12 n g_n + 4(n-1)g_{n-1} = 4 g_{n-1} - 6 g_n$,整理得到 $(n+1)g_{n+1} = (12 n - 6) g_n - (4n-8)g_{n-1}$

从而 $(n+1)f_{n+2} = (12 n - 6) f_{n+1} - (4n - 8) f_n$,即递推公式 $f_{n} = \frac{ (12 n - 30) f_{n-1} - (4 n - 16) f_{n-2} }{n-1}$。

所以原问题的答案就是

仅看分子:

如果我们定义 $b_i = a_{n-1-i}$,$c_t = \sum_{i = 0} ^{t} a_{t-i} b_{i} = \sum_{i = 0} ^{t} a_{i} b_{t-i} = \sum_{i = 0} ^{t} a_{i} a_{n-1-(t-i)}$,则$c_{n-t} = \sum_{i = 0} ^{n-t} a_{i} a_{n-1-(n-t-i)} = \sum_{i = 0} ^{n-t} a_{i} a_{i+t-1}$ 。即答案为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// https://www.luogu.com.cn/problem/U122054?contestId=31675
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

const LL M = 998244353, ROOT = 3;
LL powMod(LL x, LL n) {
LL r(1);
while (n) {
if (n & 1) r = r * x % M;
n >>= 1;
x = x * x % M;
}
return r;
}
void bitreverse(std::vector<LL> &a) {
for (int i = 0, j = 0; i != a.size(); ++i) {
if (i > j) std::swap(a[i], a[j]);
for (int l = a.size() >> 1;
(j ^= l) < l; l >>= 1);
}
}
void nft(std::vector<LL> &a, bool isInverse = false) {
LL g = powMod(ROOT, (M - 1) / a.size());
if (isInverse) {
g = powMod(g, M - 2);
LL invLen = powMod(LL(a.size()), M - 2);
for (auto & x: a) x = x * invLen % M;
}
bitreverse(a);
std::vector<LL> w(a.size(), 1);
for (int i = 1; i != w.size(); ++i) w[i] = w[i - 1] * g % M;
auto addMod = [](LL x, LL y) {
return (x += y) >= M ? x -= M : x;
};
for (int step = 2, half = 1; half != a.size(); step <<= 1, half <<= 1) {
for (int i = 0, wstep = a.size() / step; i != a.size(); i += step) {
for (int j = i; j != i + half; ++j) {
LL t = (a[j + half] * w[wstep * (j - i)]) % M;
a[j + half] = addMod(a[j], M - t);
a[j] = addMod(a[j], t);
}
}
}
}
std::vector<LL> mul(std::vector<LL> a, std::vector<LL> b) {
int sz = 1, tot = a.size() + b.size() - 1;
while (sz < tot) sz *= 2;
a.resize(sz);
b.resize(sz);
nft(a);
nft(b);
for (int i = 0; i != sz; ++i) a[i] = a[i] * b[i] % M;
nft(a, 1);
a.resize(tot);
return a;
}

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<LL> a(n);
for (auto &x : a) std::cin >> x;
std::vector<LL> b(a.rbegin(),a.rend());
auto c = mul(a, b);

LL inv[n] = {0, 1}, f[n + 1] = {1, 1};
for (int i = 2; i <= n; ++i) inv[i] = (M - M / i) * inv[M % i] % M;
for (int i = 2; i <= n; ++i) {
f[i] = ((12 * i - 30)* f[i - 1] - (4 * i - 16) * f[i - 2]) % M * inv[i - 1] % M;
if (f[i] < 0) f[i] += M;
}

LL r = 0;
for (int i = 2; i <= n; ++i) {
r += f[i] * f[n - i + 2] % M * c[n - i] % M;
}
r = r * inv[4] % M * powMod(f[n], M - 2) % M;
std::cout << r << std::endl;

return 0;
}

1382D :0-1背包问题

注意到一段选择了a[i] 那么后来连续小于a[i]的都要被选择。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int cas;
std::cin >> cas;
while (cas--) {
int n, maxn;
std::cin >> n;
int a[2 * n];
for (int i = 0; i < 2 * n; ++i) {
std::cin >> a[i];
}
bool dp[n + 1] = {1};
for (int i = 0, j = 0; i < 2 * n; i = j) {
while (j < 2 * n && a[j] <= a[i]) ++j;
int len = j - i;
for (int k = n; k >= len; --k) {
dp[k] |= dp[k - len];
}
}
std::cout << (dp[n] ? "YES" : "NO") << std::endl;
}
return 0;
}

1382C :设 f: 0-1string ---> 0-1string将字符串0换成1,1换成0,然后倒序。给定长度为n的字符串a,b。每次可以改变a的前缀,给出一种方案(不超过3n,或者不超过2n)

  • 注意到取n再取1,再去n,这样只会改变最后一个,所以就给出了不超过3n的方案
  • 可以先将a变成0,再把b变成0的方案反序,然后再复合。变成0的做法就是一直让前缀都是1,或者都是0

方案一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int cas;
std::cin >> cas;
while (cas--) {
int n;
std::string a, b;
std::cin >> n >> a >> b;
std::vector<int> q;
while (--n >= 0) {
if(a[n] != b[n]) {
q.emplace_back(n + 1);
q.emplace_back(1);
q.emplace_back(n + 1);
}
}
std::cout << q.size();
for (auto &x : q) std::cout << " " << x;
std::cout << std::endl;
}
return 0;
}

方案二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int cas;
std::cin >> cas;
while (cas--) {
int n;
std::string a, b;
std::cin >> n >> a >> b;
a += '0'; b += '0';
std::vector<int> qa, qb;
for (int i = 1; i <= n; ++i) {
if (a[i] != a[i-1]) qa.emplace_back(i);
if (b[i] != b[i-1]) qb.emplace_back(i);
}
qa.insert(qa.end(), qb.rbegin(), qb.rend());
std::cout << qa.size();
for (auto &x : qa) std::cout << " " << x;
std::cout << std::endl;
}
return 0;
}

百度之星2020初赛1008:数论函数题

已知,$ f(n) = \displaystyle \sum_{d|n} d \cdot [\gcd(d,\frac{n}{d}) == 1] $,求 $ \displaystyle \sum_{n=1} ^N f(n) $

首先

其中$ g(n) = \displaystyle \sum_{d|n} d $,所以

其中 $ h(n) = \sum_{i = 1} ^n g(i) = \sum_{d=1}^n d \lfloor \frac{n}{d} \rfloor $,求$h(n)$ 有众所周知的$ O (\sqrt{n}) $ 的算法,所以总时间复杂度为 $ O(\sum \frac{\sqrt{N}}{l}) = O(\sqrt{N} \log N) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using LL = long long;
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
const LL M = 1e9 + 7;
const int N = 1e6 + 2;

int mu[N];
void initmu() {
mu[1] = 1;
for (int i = 1; i < N; ++i) {
for (int j = i * 2; j < N; j += i) {
mu[j] -= mu[i];
}
}
}
int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
initmu();
auto f = [](LL n) {
LL ret = 0;
for (LL l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ret += ((n / l) % M) * ((l + r) % M) % M * ((r - l + 1) % M) % M;
}
return ret % M * ((M + 1) / 2) % M;
};
int cas;
std::cin >> cas;
while (cas--) {
LL n, ans = 0;
std::cin >> n;
for (LL i = 1; i * i <= n; ++i) {
if (mu[i] == 0) continue;
ans += (M + mu[i]) * i % M * f(n / (i * i)) % M;
}
std::cout << ans%M << std::endl;
}
return 0;
}

另外一种计算思考:考虑每一个 $d$ 对答案的贡献,则

Atcode:经典生成函数题

题目很容易转化成,满足所有$(a_1+\cdots+a_5)+2(b_1+\cdots+b_5) \leq N$的$a_1 \cdots a_5$之和,其中$a_i,b_i$ 均为非负整数

我一开始把$5$ 看作变量,从1,2,3,一直推出5的公式,贼麻烦。后来 querty20002 给出了生成函数做法的题解。答案唯一的依赖于$N$,即可认为答案是关于$N$的数列,那么它的生成函数即为:

所以答案就是 $\sum_{i=N\%2}^{11} \binom{11}{i} \binom{\frac{N-i-5}{2}+15}{15}$ ,所以我们选择Python交题0.0

1
2
3
4
5
6
7
8
9
import math
M = 1000000007
T = int(input())
for i in range(T):
n = int(input())
r = 0
for i in range((n-5)%2,12,2):
r+=math.comb(11,i)%M*math.comb((n-i+25)//2,15)%M;
print(r%M)

或者C++也行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr LL M = 1e9+7;
LL inv(LL a,LL p){
return a==1?1:(p-p/a)*inv(p%a,p)%p;
}
LL C(LL n, int k){
if(n<k) return 0;
if(k==0) return 1;
LL r = 1;
for(int i=0;i<k;++i){
r = r*(n-i)%M*inv(i+1,M)%M;
}
return r;
}
int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas;
cin >> cas;
while(cas--){
LL n ,r = 0;
cin >> n;
for(int i=(n+1)%2;i<=11;i+=2) {
r+=C(11,i)*C((n-i+25)/2,15)%M;
}
cout<<r%M<<endl;
}
return 0;
}

1215E:给定长度为$n$数据范围$[1,20]$的数组,求最少交换相邻位置元素使得相同的数字都紧挨着

参考 cf1215e,注意到交换两个数字,其它数字的相对位置不发生改变

状态dp:设dp[mask] 表示状态为 mask的最小交换次数,其中mask&(1<<i)=1 表示值为1+i的数已经被考虑到了。所以$dp[2^{20}-1]$ 就是我们要的结果。状态转移

其中cnt(j,k) 表示把 所有的 j 移动到k 前面需要的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
#define watch(x) cout << (#x) << " is " << (x) << endl
constexpr int N = 20;
LL cnt[N][N],s[N],dp[1<<N];

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
cin>>n;
for(int i=0,x;i<n;++i){
cin>>x;--x;
for(int j=0;j<N;++j) if(x!=j){
cnt[x][j] += s[j];
}
++s[x];
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=0;i!=(1<<N);++i){
for(int j=0;j<N;++j) if(!(i&(1<<j))){
LL s = dp[i];
for(int k=0;k<N;++k) if(i&(1<<k)){
s+=cnt[j][k];
}
dp[i|(1<<j)] = min(dp[i|(1<<j)],s);
}
}
cout<<dp[(1<<N)-1]<<endl;
return 0;
}

以上代码基本copy WZYYN代码

1228E:(二维)包容排斥原理

在 $n \times n$ 的格子中填不超过$k$的正整数,使得每行每列的最小值都为1的填法方案数。下图是官方题解

1228E

无论是dp还是包容排斥,定义好状态是最重要的。

1148B:在一次转机的旅行中,取消k个航班,使得旅客最晚达到终点

一开始被卡住了,想一下子吃个胖子0.0 其实枚举起点取消的航班数,然后取最大值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n,m,ta,tb,k;
cin>>n>>m>>ta>>tb>>k;
int a[n],b[m];
for(int i=0;i<n;++i){
cin>>a[i];
a[i]+=ta;
}
for(int i=0;i<m;++i) cin>>b[i];
if(n<=k||m<=k){
cout<<-1<<endl;
}else{
int ans = 0;
for(int i=0;i<=k;++i){
int id = lower_bound(b,b+m,a[i])-b;
if(id+k-i>=m){
ans = -1;break;
}
ans = max(ans,tb+b[id+k-i]);
}
cout<<ans<<endl;
}
return 0;
}

1251F: 组成周长固定的先单调递增后单调递减的序列。

很快就能想到周长为 $2(L+x)$,其中$L,x$ 分别表示序列最大值和长度。一开始想不明白的地方在于,如果有两个长度相同的怎么计数,后来发现相同的可以标记一个只能放左边,另一个只能放右边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr LL M = 998244353,ROOT=3;
LL powmod(LL x,LL n){
LL r(1);
while(n){
if(n&1) r=r*x%M;
n>>=1; x=x*x%M;
}
return r;
}
void bitreverse(vector<LL> &a){
for(int i=0,j=0;i!=a.size();++i){
if(i>j) swap(a[i],a[j]);
for(int l=a.size()>>1;(j^=l)<l;l>>=1);
}
}
void nft(vector<LL> &a,bool isInverse=false){
LL g = powmod(ROOT,(M-1)/a.size());
if(isInverse){
g = powmod(g,M-2);
LL invLen = powmod(LL(a.size()),M-2);
for(auto &x:a) x=x*invLen%M;
}
bitreverse(a);
vector<LL> w(a.size(),1);
for(int i=1;i!=w.size();++i) w[i] = w[i-1]*g%M;
auto addMod = [](LL x,LL y){return (x+=y)>=M?x-=M:x;};
for(int step=2,half = 1;half!=a.size();step<<=1,half<<=1){
for(int i=0;i!=a.size();i+=step){
for(int j=0;j!=half;++j){
LL t = (a[i+j+half]*w[a.size()/step*j])%M;
a[i+j+half]=addMod(a[i+j],M-t);
a[i+j]=addMod(a[i+j],t);
}
}
}
}
vector<LL> mul(vector<LL> a,vector<LL> b){
int sz=1,tot = a.size()+b.size()-1;
while(sz<tot) sz*=2;
a.resize(sz);b.resize(sz);
nft(a);nft(b);
for(int i=0;i!=sz;++i) a[i] = a[i]*b[i]%M;
nft(a,1);
a.resize(tot);
return a;
}
constexpr int N = 3e5+2;
LL fac[N],ifac[N];
void init(){
fac[0]=1;
for(int i=1;i<N;++i) fac[i] = fac[i-1]*i%M;
ifac[N-1] = powmod(fac[N-1],M-2);
for(int i=N-1;i;--i) ifac[i-1] = ifac[i]*i%M;
}
LL binom(int n,int k){
return fac[n]*ifac[k]%M*ifac[n-k]%M;
}

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
init();
int n,k,x,q;
cin>>n>>k;
int cnt[N] = {};
for(int i=0;i<n;++i){
cin>>x;
++cnt[x];
}
vector<LL> ans(2*N);
while(k--){
cin>>x;
int c1=0,c2=0;
for(int i=1;i<x;++i){
if(cnt[i]>1) c2+=2;
else if(cnt[i]==1) ++c1;
}
vector<LL> a(c1+1),b(c2+1);
auto inc = [](LL &a,LL b){if((a+=b)>=M) a-=M;};
LL p2=1;
for(int i=0;i<=c1;++i){
a[i] = binom(c1,i)*p2%M;
inc(p2,p2);
}
for(int i=0;i<=c2;++i) b[i] = binom(c2,i);
a = mul(a,b);
for(int i=0;i!=a.size();++i){
inc(ans[i+x+1],a[i]);
}
}
cin>>q;
while(q--){
cin>>x;
cout<<ans[x/2]<<endl;
}
return 0;
}

1251E: 花最少的钱,让所有人都投票给自己(选民跟风且贪财)

我们按照$m$ 分层,然后从大到小记录白嫖的人,然后实在没法白嫖的,就取消费最少的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas;
cin>>cas;
while(cas--){
int n;
cin>>n;
vector<int> a[n];
for(int i=0,x,y;i<n;++i){
cin>>x>>y;
a[x].emplace_back(y);
}
LL r = 0;
// q 也可以用 multiset 取代,会稍微快点
priority_queue<int,vector<int>,greater<int>> q; //白嫖的votes
for(int i=n-1;i>=0;--i){
for(auto &x:a[i]) q.push(x);
while(n-q.size()<i){
r+=q.top();
q.pop();
}
}
cout<<r<<endl;
}
return 0;
}

1375D: MEX once more,通过修改数组的某一个值成mex,使得数组最终非降。

不妨最终变成0~n-1,这是不好想的,特别是紧张的比赛的时候

如果当前mex = n 即数列正好是一个排列,此时选择任意一个a[i]!=i 的位置,让 a[i]=n,否则 mex < n 此时令a[mex]=n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin)
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas;
cin>>cas;
while(cas--){
int n;
cin>>n;
int a[n],v[n],c[n+1]={},step=n;
for(int i=0;i<n;++i){
cin>>a[i];
++c[a[i]];
v[i] = (a[i]==i);
if(v[i]) --step;
}
vector<int> q;
int mex = 0,l=0;
while(c[mex]) ++mex;
while(step--){
if(mex == n){
while(v[l]) ++l;
q.push_back(l+1);
--c[a[l]];
++c[mex];
mex = a[l];
a[l] = n;
}
++c[mex];
int nmex = mex;
if(--c[a[mex]]==0&&a[mex]<mex){
nmex = a[mex];
}
a[mex] = mex;
v[mex] = true;
q.push_back(mex+1);
mex = nmex;
while(c[mex]) ++mex;
}
cout<<q.size()<<endl;
for(auto &x:q) cout<<x<<" ";
cout<<endl;
}
return 0;
}

上面算法过度追求效率而丢失了可读性。其实可以缩短一半代码量

1119C: 选取4个角,反位,使得A矩阵变成B矩阵

把A,B异或到A,然后就转化成A矩阵变成0矩阵的方案了。这个时候一行行的处理就搞定了!(一开始就是没思路,后来灵光一闪)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 502;
int a[N][N];
bool f(int n,int m){
for(int i=1;i<=n;++i){
int cnt = 0;
for(int j=1;j<=m;++j){
if(a[i][j]){
++cnt;
if(i!=n){
a[i+1][j]^=a[i][j];
}
}
}
if(cnt&1) return false;
if(i==n) return cnt==0;
}
}
int main(){
//freopen("in","r",stdin)
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin>>a[i][j];
}
}
for(int i=1;i<=n;++i){
for(int j=1,x;j<=m;++j){
cin>>x;
a[i][j]^=x;
}
}
cout<<(f(n,m)?"Yes":"No")<<endl;
return 0;
}

1110:打麻将0.0

就是计算最容易听牌的数量,ABC和AAA的个数和

考虑ans[n][i][j] 表示只考虑小于n的情况下,有 i(n-1,n)jn 剩余的答案。由于三个 (n,n+1,n+2) 可以转化成(n,n,n),(n+1,n+1,n+1),(n+2,n+2,n+2),所以i,j都小于3。且 ans[n+1][j][k] = max(ans[n][i][j]+i+(c[n+1]-i-j-k)/3),最后可以优化一下空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin)
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cnt,m;
cin>>cnt>>m;
int c[m+1]={};
for(int i=0,x;i<cnt;++i){
cin>>x;
++c[x];
}
int dp[3][3],new_dp[3][3];
memset(dp,-1,sizeof(dp));
dp[0][0] = 0;
for(int n=0;n<m;++n){
memset(new_dp,-1,sizeof(new_dp));
for(int i=0;i<3;++i){
for(int j=0;j<3;++j){
for(int k=0;k<3;++k){
if(i+j+k<=c[n+1]&&dp[i][j]>=0){
new_dp[j][k] = max(new_dp[j][k],dp[i][j]+i+(c[n+1]-i-j-k)/3);
}
}
}
}
swap(new_dp,dp);
}
cout<<dp[0][0]<<endl;
return 0;
}

1371E:给定长为$n$的数组和素数$p$,记满足$x+i < a_{\sigma(i)},0\leq i<n$ 的排列个数为$f(x)$,输出所有$x$使得$p \not | n$

先排序,并且注意到 $x \in (\max a_i-n,\max a_i+n)$ 之间。

记$b_i$为数组中小于等于$i$ 的元素个数。则$f(x) = \prod\limits_{i=x}^{x+n-1} b_i-(i-x) = \prod\limits_{i=x}^{x+n-1} x-(i-b_i)$,所以我们预处理出 $i-b_i$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n,p;
cin>>n>>p;
int a[n];
for(int i=0;i<n;++i) cin>>a[i];
int mx = *max_element(a,a+n);
int bb[n*2+2]={};
int lx = mx-n;
int *b = bb - lx; // 黑科技,哈哈
for(int i=0;i<n;++i) ++b[max(lx,a[i])];
for(int i=1;i<n*2+2;++i) bb[i]+=bb[i-1];
int mp[n]={};
auto modp = [](int x,int p){
x%=p;
return x<0?x+p:x;
};
for(int i=lx;i<=mx;++i){
++mp[modp(i-b[i],p)];
}
vector<int> q;
for(int i=lx;i<=mx;++i){
if(mp[modp(i,p)]==0){
q.emplace_back(i);
}
--mp[modp(i-b[i],p)];
++mp[modp(i+n-b[i+n],p)];
}
cout<<q.size()<<endl;
for(int i=0;i!=q.size();++i){
cout<<q[i]<<" \n"[i == q.size()-1];
}
return 0;
}

1245F:经典XOR 递归!

在区间[l,r)中找(a,b) 使得 $a+b = a \wedge b$的个数 $f(l,r)$。

显然,$f(x,x) = 0 \; (x\neq 0),\; f(2l,2r) = 3f(l,r)$,若$l$为奇数,那么 $f(l,r) = f(l+1,r) + 2(g(l,r)-g(l,l))-(l==0)$,若$r$ 为奇数,那么$f(l,r) = f(l,r-1) + 2(g(r-1,r)-g(r-1,l))-(r==1)$ 。其中 $g(x,n)$ 表示满足下式的$y$的个数:

通过比较$x,n$的二进制,$g(x,n)$ 的计算是容易计算的的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
function<int(int,int)> g = [&](int x ,int n)->int{
int ret = 1,zeros=0;
for(int i=1;i<=n;i<<=1){
if(n&i){
n^=i;
if(!(x&n)) ret += 1<<zeros;
}
if(!(x&i)) ++zeros;
}
return ret;
};
function<LL(int,int)> f = [&](int l ,int r)->LL{
if(l==r) return 0;
LL ret = 0;
if(l&1){
ret += (g(l,r)-g(l,l))*2-(l==0);
++l;
}
if(r&1){
ret += (g(r-1,r)-g(r-1,l))*2-(r==1);
--r;
}
return ret + 3*f(l/2,r/2);
};
int cas;
cin>>cas;
while(cas--){
int l,r;
cin>>l>>r;
cout<<f(l,r+1)<<endl;
}
return 0;
}

1373F:$f(x)$ 表示非负整数$x$的十进制表示的各位数之和。求最小的非负整数$x$ 使得 $\sum_{i=0} ^k f(x+i) = n$

由于$0 \leq k \leq 9$,也就是说$x,x+1,\cdots,x+k$,的个位数各不相同。我们可以枚举$x$的个位数,那么 $x/10,\cdots, (x+k)/10$,最多仅有两种取值。若只有一种,即没有进位(不能为9),那么直接就可以把$x$的位数和求出来,否则$x/10$的个数必为9。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e17+2;
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
auto csum = [](int a,int b){
return (a+b)*(b-a+1)/2;
};
auto f = [](int n){
LL r = 0,d = 1;
while(n>9){
r+=9*d;
d*=10;
n-=9;
}
return r+n*d;
};
auto g = [&](int a,int k,int n) -> LL{
LL r = 0,d = 1;
if(n<a) return inf;
while((n-a)%k){
n-=9*(k-a);
r+=d*9;
d*=10;
if(n<a) return inf;
}
return r+d*(f((n-a)/k+1)-1);
};
int cas;
cin>>cas;
while(cas--){
int n,k;
cin>>n>>k;
if(k==0){
cout<<f(n)<<endl;
continue;
}
if(k*(k-1)/2 > n){
cout<<-1<<endl;
continue;
}
LL r = inf;
for(int i=0;i<=9;++i){
if(i+k<=9){
int t = csum(i,i+k);
if(n>=t&&(n-t)%(k+1)==0) r = min(r,10*f((n-t)/(k+1))+i);
}else{
int t = csum(i,9)+csum(0,i+k-10);
if(n>=t) r = min(r,10*g(i+k-9,k+1,n-t)+i);
}
}
cout<<(r==inf? -1:r)<<endl;
}
return 0;
}

以上代码按照时间顺序(2020/6/25——now)倒序,以下代码按照时间顺序(2020/5/22 —— 2020/6/25)排序

1355B :贪心模仿加法进位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int a[N];
int getans(int n){
int ans = 0,x=0;
for(int i=1;i<=n;++i){
x+=a[i];
ans+=x/i;
x%=i;
}
return ans;
}

int main(){
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas,n,x;
cin>>cas;
while(cas--){
cin>>n;
for(int i=1;i<=n;++i) a[i]=0;
for(int i=0;i<n;++i){
cin>>x;
++a[x];
}
cout<<getans(n)<<endl;
}
return 0;
}

1354C :计算包含单位正$n$边形的最小正方形的边长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);

int main(){
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas,n;
cin>>cas;
cout.precision(10);
while(cas--){
cin>>n;
if(n&1){
double x = sqrt(1-cos((n/2)*pi/n));
double y = sqrt(1-cos((n/2+1)*pi/n));
cout<<(x+y)/2/sin(pi/2/n)<<endl;
}else cout<<1.0/tan(pi/2/n)<<endl;
}
return 0;
}

1354D :模拟操作: 加数字或删除第$k$小的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int s[N], Size;

int lowbit(int n) {
return n & (-n);
}
void add(int id, int p) {
while (id <= Size) {
s[id] += p;
id += lowbit(id);
}
}
int sum(int id) {
int r = 0;
while (id) {
r += s[id];
id -= lowbit(id);
}
return r;
}
int find(int k) {
int l = 0, r = Size;
while (r>l) {
int m = (l + r) >> 1;
if (sum(m) >= k) r = m;
else l = m+1;
}
return r;
}
void del(int k) {
add(find(k), -1);
}

int main() {
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int q, x;
while (cin >> Size >> q) {
for (int i = 1; i <= Size; ++i) s[i] = 0;
for (int i = 1; i <= Size; ++i) {
cin >> x;
add(x, 1);
}
while (q--) {
cin >> x;
if (x > 0) add(x, 1);
else {
del(-x);
}
}
int ans = find(1);
cout <<(sum(ans)>0?ans:0)<< endl;
}
return 0;
}

1354F :经典DP问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
const int N = 102;
int dp[N][N];
bool isin[N][N],chose[N];
using node = tuple<int,int,int>;
node q[N];
void getans(int n,int k){
for(int i=1;i<=n;++i){
dp[i][0] = dp[i-1][0]+(k-1)*get<2>(q[i]);
for(int j = 1;j<i && j<=k;++j){
int x = dp[i-1][j]+(k-1)*get<2>(q[i]);
int y = dp[i-1][j-1]+(j-1)*get<2>(q[i])+get<1>(q[i]);
if(x>y){
dp[i][j] = x;
isin[i][j] = false;
}else{
dp[i][j] = y;
isin[i][j] = true;
}
}
if(i<=k){
dp[i][i] = dp[i-1][i-1]+(i-1)*get<2>(q[i])+get<1>(q[i]);
isin[i][i] = true;
}
}
for(int i=n,j=k;i;--i){
if(isin[i][j]){
chose[i]=true;
--j;
}else{
chose[i]=false;
}
}
}

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas,n,k,a,b;
cin>>cas;
while(cas--){
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>a>>b;
q[i] = {i,a,b};

}
sort(q+1,q+n+1,[](const node & x, const node & y){
return get<2>(x)<get<2>(y);
});
cout<<(2*n-k)<<endl;
getans(n,k);
int last = 0;
for(int i=1;i<=n;++i){
if(chose[i]){
if(++last == k){
last = i;
break;
}
cout<<get<0>(q[i])<<" ";
}
}
for(int i=1;i<=n;++i){
if(!chose[i]) cout<<get<0>(q[i])<<" "<<-get<0>(q[i])<<" ";
}
cout<<get<0>(q[last])<<endl;
}
return 0;
}

1345F :经典二分,利用二阶偏导(离散偏导,即增量)是常量!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
LL k,x;
while(cin>>n>>k){
vector<LL> q;
for(int i=0;i<n;++i){
cin>>x;
q.push_back(x);
}
auto get = [](LL x ,LL mx){
LL l=0,r=x-1;
while(l<=r){
LL m=(l+r)>>1;
if(x-m*(m+1)*3 == mx) return make_pair(m,m+1);
if(x-m*(m+1)*3 > mx) l = m+1;
else r = m-1;
}
return make_pair(l,l);
};
LL l = -3e18-3e8, r = 1e9;
while(l<=r){
LL m = (l+r)>>1,x=0,y=0;
for(auto &i:q){
auto tmp = get(i,m);
x+=tmp.first;
y+=tmp.second;
}
if(x>k) l = m+1;
else if(y<k) r = m-1;
else{
y-=k;
for(auto &i:q){
auto tmp = get(i,m);
//cout<<endl<<tmp.first<<" "<<tmp.second<<endl;;
if(tmp.first<tmp.second && y-->0){
cout<<tmp.first<<" ";
}else{
cout<<tmp.second<<" ";
}
}
cout<<endl;
break;
}
}
}
return 0;
}

1325B:Set的用法举例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas,n,x;
cin>>cas;
while(cas--){
cin>>n;
set<int> q;
for(int i=0;i<n;++i){
cin>>x;
q.insert(x);
}
cout<<q.size()<<endl;
}
return 0;
}

1325D:(异或 )位运算:判断是否有$n$ 个数,异或和为$u$, 和为$v$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
LL u,v;
while(cin>>u>>v){
if(u>v||((v-u)&1)){
cout<<-1<<endl;
}else if(u == v){
if(u) cout<<1<<endl;
cout<<u<<endl;
}else{
v = (v-u)>>1;
if(u&v) cout<<3<<endl<<u<<" "<<v<<" "<<v<<endl;
else cout<<2<<endl<<u+v<<" "<<v<<endl;
}
}
return 0;
}

注意到 $a+b = a \wedge b + 2(a\&b)$,并且 $(a \wedge b) \& (a\&b) = 0$ 当且仅当 $ab=0$

1358D:给定区间最值问题,但是可以写的很漂亮

注意到区间最值一定在左或者右端点达到局部最大值(极值)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 4e5+102;
int n,n2;
LL a[N],b[N],s[N];
LL f(LL x){
return ((x+1)*x)>>1;
}
LL sumx(LL x){
int it = lower_bound(b,b+n2,x) - b;
// 这里注意是it, 比赛的时候没减,搞得怀疑人生
return s[it-1]+f(x-b[it-1]);
}
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
LL d;
cin>>n>>d;
n2=n<<1;
for(int i=0;i<n;++i){
cin>>a[i];
a[i+n] = a[i];
}
b[0] = a[0];s[0] = f(a[0]);
for(int i=1;i<n2;++i){
b[i]=b[i-1]+a[i];
s[i]=s[i-1]+f(a[i]);
}
LL ans = 0;
for(int i=0;i<n;++i){
ans = max(ans,sumx(b[i]+d-1)-s[i]+a[i]);
}
for(int i=n;i<n2;++i){
ans = max(ans,s[i]-sumx(b[i]-d));
}
cout<<ans<<endl;
return 0;
}

1358E:很有意思的数据处理题目,官方题解

注意到如果$k$ 满足答案,则$2k$也满足,所以不妨设$k> \lfloor \frac{n}{2} \rfloor$,另一方面题目中要求若$i> \lceil \frac{n}{2} \rceil$,$a_{i} = x$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e5+5;
LL a[N],s[N],m[N];
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
cin>>n;
int n2 = (n+1)>>1;
for(int i=1;i<=n2;++i){
cin>>a[i];
s[i] = s[i-1]+a[i];
}
LL x;
cin>>x;
for(int i=n2+1;i<=n;++i){
a[i]=x;
s[i]=s[i-1]+x;
}
for(int i=1;i<=n2;++i){
m[i+1] = min(m[i],x*i-s[i]);
}
for(int k=n2;k<=n;++k){
if(s[k]+m[n-k+1]>0){
cout<<k<<endl;
return 0;
}
}
cout<<-1<<endl;
return 0;
}

1359C: 读题被坑…(反正就是倒冷热水接近给定温度)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas;
cin>>cas;
while(cas--){
int h,t,c;
cin>>h>>c>>t;
h-=c;t-=c;
if(h>=2*t){
cout<<2<<endl;
}else{
LL n = (h-t)/(2*t-h);
auto f = [](LL n,int h,int t){
return (n+1)*(2*n+3)*h+(2*n+1)*(n+2)*h>(2*n+1)*(2*n+3)*t*2;
};
if(f(n,h,t)) ++n;
cout<<2*n+1<<endl;
}
}
return 0;
}

然后对于奇数项,单调递减趋于平均问题,然后判断的时候转化成整数的判断

1359D:线段树,但是由于数据特殊,可以不用线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e5+5;
int a[N];
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(NULL);
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
int ans=0;
for(int m=1;m<=30;++m){
int suml =0,sum=0,maxa = -31;
for(int i=1;i<=n;++i){
if(a[i]>m){
sum = suml = 0;
maxa = -31;
}else{
sum+=a[i];
//这里取全局最大是因为,我们枚举了最大值的可能
maxa = max(maxa,a[i]);
ans = max(ans,sum-suml-maxa);
//相当于前面是全0的部分删了!并且这样不会避免中间负的情况
suml = min(sum,suml);
}
}
}
cout<<ans<<endl;
return 0;
}

注意到 $-30<a_i<30 $

1359E:找到公式后就是模素数组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
using LL=long long;
const int N = 5e5+2;
const LL M = 998244353;
LL inv[N],frac[N];
LL powmod(LL x, LL n, LL p) {
LL r=1;
while(n) {
if(n&1) r=r*x%p;
n>>=1;
x=x*x%p;
}
return r;
}
void init(){
frac[0]=inv[0]=1;
for(int i=1;i<N;++i){
frac[i] = frac[i-1]*i%M;
}
inv[N-1] = powmod(frac[N-1],M-2,M);
for(int i=N-2;i;--i){
inv[i] = inv[i+1]*(i+1)%M;
}
}
LL C(int n,int m){
if(n<m) return 0;
if(n==m||m==0) return 1;
return frac[n]*inv[m]%M*inv[n-m]%M;
}

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(NULL);
int n,k;
cin>>n>>k;
init();
LL ans = 0;
for(int i=1;i<=n;++i){
int x = n/i;
if(x<k) break;
ans += C(x-1,k-1);
}
cout<<ans%M<<endl;
return 0;
}

先考虑$k=2$ 的情况知道 $a_1|a_2$,然后发现对于任意$k$,仅需 $a_1|a_i$ 即可。

1363E:有根数,互换子树的节点位数到预定值,dfs和图存储范例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
// head[u] 和 cnt 的初始值都为 -1
const int N = 2e5+2;
int a[N];
vector<int> g[N];
bool b[N],c[N];

tuple<int,int,LL> dfs(int u,int parent,int mn){
int l=0,r=0;
LL cost=0;
if(b[u]!=c[u]){
if(b[u]) ++l;
else ++r;
}
for(auto &v:g[u]){
if(v == parent) continue;
auto [sl,sr,scost] = dfs(v,u,min(mn,a[u]));
l+=sl;r+=sr;cost+=scost;
}
if(a[u]<mn){
int take = min(l,r);
cost += LL(a[u])*(take*2);
l -= take;
r -= take;
}
return {l,r,cost};
}

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n,u,v;
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i]>>b[i]>>c[i];
}
for(int i=1;i<n;++i){
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
auto [l,r,cost] = dfs(1,0,2e9);
cout<<(l||r?-1:cost)<<endl;
return 0;
}

上面代码写得呢,就很优雅,哈哈!

1361E :下面代码至今没过我也是没懂为什么!

模仿进制的操作,最后用其他代码过的题。多设几个变量没坏处的其实。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e6+2;
const LL M = 1e9+7;
LL a[N],p;
template<typename T,typename U>
T powmod(T x,U n,T p){
T r(1);
while(n){
if(n&1) r=r*x%p;
n>>=1; x=x*x%p;
}
return r;
}
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas,n;
cin>>cas;
while(cas--){
cin>>n>>p;
for(int i=1;i<=n;++i){
cin>>a[i];
}
if(p==1){
cout<<(n&1)<<endl;continue;
}
sort(a+1,a+n+1);
LL ans = 1;
while(n>1){
if(ans==0){
ans = 1;
}else{
if(a[n]==a[n-1]) --ans;
else{
while(a[n]>a[n-1]){
ans*=p;
--a[n];
if(ans>n) break;
}
if(a[n]!=a[n-1]) break;
--ans;
}
}
--n;
}
ans = ans%M*powmod(p,a[n],M)%M;
for(int i=1;i<n;++i){
ans-=powmod(p,a[i],M);
}
ans = (M+ans%M)%M;
cout<<ans<<endl;
}
return 0;
}

1349F :神奇的对应

我们称一个长度为$n$ 的序列$p$为好序列,如果对任意正整数$k>1$,存在 $ 1 \leq i < j \leq n $ 使得,$p_i = k-1, p_j = k$

存在好序列和长为$n$的排列一一对应:

  • 给定排列$a_1,a_2,\cdots, a_n$ , 相邻两个之间添加 >< ,那么$p_{a_i}$ 就定义为$a_1,\cdots,a_i$ 中 < 个数加一
  • 给定好序列$p$,从右到左依次标记出$1,2,…$ ,直到标记完所有数即得到了排列

因此好序列中最大值对应这排列中单调递减区间的个数!

答案要求的是:所有好序列中出现$k$的个数之和。

下次再写吧…

1365E:这题其实没啥,但是比赛的时候竟然把 | 想成了 ^ ,很烦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
while(cin>>n){
LL a[n];
for(int i=0;i<n;++i){
cin>>a[i];
}
sort(a,a+n,greater<LL>());
LL ans = a[0];
for(int i=0;i<n;++i){
if(2*a[i]<=a[0]) break;
for(int j=i+1;j<n;++j){
LL t = a[i]|a[j];
ans = max(ans,t);
for(int k=j+1;k<n;++k){
ans = max(ans,t|a[k]);
}
}
}
cout<<ans<<endl;
}
return 0;
}

1312D:计算满足条件的数列个数

计算满足下列条件的数列个数:

  • 数列项数为$n$,且每一项都是不超过$m$的正整数,$2\cdot 10^5 =N>m \geq n \geq 2$
  • 数列中有且仅有两项是相同的
  • 数列在$i$ 项前严格单调递增,$i$ 项后严格单调递减

我们枚举$i$ 的位置和$i$的值,以及相同的项,则显然有如下计算式

预处理一下阶乘和阶乘逆,我们就可以在 $O(N)$解决问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const LL M = 998244353;
const int N = 2e5+2;
LL powmod(LL a,LL n){
LL r(1);
while(n){
if(n&1) r=r*a%M;
n>>=1; a=a*a%M;
}
return r;
}
LL fac[N],ifac[N];
void init(){
fac[0]=1;
for(int i=1;i!=N;++i){
fac[i] = fac[i-1]*i%M;
}
ifac[N-1] = powmod(fac[N-1],M-2);
for(int i=N-2;~i;--i){
ifac[i] = ifac[i+1]*(i+1)%M;
}
}
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
init();
int n,m;
while(cin>>n>>m){
LL x=0,y=0;
for(int i=n-1;i<=m;++i){
x+=fac[i-1]*ifac[i-n+1]%M;
}
for(int i=2;i<n;++i){
y+=ifac[i-2]*ifac[n-i-1]%M;
}
cout<<(x%M)*(y%M)%M<<endl;
}
return 0;
}

但是官方题解给了一个更简单的方法

首先把$n=2$时无解,所以考虑$n>2$的情况,首先把所有用到的数字选好:$m \choose n-1$,然后选择好相同的数字:$n-2$,然后剩下的非最大的数,要么放在最大的数左边要么放在最大的数右边:$2^{n-3}$,即最终答案是${m \choose n-1}(n-2)2^{n-3}$

1312E:经典DP,解释放在 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1022;
const int inf = 0x3f3f3f3f;
int ans[502][N],b[502][N];

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n,x;
while(cin>>n){
memset(ans,inf,sizeof(ans));
cin>>x;
ans[0][x] = 1;
b[0][x]=0;
for(int i=1;i<n;++i){
cin>>x;
for(int j=1;j<N;++j){
if(ans[i-1][j]!=inf){
ans[i][x] = min(ans[i][x],ans[i-1][j]+1);
}
b[i][x]=i;
}
int s = i-1;
while(s>=0&&ans[s][x]!=inf){
ans[i][x+1] = ans[s][x];
b[i][x+1] = b[s][x];
s = b[s][x]-1;
++x;
}
}
int r = inf;
for(int i=1;i<N;++i){
r = min(r,ans[n-1][i]);
}
cout<<r<<endl;
}
return 0;
}

1295E题解,相当精彩的线段树实例

下面代码取自:jiangly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <algorithm>
#include <vector>
class SegmentTree {
private:
int n;
std::vector<long long> min, tag;
void add(int p, long long v) {
min[p] += v;
tag[p] += v;
}
void push(int p) {
add(2 * p, tag[p]);
add(2 * p + 1, tag[p]);
tag[p] = 0;
}
void pull(int p) {
min[p] = std::min(min[2 * p], min[2 * p + 1]);
}
void rangeAdd(int p, int l, int r, int x, int y, int v) {
if (l >= y || r <= x)
return;
if (l >= x && r <= y)
return add(p, v);
int m = (l + r) / 2;
push(p);
rangeAdd(2 * p, l, m, x, y, v);
rangeAdd(2 * p + 1, m, r, x, y, v);
pull(p);
}
public:
SegmentTree(int n) : n(n), min(4 * n), tag(4 * n) {}
void rangeAdd(int l, int r, int v) {
rangeAdd(1, 0, n, l, r, v);
}
long long getMin() {
return min[1];
}
};
int n;
std::vector<int> p, a, pos;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
p.resize(n);
a.resize(n);
pos.resize(n);
for (int i = 0; i < n; ++i) {
std::cin >> p[i];
--p[i];
pos[p[i]] = i;
}
for (int i = 0; i < n; ++i)
std::cin >> a[i];
SegmentTree t(n - 1);
for (int i = 0; i < n; ++i)
t.rangeAdd(pos[i], n - 1, a[pos[i]]);
long long ans = t.getMin();
for (int i = 0; i < n; ++i) {
t.rangeAdd(pos[i], n - 1, -a[pos[i]]);
t.rangeAdd(0, pos[i], a[pos[i]]);
ans = std::min(ans, t.getMin());
}
std::cout << ans << "\n";
return 0;
}

1295F:给定区间的非降序列概率(个数)

下面代码取自:jiangly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <algorithm>
#include <vector>
constexpr int P = 998'244'353;
int power(int a, int b) {
int res = 1;
while (b > 0) {
if (b & 1)
res = 1LL * res * a % P;
a = 1LL * a * a % P;
b >>= 1;
}
return res;
}
int n;
std::vector<int> l, r, v, inv, dp;
std::vector<std::vector<int>> c;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
l.resize(n);
r.resize(n);
v.reserve(2 * n);
inv.resize(n + 1);
for (int i = 1; i <= n; ++i)
inv[i] = power(i, P - 2);
int total = 1;
for (int i = 0; i < n; ++i) {
std::cin >> l[i] >> r[i];
++r[i];
v.push_back(l[i]);
v.push_back(r[i]);
total = 1LL * total * (r[i] - l[i]) % P;
}
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
for (int i = 0; i < n; ++i) {
l[i] = std::lower_bound(v.begin(), v.end(), l[i]) - v.begin();
r[i] = std::lower_bound(v.begin(), v.end(), r[i]) - v.begin();
}
c.assign(v.size() - 1, std::vector<int>(n + 1));
for (int i = 0; i < int(v.size()) - 1; ++i) {
c[i][0] = 1;
for (int j = 1; j <= n; ++j)
c[i][j] = 1LL * c[i][j - 1] * (j - 1 + v[i + 1] - v[i]) % P * inv[j] % P;
}
dp.resize(n + 1);
dp[0] = 1;
for (int i = int(v.size()) - 1; i >= 0; --i) {
for (int a = n - 1; a >= 0; --a) {
for (int b = a; b < n; ++b) {
if (i < l[b] || i >= r[b])
break;
dp[b + 1] = (dp[b + 1] + 1LL * dp[a] * c[i][b - a + 1]) % P;
}
}
}
std::cout << 1LL * dp[n] * power(total, P - 2) % P << "\n";
return 0;
}

1364C:已知 $a_i=MEX({b_1,\cdots,b_i})$ 为不出现在$b_1,\cdots,b_i$中的最小非负整数,在给定$0\leq a_i \leq i,a_i<a_{i+1}$的情况下,给出一种$b_i$的方案。

方案就是:设当前最大值为$n$,从尾部开始,先标记a[i] 的值被访问,然后看a[i]是否等于a[i-1],如果是就在没被访问的点中给一个最大给b[i],否则$b[i]=a[i-1]$。然后边界判断!i=1时,当作不等处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e5+2;
int a[N],b[N];
bool v[N];
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
int ma = n;
for(int i=n;i>0;--i){
v[a[i]]=1;
if(i==1||a[i]==a[i-1]){
while(ma>=0&&v[ma]) --ma;
v[ma] = true;
b[i] = ma--;
}else{
b[i]=a[i-1];
v[b[i]]=1;
}
}
for(int i=1;i<=n;++i){
cout<<b[i]<<" ";
}
cout<<endl;
return 0;
}

1353D:有趣的标准优先队列+BFS题目

初始值为0的长度为n的数组,每次在连续0中长度最大的那一段的中点编号,直到编完。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
struct Node{
int l,r;
bool operator<(const Node & A)const{
return (r-l)<(A.r-A.l)||((r-l)==(A.r-A.l)&&l>A.l);
}
Node(int _l,int _r){
l = _l;
r = _r;
}
};
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas;
cin>>cas;
while(cas--){
LL n;
cin>>n;
int a[n+1];
priority_queue<Node> q;
q.push({1,n});
int now=0;
while(!q.empty()){
auto u = q.top();
int l=u.l,r=u.r;
q.pop();
a[(l+r)/2] = ++now;
if(l==r) continue;
if((r-l)%2==0){
q.push(Node(l,(l+r)/2-1));
q.push(Node((l+r)/2+1,r));
}else{
q.push(Node((l+r)/2+1,r));
if(l<(l+r)/2) q.push(Node(l,(l+r)/2-1));
}
}
for(int i=1;i<=n;++i){
cout<<a[i]<<" \n"[i==n];
}
}
return 0;
}

1353E:在01序列中改变最小的位,使得其中的所有1都是连续的。

dp[i] 为使得前i位中1连续出现,且第i位为1的最小改变位数,状态转移就显然了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas;
cin>>cas;
while(cas--){
int n,k;
string a;
cin>>n>>k>>a;
auto solve = [](const string &s){
int n = s.length();
int all = count(s.begin(),s.end(),'1');
int s1=(s[0]=='1');
int ans = all-s1,res = 1-s1;
for(int i=1;i<n;++i){
int cur = (s[i]=='1');
s1+=cur;
res = 1-cur+min(res,s1-cur);
ans = min(ans,res+all-s1);
}
return all-ans;
};
int mx=0;
for(int i=0;i<k;++i){
string s;
for(int j=i;j<n;j+=k){
s+=a[j];
}
mx = max(mx,solve(s));
}
cout<<count(a.begin(),a.end(),'1')-mx<<endl;
}
return 0;
}

1367E:不难但是很有趣的数学题

在给定一些元素中取出最大数量构成一个k旋转不变的圈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas;
cin>>cas;
while(cas--){
int n,k;
string s;
cin>>n>>k>>s;
int c[26]={0};
for(auto &i:s) ++c[i-'a'];
sort(c,c+26,greater<int>());
auto check=[&](int m){
int d = __gcd(m,k);
int md = m/d;
int x = 0;
for(int i=0;i<26;++i){
x+=c[i]/md;
}
return x>=d;
};
while(!check(n)) --n;
cout<<n<<endl;
}
return 0;
}

1367F:给定规则最小步骤使得数列有序

只允许将数列中某一个数最前或者最后,问最少多少步使得数列有序。

我们称数列中两个数$a_i \leq a_j$是相接的,如果$i<j$ 且排好序后$a_i,a_j$ 相邻。那么我们的答案就是 $n-$ 最长相接子列的长度。

原因:首先它是一个可行的答案,其次答案的方案去掉数列中被移动的数,剩下的数必然是相接的!

因为数列中的数的大小并不影响结果,影响结果的是相对关系,因此可以通过预处理,让数列的取值范围是一个区间。

dp[i] 为以 $i$ 结尾的最长相接子列。状态转移是好写的。

如果数列中元素两两互异,会很简单,因为有相同元素的时候要考虑 0 1 0 2 这种数列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas;
cin>>cas;
while(cas--){
int n;
cin>>n;
int a[n],id[n];
for(int i=0;i<n;++i) cin>>a[i];
iota(id,id+n,0);
sort(id,id+n,[&](int &i,int &j){
return a[i]==a[j]?i<j:a[i]<a[j];
});
for(int i=0;i<n;++i){
a[id[i]] = i;
}
int dp[n],ans=0;
for(int i =0;i<n;++i){
dp[i] = 1;
if(a[i]>0 && id[a[i]-1]<i) dp[i] += dp[id[a[i]-1]];
ans = max(ans,dp[i]);
}
cout<<n-ans<<endl;
}
return 0;
}

否则,我们就要考虑$i$ 之前a[i]严格小的相接元的dp 最小值加上这些元的元素个数。

但是也可以直接求不用DP参考 jiangly的代码,直接找包含第$i$ 位最长的相接子列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
constexpr int N = 2e5;
int a[N], p[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int z;
std::cin >> z;
while (z--) {
int n;
std::cin >> n;
for (int i = 0; i < n; ++i)
std::cin >> a[i];
std::iota(p, p + n, 0);
std::sort(p, p + n, [&](int i, int j) {return a[i] < a[j] || (a[i] == a[j] && i < j);});
int ans = 0;
for (int l = 0, r; l < n; l = r) {
for (r = l + 1; r < n && p[r] > p[r - 1]; ++r)
;
int res = r - l;
if (l)
for (int i = l - 1; i >= 0 && a[p[i]] == a[p[l - 1]]; --i)
if (p[i] < p[l])
++res;
if (r < n)
for (int i = r; i < n && a[p[i]] == a[p[r]]; ++i)
if (p[i] > p[r - 1])
++res;
ans = std::max(ans, res);
}
for (int l = 0, m, r; l < n; l = m) {
for (m = l; m < n && a[p[m]] == a[p[l]]; ++m)
;
if (m == n)
break;
for (r = m; r < n && a[p[r]] == a[p[m]]; ++r)
;
for (int i = l, j = m; i < m; ++i) {
while (j < r && p[j] < p[i])
++j;
ans = std::max(ans, i + 1 - l + r - j);
}
}
std::cout << n - ans << "\n";
}
return 0;
}

1368B:简单的问题比赛的时候无语的想复杂了!然后就是参看tourist男神的优雅代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* author: tourist
* created: 18.06.2020 17:46:48
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
long long k;
cin >> k;
string s = "codeforces";
int n = (int) s.size();
vector<long long> a(n, 1);
long long prod = 1;
for (int it = 0; prod < k; it = (it + 1) % n) {
prod = prod / a[it] * (a[it] + 1);
++a[it];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < a[i]; j++) {
cout << s[i];
}
}
cout << '\n';
return 0;
}

1368D:一眼看出!哎要不是B题被卡了,我决定能上大分!好气

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
while(cin>>n){
int a[20]={0},x;
for(int i=0;i<n;++i){
cin>>x;
int j=0;
while(x){
if(x&1) ++a[j];
x>>=1; ++j;
}
}
LL r=0;
for(int i=0;i<n;++i){
LL t = 0;
for(int i=0,j=1;i<20;++i,j<<=1){
if(a[i]){
t+=j;
--a[i];
}
}
r+=t*t;
}
cout<<r<<endl;
}
return 0;
}

1285D:比赛的时候想到了,但是怕复杂度过补了,能过复杂度是因为每个元素$a$最多递归$\log a$次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
LL solve(vector<int> &a,int bit){
if(bit<0) return 0;
vector<int> l,r;
for(auto &x:a){
if((x>>bit)&1) l.push_back(x);
else r.push_back(x);
}
if(l.size()==0) return solve(r,bit-1);
if(r.size()==0) return solve(l,bit-1);
return min(solve(l,bit-1),solve(r,bit-1))+(1<<bit);
}
int main(){
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
while(cin>>n){
vector<int> a(n);
for(auto &x:a) cin>>x;
cout<<solve(a,30)<<endl;
}
return 0;
}

1285C:找出使得$\max(a,b)$最小并使得$lcm(a,b)=x$的最小$a,b$

将$x$分解素因子可知,$\max(a,b)$ 最小的前提是,$\gcd(a,b)=1$,又因为$x$的因子个数不超过$2\sqrt{x}$,搞定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
LL n;
while(cin>>n){
LL r = 1;
for(LL i=1;i*i<=n;++i){
if(n%i==0&&__gcd(i,n/i)==1){
r=i;
}
}
cout<<r<<" "<<n/r<<endl;
}
return 0;
}

本来不想写这个题,但是由于下题都是lcm问题,又是同一场,所以就记录一下

1285F:一道很秀的 lcm 题,计算 $\displaystyle \max_{1\leq i< j \leq n} lcm(a_i,a_j)$

参考这里:https://www.xht37.com/codeforces-round-613-div-2-%E9%A2%98%E8%A7%A3/#Classical

通过加入$a_i$ 的所有因子,我们可以改成计算 $\displaystyle \max_{\gcd(a_i,a_j)=1} a_ia_j$,我们将$a_i$ 从大到小排序,然后开始遍历,用堆s保存之前的内容,注意到,如果堆s中有一个元素t,跟当前需要遍历的元素$a_i$互素,那么小于s中小于$t$的元素讲不再能为结果做贡献。因此可以踢出栈中,现在问题是我们如何快速的记录堆$s$中是否有与$a_i$互素的元素。记$c_i$为堆中是$i$的倍数的元素个数,那么堆中和$x$互素的个数为 $cop = \sum_{d|x} \mu(d) c_d$,这是因为包容排斥原理,首先所有数都是$1$的倍数,然后减去和$x$的最小公约数为素数的,在加上和$x$的最小公约数为两个素数相乘…。若$cop$ 不为0,那么就一个个的剔除,剔除的时候可以计算一下乘积(虽然不一定互素,但是不会影响的最终结果)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e5+2;
int main(){
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
while(cin>>n){
bool a[N]={};
int mx=0;
for(int i=0,x;i<n;++i){
cin>>x;
a[x]=1;
mx = max(mx,x);
}
vector<int> p[mx+1];
int mu[mx+1]={},c[mx+1]={};
mu[1] = 1;
for(int i=1;i<=mx;++i){
p[i].push_back(i);
for(int j=2*i;j<=mx;j+=i){
p[j].push_back(i);
a[i]|=a[j];
mu[j]-=mu[i];
}
}
stack<int> s;
LL ans = mx;
for(int i=mx;i;--i){
if(a[i]){
int cop = 0;
for(auto &x:p[i]) cop+=mu[x]*c[x];
while(cop){
for(auto &x:p[s.top()]){
--c[x];
if(i%x==0) cop-=mu[x];
}
ans = max(ans,LL(i)*s.top());
s.pop();
}
for(auto &x:p[i]) ++c[x];
s.push(i);
}
}
cout<<ans<<endl;
}
return 0;
}

1370D:在长为n的序列中找一个长为k的子列,子列中奇数项最大值和偶数项最大值的最小值最小

比赛的时候,我很快就知可以二分查找答案,但是顾前不顾尾,下面代码没过,因为当最后一个数正好是满足a[i]<=m 时答案就不行了!应该按照原来的逻辑去叠加啊!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 此代码是错误代码!
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n,k;
cin>>n>>k;
int a[n],r=0,l=1e9+2;
for(int i=0;i<n;++i){
cin>>a[i];
r = max(r,a[i]);
l = min(l,a[i]);
}
auto f = [&](int m){
int now = -2,s=0;
for(int i=k%2;i<n;++i){
if(a[i]<=m){
if(i>now+1){
++s;
now = i;
}
}
}
return s>=k/2;
};
while(l<=r){
int m = (l+r)/2;
if(f(m)) r=m-1;
else l=m+1;
}
cout<<l<<endl;
return 0;
}

下面是修正的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n,k;
cin>>n>>k;
vector<int> a(n);
for(auto &x:a) cin>>x;
auto g = [&](int m,bool cur){
int s = 0;
for(int i=0;i<n;++i){
if(cur){
cur = !cur;
++s;
}else{
if(a[i]<=m){
++s;
cur = !cur;
}
}
}
return s>=k;
};
int l = *min_element(a.begin(),a.end());
int r = *max_element(a.begin(),a.end());
//auto lr = minmax_element(a.begin(),a.end());
//int l = *lr.first,r = *lr.second;
while(l<=r){
int m = (l+r)/2;
if(g(m,0)||g(m,1)) r=m-1;
else l=m+1;
}
cout<<l<<endl;
return 0;
}

1370E:找出最少的轮换使得字符串s变成t

我一开始知道是贪心,然后我以为是找到其中最长的连续0或者1,然后发现并不是!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 此代码是错误代码!
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
string a,b;
cin>>n>>a>>b;
int ab=0;
for(auto &x:a) if(x=='1') ++ab;
for(auto &x:b) if(x=='1') --ab;
if(ab){
cout<<-1<<endl;return 0;
}
string s;
for(int i=0;i<n;++i){
if(a[i]!=b[i]) s.push_back(a[i]);
}
s+=s;
//cout<<s<<endl;
int ans = 0;
for(int i=0,t;i<s.size();++i){
if((i == 0)||(s[i]!=s[i-1])) t=0;
ans = max(ans,++t);
}
cout<<ans<<endl;
return 0;
}

然后看了官方题解

在有解的前提下,我们可以构造取值在$\{-1,0,1\}$ 的数组$a$: if $s_i = t_i,a_i = 0$,else if $s_i = 1,a_i=1$ else $a_i=-1$。因此答案就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
string s,t;
cin>>n>>s>>t;
vector<int> a;
for(int i=0;i<n;++i){
if(s[i]==t[i]) continue;
a.emplace_back(s[i]=='1'?1:-1);
}
if(accumulate(a.begin(),a.end(),0)){
cout<<-1<<endl;
return 0;
}
auto f = [&](int sign){
int mx = 0,cur=0;
for(auto &x:a){
cur += sign*x;
mx = max(mx,cur);
cur = max(cur,0);
}
return mx;
};
cout<<max(f(1),f(-1))<<endl;
return 0;
}

1263DSet<int> 集合操作范例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
//freopen("in","r",stdin)
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int n;
cin>>n;
set<int> a[26];
for(int i=0;i<n;++i){
string s;
cin>>s;
for(auto &c:s) a[c-'a'].insert(i);
}
set<set<int>> q;
int x=0;
while(a[x].size()==0) ++x;
q.insert(a[x]);
for(int i=x+1;i<26;++i){
if(a[i].size()==0) continue;
set<set<int>> p;
for(auto &x:q){
set<int> t;
set_intersection(x.begin(),x.end(),a[i].begin(),a[i].end(),inserter(t, t.begin()));
if(t.size()){
set_union(x.begin(),x.end(),a[i].begin(),a[i].end(),inserter(t, t.begin()));
a[i] = t;
p.insert(x);
}
}
set<set<int>> t;
set_difference(q.begin(),q.end(),p.begin(),p.end(),inserter(t, t.begin()));
t.insert(a[i]);
q = t;
}
cout<<q.size()<<endl;
return 0;
}

1369D: 组合计数问题

题解写在官方的教程里面,代码也不想copy过来了。

补充一个更好的生成函数的做法:已知 $a_n$,满足$a_n = a_{n-1} + 2 a_{n-2} + (n \% 3==0?4:0)$,$a_0 = a_1= a_2 = 0$,计算$a_n$。

设$f(x) = \sum_{n=0} ^ {\infty} a_n x^n$,则我们有

所以

由于 $\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$,所以$\frac{1}{(1-2x)(1+x)} = \frac{2}{3(1-2x)} + \frac{1}{3(1+x)} = \sum_{n=0}^{\infty} \frac{2^{n+1}+(-1)^n}{3}x^n$(推荐),$\frac{1}{(1-2x)(1+x)} = \sum_{n=0}^{\infty} (2x)^n \sum_{n=0}^{\infty}(-x)^n = \sum_{n=0}^{\infty} \frac{2^{n+1}+(-1)^n}{3}x^n$(不推荐),因此

1369F:博弈题!

给定两个正整数$s \leq t$,$A,B$ 两人依次玩游戏,每次可以从$s$变成$s+1$或$2s$,谁先严格大于$t$,谁输了。

现在给你一堆的$s_i,t_i$,$A,B$ 两人依次玩游戏,每一局输了的人作为下一局开始的人。问$A$ 能否最后一局必赢,能否最后一局必输

先考虑单个$s,t$ 的情况。

用$f(s,t)$ 分别表示$A$ 是否有必胜策略。

  • $t$ 为奇数,若 $s$为偶数,那么$A$就让它变成$s+1$,那么无论$B$如何操作只能变成偶数,所以此时$f(s,t) = 1$,若$s$ 为奇数,显然若$B$ 用$A$ 刚刚的策略,则$A$输,$f(s,t) = 0$。
  • $t$ 为偶数,若$2s>t$,此时只能做加法,$f(s,t) = s \mod 2$,若$4s>t \geq 2s$,此时$f(s,t)=1$,因为总可以变成$f(2s,t)=0$。若$4s \leq t$,若$f(s,\lfloor \frac{t}{4} \rfloor) = 1$, 则 $A$ 必有策略到达区间$(\lfloor \frac{t}{4} \rfloor,2\lfloor \frac{t}{4} \rfloor)$的某一点,从而 $f(s,t)=1$, 同理若$f(s,\lfloor \frac{t}{4} \rfloor) = 0$,则$B$有$A$的策略,从而$f(s,t)=0$ (比赛的时候能想出来的人是真的虎) 。

用$g(s,t)$ 分别表示$A$ 是否有必输的策略:若$2s>t$,则$g(s,t)=1$,同理,若$2s \leq t$,$ f(s,\lfloor \frac{t}{2} \rfloor)=1$,则必有策略使得$B$到达$(\lfloor \frac{t}{2} \rfloor,2\lfloor \frac{t}{2} \rfloor)$的某一点,所以$g(s,t) = f(s,\lfloor \frac{t}{2} \rfloor)$

有了这两个函数后,我们就可以从后往前依次来决定最后能否有必胜或必输的决策。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
//freopen("in","r",stdin)
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
function<bool(LL,LL)> f = [&](LL s,LL t)->bool{
if(t%2==1) return s%2==0;
if(2*s>t) return s%2==1;
if(4*s>t) return 1;
return f(s,t/4);
};
function<bool(LL,LL)> g = [&](LL s,LL t)->bool{
if(2*s>t) return true;
return f(s,t/2);
};
int n;
cin>>n;
bool win=0,lose=1;
for(int i=0;i<n;++i){
LL s,t;
cin>>s>>t;
if(win^lose==0) continue;
if(lose){
win = f(s,t);
lose = g(s,t);
}else{
win = !f(s,t);
lose = !g(s,t);
}
}
cout<<win<<" "<<lose<<endl;
return 0;
}

我们可以认为一开始仅有必输策略所以让$A$先选,然后如果$A$原来有必胜且有必败策略,这后面必然一直有,若没有必胜也没有必败策略,则后面也是。所以只用考虑仅有其中之一的情形。

补充和强化知识

  • 需要补充:图论
  • 需要强化:二分法,动态规划,代码能力,找公式速度,读题速度。
  • 需要模板:高斯消元法C++版。
  • 水题刷题速度太慢!(题刷少了,每天一套Codeforces since 2020/6/8)
  • 不细心坑自己,让自己不自信!
  • 系统的学习了一下STL,总结出好用的部分!(2020/6/21)放在C++模板博文中
  • vector<bool> 不是容器!
  • 用指法敲代码
  • 急需各种图论算法好用的模板: 看Jiangly的代码找模板?

OI-wiki 复习和学习算法,在 codeforces 训练算法和编程能力。

图论

图的存储

  • 直接tuple类型数组直接存边,vector 类型直接push_back貌似不错啊!(见上面1363E的例子)
  • 邻接矩阵(只能用于无重边的图)
  • 链式前向星(推荐,优雅)

前两种都很基础,我们一般用链式前向星来存储,oi-wiki上的例子

1
2
3
4
5
6
7
8
9
10
11
12
// head[u] 和 cnt 的初始值都为 -1
int head[N],to[M]
void add(int u, int v) {
nxt[++cnt] = head[u]; // 当前边的后继
head[u] = cnt; // 起点 u 的第一条边
to[cnt] = v; // 当前边的终点
}

// 遍历 u 的出边
for (int i = head[u]; ~i; i = nxt[i]) { // ~i 表示 i != -1
int v = to[i];
}

但是,自从我会C++17后,我们可以这么写(优雅)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N =1e5;   // 顶点数
const int M = 1e6; // 边数,在树中是 2*(n-1)
// head[u] 和 cnt 的初始值都为 -1
int head[N],cnt,nxt[M];
tuple<int,int> edge[M];
void init(){
cnt = -1;
memset(head,-1,sizeof(head));
}
void add(int u, int v, int w){
nxt[++cnt] = head[u];
head[u] = cnt;
edge[cnt] = {v,w}; // 也可以存入u但没必要
}
// 遍历 u 的出边
void vis(int u){
for (int i = head[u];~i;i=nxt[i]) {
auto [v,w] = edge[i];
cout<<u<<" "<<v<<" "<<w<<endl;
}
}

存双向边时 i ^ 1 即是 i 的反边。

DFS(深度优先搜索)

递归的调用自己,要用到

在 Windows 上,通常的方法是在 编译选项 中加入 -Wl,--stack=1000000000

在 Linux 上,通常的方法是在运行程序前 在终端内 执行 ulimit -s unlimited (WSL下无法设置可惜)

BFS(广度优先搜索)

queue保存节点,先进先出。队列为空。

priority_queue 保存节点,可用于优化Dijkstra算法。

无根树的Prufer序列

$n$个节点的无根树和长度为$n-2$,数值在$1 \to n$ 的序列有一一对应

构造方式:删除编号最小的叶子节点,并记录它的父节点。

之前在猫咪状态数 中有记录过,代码可以见这里

有根树的Euler序列

通过DFS,可以把一个有根树转化成长度为$2n-1$,数值在$1 \to n$ 的序列。

最近公共祖先简称 LCA(Lowest Common Ancestor)

  • 策略1:其中一个节点一直往上标记父辈到根,然后另一个节点往上找父辈,直到找到首次被标记过的节点
  • 策略2:标记没个节点的深度,深度高的往上到同一层,然后一起一步步上去,直到是公共节点
  • 策略3:做一次DFS得到Euler序列,然后就变成找区间最小值问题了(可以使用线段树)
  • 其他:倍增(记录fa[u][i]:表示u的第$2^i$祖先),Tarjan 算法,动态树

有向图的拓扑排序之Kahn算法

给定有向图,然后把节点按照顺序排列,使得任意有向边的起点在终点前。

做法:维护一个入度为0的节点集合,一次删除节点(加入拓扑序列),删除的时候它连接的所有点入度减1,为0就加入节点集合。

一个有向图是无环图,当且仅当它存在拓扑排序。

有向图最小生成树的Kruskal算法(更推荐)

把边排序,每次加入最短边,如果加入不构成环,就加入,否则不加。

需要(带路径压缩)并查集维护。

(有向图)最小生成树的Prim算法

讲节点分为两类:已加入和未加入。每次从未加入的节点中找一个和已知节点最近的边,然后加入该节点,连接这条边。(初始加入节点任意)

(有向图)的次小生成树(下次一定)

最小树形图(有向图的最小生成树)的朱刘算法

  1. 找入度为0的root节点(唯一,否则不存在最小树形图)
  2. 除了root节点外,找出每个点的最小入边
  3. 检测是否有环,有环则缩点,更新新节点的距离
  4. 重复上述过程

强连通分量的Kosaraju 算法

Kosaraju 算法依靠两次简单的 DFS 实现。

第一次 DFS,选取任意顶点作为起点,遍历所有未访问过的顶点,并在回溯之前给顶点编号,也就是后序遍历。

第二次 DFS,对于反向后的图,以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点,选取标号最大的,重复上述过程。

两次 DFS 结束后,强连通分量就找出来了,Kosaraju 算法的时间复杂度为O(m+n)。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// g 是原图,g2 是反图
void dfs1(int u) {
vis[u] = true;
for (int v : g[u])
if (!vis[v]) dfs1(v);
s.push_back(u);
}

void dfs2(int u) {
color[u] = sccCnt;
for (int v : g2[u])
if (!color[v]) dfs2(v);
}

void kosaraju() {
sccCnt = 0;
for (int i = 1; i <= n; ++i)
if (!vis[i]) dfs1(i);
for (int i = n; i >= 1; --i)
if (!color[s[i]]) {
++sccCnt;
dfs2(s[i]);
}
}

我们可以将一张图的每个强连通分量都缩成一个点,然后这张图会变成一个有向无环图

强连通分量的Tarjan算法

二分图的匈牙利算法:dfs硬搞

Kirchhoff 矩阵树定理:解决了一张图的生成树个数计数问题

生成函数

在codeforces上zscoder大佬给了一个入门教程进阶教程 还有 MiFaFaOvO终极教程

生成函数分两种:Original generating function,Expentional generating function,选择哪一种是看问题中是否牵扯组合数。无论哪一种都能保存原数列的全部信息,并且由于级数可以使用微积分和常微分方程的技术,所以会变得更好处理。然后大概率可以优化算法复杂度$O(n^2) \to O(n \log n)$

关于生成函数多项式的处理:https://cp-algorithms.com/algebra/polynomial.html

多项式高效运算模板:https://github.com/e-maxx-eng/e-maxx-eng-aux/blob/master/src/polynomial.cpp

生成函数一般的处理思路:计算生成函数,分解成有分母不超过二次的分式之和,然后每一个二次的分母部分找一个递推数列来搞定。

OI-wiki 多项式运算

耻辱记录

  • 2020/5/24 水题竟然也能被卡,傻子吧我!
  • lower_bound 坑了,也怪自己,lower_bound(a.begin(),a.end(),x)-a :对于单调递增的序列,返回第一个大于等于x的序号。upper_bound 返回的是第一个大于 x 的序号,所以讲道理,upper_bound 更好用!
  • 2020/6/1 低级错误,把int型变量放在 bool 型后面定义了!结果找了半天的错误!!导致少做一题。给了自己几巴掌
  • Codeforces Round #657 (Div. 2):只做了一题???被A卡了一个多小时???

记录