初赛成绩出了,和预想的一样,一分都没挂,开心。
subtask 1 ($n \leq 200$)
因为高位取$0$一定比高位取$1$优,我们考虑按照位从高到低进行检验,设$f_{i, j}$表示前$i$个数划分成$j$段是不是可行,在转移的时候要注意不能让之前计算过的高位从$0$变成$1$,最后只要找到一个$i$满足$A\leq i \leq B$并且$f_{n, i} == true$就可以使当前位取$0$了。
时间复杂度$O(n^3log(MaxInt))$。
subtask 2 ($n \leq 2000,\ A == 1$)
仍然从高位到低位倒叙循环考虑检验,因为这次划分的段数没有下界的限制,我们只要设$g_i$表示到$i$满足这一位取$0$所要划分的最大段数,转移的条件和$f$差不多,最后只要看一看是不是满足$g_n \leq B$就可以知道能不能取$0$了。
时间复杂度$O(n^2log(MaxInt))$。
代码里借鉴了上面大佬的一些写法。
Code:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int N = 205; const int M = 2005; const ll inf = 1 << 30; int n, len = 0, st, ed, g[M]; ll ans = 0, a[M], sum[M]; bool f[N][N]; template <typename T> inline void read(T &X) { X = 0; char ch = 0; T op = 1; for(; ch > '9'|| ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } template <typename T> inline void chkMin(T &x, T y) { if(y < x) x = y; } inline void solve1() { for(; len; --len) { for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) f[i][j] = 0; f[0][0] = 1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= i; j++) for(int k = 0; k < i; k++) if(f[k][j - 1]) { ll now = sum[i] - sum[k]; if((now & (1LL << (len - 1))) == 0 && (ans | (now >> len)) == ans) f[i][j] = 1; } } bool flag = 0; for(int i = st; i <= ed; i++) flag |= f[n][i]; ans <<= 1; if(!flag) ans |= 1; } } inline void solve2() { for(; len; --len) { for(int i = 1; i <= n; i++) g[i] = inf; g[0] = 0; for(int i = 1; i <= n; i++) for(int j = 0; j < i; j++) { ll now = sum[i] - sum[j]; if((now & (1LL << (len - 1))) == 0 && (ans | (now >> len)) == ans) chkMin(g[i], g[j] + 1); } ans <<= 1; if(g[n] > ed) ans |= 1; } } int main() { read(n), read(st), read(ed); for(int i = 1; i <= n; i++) { read(a[i]); sum[i] = sum[i - 1] + a[i]; } len = 0; for(ll tmp = sum[n]; tmp > 0; tmp >>= 1) ++len; if(st != 1) solve1(); else solve2(); printf("%lld\n", ans); return 0; }