网站建设需要哪些条件,phpcms律师网站源码,永州网站制作,微信公众平台注册要钱吗给定一长度为 N N N 的由非负整数组成的数组 a a a#xff0c;你需要进行一系列操作#xff0c;每次操作选择一个区间 [ l , r ] [l,r] [l,r]#xff0c;将 a [ l , r ] a_{[l,r]} a[l,r] 异或上 w w w。你需要将 a i a_i ai 全部变为 0 0 0。
求最小操作次数。…给定一长度为 N N N 的由非负整数组成的数组 a a a你需要进行一系列操作每次操作选择一个区间 [ l , r ] [l,r] [l,r]将 a [ l , r ] a_{[l,r]} a[l,r] 异或上 w w w。你需要将 a i a_i ai 全部变为 0 0 0。
求最小操作次数。 N ≤ 17 N\le17 N≤17 考虑两个左端点相同的修改 [ l , r 1 ] , [ l , r 2 ] ( r 1 r 2 ) [l,r_1],[l,r_2](r_1r_2) [l,r1],[l,r2](r1r2)可以把它拆成 [ l , r 1 ] [l,r_1] [l,r1] 和 [ r 1 1 , r 2 ] [r_11,r_2] [r11,r2]次数相同。所以没有两个区间左端点相同反过来右端点也不相同。
将 a a a 序列异或差分得到 b b b其中 b i a i ⊕ a i − 1 b_ia_i\oplus a_{i-1} biai⊕ai−1区间修改就变成双点修改区间非后缀或单点修改区间为后缀。最后同样要求 b b b 全为 0 0 0。
把 N N N 个数抽象成 N N N 个点修改就是在两个点之间连边如果是单点修改就是自环一组方案由几个连通块组成。先暂时不管 w w w 的取值考虑什么情况时会存在一个 w w w。
一个连通块大小为 x x x中的边数只可能有两种情况 x − 1 x-1 x−1一棵树 x x x一棵树加自环。我们的目标是让最后连通块的数全为 0 0 0。
考虑树的情况发现有解当且仅当连通块内的数异或和为 0 0 0。下证之。
必要性每次操作都是双点修改整个连通块内的异或和不变而最后要求异或和为 0 0 0那么一开始也必须是 0 0 0。
充分性考虑把这些数按编号顺序排成一排从前往后做操作每次操作都把最前面的消掉了变成 0 0 0而最后应得到全 0 0 0 的序列所以异或和必为 0 0 0。
对于有自环的情况自环的操作把那个点改成一个适当的值让除去自环的这棵树的异或和为 0 0 0所以这无论如何都有解。
发现答案就是 N N N 减去异或和为 0 0 0 的子序列个数。现在目标是最大化这样的子序列个数。
可以用状压 DP 求解先枚举状态 i i i再枚举它的子集 s s s若 s s s 的异或和为 0 0 0 d p i ← max ( d p i , d p i ⊕ s ) dp_i\gets\max(dp_i,dp_{i\oplus s}) dpi←max(dpi,dpi⊕s)。时间复杂度 O ( 3 n ) O(3^n) O(3n)。
注意要预处理出每个子集的异或和。
具体实现参照代码。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N(117)1;
int n,dp[N];
ll a[20],b[20],sum[N];
int main()
{freopen(xor.in,r,stdin);freopen(xor.out,w,stdout);scanf(%d,n);for(int i1;in;i) scanf(%lld,a[i]),b[i]a[i]^a[i-1];int N1n;for(int i0;iN;i){for(int j0;jn;j){if(ij1){sum[i]^b[j1];}}}for(int i0;iN;i){for(int si;s;s(s-1)i){if(!sum[s]) dp[i]max(dp[i],dp[i^s]1);}}printf(%d,n-dp[N-1]);
}
