Namomo Spring Camp 2022 Div1 每日一题记录 (Week 13)

发表于 更新于 分类于 ， 本文字数： 2k 阅读时长 ≈ 7 分钟

Namomo Spring Camp 2022 Div1 每日一题记录 (2022.05.21-2022.05.27)

序列中 ab 的个数 (CF908D)

题目链接

5 s, 1024 MB

题目描述

给三个整数 \(k,pa,pb\), 最初有一个空序列，每一秒都可以执行以下操作，以 \(pa\) \(/\) \((pa+pb)\) 的概率将 \(a\) 添加到末尾或者以 \(pb\) \(/\) \((pa+pb)\) 的概率将 \(b\) 添加到末尾，一旦至少出现 k 个子序列 \(ab\), 就停止操作，求最终子序列 \(ab\) 的期望次数，输出一个整数 \(mod\) \((1e9+7)\)

输入格式

一行输入三个整数 \(k,pa,pb\)

输出格式

一个数，表示答案

样例 1 输入

1
3 1 4

样例 1 输出

1
370000006

样例 2 输入

1
1 1 1

样例 2 输出

1
2

数据规模

所有数据保证 \(1 \le k \le 1000 ,1 \le pa,pb \le 1e6\)

解题思路

概率 DP

设 \(f(x,y)\) 表示有 \(x\) 个 a, 且有 \(y\) 个子串 ab 时的概率，则

\[ f(x,y)=\frac{p_a}{p_a+p_b}f(x-1,y)+\frac{p_b}{p_a+p_b}f(x,y-x) \]

另外，若 \(x+y>k\), 则期望应为 \(\sum_{i=0}^{\infty}(\frac{p_a}{p_a+p_b})^i\frac{p_b}{p_a+p_b}(x+y+i)\)

然后倒着推即可

代码参考

Show code

