Codeforces618F Double Knapsack

未分类

很妙的一道题。

考虑加强限制，将子集变为连续子序列。假设 $\sum\limits_{i=1}^n a_i \leq \sum\limits_{i=1}^n b_i$，那么对于任意一个 ${a_n}$ 的前缀和 $suma_i$ 都能找到一个最小的 $sumb_j \geq suma_i$，此时因为数字的值域是 $[1,n]$，一定有 $sumb_j-suma_i \in [0,n)$，因为有 $n+1$ 个 $sumb_j - suma_i$ 而值域里只有 $n$ 个数字，根据鸽巢原理一定能找到一组 $(i_0,j_0,i_1,j_1)$，满足 $sumb_{j_0}-suma_{i_0}=sumb_{j_1}-suma_{i_1}$，移项得 $sumb_{j_1}-sumb_{j_0}=suma_{i_1}-suma_{i_0}$ 也就是题目要求的序列。

#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long LL;
const int MAXN = 1e6;
int n;
int pos[2][MAXN | 1];
LL a[MAXN | 1], b[MAXN | 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
int main() {
  freopen("code.in", "r", stdin);
  freopen("code.out", "w", stdout);
  n = read();
  for (int i = 1; i <= n; ++i) {
    a[i] = a[i - 1] + read();
    // printf("i=%d a[i]=%d b[i]=%d\n", i, a[i], b[i]);
  }
  for (int i = 1; i <= n; ++i) {
    b[i] = b[i - 1] + read();
  }
  bool flag = false;
  if (a[n] > b[n]) std::swap(a, b), flag = true;
  memset(pos, -1, sizeof(pos));
  pos[0][0] = 0;
  pos[1][0] = 0;
  for (int i = 1, p = 0; i <= n; ++i) {
    while (b[p] < a[i]) ++p;
    if (pos[0][b[p] - a[i]] != -1) {
      if (flag == false) {
        printf("%d\n", i - pos[0][b[p] - a[i]]);
        for (int j = pos[0][b[p] - a[i]] + 1; j <= i; ++j) printf("%d ", j);
        printf("\n");
        printf("%d\n", p - pos[1][b[p] - a[i]]);
        for (int j = pos[1][b[p] - a[i]] + 1; j <= p; ++j) printf("%d ", j);
        printf("\n");
      } else {
        printf("%d\n", p - pos[1][b[p] - a[i]]);
        for (int j = pos[1][b[p] - a[i]] + 1; j <= p; ++j) printf("%d ", j);
        printf("\n");
        printf("%d\n", i - pos[0][b[p] - a[i]]);
        for (int j = pos[0][b[p] - a[i]] + 1; j <= i; ++j) printf("%d ", j);
        printf("\n");
      }
      return 0;
    }
    pos[0][b[p] - a[i]] = i;
    pos[1][b[p] - a[i]] = p;
  }
  return 0;
}