滴滴笔试编程A题解法，状压DP O(N)解法
编程题，一眼秒了A题，但是先去做了B题，手贱提交了试卷。A题交了白卷，心痛。
笔试结束后发题解。
// update
先贴代码
#include <iostream>
using namespace std;
const int MAXBIT = 17;
const int maxn = 1e5 + 5;
const int MASK = (1<<MAXBIT) - 1;
int dp[(1<<MAXBIT) + 5];
int A[maxn];
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> A[i];
int m = 0;
dp[0] = 1;
int cur_max = 1;
for (int i = 0; i < n; i++) {
m ^= A[i];
cur_max = max(dp[m] + 1, cur_max);
dp[m] = cur_max;
}
cout << cur_max - 1 << endl;
}
其实就是一个状态dp，
考虑区间一定要连续分割，dp[m] 表示前缀xor和为m时的分割数，
那么dp[m] = dp[m] + 1;
因为这里区间可以不连续，所以加一个cur_max 记录一下就好了。这里可能有点不好理解，因为虽然当前前缀和为m，但是可以不连续划分，所以他可以的计数可以为前面所有点的max。
最后-1是因为需要处理 第一次划分，第一段前缀不为0的情况.
ps:
尴尬。怎么这么多熟人。提交了没有事做，来这里发个帖发发牢骚，求各位大佬莫笑。
ps2:
newcoder要是能提交之前再加一个确认就好了，一不小心就手贱了。
字节跳动公司氛围 642人发布
投递牛客等公司 >