CodeForces_908Dview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _rfor(i, r, l, vals...) \
  for (int i = (r), i##end = (l), ##vals; i >= i##end; --i)
const uint32_t OFFSET = 5;
const uint32_t N = 1e3 + OFFSET;
const uint32_t MOD = 1e9 + 7;
constexpr i64 qpow(i64 a, i64 b = MOD - 2, const i64 &mod = MOD) {
  i64 res(1);
  for (; b; b >>= 1, (a *= a) %= mod)
    if (b & 1) (res *= a) %= mod;
  return res;
};
i64 f[N][N];
auto solve() -> void {
  i64 k, pa, pb;
  cin >> k >> pa >> pb;
  i64 A = (pa * qpow(pa + pb) % MOD), B = (1 - A + MOD) % MOD,
      C = (pa * qpow(pb) % MOD);
  _rfor(i, k, 1)
    _rfor(j, k, 0)
      f[i][j] =
        (i + j >= k ? (i + j + C) : (A * f[i + 1][j] + B * f[i][i + j])) % MOD;
  cout << f[1][0];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

谁才是最终赢家？

题目链接

1 s, 256 MB

题目描述

小明和小红经常玩一个博弈游戏。给定一个 \(n \times n\) 的棋盘，一个石头被放指定位置。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输

假如小明先移动石头，而且两个选手都以最优策略走步，问最后谁能赢？

如果小明赢则输出 Alice, 否则输出 Bob

输入格式

第一行一个整数 \(n\), 表示一个 \(n \times n\) 的棋盘

第二行两个整数 \(x, y\) 表示起点的位置

输出格式

一行一个字符串

样例输入

1
2
2
1 1

样例输出

1
Alice

数据限制

\(1 \le n \le 10000, 1 \le x, y \le n\)

解题思路

代码参考

Show code

矩阵游戏 (BZOJ4766)

题目链接

1 s, 1024 MB

题目描述

小 \(s\) 正在玩一个游戏：他有一个长为 \(N\), 宽为 \(M\) 的棋盘，其中有一些格子是黑色的 (其余的格子是白色的)

每次操作他可以选择一个长度和宽度均大于 \(1\) 的矩形区域，如果其中 3 个角落的格子是黑色的，那么他可以把剩余那个角落的白色格子涂成黑色

试求出有多少种不同的长为 \(N\), 宽为 \(M\) 的棋盘，满足小 \(s\) 可以通过有限次操作把整个棋盘变成黑色，并且黑色格子个数最少。两个棋盘不同当且仅当存在一个格子在两个棋盘中的颜色不同

你只需要输出这个数字对 \(998244353\) 取模后的结果

输入格式

第一行一个正整数 \(T\), 表示数据组数。对于每组测试数据，第一行输入两个正整数 \(N\) 和 \(M\)

数据范围：对于所有数据，满足 \(1 \leq T \leq 100\), \(1 \leq N \leq 100\), \(1 \leq M \leq 100\)

输出格式

对于每组数据，输出一行一个整数表示答案

样例输入

1
2
3
2
1 1
2 2

样例输出

1
2
1
4

解题思路

矩阵树定理

题目所求等价于 \(K_{n,m}\) 的最小生成树个数，即 \(m^{n-1}n^{m-1}\)

代码参考

Show code

BZOJ_4766view raw
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: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
constexpr i64 qpow(i64 a, i64 b, const i64 &mod) {
  i64 res(1);
  a %= mod;
  for (; b; b >>= 1, (a *= a) %= mod)
    if (b & 1) (res *= a) %= mod;
  return res;
};
auto solve() -> void {
  i64 n, m, p;
  cin >> n >> m >> p;
  cout << qpow(m, n - 1, p) * qpow(n, m - 1, p) % p << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

最大化深度和 (POI2008 STA-Station)

题目链接

1 s, 1024 MB

题目描述

给定一个 \(n\) 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大，输出最大的深度之和即可

注意: 根的深度为 \(1\)

输入格式

第一行有一个整数，表示树的结点个数 \(n\)

接下来 \((n−1)\) 行，每行两个整数 \(u, v\), 表示存在一条连接 \(u, v\) 的边

输出格式

一个正整数，表示最大的深度之和

样例输入

1
2
3
4
5
6
7
8
8
1 4
5 6
4 5
6 7
6 8
2 4
3 4

样例输出

1
28

数据规模

\(0 \leq n \leq 10^6\). 即可能存在空树

\(1 \leq u, v \leq n\), 保证给出的是一棵树

解题思路

换根 DP

典中典，设 \(f(x)\) 是以 \(x\) 为根时的结果，先随便取个根 \(r\) DFS 出结果，然后

\[ f(x)=f(y)-s(x)+n-s(x) \]

其中

  • \(s(x)\) 代表以 \(r\) 为根时 \(x\) 的子树大小
  • \(y\) 是以 \(r\) 为根时 \(x\) 的父结点

复杂度

\(O(n)\)

代码参考 (洛谷 P3478)

Show code

Luogu_P3478view raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
#define _run_return_void(expressions) \
  {                                   \
    expressions;                      \
    return;                           \
  }
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 1e6 + OFFSET, M = 2e6 + OFFSET;
struct Edge {
  int to, next;
  Edge(int _to = 0, int _next = 0): to(_to), next(_next) {}
} e[M];
int head[N], cnt_edge;
void addEdge(int x, int y) {
  e[++cnt_edge] = Edge(y, head[x]);
  head[x] = cnt_edge;
}
#define _for_graph(head, e, i, now) \
  for (int i = head[now], to = e[i].to; i; to = e[i = e[i].next].to)
i64 ans[N];
i64 sz[N], dep[N];
void dfs(int now, int fa) {
  sz[now] = 1;
  dep[now] = dep[fa] + 1;
  _for_graph(head, e, i, now) {
    if (to == fa) continue;
    dfs(to, now);
    sz[now] += sz[to];
  }
}
int n;
void dfs2(int now, int fa) {
  _for_graph(head, e, i, now) {
    if (to == fa) continue;
    ans[to] = ans[now] + n - 2 * sz[to];
    dfs2(to, now);
  }
}
auto solve() -> void {
  cin >> n;
  if (n == 0) _run_return_void(cout << '0');
  _for(i, 1, n - 1, x, y) {
    cin >> x >> y;
    addEdge(x, y);
    addEdge(y, x);
  }
  dfs(1, 0);
  _for(i, 1, n) ans[1] += dep[i];
  dfs2(1, 0);
  i64 max_ans = ans[1], idx = 1;
  _for(i, 2, n)
    if (ans[i] > max_ans) max_ans = ans[idx = i];
  cout << idx;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

稳定数组 (CF1547F)

题目链接

2 s, 1024 MB

题目描述

给定 \(n\) 个正整数 \(a_1,a_2,\dots ,a_n\), 每次操作对所有的 \(i,1\leq i \leq n\), 令 \(a_i=gcd(a_i,a_{(i+1)\% n})\), 求最少执行多少次操作，使得 \(a_1=a_2=\dots =a_n\)

输入格式

第一行一个正整数 \(n\)

第二行 \(n\) 个正整数 \(a_1,a_2,\dots ,a_n\)

输出格式

一个非负整数，表示最少操作数

样例输入

1
2
4
16 24 10 5

样例输出

1
3

数据规模

\(2\leq n \leq 10^6\)

\(1\leq a_i \leq 10^6\)

解题思路

RMQ + 二分 / 双指针

这里写的 ST 表 + 二分，因为好写

要注意因为要断环成链所以要开 2 倍空间

复杂度

\(O(n\log^2 n)\)

代码参考

Show code

CodeForces_1547Fview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
#define _run_return_void(expressions) \
  {                                   \
    expressions;                      \
    return;                           \
  }
#define _mid(l, r) ((l) + (((r) - (l)) >> 1))
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 4e5 + OFFSET, M = 2e5 + OFFSET, K = 21;
template <size_t N, typename data_t, typename init_func, typename query_func>
class RMQ_ST {
protected:
  init_func ifunc;
  query_func qfunc;
  data_t f[(size_t)log2(N) + 1][N];
  size_t log_table[N];

public:
  RMQ_ST() {}
  void clear(size_t n) {
    for (size_t i = 0; i <= (size_t)(log2(n)); ++i)
      memset(f[i], 0, sizeof(f[i][0]) * (n + 1 - i));
  }
  void init(size_t n) {
    for (size_t i = 1; i <= n; ++i) f[0][i] = ifunc(i);
    for (size_t i = 1; i <= std::log2(n); ++i)
      for (size_t j = 1; j + (1 << i) - 1 <= n; ++j)
        f[i][j] = qfunc(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
  }
  data_t query(size_t l, size_t r) const {
    size_t _ = std::log2(r - l + 1);
    return qfunc(f[_][l], f[_][r - (1 << _) + 1]);
  }
};
int a[N];
struct ifunc {
  int operator()(const size_t x) const { return a[x]; }
};
struct qfunc {
  int operator()(const int l, const int r) const { return gcd(l, r); }
};
RMQ_ST<N, int, ifunc, qfunc> tr;
bool judge(int n, int k) {
  int x = tr.query(1, k + 1);
  _for(l, 2, n)
    if (tr.query(l, l + k) != x) return false;
  return true;
}
auto solve() -> void {
  int n;
  cin >> n;
  _for(i, 1, n) cin >> a[i];
  bool f = 1;
  int x = a[1];
  _for(i, 2, n)
    if (a[i] != x) f = 0;
  if (f) _run_return_void(cout << "0\n");
  _for(i, 1, n) a[i + n] = a[i];
  tr.clear(n * 2);
  tr.init(n * 2);
  int l = 1, r = n, mid, ans = r;
  while (l <= r)
    if (judge(n, mid = _mid(l, r))) {
      ans = mid;
      r = mid - 1;
    } else l = mid + 1;
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int _t;
  cin >> _t;
  while (_t--) solve();
  return 0;
}

序列和 (CF1373D)

题目链接

1 s, 1024 MB

题目描述

给定一个长度为 \(n\) 序列 \(a_0 , a_1 , \dots , a_{n - 1}\) , 你可以翻转它的一个连续子段 (可以为空) , 使得所有偶数下标的数字之和最大

输入格式

第一行一个整数 \(n\) , 表示序列的长度 \((1 \leq n \leq 2 \times 10^5)\)

第二行 \(n\) 个整数 \(a_0 , a_1 , \dots , a_{n - 1}\) 表示序列 \(a\) \(( 1 \leq a_i \leq 10^9 )\)

输出格式

输出一个整数表示偶数下标之和的最大值

样例输入

1
2
8
1 7 3 4 7 6 2 9

样例输出

1
26

解题思路

不难发现选择即是将一段偶数下标的和变为奇数下标的和，所以取一下差值最大区间和即可

复杂度

\(O(n)\)

代码参考

Show code

CodeForces_1373Dview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 2e5 + OFFSET, M = 2e5 + OFFSET, K = 21;
int a[N];
auto solve() -> void {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];
  i64 sum = 0, ans1 = 0;
  for (int i = 1; i < n; i += 2) {
    if ((sum += a[i] - a[i - 1]) < 0) sum = 0;
    chkmax(ans1, sum);
  }
  sum = 0;
  for (int i = 2; i < n; i += 2) {
    if ((sum += a[i - 1] - a[i]) < 0) sum = 0;
    chkmax(ans1, sum);
  }
  i64 ans = 0;
  for (int i = 0; i < n; i += 2) ans += a[i];
  cout << ans + ans1 << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int _t;
  cin >> _t;
  while (_t--) solve();
  return 0;
}

变量

题目链接

1 s, 1024 MB

题目描述

给定 \(n\) 个整数常数 \(c_1, c_2, \dots, c_n\) 和一个整数 \(k\). 现在需要给 \(2k\) 个整数变量 \(x_1, x_2, \dots, x_k, y_1, y_2, \dots, y_k\) 赋值，满足

  1. 对于所有 \(1 \leq i \leq k\), 都有 \(x_i \leq y_i\)
  2. 对于所有 \(1 \leq i \leq n\), 都存在至少一个 \(j (1 \leq j \leq k)\), 使得 \(x_j \leq c_i \leq y_j\)

求出 \(S=(y_1 + y_2 + \dots + y_k) - (x_1 + x_2 + \dots + x_k)\) 的最小值

输入格式

第一行两个整数 \(n, k\)

接下来一行，共 \(n\) 个整数 \(c_1, c_2, \dots, c_n\)

输出格式

一个整数表示 \(S\) 的最小值

样例输入 1

1
2
5 2
-5 0 10 4 0

样例输出 1

1
9

样例输入输出 2

见下发文件

数据规模

共 10 个测试点

测试点 \(1, 2\) 满足 \(n\leq 5, -5\leq c_i\leq 5\)

测试点 \(3, 4, 5\) 满足 \(n\leq 100\)

对于所有数据，满足 \(1\leq n, k\leq 10^5,-10^9\leq c_i\leq 10^9\)

解题思路

直接做就行，没啥值得说的

复杂度

\(O(n\log n)\)

代码参考

Show code

Daimayuan_138view raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (int i = (l), i##end = (r), ##vals; i <= i##end; ++i)
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, k;
  cin >> n >> k;
  if (k >= n) {
    cout << "0\n";
    return 0;
  };
  vector<int> c;
  c.reserve(n);
  _for(i, 1, n, x) {
    cin >> x;
    c.push_back(x);
  }
  sort(c.begin(), c.end());
  priority_queue<int> pq;
  _for(i, 1, n - 1)
    if (c[i] - c[i - 1] > 0) pq.push(c[i] - c[i - 1]);
  while (--k && !pq.empty()) pq.pop();
  i64 ans = 0;
  while (!pq.empty()) {
    ans += pq.top();
    pq.pop();
  }
  cout << ans;
  return 0;
}