Codeforces 804 div2

比赛链接

A. The Third Three Number Problem

题意

找出任意的$a,b,c\ (0 \le a, b, c \le 10^9)$ 使得 $(a\oplus b)+(b\oplus c)+(a\oplus c)=n$ $(1 \le n \le 10^9)$ ，不存在输出 $-1$。

题解

因为是二进制运算，所以按位考虑。考虑三个数同一二进制位的$1$的个数。

Code

   (a ^ b) + (b ^ c) + (a ^ c)
0: (0 ^ 0) + (0 ^ 0) + (0 ^ 0) = 0
1: (1 ^ 0) + (0 ^ 0) + (1 ^ 0) = 2
2: (1 ^ 1) + (1 ^ 0) + (1 ^ 0) = 2
3: (1 ^ 1) + (1 ^ 1) + (1 ^ 1) = 0

这说明了，如果对应二进制位$i$(从$0$开始)上有$1$或$2$个$1$，则结果增加$2 \cdot 2^i = 2^{i+1}$。

由此可以结果必然是一个偶数，奇数直接输出$-1$。否则输出一个或两个$\frac{n}{2}$和$0$即可。

代码

略

B. Almost Ternary Matrix

题意

给出两个正偶数$n,m$，构造一个$n$行$m$列的01矩阵，使得矩阵中任一元素，它的上下左右四个方向中有且仅有两个与之不同。

题解

找规律题，规律如下

Code

□ ■ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ □ . . .
■ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ . . .
■ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ . . .
□ ■ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ □ . . .
□ ■ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ □ . . .
■ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .

代码

略

C. The Third Problem

题意

给出一个排列$a_1,a_2,\ldots,a_n$，值为$0$到$n-1$，询问有多少种排列$b_1,b_2,\ldots,b_n$与$a$相似。

相似的定义为，对于$a$和$b$的任意区间$[l,r]$ $(1 \le l \le r \le n)$：
$$\operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r])$$

$\operatorname{MEX}$函数即博弈论中的最小未出现非负整数。

条件 $n \le 10^5$，答案模$10^9+7$。

题解

既然是$\operatorname{MEX}$，则从$0$开始考虑。

如果区间$[l,r]$在$a$中包含了$0$，则在$b$中，它也必须要包含$0$，否则$a$中的该区间$\operatorname{MEX}>0$，而$b$中该区间的$\operatorname{MEX}=0$。最小的case为仅包含$0$这个数的区间，也就代表着，$a$和$b$中的$0$的位置必须相同。

再考虑$1$，如果$a$，$b$中$1$的位置不同，不失一般性，假设$a$中$0$和$1$距离较远，则可以找到这样一个区间，在$a$中它包含$0$，不包含$1$，而在$b$中包含了$0$和$1$，此时它们的$\operatorname{MEX}$不等。因此$1$的位移也必须相同。

再考虑$2$，此时$2$的位置有两种可能，在$0$与$1$之间或之外。

• 如果在$0$与$1$之间：$2$出现在任意位置都是可以的，因为使得$\operatorname{MEX} \ge 2$的区间必须要同时包含$0$和$1$，而包含了$0$和$1$自然也就包含了$2$，也就是$2$的位置不会对已经包含$0$和$1$的区间是否相似产生影响。方案数应该乘以它当前的可选位置数。
• 如果在$0$与$1$之外：$a$和$b$中$2$的位置必须相同，否则会出现和上面$1$的情况相同的问题。

因此，维护一个区间$[l,r]$，从小到大枚举数值$x$，如果$a$中$x$在当前区间内，则它的可选位置是区间长度减去已经固定位置的数值的个数，答案乘以$((r-l+1)-(x-1))$。如果$x$在当前区间外，则它将区间进行了扩展，之前出现的数值全部视为已固定位置的数值。

我在做题过程中想得复杂了，将在下一次扩大区间前加入的数字一起计算了，计算方法是在区间扩大时方案乘以
$$
A_{(区间长度-已经固定位置的数值数)}^{(未固定位置的数值数)}
$$
思路是等价的。

