第一次做subtask题= =其实这题也没啥难度吧

其实就是两个subtask……

对于第一个subtask，就是满足\(1\leq n\leq 100\)且\(1\leq a\leq b\leq n\)。我们应该优先满足高位为\(0\)，于是乎可以贪心，从高位枚举到低位，看是否能在满足之前几位的限制条件的同时满足这一位答案为\(0\)。这个判定过程的话，可以设计状态\(d[i][k]\)表示前\(i\)位割成\(k\)段是否满足约束条件，枚举断点\(O(n)\)转移。

第二个subtask，虽然有\(n\leq 2000\)但是满足\(a = 1\)。这意味着分段数想怎么小就怎么小，所以我们可以直接去求这个序列要满足限制条件的话最少可以割成几段，这样的话第二维就可以省掉了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 2005;
ll Y[maxn], S[maxn];
int n, a, b;
const int maxb = 41;
ll st = 0;
namespace Task1 {
  bool d[105][105];
  bool dp(int bi) {
    memset(d, 0, sizeof(d));
    d[0][0] = true;
    for(int i = 1; i <= n; i ++) {
      for(int k = 1; k <= b; k ++) {
        for(int j = 0; j < i; j ++) {
          ll sum = S[i] - S[j];
          if((sum & (st | (1LL << bi))) == 0LL) {
            d[i][k] = (d[i][k] || d[j][k - 1]);
          }
        }
      }
    }
    for(int k = a; k <= b; k ++) {
      if(d[n][k]) return true;
    }
    return false;
  }
};
namespace Task2 {
  int d[maxn];
  bool dp(int bi) {
    d[0] = 0;
    for(int i = 1; i <= n; i ++) {
      d[i] = 0x3f3f3f3f;
      for(int j = 0; j < i; j ++) {
        ll sum = S[i] - S[j];
        if(!(sum & (st | (1LL << bi)))) {
          d[i] = std::min(d[i], d[j] + 1);
        }
      }
    }
    return (d[n] <= b);
  }
};

ll solve() {
  ll ans = 0;
  for(int i = maxb; i >= 0; i --) {
    bool flag = n <= 100 ? Task1::dp(i) : Task2::dp(i);
    if(flag) {
      st |= (1LL << i);
    } else {
      ans |= (1LL << i);
    }
  }
  return ans;
}

int main() {
  scanf("%d%d%d", &n, &a, &b);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &Y[i]);
    S[i] = S[i - 1] + Y[i];
  }
  printf("%lld\n", solve());
  return 0;
}

• 相关文章
• 全局相关文章