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

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

Namomo Spring Camp 2022 Div1 每日一题记录 (2022.03.12-2022.03.18)

连续子序列 (CF977F)

题目链接

1 s, 512 MB

给定一个长度为 \(n\) 的数组 \(a_1,a_2,\dots ,a_n\), 问其中最长的连续上升子序列。也就是说，我们要找到数组 \(p_1,p_2,\dots,p_m\), 满足 \(1\leq p_1 < p_2 < \dots < p_m \leq n\) 并且 \(a_{p_m} - a_{p_{m-1}} = a_{p_{m-1}} - a_{p_{m-2}} = \dots = a_{p_2} - a_{p_1} = 1\), 要求找出最大的 \(m\) 和字典序最小的答案子序列

输入格式

第一行一个数字 \(n\)

接下来一行 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)

输出格式

第一行一个数字 \(m\), 表示答案子序列的长度

第二行 \(m\) 个数字，表示答案子序列

样例输入

1
2
7
3 3 4 7 5 6 8

样例输出

1
2
4
3 4 5 6

数据规模

所有数据保证 \(1\leq n\leq 200000, 1 \leq a_i \leq 10^9\)

解题思路

一维线性 DP

设 \(f(x)\) 为以 \(x\) 结尾的最长连续子序列长度，则

\[ f(x)=f(x-1)+1 \]

复杂度

\(O(n\log n)\)

代码参考 (CF977F)

Show code

