• 欢迎光临~

AGC005D 做题体验

开发技术 开发技术 2022-07-30 次浏览

题目链接
本人再次认为是一道不错的题目,可能是我菜。

判定可行解

首先假定我们已经得到了 (a)(b) 这两个序列,我们如何判断是否是有解的。

从图论的角度去分解这个问题,我们设当前序列为 (c)
(c_i=c_j) 时,我们连一条 ((i,j)) 双向边,代表第 (i) 位和第 (j) 位的数字应是相同的。
很显然,这几条边把相同数字的点都连上了边,那么如果整张图中只有一个连通块时,说明都是一种数值。
那么该如何连边,在这道题中非常显然,对于回文串连边即可。
因为对于一个长度为 (Len) 的回文串,我们能够连 (⌊frac{Len}{2}⌋) 这样的边。
所以如果 (Len) 为奇数,就不能恰好连完所以的边,我们设奇数段的个数为 (p)
那么很显然,一共会连出来 (frac{n-p}{2}) 条边,因为要求只有一个连通块所以边数至少为 (n-1) ,可以得出 (pleq 2) 的结论。

到现在为止,我们已经判断了是否有可行解的情况,现在考虑构造方案。

(p = 0)

先从 (p=0) 也就是说 (a) 中没有奇数元素的情况进行构造。
我们发现 (a) 可以保持不动,最主要的是要把相邻组的数字和同一组不同对的数组搞成一样。
这里直接给出结论:

[B={A_1+1,A_2,A_3,cdots,A_{m-1},A_m-1} ]

注意,当 (A_m-1 =0) 的时候直接把最后一位省略即可。

(p=1)(p=2)

其实我们只要构造出 (A) 那么 (B) 直接按照上述的情况构造即可。
(p=1) 时,我们可以把奇数的元素 (A_{odd}) 放到 (A) 的最后一个位置。
同样的,对于 (p=2) 的情况,我们把 (A_{odd}) 分别放到第一位和最后一位。

上述的思路仔细思索还是不难理解的。
具体细节可以看一下代码:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define Enter putchar('n')
#define quad putchar(' ')

const int N = 105;

int n, m, a[N], s, b[N];

signed main(void) {
  std::cin >> n >> m;
  for (int i = 1; i <= m; i++) std::cin >> a[i];
  for (int i = 1; i <= m; i++) s += (a[i] & 1);
  if (s > 2) {
    std::cout << "Impossible" << std::endl;
    return 0;
  }
  if (m == 1) {
    std::cout << a[1] << std::endl;
    if (a[1] == 1) {
      std::cout << 1 << std::endl << 1;
      return 0;
    }
    std::cout << 2 << std::endl;
    std::cout << 1 << " " << a[1] - 1 << std::endl;
  } else if (s == 0) {
    for (int i = 1; i <= m; i ++) std::cout << a[i], quad; Enter;
    a[1] ++; a[m] --;
    if (a[m] == 0) m --;
    std::cout << m << std::endl;
    for (int i = 1; i <= m; i++) std::cout << a[i], quad;
    Enter;
  } else if (s == 1) {
    std::stable_sort(a + 1, a + 1 + m, [](int p, int q) {return p % 2 < q % 2;});
    for (int i = 1; i <= m; i++) std::cout << a[i], quad; Enter;
    a[1] ++; a[m] --;
    if (a[m] == 0) m --;
    std::cout << m << std::endl;
    for (int i = 1; i <= m; i++) std::cout << a[i], quad;
    Enter;
  } else {
    int first = -1, last = -1;
    for (int i = 1; i <= m; i++) {
      if (a[i] % 2 == 0) continue;
      if (first == -1) first = a[i];
      else {last = a[i]; break;}
    } 
    int tot = 1;
    b[1] = first;
    for (int i = 1; i <= m; i++) 
      if (a[i] % 2 == 0) b[++tot] = a[i];
    b[++tot] = last;
    for (int i = 1; i <= m; i++) std::cout << b[i], quad; Enter;
    b[1] ++; b[m] --;
    if (b[m] == 0) m --;
    std::cout << m << std::endl;
    for (int i = 1; i <= m; i++) std::cout << b[i], quad;
  }
  return 0;
}
程序员灯塔
转载请注明原文链接:AGC005D 做题体验
喜欢 (0)