CF Round 773 小记

Posted on | In

又是一场下分场……

整体感受

一眼切 R2A，手滑 +1 了一次。
看了 R2B 之后被样例解释误导，+4 并且浪费半小时。
R1A 直接切，正确性显然。
R1B 看上去也不难做，可是只剩二十分钟了，最后连样例都没过。

R2A Hard Way

题意

给定一个三个顶点都是自然数的三角形 $\triangle ABC$，称 $\triangle ABC$ 边界上一个点 $P$ 是好的，当且仅当存在 $x$ 轴上的一个点 $Q$ 使得线段 $PQ$ 与 $\triangle ABC$ 的内部无交。Z求不好的点 $P$ 构成的集合的测度。（容易证明它可测）

$t\le 1000$，$x,y\le 10^9$。

link: https://codeforces.com/contest/1642/problem/A

做法

画个图容易知道，当且仅当存在一条平行于 $x$ 轴的边 $AB$，且第三个顶点 $C$ 在这条边下方集合才非空。此时集合为线段 $AB$ 去掉两个端点。

直接做即可。时间复杂度 $\Theta(1)$。

比赛的时候忘了 $C$ 在 $AB$ 下方这个限制了……Wrong answer on pretest 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
#include <cstdio>
#include <cmath>

namespace mirai {

int main(int argc, char** argv) {
  int t;
  std::scanf("%d", &t);
  while (t--) {
    int x[3], y[3];
    for (int i = 0; i < 3; ++i) {
      std::scanf("%d %d", &x[i], &y[i]);
    }
    int ans = 0;
    for (int i = 0; i < 3; ++i) {
      if (y[i] == y[(i + 1) % 3] && y[i] != 0) {
        ans = std::abs(x[i] - x[(i + 1) % 3]);
        break;
      }
    }
    std::printf("%d\n", ans);
  }
  return 0;
}

} // namespace mirai

int main(int argc, char** argv) {
  return mirai::main(argc, argv);
}

R2B Power Walking

题意

给定 $n$ 个数 $S={a1,\cdots,a_n}$，对每个 $k\in[1,n]$ 求出：$\min{\sum\limits{i=1}^kf(S_i)}$，其中 $S_i(1\le i\le k)$ 是 $S$ 的一个可重集划分，而 $f(S_i)$ 表示将 $S_i$ 变为不可重集后 $S_i$ 的大小。

$t\le 10^5$，$\sum n\le 3\times10^5$，$1\le a_i\le 10^9$。

link: https://codeforces.com/contest/1642/problem/B

做法

令 $m=f(S)$，则容易知道当 $k\le m$ 时答案为 $m$。（让不同的可重集交集为空）

当 $k>m$ 时，对于其中的 $m$ 个仍然可以采用原来的策略，对于剩下的 $m-k$ 个就直接从原来的 $m$ 个找 $m-k$ 个数扔出来单独成集合即可。容易知道这是最优解。时间复杂度 $\Theta(n\log n)$，因为用了快排来计算 $m$。当然也可以用 std::unordered_set 优化到 $\Theta(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
#include <cstdio>
#include <cstring>
#include <algorithm>

namespace mirai {

int a[300005];
class type {
 public:
  int val, cnt;
};
type b[300005];

int main(int argc, char** argv) {
  int t;
  std::scanf("%d", &t);
  while (t--) {
    int n;
    // std::memset(a, 0x00, sizeof(a));
    std::scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
      std::scanf("%d", &a[i]);
    }
    a[n + 1] = 0;
    std::sort(a + 1, a + n + 1);
    int m = 0;
    for (int i = 1; i <= n; ++i) {
      if (a[i] != a[i + 1]) {
        m++;
      }
    }
    int ans = m;
    for (int i = 1; i <= n; ++i) {
      std::printf("%d ", ans);
      ans += i >= m;
    }
    std::printf("\n");
  }
  return 0;
}

} // namespace mirai

int main(int argc, char** argv) {
  return mirai::main(argc, argv);
}

R1A Great Sequence

题意

给定一个可重数集 ${a_1,\cdots,a_n}$，请通过若干次插入数的操作，使得这个数集可以被两两划分成可重有序数对集 ${(x_i,y_i)}$，使得 $\forall (x_i,y_i):x_i=ky_i$。最小化操作数。

$t\le 2\times 10^4$，$\sum n\le 2\times 10^5$，$1\le a_i\le 10^9$，$2\le k\le 10^6$。

link: https://codeforces.com/contest/1641/problem/A

做法

对原数组排序。每次设当前最小数为 $x$，若 $kx$ 存在则将 $x$ 与 $kx$ 配对；否则添加一个 $kx$ 并与 $x$ 配对。

容易知道这是正确的。