Educational Codeforces Round 156 (Rated for Div. 2)

A.

x 从 1 枚举到 6，y 从 1 枚举到 6，判断 x,y,z 是否合法即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
  int n;
  cin >> n;
  rep(a, 1, 6) {
    rep(b, a + 1, 6) {
      int c = n - a - b;
      if (c <= 0 || a % 3 == 0 || b % 3 == 0 || c % 3 == 0) {
        continue;
      }
      if (a == b || b == c || a == c) {
        continue;
      }
      cout << "YES\n";
      cout << a << " " << b << " " << c << "\n";
      return;
    }
  }
  cout << "NO\n";
}

B.

考虑四种情况，只用 a 灯，只用 b 灯，两个圆相切的两种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

double dist(pii x, pii y) {
  return sqrt((y.fi - x.fi) * (y.fi - x.fi) + (y.se - x.se) * (y.se - x.se));
}

void solve() {
  pii o, p, a, b;
  o.fi = o.se = 0;
  cin >> p.fi >> p.se;
  cin >> a.fi >> a.se;
  cin >> b.fi >> b.se;
  cout << min({
      max(dist(o, a), dist(a, p)),
      max(dist(o, b), dist(b, p)),
      max({dist(o, a), dist(a, b) / 2, dist(b, p)}),
      max({dist(o, b), dist(a, b) / 2, dist(a, p)})
  }) << "\n";
}

C.

贪心的删掉第一个 $s_i > s_{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
38
39
40
41
42
void solve() {
  string s;
  cin >> s;
  ll pos;
  cin >> pos;
  --pos;
  int n = sz(s);
  vi L(n), R(n);
  rep(i, n) {
    L[i] = i - 1;
    R[i] = i + 1;
  }
  vi vis(n, 0);
  auto del = [&](int x) {
    vis[x] = 1;
    int l = L[x];
    int r = R[x];
    if (0 <= l && l < n) R[l] = r;
    if (0 <= r && r < n) L[r] = l;
  };
  int j = 0, c = 0;
  while (pos > n - 1 - c) {
    while (R[j] < n && s[j] <= s[R[j]]) {
      j = R[j];
    }
    pos -= n - c;
    c += 1;
    del(j);
    if (L[j] != -1)
      j = L[j];
    else
      j = R[j];
  }
  int h = j;
  while (L[h] != -1) {
    h = L[h];
  }
  while (pos--) {
    h = R[h];
  }
  cout << s[h];
}

D.

考虑第一个字符一定得是 $<$ 或者 $>$，否则一定不是排列，答案必定是 0。

考虑前缀 $[1…i]$ 的答案是 $ans$。

  • 如果第 $i$ 个字符是 $<$ 或者 $>$，那么一定只有一种方案，就是选最小的或者最大的。
  • 如果第 $i$ 个字符是 $?$，那么 $i+1$ 这个位置可以选择 $[2…i]$，把 $p_{i+1}$ 这个数字插进去，就是将原先 $\geq p_{i+1}$ 的位置都加上一个 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
38
39
40
41
42
43
44
45
46
47
48
49
50
const int P = 998244353;
int power(int x, int y) {
  int r = 1;
  while (y) {
    if (y % 2 == 1) {
      r = 1ll * r * x % P;
    }
    x = 1ll * x * x % P;
    y /= 2;
  }
  return r;
}
 
int inv(int x) { return power(x, P - 2); }
 
void solve() {
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  int ans = 1;
  for (int i = 1; i < n; i++) {
    if (s[i] == '?') {
      ans = 1ll * ans * i % P;
    }
  }
 
  auto print = [&]() {
    if (s[0] == '?') {
      cout << 0 << "\n";
    } else {
      cout << ans << "\n";
    }
  };
  print();
  while (q--) {
    int x;
    char c;
    cin >> x >> c;
    x -= 1;
    if (x && s[x] == '?') {
      ans = 1ll * ans * inv(x) % P;
    }
    s[x] = c;
    if (x && s[x] == '?') {
      ans = 1ll * ans * x % P;
    }
    print();
  }
}

E.

假定 $a$ 是一个递增的序列。

$avail_{i,j}$ 表示 $b_{i}$ 如果要从 $j$ 这个位置开始选，需要分配多少个人。

但是考虑到序列并不连续，且可能存在空区间更优的情况。

将 $avail_{i,j}$ 定义成一个二元组 $(fi, se)$，$fi$ 表示需要跳过多少个人，$se$ 表示实际上需要用多少个人。

然后开始状压，$dp_{S}$ 存一个三元组表示完成 $S$ 集合的最小位置，上一个用的是哪个 $b_j$，实际上用了几个人。

$avail_{i,j}$ 的初值设错了，狂 wa29。

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
void solve() {
  int n, m;
  cin >> n >> m;
  vc<pii> a(n);
  rep(i, n) {
    cin >> a[i].first;
    a[i].second = i;
  }
  sort(all(a));
  vc<vc<pii>> avail(m, vector<pii>(n, {n + 1, n + 1}));
  rep(i, m) {
    int x;
    cin >> x;
    vc<pii> t;
    for (int k = 1; k <= n; k++) {
      int value = (x + k - 1) / k;
      if (t.empty() || t.back().first != value) {
        t.pb(value, k);
      }
    }
    for (auto [value, k] : t) {
      int l = lower_bound(all(a), pii(value, 0)) - a.begin();
      if (l < n) {
        cmin(avail[i][l], pii(k, k));
      }
    }
    rep(j, 1, n) { cmin(avail[i][j], avail[i][j - 1]); }
    for (int j = n - 2; j >= 0; j--) {
      cmin(avail[i][j], pii(avail[i][j + 1].first + 1, avail[i][j + 1].second));
    }
  }
  vc<array<int, 3>> dp(1 << m, array<int, 3>{n + 1, -1, -1});
  dp[0] = array<int, 3>{0, -1, -1};
  rep(s, 1, 1 << m) {
    rep(j, m) {
      if (s >> j & 1) {
        int t = s ^ (1 << j);
        int lst = dp[t][0];
        if (lst < n) {
          cmin(dp[s], array<int, 3>{lst + avail[j][lst].first, j,
                                    avail[j][lst].second});
        }
      }
    }
  }
  if (dp.back()[0] <= n) {
    cout << "YES\n";
    int s = (1 << m) - 1;
    vc<vi> ans(m);
    int N = n;
    while (s) {
      int j = dp[s][1], k = dp[s][2];
      rep(i, k) { ans[j].pb(a[--N].second); }
      s ^= 1 << j;
    }
    rep(i, m) {
      cout << sz(ans[i]) << " ";
      for (auto j : ans[i]) {
        cout << j + 1 << " ";
      }
      cout << "\n";
    }
  } else {
    cout << "NO\n";
  }
}

F.

F 好难，没什么人过，摆了。