【Atcoder】AGC022 B-F简要题解

一场咕咕咕了三天的AGC
可能我的智商不太适合做AGC？
可是立的flag总得完成！

*B.GCD Sequence

$n=3$不好构造，但是给了样例，直接输出即可。

为使全局$\gcd =1$，构造任意个2的倍数，奇数个3的倍数即可。
总存在方案使得$6|sum$：
打表找出$\le 12$的长度为$8$的构造，每次整体$+12$即可(注意分$n$的奇偶讨论)

C.Remainder Game

由于第$k$位操作的贡献是$2^k$，所以贪心从高到低诸位确定。
优化也不需要，暴力判即可。

*D.Shopping

求解最小化火车往返次数。

对于$\ge 2L$的$t_i$，直接$t_{i}mod2L$。

此时所有$t_i<2L$，设$l_i=[t_i\le 2x_i],r_i=[t_i\le 2(L-x_i)]$分别表示点$i$能否直接右进右出/左进左出。

安排所有点按标号依次选择，逐步优化：
对于$i<j,l_i=r_j=1$，可以先走$j$再从$j\to i$，贪心匹配最多即可。

注意讨论的细节：
code from wxh010910

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

const int N = 300005;

int n, m, x, y, a[N];
bool l[N], r[N];
LL ans;

int main() {
#ifdef wxh010910
  freopen("d.in", "r", stdin);
#endif
  Read(n), Read(m);
  for (int i = 1; i <= n; ++i) {
    Read(a[i]);
  }
  for (int i = 1, t; i <= n; ++i) {
    Read(t);
    if (t % (m << 1) == 0) {
      ans += t;
    } else {
      ans += 1LL * (t / (m << 1) + 1) * (m << 1), t %= m << 1;
      if (t <= a[i] << 1) {
        l[i] = true;
      }
      if (t <= m - a[i] << 1) {
        r[i] = true;
      }
    }
  }
  for (int i = 1; i < n; ++i) {
    if (x && r[i]) {
      if (l[i]) {
        ++y;
      }
      --x, ans -= m << 1;
    } else if (!l[i] && r[i]) {
      if (y) {
        --y, ++x;
      }
    } else if (l[i]) {
      ++x;
    }
  }
  if (!r[n]) {
    ans += m << 1;
  }
  printf("%lld\n", ans);
#ifdef wxh010910
  Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}

*E.Median Replace

设相邻第$i$个1和第$i+1$个1之间的$0$的个数为$a_i$(包括首尾端点)，分析如下：

• 通过$000\to 0$将$\ge 3$的$a_i$不断$-2$，使得每个$a_i\in \{0,1,2\}$。
• $101\to 0$相当于可以直接删除$a$序列中的$1$，此时$a$序列由$0,2$构成。
• 合并两个偶数(2或0)一定会变成奇数(1)，再删去这个奇数，相当于序列中数可以两两抵消

若存在$a_p=a_q=0,p<q$且$p$为奇数，$q$为偶数，则可达目标状态：$0,0$。

DP处理。

另：自动机解法

*F.Checkers

要被“显然”坑死了(智商捉急)
证明很不完善/严谨，欢迎指正(轻喷

一些明显的条件：

将答案看做$X$进制数，每一位上答案互不相关。问题转化为找合法的(由合法转移得到)$X$进制数的个数。

且系数均为$+2^p/-2^p$的形式，设第$i$位系数为$p_i$，则$\sum _{i=1}^n{p}_i=1$。且$p$序列中$1$和$-1$的总共出现次数为$1$，且若$\pm 2^i(i>0)$出现，$\pm 2^{i-1}$必然出现(即系数在2的次幂上是连续的)。

最关键的条件(和命题充分必要):
对于任意$i$，可以通过调整绝对值为$2^i$的$p$的符号使得绝对值$\le 2^i$的数和为$1$。

考虑构造过程，必要性“显然”。
？？？这里就看不懂了。
经过我长久的思考(1天，我TCL)，发现可以归纳法证明(？？？):
$A$满足，$B$满足，$2A-B$的所有绝对值$\le 2^i$项相当于$A$中所有绝对值$\le 2^{i-1}$的项(可以调整$2^{i-1}$的系数得到$1$，然后$\times 2$得到$2$)和$B$中所有绝对值$\le 2^i$的项，可以调整$2^i$的系数得到1，所以最终得到1。

充分性也可以归纳法证明(对于一个满足性质集合$S$，如果能分成$2A,-B$，$A,B$也满足这个条件，即得证)：

不妨设$-1\in S$($1\in S$的情况类似)，设$k$为最小的$2^k\in S$：

• 若对于$1\le i<k$，$-2^i$都至少出现了两次，则可以构造$A=\{-2^0,-2^1,...,-2^{k-2},2^{k-1}\}$
  这里又“显然”了qwq，再来证明一下：
  $2A=\{-2^1,-2^2,...,-2^{k-1},2^k\}$
  设$B=\{1,a_1{2}^1,a_2{2}^2,...,a_{k-1}{2}^{k-1},a_k{2}^k,...\}$
  则$S=\{-1,-(a_1+1)2^1,-(a_2+1)2^2,...,-(a_{k-1}+1)2^{k-1},(1-a_k)2^k,...\}$
  $a_i+1\ge 2\to a_i\ge 1(1\le i<k),1-a_k>1\to a_k<0$
  在$S$中，调整绝对值为$2^i(0\le i\le k)$项的系数得到1，而$B$中调整得到$-1-2^1-2^2-...-2^{i-1}\pm 2^i$，$2^i$可以随意定符号，所以定成删去的那个是$-2^i$即值$+2^i$可以得到1。
  而对于$i>k$，设原本$S$的前缀和$=sum$，则$B$的前缀和$=-sum-2^1-...-2^{k-1}+2^k=-sum+2$，设绝对值为$2^i$的项随意定符号后得到$1-sum$，同样可以系数取反得到$sum-1\to sum-1-sum+2=1$，得证。
• 否则记最小的只出现过一次的是$-2^i$。如果$i=1$，那么$B=\{0\}$满足条件；否则$-1-2\sum _{j<i}{2}^j<-2^i-1$，无解。

考虑$DP$，设$f[i][j]$表示前$i$个数，总和为$1+jV$的方案数，$V$表示当前枚举到的$V=2^k$项，$V$具体是多少不需要知道，预处理组合数$n^4$转移即可。