代码

c++

#include <bits/stdc++.h>

#define kN 100010LL
#define kMod 1000000007LL

int fac[kN];
int inv[kN];
int pos[kN];

int qpow(int a, int k) {
  int res = 1;
  while (k) {
    if (k & 1) res = (long long)res * a % kMod;
    k >>= 1;
    a = (long long)a * a % kMod;
  }
  return res;
}

void prepare() {
  fac[0] = 1;
  for (long long i = 1; i <= 100000; i++) {
    fac[i] = fac[i - 1] * i % kMod;
    inv[i] = qpow(fac[i], kMod - 2);
  }
  inv[0] = inv[1];
}

int a[kN];

inline int A(int m, int n) { return 1LL * fac[m] * inv[m - n] % kMod; }

inline void work() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    pos[a[i]] = i;
  }
  int l, r;
  l = r = pos[0];
  int x = 1;
  int fixed = 1;
  int in = 0;
  int ans = 1;
  while (x <= n) {
    if (x == n) {
      // 计算之前的区间的方案数
      ans = 1LL * ans * A(r - l + 1 - fixed, in) % kMod;
      break;
    }
    int p = pos[x];
    if (p >= l && p <= r) {
      in++;
      x++;
      continue;
    }
    // 计算之前的区间的方案数
    ans = 1LL * ans * A(r - l + 1 - fixed, in) % kMod;
    if (p < l)
      l = p;
    else if (p > r)
      r = p;
    fixed += in + 1;
    in = 0;
    x++;
  }
  printf("%d\n", ans);
}

int main() {
  prepare();
  int t;
  scanf("%d", &t);
  while (t--) work();
  return 0;
}

D. Almost Triple Deletions

题意

给定长度为$n$ $(n\le 5000)$的数组$a_1,a_2,\ldots,a_n$，每次操作可以删除相邻两个不相等的数字，要求进行任意次这样的操作使得数组剩余数字相同，询问最终结果最长可以有多长。

题解

最终删除到仅剩一种数字，设其为$x$，则一定是删除了首尾段或$x$之间的段。那么一段数字怎样确定能否被完全删除呢？

结论：一段数字能被完全删除的冲要条件是长度为偶数且出现次数最多的数字的出现次数不大于$\frac{L}{2}$

证明：首先长度为奇数肯定不能被完全删除。再看出现次数：出现次数为如果小于等于$\frac{L}{2}$，则采用此策略将其删完：每次选择出现次数最多的数，删除它和它相邻不等的数。任意时刻，此操作后仍然不会有数字出现次数大于长度一半$L’ = \frac{L-2}{2}$。分情况讨论：

• 如果当前最大次数为$\frac{L}{2}$且存在多个，则只会存在两个数，它们同时减一后次数为$\frac{L}{2}-1 \le L’$。
• 如果当前最大次数为$\frac{L}{2}$且只有一个数$a$，则至少存在另外两个数，他们的次数和是$\frac{L}{2}$，则删除$a$与随便另外一个数，剩下的数中出现最多的次数是$\frac{L}{2}-1\le L’$。
• 如果所有数字出现次数小于$\frac{L}{2}$，设出现次数最多的次数为$z \le \frac{L}{2}-1$，则删除出现次数最多的一个数和随便另外一个数，剩下的数中出现最多的次数最大可能为$z$或$z-1$，而$z \le L’$。

因此可以$O(n^2)$处理出来所有区间是否可以被删除。再$O(n)$扫一遍，如果当前值$x$与前面某个$x$之间的区间可以被删除，则以它为结尾的$x$最长长度为之前的$x$的长度$+1$。

代码

c++

#include <bits/stdc++.h>

#define kN 5010LL

int deletable[kN][kN];
int a[kN];
int f[kN];
int d[kN];

