CP Wiki

# Codeforces Round 660 (CF1388) 题解

# Problem A - Captain Flint and Crew Recruitment

# 题目描述

给定一个正整数nn，问能否将其表示为四个互不相等的正整数的和，要求其中至少三个正整数可以表示为p⋅qp\cdot q的形式（pp和qq是不相等的质数）。

# 题解

这题乍一看有点恐怖，毕竟跟质数沾上了边，怎么想也不像是Div.2A。再看题目，关键点是至少三个，也就是说，我们只要保证三个数符合条件，剩下一个数直接用剩下的差就行。

考虑符合条件的三个数，我们选尽可能小的，那就是6=2×36=2\times3，10=2×510=2\times5，14=2×714=2\times7。这三个数的和为3030，因此剩下那个数为n−30n-30，所以n≤30n\leq30时无解。

还要考虑几个特殊情况，也就是剩下那个数n−30n-30跟已有的三个数中某一个相等。此时，把1414换成1515，剩下那个数换成n−31n-31即可。

经验就是CF的题号和难度对应关系是非常明确的，在Div.2的A/B题感觉卡住了的话，通常可以认为是有关键条件没有注意到，导致想复杂了。

参考代码（C++） 
#include <cstdio>
#include <iostream>

using namespace std;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve() {
    int n;
    read(n);
    if (n <= 30) {
      printf("NO\n");
      return;
    }
    printf("YES\n");
    if (n == 36 || n == 40 || n == 44)
      printf("6 10 15 %d\n", n - 31);
    else
      printf("6 10 14 %d\n", n - 30);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  while (t--) {
    Solution solution = Solution();
    solution.solve();
  }
}
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

# Problem B - Captain Flint and a Long Voyage

# 题目描述

求出能够使得逐位二进制展开再去掉最后nn位的结果对应的二进制数最大的最小nn位数。

例如，99逐位展开的结果是10011001，再去掉最后11位，变为100100。

# 题解

因为二进制展开结果不会有先导00，所以肯定位数越多结果越大，因此我们的nn位数每一位只能选88或99，否则位数就损失了。什么情况下要选88呢？因为88对应10001000，99对应10011001，所以只要最后一位是要被删去的，88和99的结果就没有区别，此时为了使得这一nn位数最小，这一位上就要选88。

所以就是很简单的贪心了，最后⌈n4⌉\left\lceil\frac{n}{4}\right\rceil位放88，前面都放99。

参考代码（C++） 
#include <cstdio>
#include <iostream>
#define MOD 1000000007

using namespace std;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve() {
    int n;
    read(n);
    int m = (n - 1) / 4 + 1;
    string a(n - m, '9');
    string b(m, '8');
    string ans = a + b;
    printf("%s\n", ans.c_str());
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  while (t--) {
    Solution solution = Solution();
    solution.solve();
  }
}
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

# Problem C - Uncle Bogdan and Country Happiness

# 题目描述

一棵根为11的树，一开始所有人都在根节点处，接下来他们会沿着最短路径回家。已知家在第ii个节点的人有pip_i个，第ii个节点处的快乐值为hih_i表示在该节点处快乐的人和不快乐的人的个数差。已知一个人只会从快乐变成不快乐，问给定的hh是否有可能成立。

# 题解

很显然是一道DFS的题目，关键是如何提取出约束条件。因为一个人只会从快乐变为不快乐，所以任意子树的根节点处，快乐的人数一定不少于这一子树的所有子节点的快乐人数之和。另一方面，快乐的人数也不会超过经过该节点的总人数。除了这两个比较显而易见的约束，还有一个不那么明显的约束。事实上，我们是可以得到下面的等式的

happy[i]−(cnt[i]−happy[i])=hihappy[i] - (cnt[i] - happy[i]) = h_i

其中happy[i]happy[i]表示第ii个节点处快乐的人数，cnt[i]cnt[i]表示第ii个节点处的总人数。

我们进一步可以得到

happy[i]=hi+cnt[i]2happy[i]=\frac{h_i+cnt[i]}{2}

