注意：sum[ ii ]表示第 ii 块的所有数字和，因为有序，实际上就是一个区间和。
题解：二进制枚举答案ans，怎么枚举呢？从高位到低位放1，如果这个序列划分成m块后，能够sum[1] & sum[2] & ···· & sum[m] = ans，那么这位能够放1。dp[ i ][ j ] 表示 1 ~ i 这i个数能否划成 j 个块，使得 sum[1] & sum[2] & ····· & sum[j] = ans。dp[ i ][ j ] = 1 only if some p ( j - 1 <= p < i ), dp[ p ][ j - 1 ] = 1 and ( a[ i ] - a[ p ] )&x == x。意思是当存在 1 ~ p 这 p 个数能划分成 j - 1 块，所以当第 j 块的区间和与上 x 等于 x 的时候，这 i 个数能划分成 j 块。怎么判断这些块的与等于ans？显然不能求出所有的区间和然后再进行与操作，转化一下，如果 a & x = x, b & x = x, c & x = x,则 a & b & c = x。正确性我没考证！！！所以这需要单独的判断每个区间就行了。
感受：连着两场的dp都没写出来，dp非常有意思就是有点难理解。
#pragma warning(disable:4996)#include#include #include #include #include #define ll long long#define mem(arr, in) memset(arr, in, sizeof(arr))using namespace std;const int maxn = 100;bool dp[maxn][maxn];ll n, m, ans, a[maxn];bool check(ll x) { mem(dp, 0); dp[0][0]=1; for (int i = 1; i <= n; i++) { // 枚举 i 个数 for (int j = 1; j <= i; j++) { // 枚举块，所以写成 j <= min( m, i ) 也行 for (int k = j - 1; k < i; k++) if (dp[k][j - 1] && ((a[i] - a[k]) & x) == x) dp[i][j] = 1; // 一定要从 j - 1 开始 } } return dp[n][m];}int main(){ while (cin >> n >> m) { for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1]; ans = 0; for (int i = 60; i >= 0; i--) if (check(ans | 1LL << i)) ans |= 1LL << i; cout << ans << endl; } return 0;}
题解：考虑每个点，包含这个点的区间能够产生不同的数，实际上就是考虑这些区间的子集（2^n-1)，先用线段树标记一下，用bitset暴力枚举。
感受：这道题我也没完全搞明白，题解只是一个笑话。重点依然是bitset这个数据结构！！！！其实不是状态转移了，就是bitset优化的暴力而已。对于一个集合，bitset可以枚举出这个集合的任意一个子集的和。注意bitset的每一位代表着什么，然后手动模拟一些数据，体验一下移位和或这两个操作的意思。一定要明白bitset里面的每一位表示什么
#pragma warning(disable:4996)#include#include #include #include #include #include #define ll long long#define lson root<<1#define rson root<<1|1#define mem(arr, in) memset(arr, in, sizeof(arr))using namespace std;const int maxn = 10004;using bs = bitset ;int n, q;vector v[4 * maxn];void Update(int l, int r, int root, int L, int R, int x) { if (l > R || r < L) return; if (L <= l && r <= R) { v[root].push_back(x); return; } int mid = (l + r) >> 1; Update(l, mid, lson, L, R, x); Update(mid + 1, r, rson, L, R, x);}bs ans;void DFS(int l, int r, int root, bs dp) { bs go = dp; for (auto op : v[root]) go |= go << op; if (l == r) { ans |= go; return; } int mid = (l + r) >> 1; DFS(l, mid, lson, go); DFS(mid + 1, r, rson, go);}int main(){ while (scanf("%d %d", &n, &q) != EOF) { for (int i = 1; i <= q; i++) { int l, r, x; scanf("%d %d %d", &l, &r, &x); Update(1, n, 1, l, r, x); } bs dp; dp[0] = 1; DFS(1, n, 1, dp); int cnt = 0; for (int i = 1; i <= n; i++) if (ans[i]) cnt++; printf("%d\n", cnt); for (int i = 1; i <= n; i++) if (ans[i]) { printf("%d ", i); } printf("\n"); } return 0;}