Codeforces Round #700 Div. 1

A. Searching Local Minimum

交互题，查找数组的一个波谷，要求查询次数在 100 次内，数组长度为 \(10^5\)。

经典二分查找即可。

 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


int n;
int ask(int k) {
  static int a[MAXN];
  if (k <= 0 || k > n) return INT_MAX;
  if (a[k]) return a[k];
  cout << "? " << k << endl;
  cout.flush();
  cin >> a[k];
  return a[k];
}

void answer(int k) {
  cout << "! " << k << endl;
  cout.flush();
  exit(0);
}

int main() {
  ios::sync_with_stdio(false);

  cin >> n;
  int l = 1, r = n;
  while (l < r) {
    int m = (l + r) / 2;
    if (ask(m) < ask(m + 1)) {
      r = m;
    } else {
      l = m + 1;
    }
  }
  answer(l);

  return 0;
}

B1. Painting the Array I

给定一个数组 \(a\)，要求将其划分为两个子序列 \(a^{(0)}, a^{(1)}\)，使得 \(seg(a^{(0)}) + seg(a^{(1)})\) 最大，其中 \(seg(a) = \sum [a_{i} \neq a_{i + 1}]\)。

做法很多，学弟用的 DP，题解给了一个形式化的证明。我的做法是首先将若干重复的串合并为两个，之后考虑什么情况下必定会出现 \(a^{(x)}_i = a^{(x)}_{i + 1}\)。对于两个成对出现的 \(a_i = a_{i + 1}, a_{j} = a_{j + 1}, i < j\) ：若 \(a_{i} \neq a_{j}\)，那么就可以直接将两个均分给两个子序列；若 \(a_{i} = a_{j}\)，那么我们就需要两个数字将两个对隔开，这就需要至少两个连续的数字来隔开，且均不为 \(a_{i}\)。

 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


const int MAXN = 1e5 + 3;

int a[MAXN];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  int n, m = 1;
  cin >> n >> a[0];
  for (int i = 1, cnt = 0; i < n; ++i) {
    cin >> a[m];
    if (a[m] == a[m - 1]) {
      if (cnt == 0) ++m, cnt = 1;
    } else {
      ++m, cnt = 0;
    }
  }

  int ans = m, pre = -1, len = 0, mx = 0;
  for (int i = 1; i < m; ++i) {
    if (a[i] != a[i - 1]) {
      if (a[i] == pre) {
        if (len) {
          if (len > mx) mx = len;
          len = 0;
        }
      } else {
        ++len;
      }
      continue;
    }
    if (len > mx) mx = len;
    if (a[i] == pre && mx < 2) --ans;
    pre = a[i], len = mx = 0;
  }
  cout << ans << "\n";

  return 0;
}

B2. Painting the Array II

与 B1 题意类似，要求 \(seg(a^{(0)}) + seg(a^{(1)})\) 最小。

使用 Bélády’s algorithm 算法来贪心。

 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


const int MAXN = 1e5 + 3;

int n, a[MAXN], pos[MAXN], nxt[MAXN];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(10);

  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];

  memset(pos + 1, 0x63, sizeof(int) * n);
  for (int i = n - 1; ~i; --i) {
    nxt[i] = pos[a[i]];
    pos[a[i]] = i;
  }
  int x = -1, y = -1, ans = 0;
  for (int i = 0; i < n; ++i) {
    debug(x, y, ans, a[i]);
    if ((~x) && a[x] == a[i]) {
      x = i;
    } else if ((~y) && a[y] == a[i]) {
      y = i;
    } else {
      ++ans;
      ((x == -1 || (y != -1 && nxt[x] > nxt[y])) ? x : y) = i;
    }
  }
  cout << ans << "\n";

  return 0;
}

C. Continuous City

构造一个图使得 \(1\) 到 \(n\) 的路径长度 \(\in [L, R]\)，且每个距离都恰好存在对应的一条路径。

二进制构造即可，构造题好靠智商啊 <(\= －︿－\=)>﹀)>

 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


vector<tuple<int, int, int>> edges;
void add_edge(int u, int v, int w) { edges.emplace_back(u, v, w); }

int solve(int l, int r) {
  if ((r & -r) == r) {
    int k = __builtin_ctz(r) + 2;
    add_edge(1, 2, 1);
    for (int i = 3; i <= k; ++i) {
      add_edge(1, i, 1);
      for (int j = 2; j < i; ++j) add_edge(j, i, 1 << (j - 2));
    }
    return k;
  }
  int k = 0;
  while ((1 << (k + 1)) < r) ++k;
  solve(1, 1 << k);
  add_edge(1, k + 3, 1);
  for (int i = 0; i <= k; ++i)
    if ((r - 1) >> i & 1)
      add_edge(i + 2, k + 3, ((r - 1) >> (i + 1) << (i + 1)) + 1);
  return k + 3;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(10);

  int l, r;
  cin >> l >> r;
  int n = solve(1, r - l + 1);
  if (l > 1) {
    ++n;
    add_edge(n - 1, n, l - 1);
  }
  cout << "YES\n" << n << " " << edges.size() << "\n";
  for (auto [u, v, w] : edges) cout << u << " " << v << " " << w << "\n";

  return 0;
}