因为happy[i]happy[i]需要为非负整数，所以hi+cnt[i]h_i+cnt[i]必须为偶数。

然后在DFS过程中判断上面三个条件是否都满足就行了。

参考代码（C++） 
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
  bool ok = true;
  int n, m;
  vector<int> p, h, cnt, happy;
  vector<vector<int>> adj;
  void check(int u, int pre) {
    int lo = 0;
    cnt[u] = p[u];
    for (int v : adj[u]) {
      if (v != pre) {
        check(v, u);
        cnt[u] += cnt[v];
        lo += happy[v];
      }
    }
    if ((h[u] + cnt[u]) % 2 != 0)
      ok = false;
    happy[u] = (h[u] + cnt[u]) / 2;
    if (happy[u] < lo || happy[u] > cnt[u])
      ok = false;
  }

public:
  void solve() {
    read(n), read(m);
    adj = vector<vector<int>>(n + 1);
    p = vector<int>(n + 1);
    h = vector<int>(n + 1);
    cnt = vector<int>(n + 1);
    happy = vector<int>(n + 1);
    for (int i = 1; i <= n; ++i)
      read(p[i]);
    for (int i = 1; i <= n; ++i)
      read(h[i]);
    for (int i = 1; i < n; ++i) {
      int u, v;
      read(u), read(v);
      adj[u].emplace_back(v);
      adj[v].emplace_back(u);
    }
    check(1, 0);
    printf(ok ? "YES\n" : "NO\n");
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  while (t--) {
    Solution solution = Solution();
    solution.solve();
  }
}
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

# Problem D - Captain Flint and Treasure

# 题目描述

有nn个数a1⋯ana_1\cdots a_n，以及对应的nn个序号b1⋯bnb_1\cdots b_n。要求对nn个数按照某一顺序依次操作一次，使得得到的总和最大，求出这个总和并给出这一顺序。

其中，每次操作会使得总和增加aia_i，如果bi≠−1b_i\neq-1，还会使得abi+=aia_{b_i}+=a_i。

对于任意的ii，bi,bbi,bbbi,⋯b_i,b_{b_i},b_{b_{b_i}},\cdots不构成循环。

# 题解

题目明确说了bb中不存在环，所以我们可以按照bb所描述的依赖关系进行拓扑排序，然后依次处理。

对于当前处理到的ii，如果ai>0a_i>0，显然我们希望把它加到后面的依赖项上，因此我们应当把ii排在前面（从左往右排）；反之，我们则应当把ii排在后面（从右往左排）。

显然，这样得到的结果一定是最优的。

参考代码（C++） 
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
  int n;
  vector<ll> a;
  vector<int> b, in, left, right;

public:
  void solve() {
    read(n);
    a = vector<ll>(n + 1);
    b = vector<int>(n + 1);
    in = vector<int>(n + 1);
    for (int i = 1; i <= n; ++i)
      read(a[i]);
    for (int i = 1; i <= n; ++i) {
      read(b[i]);
      if (b[i] != -1)
        in[b[i]]++;
    }
    queue<int> q;
    ll result = 0;
    for (int i = 1; i <= n; ++i) {
      if (in[i] == 0)
        q.push(i);
    }
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      if (a[u] < 0)
        right.emplace_back(u);
      else {
        left.emplace_back(u);
        if (b[u] != -1)
          a[b[u]] += a[u];
      }
      result += a[u];
      if (b[u] != -1) {
        in[b[u]]--;
        if (in[b[u]] == 0)
          q.push(b[u]);
      }
    }
    printf("%lld\n", result);
    reverse(right.begin(), right.end());
    for (int i : left)
      printf("%d ", i);
    for (int i : right)
      printf("%d ", i);
    printf("\n");
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  Solution solution = Solution();
  solution.solve();
}
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

# Problem E - Uncle Bogdan and Projections

# 题目描述

X轴上方有nn条互不相交且平行于X轴的线段。现在要求将这些线段互不相交地沿同一方向投影到XX轴上，问最后得到的投影在X轴上的左端点和右端点间的距离最短为多少。

