手机网站首页新闻模板,网站建设外包服务公司创业计划书,有了云服务器怎么做网站,帝国文章网站模板洛谷P8877 [传智杯 #5 初赛] I-不散的宴会
题目大意
学生社会可以被看作一个排列成等腰直角三角形的节点阵列。该节点阵列共有 n n n行#xff0c;第 i i i行共有 i i i个节点#xff0c;我们将第 i i i行第 j j j列的节点标号为 ( i , j ) (i,j) (i,j)。
这些点具有权值。…洛谷P8877 [传智杯 #5 初赛] I-不散的宴会
题目大意
学生社会可以被看作一个排列成等腰直角三角形的节点阵列。该节点阵列共有 n n n行第 i i i行共有 i i i个节点我们将第 i i i行第 j j j列的节点标号为 ( i , j ) (i,j) (i,j)。
这些点具有权值。节点 ( i , j ) (i,j) (i,j)的权值为 r i ⊕ c j r_i\oplus c_j ri⊕cj其中 r r r和 c c c是给定的 01 01 01序列。
这些点有边相连。对于 1 ≤ i n 1\leq in 1≤in 1 ≤ j i 1\leq ji 1≤ji会有一条边连接 ( i , j ) (i,j) (i,j)和 ( i 1 , j ) (i1,j) (i1,j)。此外对于 2 ≤ i ≤ n 2\leq i\leq n 2≤i≤n还会有边连接 ( i , i ) (i,i) (i,i)和 ( i − 1 , a i ) (i-1,a_i) (i−1,ai)其中 a a a是给定的序列。
现在你需要从这些节点中选出一些节点使得这些节点间两两不存在边相连最大化选出来的节点的权值之和。 1 ≤ n ≤ 1 0 6 , 1 ≤ a i i 1\leq n\leq 10^6,1\leq a_ii 1≤n≤106,1≤aii 题解
首先我们可以发现这个图有 n ( n 1 ) 2 \dfrac{n(n1)}{2} 2n(n1)个点 n ( n − 1 ) 2 ( n − 1 ) \dfrac{n(n-1)}{2}(n-1) 2n(n−1)(n−1)条边边数比点数少 1 1 1这个图还是连通的所以这个图是一棵树。
我们将所有第 1 1 1层的点、第 n n n层的点和度数为 3 3 3的点设为关键点。那么关键点的个数是 O ( n ) O(n) O(n)的因为关键点只可能出现在第 1 1 1层、第 n n n层和连接 ( i , i ) (i,i) (i,i)和 ( i − 1 , a i ) (i-1,a_i) (i−1,ai)的边上可以自己画图感受一下。
除了关键点其他点的度数都为 2 2 2那么这些点肯定都在一条链上。于是我们可以把一条链看成两个关键点的边这些关键点和边就构成一棵虚树因为它的点的个数是 O ( n ) O(n) O(n)的所以边的个数也是 O ( n ) O(n) O(n)的。
建虚树时我们从下往上枚举每一行用 v i v_i vi表示第 i i i列最后一个关键点在虚树上的编号。假设当前遍历到第 i i i行则将 ( i − 1 , a i ) (i-1,a_i) (i−1,ai)和 v a i v_{a_i} vai在虚树上连一条边将 ( i , i ) (i,i) (i,i)和 ( i − 1 , a i ) (i-1,a_i) (i−1,ai)在虚树上连一条边并用 ( i − 1 , a i ) (i-1,a_i) (i−1,ai)来更新 v a i v_{a_i} vai还要求出新加在虚树上的点的权值。
建好的虚树后即求树上最大点权独立集可以用 D P DP DP来求。
设 f u , g u f_u,g_u fu,gu分别表示选择或不选择虚树上的节点 u u u的情况下子树 u u u能取得的最大点权独立集的值。
假设有两个关键点 u u u和 v v v它们之间通过链 s { v 1 , v 2 , … , v k } s\{v_1,v_2,\dots,v_k\} s{v1,v2,…,vk}连接则转移式为 f u max { v a l ( v 2 , v 3 , … , v k − 1 ) f v , v a l ( v 2 , v 3 , … , v k ) g v } f_u\max\{val(v_2,v_3,\dots,v_{k-1})f_v,val(v_2,v_3,\dots,v_k)g_v\} fumax{val(v2,v3,…,vk−1)fv,val(v2,v3,…,vk)gv} g u max { v a l ( v 1 , v 2 , … , v k − 1 ) f v , v a l ( v 1 , v 2 , … , v k ) g v } g_u\max\{val(v_1,v_2,\dots,v_{k-1})f_v,val(v_1,v_2,\dots,v_k)g_v\} gumax{val(v1,v2,…,vk−1)fv,val(v1,v2,…,vk)gv}
其中 v a l ( v 1 , v 2 , … , v k ) val(v_1,v_2,\dots,v_k) val(v1,v2,…,vk)表示 v 1 v_1 v1到 v k v_k vk在不能选择相邻元素的情况下可以取得的最大点权独立集。
这个图还有一个性质虚树中每条边在原图中对应的链上的点在同一列上。
那么假设这条链在第 k k k列其所在的区间为 [ a , b ] [a,b] [a,b]则
若 c k 0 c_k0 ck0则每个位置的权值为 r a , r a 1 … , r b r_a,r_{a1}\dots,r_b ra,ra1…,rb若 c k 1 c_k1 ck1则每个位置的权值为 ¬ r a , ¬ r a 1 , … , ¬ r b \neg r_a,\neg r_{a1},\dots,\neg r_b ¬ra,¬ra1,…,¬rb
那么问题就转化为查询对 r r r序列或 ¬ r \neg r ¬r序列求区间最大点独立集的大小。
对于一个 01 01 01序列我们可以用贪心来求最大点独立集。比如对于长度为 2 k 2k 2k的全 1 1 1段最大点独立集显然为 k k k对于长度为 2 k 1 2k1 2k1的全 1 1 1段最大点独立集显然为 k 1 k1 k1。对于含有 0 0 0的序列可以以 0 0 0作为分隔划分出各种全 1 1 1段在分别求和相加即可。
下面我们考虑如何求区间最大点独立集。
我们可以预处理出两个数组 h i h_i hi表示仅考虑前 i i i个元素得出的最大点独立集的大小 p i p_i pi表示第 i i i个元素所在的全 1 1 1段的最后一个 1 1 1的位置。如果位置 i i i是 0 0 0则 p i i − 1 p_ii-1 pii−1
假设我们当前要计算区间 [ l , r ] [l,r] [l,r]的最大点权独立集的大小那么结果为 h r − h min ( r , p l ) ⌊ min ( r , p l ) − l 2 2 ⌋ h_r-h_{\min(r,p_l)}\lfloor\dfrac{\min(r,p_l)-l2}{2}\rfloor hr−hmin(r,pl)⌊2min(r,pl)−l2⌋
即先求出 [ min ( r , p l ) 1 , r ] [\min(r,p_l)1,r] [min(r,pl)1,r]这一段的最大点权独立集的大小再统计 [ l , min ( r , p l ) ] [l,\min(r,p_l)] [l,min(r,pl)]这一段长度为 r − min ( r , p l ) 1 r-\min(r,p_l)1 r−min(r,pl)1的全 1 1 1段的最大点权独立集大小长度为 k k k的全 1 1 1段的最大点权独立集的大小为 ⌊ k 1 2 ⌋ \lfloor\dfrac{k1}{2}\rfloor ⌊2k1⌋。
时间复杂度为 O ( n ) O(n) O(n)。
code
#includebits/stdc.h
using namespace std;
const int N1000000;
int n,cnt0,R[N5],C[N5],a[N5],v[N5],vd[N5],s[2*N5],h[2][N5],p[2][N5];
int tot0,d[2*N5],l[2*N5],r[2*N5];
long long f[2*N5],g[2*N5],w[2*N5][4];
long long gt(int i,int l,int r){if(r-l1-2) return -1e18;if(lr) return 0ll;int eC[i];return 1ll*h[e][r]-h[e][min(r,p[e][l])](min(r,p[e][l])-l2)/2;
}
void gtin(long long *v1,int i,int l,int r){v1[0]gt(i,l,r);v1[1]gt(i,l,r-1);v1[2]gt(i,l1,r);v1[3]gt(i,l1,r-1);
}
void add(int xx,int yy,int i,int ll,int rr){l[tot]r[xx];d[tot]yy;r[xx]tot;gtin(w[tot],i,ll,rr);
}
void init(int e){for(int i1,lst0;in;i){if((R[i]^e)0){h[e][i]h[e][i-1];lsti;}else h[e][i]h[e][lst](i-lst1)/2;}p[e][n1]n;for(int in;i1;i--){if((R[i]^e)0) p[e][i]i-1;else p[e][i]p[e][i1];}
}
void dfs(int u){f[u]s[u];for(int ir[u];i;il[i]){int vd[i];dfs(v);f[u]max(f[v]w[i][3],g[v]w[i][2]);g[u]max(f[v]w[i][1],g[v]w[i][0]);}
}
int main()
{scanf(%d,n);for(int i1;in;i) scanf(%d,R[i]);for(int i1;in;i) scanf(%d,C[i]);for(int i2;in;i) scanf(%d,a[i]);init(0);init(1);for(int i1;in;i){v[i]cnt;vd[i]n;s[cnt]R[n]^C[i];}for(int in;i2;i--){add(cnt,v[a[i]],a[i],i,vd[a[i]]-1);v[a[i]]cnt;vd[a[i]]i-1;s[cnt]R[i-1]^C[a[i]];add(cnt,v[i],i,i,vd[i]-1);}dfs(cnt);printf(%lld,max(f[cnt],g[cnt]));return 0;
}
