Codeforces 733C Epidemic in Monstropolis

发表于 分类于 Disqus：

链接

传送门

题意

给出两个序列\(a\)和\(b\)。每次可以将\(a\)中的两个大小不同的数字合并，合并后的数字为原来两数字之和，问能否使序列\(a\)与\(b\)相同，如果能输出合并方法。

思路

对于\(b\)中的每个数字都是由\(a\)中的一段区间和组成的，显然\(b\)中数字对应的\(a\)中的区间是唯一的，如果有区间包含的数字个数大于1且所有数字相同就无法合并。确定\(b\)中每个数对应的区间后，每次找最大且周围存在数比他小的数字合并即可。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>

using namespace std;

const int maxn = 510;

int a[maxn], b[maxn];
int p[maxn], Max[maxn];

int main() {
  int n, m;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  scanf("%d", &m);
  p[0] = 1;
  for (int i = 1; i <= m; ++i) {
    scanf("%d", &b[i]);
    int cnt = 0, sum = 0, j = p[i - 1];
    while (sum < b[i] && j <= n) {
      if (a[j] > Max[i]) {
        Max[i] = a[j];
        cnt = 0;
      }
      if (a[j] == Max[i]) {
        ++cnt;
      }
      sum += a[j];
      ++j;
    }
    p[i] = j;
    if (sum != b[i] || (cnt == p[i] - p[i - 1] && cnt != 1)) {
      puts("NO");
      return 0;
    }
  }
  if (p[m] != n + 1) {
    puts("NO");
    return 0;
  }
  puts("YES");
  for (int i = 1; i <= m; ++i) {
    int l = 0, r = 0, pos = 0, dt = p[i] - p[i - 1];
    if (dt == 1) {
      continue;
    }
    for (int j = 0; j < dt; ++j) {
      if (a[j + p[i - 1]] == Max[i]) {
        if (j != 0 && a[j + p[i - 1] - 1] != Max[i]) {
          printf("%d L\n", j + i);
          l = j - 1, r = dt - j - 1;
          pos = j + i - 1;
          break;
        }
        if (j != dt - 1 && a[j + p[i - 1] + 1] != Max[i]) {
          printf("%d R\n", j + i);
          l = j, r = dt - j - 2;
          pos = j + i;
          break;
        }
      }
    }
    while (l--) {
      printf("%d L\n", pos--);
    }
    while (r--) {
      printf("%d R\n", i);
    }
  }
  return 0;
}
相关文章