# 题解

实际上就是要找到最优的倾角。

显然，对于任意两条线段，可以计算出不可行的倾角区间(θl,θr)(\theta_l,\theta_r)。将这些区间进行合并，可以得到总的不可行区间。

接下来，我们要选择的倾角一定是某个区间的端点（有一种特殊情况是所有线段的yy都相同，此时可以选择任意倾角）；如果不选择端点，那么在其相邻的端点中，一定有一个比它更优。（证明……略。）

所以，就枚举合并后剩下区间的端点，对每一个倾角的取值，枚举所有线段，计算得到最后的左端点和右端点。

为了避免误差，所有的倾角都用分数表示。

这实际上还是O(n3)O(n^3)的暴力，不过用C++ 64可以在时限内通过。

参考代码（C++） 
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

struct Line {
  int l, r, y;
};

int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }

struct Fraction {
  int a, b;
  Fraction(int a, int b) {
    if (b < 0) {
      a = -a;
      b = -b;
    }
    int g = gcd(abs(a), abs(b));
    this->a = a / g;
    this->b = b / g;
  };
  bool operator<(const Fraction &other) const {
    return (ll)a * other.b < (ll)b * other.a;
  }
  bool operator<=(const Fraction &other) const {
    return (ll)a * other.b <= (ll)b * other.a;
  }
  bool operator>(const Fraction &other) const {
    return (ll)a * other.b > (ll)b * other.a;
  }
  bool operator>=(const Fraction &other) const {
    return (ll)a * other.b >= (ll)b * other.a;
  }
  bool operator!=(const Fraction &other) const {
    return (ll)a * other.b != (ll)b * other.a;
  }
  bool operator==(const Fraction &other) const {
    return (ll)a * other.b == (ll)b * other.a;
  }
};

class Solution {
  vector<pair<Fraction, Fraction>> seg;

  Fraction theta(int x1, int x2, int dy) { return Fraction(x1 - x2, dy); }

  void calc(Line a, Line b) {
    if (a.y == b.y)
      return;
    if (a.y < b.y)
      swap(a, b);
    Fraction t1 = theta(a.l, b.r, a.y - b.y);
    Fraction t2 = theta(a.r, b.l, a.y - b.y);
    if (t1 > t2)
      swap(t1, t2);
    seg.emplace_back(t1, t2);
  }

public:
  void solve() {
    int n;
    read(n);
    vector<Line> a(n);
    for (int i = 0; i < n; ++i)
      read(a[i].l), read(a[i].r), read(a[i].y);
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j)
        calc(a[i], a[j]);
    double ans = 1e18;
    sort(seg.begin(), seg.end());
    vector<pair<Fraction, Fraction>> t;
    const Fraction magic(1, MOD);
    Fraction l0 = magic, r0 = magic;
    for (auto &[l, r] : seg) {
      if (l >= r0) {
        if (r0 != magic)
          t.emplace_back(l0, r0);
        l0 = l;
        r0 = r;
      } else {
        if (l0 == magic) {
          l0 = l;
          r0 = r;
        } else
          r0 = max(r0, r);
      }
    }
    if (l0 != magic)
      t.emplace_back(l0, r0);
    vector<Fraction> vt;
    for (auto &[l, r] : t)
      vt.emplace_back(l), vt.emplace_back(r);
    if (vt.empty())
      vt.emplace_back(0, 1);
    for (Fraction d : vt) {
      double l = 1e18, r = -1e18;
      for (auto &e : a) {
        l = min(l, (double)-d.a / d.b * e.y + e.l);
        r = max(r, (double)-d.a / d.b * e.y + e.r);
      }
      ans = min(ans, r - l);
    }
    printf("%.9f", ans);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  Solution solution = Solution();
  solution.solve();
}
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

官方题解O(n2log⁡n)O(n^2\log n)的凸包方法还没学会。

← Educational Codeforces Round 97 (CF1437) 题解 →