inline void work() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int l = 1; l <= n; l++) {
    memset(f, 0, sizeof(int) * (n + 1));
    int maxfreq = 0;
    for (int r = l; r <= n; r++) {
      int w = r - l + 1;
      f[a[r]]++;
      if (maxfreq < f[a[r]]) maxfreq = f[a[r]];
      if (((w & 1) == 0) && maxfreq <= w / 2)
        deletable[l][r] = true;
      else
        deletable[l][r] = false;
    }
    deletable[l][l - 1] = true;  // empty seg
  }
  deletable[n + 1][n] = true;
  memset(d, 0, sizeof(int) * (n + 1));
  for (int now = 1; now <= n; now++) {
    if (deletable[1][now - 1]) d[now] = 1;  // a[now] as the last
    for (int pre = 1; pre <= now - 1; pre++)
      if (a[pre] == a[now] && d[pre] > 0 && deletable[pre + 1][now - 1] && d[pre] + 1 > d[now]) {
        d[now] = d[pre] + 1;
      }
  }
  int ans = 0;
  for (int now = 1; now <= n; now++) {
    if (d[now] > ans && deletable[now + 1][n]) {
      ans = d[now];
    }
  }
  printf("%d\n", ans);
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) work();
  return 0;
}

E. Three Days Grace

题意

给定一个大小为$n$ （$n\le 10^6$）的multiset $A$，数值范围从$1$到$m$（$m\le 5\cdot 10^6$）。

可以执行以下操作：取出一个数$x$，将其分解为两个大于$1$的整数$p$和$q$，且 $p\cdot q=x$，将$p$，$q$放入multiset。定义平衡度为$\operatorname{max}(A)-\operatorname{min}(A)$。

可以执行任意次此操作，询问最小平衡度是多少。

题解

假设最小值为$L$，则每一个数字它应当分解为尽量接近$L$的几个因子。再考虑$L$的变化，如果$L-1$，则$a_i \nmid (L-1)$的$a_i$的分解是不会变化的。

对于$a_i \mid (L-1)$的$a_i$，则考虑它在$L$时的分解最大值与在$L-1$时的分解最大值哪个更小。对于$L-1$时的分解最大值怎么求呢？因为它在$L-1$时可能产生变化，是因为它能整除$L-1$，因此直接取$\frac{a_i}{L-1}$的最大值即可。这也就要求了这些能被$L-1$整除的数的更新数据要从小到大更新。详情见代码，复杂度约为$O(m\cdot \log{m})$。

这是枚举最小值，枚举最大值也是可以的，但是感觉思路更绕。

代码

c++

#include <bits/stdc++.h>

/*
枚举最小值L，计算每个初始值分解为>=L的尽可能小的因子的最大值是多少
*/

#define kM 5000010LL

bool exist[kM];
int maxfac[kM];
int cntmaxfac[kM];

inline void work() {
  int n, m, mi = kM, ma = -1;
  scanf("%d%d", &n, &m);
  memset(exist, 0, sizeof(bool) * (m + 1));
  memset(cntmaxfac, 0, sizeof(int) * (m + 1));
  for (int i = 1, v; i <= n; i++) {
    scanf("%d", &v);
    if (v > ma) {
      ma = v;
    }
    if (v < mi) {
      mi = v;
    }
    exist[v] = true;
  }
  for (int v = 1; v <= ma; v++) {
    maxfac[v] = v;
    if (exist[v]) cntmaxfac[v]++;
  }
  int p = ma;
  int ans = ma - mi;
  for (int l = ma; l > 0; l--) {
    if (1LL * l * l <= ma) {
      for (int v = l * l; v <= ma; v += l) {
        if (exist[v]) cntmaxfac[maxfac[v]]--;
        int pre = maxfac[v / l];
        if (pre < maxfac[v]) maxfac[v] = pre;
        if (exist[v]) cntmaxfac[maxfac[v]]++;
      }
    }
    while (!cntmaxfac[p]) p--;
    int now = p - mi;
    if (l <= mi) {
      now = p - l;
    }
    if (now < ans) ans = now;
  }
  printf("%d\n", ans);
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) work();
  return 0;
}