CodeForces_977Fview 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
/*
 * @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, vars...)                                            \
  for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \
       i <= i##end;                                                       \
       ++i)
#define rfor_(i, r, l, vars...)                                           \
  for (std::make_signed_t<decltype(r - l)> i = (r), i##end = (l), ##vars; \
       i >= i##end;                                                       \
       --i)
#define foreach_ref_(i, container) for (auto &i : container)
#define foreach_riter_(it, container) \
  for (auto it = (container).rbegin(); it != (container).rend(); ++it)
auto solve([[maybe_unused]] int t_ = 0) -> void {
  int n;
  std::cin >> n;
  vector<int> a(n);
  foreach_ref_(i, a) std::cin >> i;
  vector<int> idx(n);
  map<int, int> f;
  int ans = 0, x = 0;
  for_(i, 0, n - 1)
    if (ans < (f[a[i]] = f[a[i] - 1] + 1)) ans = f[x = a[i]];
  cout << ans << '\n';
  vector<int> tmp;
  rfor_(i, n - 1, 0)
    if (a[i] == x) {
      tmp.push_back(i + 1);
      --x;
    }
  foreach_riter_(it, tmp) cout << *it << " \n"[it == tmp.rend()];
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  solve(i_);
  return 0;
}

工作安排

题目链接

1 s, 256 MB

约翰有太多的工作要做

为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间

他的工作日从 \(0\) 时刻开始，有 \(10^9\) 个单位时间

在任一时刻，他都可以选择编号 \(1\) 到 \(N\) 的 \(N\) 项工作中的任意一项工作来完成

每项工作又有一个截止日期，对于第 \(i\) 个工作，有一个截止时间 \(D_i\), 如果他可以完成这个工作，那么他可以获利 \(P_i\)

在给定的工作利润和截止时间下，约翰能够获得的利润最大为多少

输入格式

第 \(1\) 行一个整数 \(N\)

第 \(2\) 行至第 \(N+1\) 行每行两个整数 \(D_i\) 和 \(P_i\)

输出格式

一个数，表示最大获利

样例输入

1
2
3
4
3
2 10
1 5
1 7

样例输出

1
17

数据规模

\(1 \leq N \leq 1 \times 10^5\)

\(0 \leq D_i,P_i \leq 1\times10^9\)

解题思路

堆 + 贪心

首先按时间升序排序，时间相同的按价值降序排序

一个显然的贪心策略是尽量选截止时间短的，要是当前的工作已经截止了就看插队的收益是否更优

这个操作显然可以用小根堆实现

复杂度

\(O(n\log n)\)

代码参考

Show code

Daimayuan_503view 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
/*
 * @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 foreach_ref_(i, container) for (auto &i : container)
#define foreach_binding_(container, vars...) for (auto &&[vars] : container)
auto solve([[maybe_unused]] int t_ = 0) -> void {
  int n;
  std::cin >> n;
  priority_queue<int, vector<int>, greater<int>> pq;
  vector<pair<int, int>> a(n);
  foreach_ref_(i, a) cin >> i.first >> i.second;
  sort(a.begin(), a.end(), [](auto const &lhs, auto const &rhs) {
    return lhs.first == rhs.first ? lhs.second > rhs.second :
                                    lhs.first < rhs.first;
  });
  foreach_binding_(a, t, val) {
    if (t > pq.size()) pq.push(val);
    else if (pq.top() < val) {
      pq.pop();
      pq.push(val);
    }
  }
  i64 ans = 0;
  while (!pq.empty()) {
    ans += pq.top();
    pq.pop();
  }
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  solve(i_);
  return 0;
}

三角果计数

题目链接

1 s, 1024 MB

题目描述

给一个 \(n\) 个节点的树，三角果定义为一个包含 \(3\) 个节点的集合，且他们两两之间的最短路长度 \(a\), \(b\), \(c\) 能够构成一个三角形

计算这棵树上有多少个不同的三角果

注：两个集合相同当且仅当 \(A \subseteq B\), 且 \(B \subseteq A\)

输入格式

第一行一个正整数 \(n\), 表示树的节点个数

接下来 \(n - 1\) 行，每一行三个整数 \(u\), \(v\), \(w\) 表示节点 \(u\) 和 \(v\) 之间有一条边权为 \(w\) 的边

输出格式

一行一个整数，表示答案

样例输入

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

样例输出

1
8

数据范围

对于所有的数据，满足 \(1 \leq n \leq 10^5\), 边权 \(1 \leq w \leq 10^5\), \(1 \leq u, v \leq n\)

解题思路

树上 DFS

显然三个结点构成三角果当且仅当任意一个结点均不在另外两个结点的最短路上

所以我们只需枚举这三个点的 LCA 然后根据其各子树大小计算即可

这里有一个枚举技巧：我们可以让这三个点分别位于 "刚刚搜索过的子树", "之前搜索过的所有子树", "未搜索的所有子树" 这三部分中

复杂度

\(O(n)\)

代码参考

Show code

Daimayuan_505view 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
/*
 * @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, vars...)                                            \
  for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \
       i <= i##end;                                                       \
       ++i)
vector<vector<int>> g;
vector<int> sz;
i64 ans;
int n;
void dfs(int now, int fa) {
  if (g[now].size() == 1) {
    sz[now] = 1;
    return;
  }
  for (auto &&to : g[now]) {
    if (to == fa) continue;
    dfs(to, now);
    ans += 1ll * sz[now] * sz[to] * (n - 1 - sz[now] - sz[to]);
    sz[now] += sz[to];
  }
  ++sz[now];
}
auto solve([[maybe_unused]] int t_ = 0) -> void {
  std::cin >> n;
  sz.resize(n + 1);
  g.resize(n + 1);
  for_(i, 1, n - 1, u, v, w) {
    cin >> u >> v >> w;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 0);
  cout << ans;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  solve(i_);
  return 0;
}

整齐的数组 2

题目链接

1 s, 512 MB

Polycarp 有一个长度为 \(n\) 的数组 \(a_1,a_2,...,a_n\) (\(n\) 是偶数) . Polycarp 还得到了一个正整数 \(k\), 他开始对数组 \(a\) 做如下操作：选择一个下标 \(i\ (1 \leq i \leq n)\) 使 \(a_i\) 减去 \(k\)

​ 在 Polycarp 进行若干次操作后 (可能 \(0\) 次), 数组 \(a\) 中的数至少有一半都变成相同的了。请你找到最大的符合要求的 \(k\), 如果 \(k\) 可以为任意大，请输出 \(-1\)

输入格式

​ 第一行一个整数 \(t\), 表示测试单元的个数

​ 接下来每个测试单元有两行。第一行包含一个偶数 \(n\). 第二行包含 n 个整数 \(a_1, a_2,...,a_n\)

输出格式

​ 对于每个测试单元输出单独一行一个整数 \(k\ (k\geq 1)\) —— Polycarp 能用来对数组进行操作的最大的数，或者 \(-1\) —— 如果 \(k\) 能任意大的话

样例输入

1
2
3
4
5
6
7
8
9
4
6
48 13 22 -15 16 35
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000
4
1 1 1 1

样例输出

1
2
3
4
13
2
-1
-1

数据规模

​ 所有数据保证 \(1 \leq t \leq 10\), \(4\leq n\leq 40\) (\(n\) 是偶数), \(-10^6 \leq a_i\leq 10^6\), 并且 \(n\) 的总和不超过 \(100\)

解题思路

数学

建议先看 弱化版

弱化版的做法就是求一下所有数与最小数差的 gcd

本题思路类似：我们枚举最小数，记录所有大于和等于该数的 a 的个数

若和当前枚举的最小数相等的数已经过半，则直接输出 -1, 否则我们枚举差的所有因子并计数，若某个因子出现次数 + 和最小数相等的数过半了，则说明这个因子是可能的答案，最后取个最大值即可

复杂度

\(O(n^2\max\{\sqrt{a_i}\log{a_i}\})\)

代码参考

Show code

Daimayuan_555view 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
/*
 * @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;
auto solve([[maybe_unused]] int t_ = 0) -> void {
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto &&i : a) cin >> i;
  int ans = 0;
  for (auto &&i : a) {
    int cntg = 0, cnte = 0;
    map<int, int> cnt;
    for (auto &&j : a) {
      if (j > i) {
        ++cntg;
        ++cnt[j - i];
      } else if (j == i) ++cnte;
    }
    if (cnte >= n / 2) {
      cout << "-1\n";
      return;
    }
    if (cntg + cnte < n / 2) continue;
    map<int, int> gcd_cnt;
    for (auto &&[k, v] : cnt) {
      for (int j = 1; j * j <= k; ++j)
        if (k % j == 0) {
          gcd_cnt[j] += v;
          if (k != j * j) gcd_cnt[k / j] += v;
        }
    }
    for (auto &&[k, v] : gcd_cnt)
      if (cnte + v >= n / 2) ans = max(ans, k);
  }
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

三进制循环

题目链接

2 s, 256 MB

在神奇的树の国度，叽叽 发现了一棵包含 \(n\) 个节点三进制树，节点的编号是 \(1 \sim n\) . 这棵树的任意一个节点的值可能为 \(0, 1, 2\) 其中的一个。她喜欢有规律而不是杂乱无章的序列，她想在这棵树上找到一个路径，要满足从路径的一端到另一端，从第二个节点开始，每个节点的值都等于上一个节点的值 \(+ 1\) 之后对 \(3\) 取余的结果

换言之，把路径化为一个长度为 \(len\) 的序列 \(G\), 对于序列的第 \(2 \leq i \leq len\) 项，要满足 \(G_i = (G_{i - 1} + 1) \bmod 3\). 例如: \(2, 0, 1, 2, 0\)

现在，给出这棵三进制树，你能帮她找到最长的满足条件的路径吗，输出最长的路径长度.

输入格式

第一行输入一个整数 \(n (n \leq 500000)\) 为树的节点数量

接下来 \(n - 1\) 行，每行输入两个数 \(a_i\) , \(b_i\) 表示编号为 \(a_i\) 和 \(b_i\) 的节点之间存在一条边

接下来一行输入 \(n\) 个整数 \(val_j (0 \leq val_j \leq 2)\) 为第 \(j\) 个节点的值

输出格式

输出一个整数，为最大的满足条件的路径长度

样例输入 1

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

样例输出 1

1
4

样例解释

解题思路

树形 DP

思路挺显然的，就是树形 DP 找一下前缀和后缀然后一拼就是了

复杂度

\(O(n)\)

代码参考

Show code

Daimayuan_556view 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
/*
 * @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, vars...)                                            \
  for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \
       i <= i##end;                                                       \
       ++i)
auto solve([[maybe_unused]] int t_ = 0) -> void {
  int n;
  cin >> n;
  vector<vector<int>> g(n + 1);
  vector<int> id(n + 1), pre(n + 1), suc(n + 1);
  for_(i, 1, n - 1, u, v) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for_(i, 1, n) cin >> id[i];
  function<void(int, int)> dfs = [&](int now, int fa) {
    if (g[now].size() == 1) return;
    for (auto &&to : g[now]) {
      if (to == fa) continue;
      dfs(to, now);
      if (id[to] == (id[now] + 1) % 3) pre[now] = max(pre[now], pre[to] + 1);
      if (id[to] == (id[now] + 2) % 3) suc[now] = max(suc[now], suc[to] + 1);
    }
  };
  dfs(1, 0);
  int ans = 0;
  for_(i, 1, n) ans = max(ans, pre[i] + suc[i] + 1);
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  solve(i_);
  return 0;
}

树上逆序对

题目链接

1 s, 1024 MB

对于一棵有根树，定义树上的逆序对为满足 \(a_i < a_{fa_i}\) 的二元对 \((i,fa_i)\) , 其中 \(fa_i\) 表示结点 \(i\) 的父亲结点

对于一棵 \(k\) 叉树，结点 \(i\) 的子节点的编号集合为 \([1,n] \cap [k(i - 1) + 2,ki + 1]\) 中的所有整数

给定 \(n\) 个结点的权值 \(a_1,a_2, \dots , a_n\) , 对于 \(k = 1 , 2 , \dots , n - 1\) 求出当这 \(n\) 个结点构成一棵 \(k\) 叉树时树上逆序对数

输入格式

第一行一个整数 \(n\) , 表示结点的个数 \((2 \leq n \leq 2 \times 10^5)\)

第二行包含 \(n\) 个整数 \(a_1,a_2, \dots , a_n\) 表示结点的权值 \((1 \leq a_i \leq 10^9)\)

输出格式

输出一行 \(n - 1\) 个整数分别表示 \(k = 1 , 2 , \dots , n - 1\) 时树上逆序对数

样例输入

1
2
5
5 4 5 4 3

样例输出

1
3 2 3 3

解题思路

树状数组 / 主席树 询问区间大于给定数的个数

相当于对给定数组做 \(O(n\log n)\) 次询问，每次询问某段区间上小于给定数的个数，可以参照 数数

复杂度

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

代码参考

Show code

约分 (CCPC Harbin 2021 D)

题目链接

1 s, 1024 MB

题目描述

大家都知道两个分数等价是什么概念，我们说 \(\frac{a}{b}\) 和 \(\frac{p}{q}\) 等价当且仅当 \(\frac{a}{b} = \frac{p}{q}\)

通常我们约分是将分子分母同时约去一个相同的因数。但是这样太难了，于是小 t 对约分提出了新的定义。我们可以一次性从分子分母中同时划掉若干个相同的数字。比如，\(\frac{123}{233}\) 可以划掉一个数变成 \(\frac{12}{23}\), 也可以变成 \(\frac{13}{33}\), 容易发现这样可能造成原来的分数跟当前的分数不等价

现在小 t 想问你，在此约分操作下 \(\frac{a}{b}\) 的最简分数是哪一个。最简分数是，与 \(\frac{a}{b}\) 等价的 \(\frac{p}{q}\) 中，\(p\) 最小的那一个。比如

  • \(\frac{163}{326} \rightarrow \frac{16}{26} \rightarrow \frac{1}{2}\), 我们说 \(\frac{1}{2}\) 是 \(\frac{163}{326}\) 的最简分数
  • \(\frac{24}{48}\) 的最简分数是 \(\frac{24}{48}\), 因为 \(\frac{2}{8} \neq \frac{24}{48}\)
  • \(\frac{22222}{22222}\) 的最简分数是 \(\frac{2}{2}\), 因为 \(\frac{0}{0}\) 不合法

需要注意的是，如果答案是 \(\frac{007}{233}\), 你需要输出的是 \(\frac{7}{233}\). 可以理解为前导零会在约分的过程中自动消散

输入格式

一行两个整数 \(a, b\), 分别表示分子和分母

输出格式

一行两个整数 \(p, q\), 分别表示最简分数的分子和分母

样例输入

1
2232 162936

样例输出

1
232 16936

数据范围

对于所有数据，保证 \(1\leq a, b\leq 2^{63}-1\)

原题链接

https://codeforces.com/gym/103447/problem/D

解题思路

复杂度

代码参考

Show code