考试过程：开题顺序1,2，3,做T1的时候我想到了要求的东西，就是分成尽量少的段使得每段之和>=k，但是我不会求,就打了个暴力走了，然后看T2，这题我觉得和之前做过的一道题比较像，因为我觉得\(a_i\)比较大，所以我就把每个数取了个log,结果错了，根据log函数图象可知，或者根据公式\(log(a\times b)=log(a)+log(b)\),所以用 log 只适合有乘法运算的时候。然后T3，暴力没时间打了，其实是考场上\(n^2\)可以水过的一道题。总结一下：1.有一个想法之后可以联系之前学过的知识思考如何实现。2.要合理分配时间，没道题必须都要有分，模拟真实考试环境。

思路：容易发现，如果只考虑朝上走,就是求出每个点可以走到的点,接下来就是一个简单的倍增，（好吧，我在考场上就是想不到），接下来考虑往下走的一段。这里有一个神秘的观察,对于一条链,如果体力都是满的从两边开始走,那么复活的次数是一样的，证明的话可以使用调整法，将满足条件的一段进行左移即可。最后感谢varuxn教我关于倍增的基础知识，要从大到小进行枚举….代码如下：

AC_code 

  3. #include<bits/stdc++.h>
  4. #define int long long
  5. #define re register int
  6. #define ii inline int
  7. #define iv inline void
  8. #define head heeeaddd
  9. #define next net
  10. #define f() cout<<"YES"<<endl
  11. using namespace std;
  12. const int N=2e5+10;
  13. const int INF=1e9+10;
  14. int n,k,tot,q,timi;
  15. int to[N<<1],next[N<<1],head[N],val[N<<1];
  16. int size[N],top[N],son[N],deep[N],dfn[N],id[N],dis[N],fa[N];
  17. int die[N][35];
  18. vector<int> v;
  19. ii read()
  20. {
  21. 	int x=0;
  22. 	char ch=getchar();
  23. 	bool f=1;
  24. 	while(ch<'0' or ch>'9')
  25. 	{
  26. 		if(ch=='-') f=0;
  27. 		ch=getchar();
  28. 	}
  29. 	while(ch>='0' and ch<='9')
  30. 	{
  31. 		x=(x<<1)+(x<<3)+(ch^48);
  32. 		ch=getchar();
  33. 	}
  34. 	return f?x:(-x);
  35. }
  36. iv add(int x,int y,int z)
  37. {
  38. 	to[++tot]=y;
  39. 	next[tot]=head[x];
  40. 	head[x]=tot;
  41. 	val[tot]=z;
  42. }
  43. iv dfs(int st,int f)
  44. {
  45. 	deep[st]=deep[f]+1;
  46. 	size[st]=1;
  47. 	for(re i=head[st];i;i=next[i])
  48. 	{
  49. 		int p=to[i];
  50. 		if(p==f) continue;
  51. 		dis[p]=dis[st]+val[i];
  52. 		dfs(p,st);
  53. 		size[st]+=size[p];
  54. 		fa[p]=st;
  55. 		son[st]=(size[son[st]]>size[p])?son[st]:p;
  56. 	}
  57. }
  58. iv dfs2(int st,int t)
  59. {
  60. 	dfn[st]=++timi;
  61. 	id[timi]=st;
  62. 	top[st]=t;
  63. 	if(!son[st]) return;
  64. 	dfs2(son[st],t);
  65. 	for(re i=head[st];i;i=next[i])
  66. 	{
  67. 		int p=to[i];
  68. 		if(p==fa[st] or p==son[st]) continue;
  69. 		dfs2(p,p);
  70. 	}
  71. }
  72. ii get(int x,int y)
  73. {
  74. 	if(x==y) return x;
  75. 	int fx=top[x],fy=top[y];
  76. 	while(fx!=fy)
  77. 	{
  78. 		if(deep[fx]<deep[fy]) swap(x,y),swap(fx,fy);
  79. 		x=fa[fx],fx=top[x];
  80. 	}
  81. 	return deep[x]<deep[y]?x:y;
  82. }
  83. iv DFS(int st,int f)
  84. {
  85. 	int l=0,r,pos=INF;
  86. 	if(!v.empty())
  87. 	{
  88. 		r=v.size()-1;
  89. 		while(l<=r)
  90. 		{
  91. 			int mid=(l+r)>>1;
  92. 			if(dis[st]-dis[v[mid]]>=k)
  93. 			{
  94. 				pos=v[mid];
  95. 				l=mid+1;
  96. 			}
  97. 			else r=mid-1;
  98. 		}
  99. 		if(pos!=INF)
  100. 		{
  101. 			die[st][0]=pos;
  102. 			for(re i=1;(1<<i)<=n;i++) die[st][i]=die[die[st][i-1]][i-1];	
  103. 		}
  104. 	}
  105. 	v.push_back(st);
  106. 	for(re i=head[st];i;i=next[i])
  107. 	{
  108. 		int p=to[i];
  109. 		if(p==f) continue;
  110. 		DFS(p,st);
  111. 	}
  112. 	v.pop_back();
  113. }
  114. signed main()
  115. {
  116. 	n=read(),k=read();
  117. 	int u,v,c,x,y;
  118. 	for(re i=1;i<n;i++)
  119. 	{
  120. 		u=read(),v=read(),c=read();
  121. 		add(u,v,c);
  122. 		add(v,u,c);
  123. 	}
  124. 	dfs(1,0),dfs2(1,1),DFS(1,0);
  125. 	q=read();
  126. 	while(q--)
  127. 	{
  128. 		x=read(),y=read();
  129. 		int lca=get(x,y),now,cnt=0,ans=0,las1,las2;
  130. 		cnt=22;
  131. 		while(1)
  132. 		{
  133. 			if(deep[die[x][0]]<deep[lca] or (!die[x][0])) break;
  134. 			while( (!die[x][cnt] and cnt>=0) or (deep[die[x][cnt]]<deep[lca])) --cnt;
  135. 			ans+=(1<<cnt);
  136. 			x=die[x][cnt];
  137. 		}
  138. 		cnt=22;
  139. 		while(1)
  140. 		{
  141. 			if(deep[die[y][0]]<deep[lca] or (!die[y][0])) break;
  142. 			while( (!die[y][cnt] and cnt>=0) or (deep[die[y][cnt]]<deep[lca])) --cnt;
  143. 			ans+=(1<<cnt);
  144. 			y=die[y][cnt];
  145. 		}
  146. 		if(dis[x]+dis[y]-2*dis[lca]>=k) ++ans;
  147. 		printf("%lld\n",ans);
  148. 	}
  149. 	return 0;
  150. }


思路：这道题\(o(n^2)\)的朴素DP是很好想的，主要是说说如何进行优化，考虑分治,求通过中间的答案.
对于每个点,可以分别求出取不不取对应的中间的点的最优答案,记为\(l_{i,0/1}\),\(r_{i,0/1}\),那么考虑合并，对于 i,j,那么合并答案为\(max(l_{i,0}+r_{j,0},l_{i,1}+r_{j,0},l_{i,0}+r_{j,1})\).
令\(ld_i=max(l_{i,1}-l_[i,0],0)\),\(rd_i=max(r_{j,1}-r_{j,0},0)\),那么答案即为\(l_{i,0}+r_{j,0}+max(ld_i,rd_j)\),这东西可以进行排序，然后我们枚举左区间，二分查找右区间即可。实现细节较多，代码如下：

AC_code 

  3. #include<bits/stdc++.h>
  4. #define int	long long
  5. #define re register int
  6. #define ii inline int
  7. #define iv inline void
  8. using namespace std;
  9. const int N=2e5+10;
  10. const int mo=998244353;
  11. const int INF=1e18;
  12. int n,ans;
  13. int a[N],l[N][3][3],r[N][3][3],sumd[N],sumr[N];
  14. struct node {int val,pos;friend bool operator < (node a,node b) {return a.val<b.val;}}ld[N],rd[N];
  15. ii read()
  16. {
  17. 	int x=0;
  18. 	char ch=getchar();
  19. 	bool f=1;
  20. 	while(ch<'0' or ch>'9')
  21. 	{
  22. 		if(ch=='-') f=0;
  23. 		ch=getchar();
  24. 	}
  25. 	while(ch>='0' and ch<='9')
  26. 	{
  27. 		x=(x<<1)+(x<<3)+(ch^48);
  28. 		ch=getchar();
  29. 	}
  30. 	return f?x:(-x);
  31. }
  32. void solve(int L,int R)
  33. {
  34. 	if(L==R) return ans=(ans+a[L])%mo,void();
  35. 	int mid=(L+R)>>1;
  36. 	solve(L,mid),solve(mid+1,R);
  37. 	l[mid][1][1]=l[mid][2][1]=a[mid],l[mid][1][0]=l[mid][0][1]=-INF,l[mid][0][0]=0,ld[mid]=(node){a[mid],mid};
  38. 	r[mid+1][1][1]=r[mid+1][2][1]=a[mid+1],r[mid+1][1][0]=r[mid+1][0][1]=-INF,r[mid+1][0][0]=0,rd[mid+1]=(node){a[mid+1],mid+1};
  39. 	for(re i=mid-1;i>=L;i--)
  40. 	{
  41. 		l[i][1][0]=l[i+1][0][0]+a[i],l[i][1][1]=l[i+1][0][1]+a[i];//l[i][0][0] 左边的，自己不选，分界点(mid)不选
  42. 		l[i][0][0]=max(l[i+1][1][0],l[i+1][0][0]),l[i][0][1]=max(l[i+1][1][1],l[i+1][0][1]);
  43. 		l[i][2][0]=max(l[i][1][0],l[i][0][0]),l[i][2][1]=max(l[i][1][1],l[i][0][1]);//l[i][2][0/1] 表示在 i 处选不选右边界的最大值，起统计答案作用
  44. 		ld[i]=(node){max(0ll,l[i][2][1]-l[i][2][0]),i};
  45. 	}
  46. 	for(re i=mid+2;i<=R;i++)
  47. 	{
  48. 		r[i][1][0]=r[i-1][0][0]+a[i],r[i][1][1]=r[i-1][0][1]+a[i];//r[i][0][0] 右边的，自己不选，分界点(mid+1)不选
  49. 		r[i][0][0]=max(r[i-1][1][0],r[i-1][0][0]),r[i][0][1]=max(r[i-1][1][1],r[i-1][0][1]);
  50. 		r[i][2][0]=max(r[i][1][0],r[i][0][0]),r[i][2][1]=max(r[i][1][1],r[i][0][1]);
  51. 		rd[i]=(node){max(0ll,r[i][2][1]-r[i][2][0]),i};
  52. 	}
  53. 	sort(ld+L,ld+mid+1),sort(rd+mid+1,rd+R+1);
  54. 	sumr[mid]=sumd[mid]=0,sumr[mid+1]=r[rd[mid+1].pos][2][0],sumd[mid+1]=rd[mid+1].val;
  55. 	for(re i=mid+2;i<=R;i++) sumr[i]=(sumr[i-1]+r[rd[i].pos][2][0])%mo,sumd[i]=(sumd[i-1]+rd[i].val)%mo;
  56. 	for(re i=L;i<=mid;i++)
  57. 	{
  58. 		int p=upper_bound(rd+mid+1,rd+R+1,ld[i])-rd-1;
  59. 		ans=(ans+(p-mid)*((l[ld[i].pos][2][0]+ld[i].val)%mo)%mo+sumr[p]%mo)%mo;
  60. 		ans=(ans+(R-p)*(l[ld[i].pos][2][0])%mo+(sumr[R]-sumr[p]+mo)%mo+(sumd[R]-sumd[p]+mo)%mo)%mo;
  61. 	}
  62. }
  63. signed main()
  64. {
  65. 	n=read();
  66. 	for(re i=1;i<=n;i++) a[i]=read();
  67. 	solve(1,n);
  68. 	printf("%lld\n",ans);
  69. 	return 0;
  70. }


思路：因为这题数据太水了，\(o(n^2)\)的算法就能过，这也提示我们对于暴力算法可以进行优化，让他能够计算较大的数据，可能会多得分。
代码如下：

AC_code 

  1. #include<bits/stdc++.h>
  2. #define re register int
  3. #define int	long long
  4. #define ii inline int
  5. #define iv inline void
  6. #define head heeeaddd
  7. #define next net
  8. #define f() cout<<"YES"<<endl
  9. using namespace std;
  10. typedef unsigned long long u64;
  11. const int mo=998244353;
  12. const int N=5e6+10;
  13. int n,L,X,Y,A,B,cnt,timi,ans;
  14. int l[N],r[N],f[N],jc[N];
  15. bool hav[N];
  16. int q1[N],q2[N];
  17. struct node
  18. {
  19. 	int l,r;
  20. }cun[N];
  21. ii read()
  22. {
  23. 	int x=0;
  24. 	char ch=getchar();
  25. 	bool f=1;
  26. 	while(ch<'0' or ch>'9')
  27. 	{
  28. 		if(ch=='-') f=0;
  29. 		ch=getchar();
  30. 	}
  31. 	while(ch>='0' and ch<='9')
  32. 	{
  33. 		x=(x<<1)+(x<<3)+(ch^48);
  34. 		ch=getchar();
  35. 	}
  36. 	return f?x:(-x);
  37. }
  38. u64 xorshift128p(u64 &A, u64 &B) { 
  39.     u64 T = A, S = B; 
  40.     A = S; 
  41.     T ^= T << 23; 
  42.     T ^= T >> 17; 
  43.     T ^= S ^ (S >> 26); 
  44.     B = T; 
  45.     return T + S; 
  46. }   
  47. void gen(int n, int L, int X, int Y, u64 A, u64 B, int l[], int r[]) 
  48. { 
  49.     for (int i = 1; i <= n; i ++) { 
  50.         l[i] = xorshift128p(A, B) % L + X; 
  51.         r[i] = xorshift128p(A, B) % L + Y; 
  52.         if (l[i] > r[i]) swap(l[i], r[i]); 
  53.     } 
  54. }
  55. signed main()
  56. {
  57. 	n=read(),L=read(),X=read(),Y=read();
  58. 	scanf("%llu%llu",&A,&B);
  59. 	gen(n,L,X,Y,A,B,l,r);
  60. 	for(re i=1;i<=n;i++) 
  61. 		if(!l[i] and !r[i]) ++cnt,f[i]=0;
  62. 		else hav[i]=1,q1[++q1[0]]=i;
  63. 	jc[0]=1;
  64. 	for(re i=1;i<=n;i++) jc[i]=(jc[i-1]%mo)*3%mo;
  65. 	while(1)
  66. 	{
  67. 		if(cnt==n) break;
  68. 		++timi;
  69. 		q2[0]=0;
  70. 		for(re i=1;i<=q1[0];i++)
  71. 		{
  72. 			if(i==1 or i==q1[0] or l[q1[i]]==r[q1[i]] or l[q1[i]]+1==r[q1[i]] or (!hav[q1[i]-1]) or (!hav[q1[i]+1])) {f[q1[i]]=timi;continue;}
  73. 			cun[q1[i]].l=max(l[q1[i]]+1,max(l[q1[i-1]],l[q1[i+1]]));
  74. 			cun[q1[i]].r=min(r[q1[i]]-1,min(r[q1[i-1]],r[q1[i+1]]));
  75. 			if(cun[q1[i]].l>cun[q1[i]].r) f[q1[i]]=timi;
  76. 			else q2[++q2[0]]=q1[i];
  77. 		}
  78. 		for(re i=1;i<=q1[0];i++) hav[q1[i]]=0,l[q1[i]]=cun[q1[i]].l,r[q1[i]]=cun[q1[i]].r;
  79. 		for(re i=1;i<=q2[0];i++) hav[q2[i]]=1,q1[i]=q2[i];
  80. 		cnt+=q1[0]-q2[0];
  81. 		q1[0]=q2[0];
  82. 	}
  83. 	for(re i=1;i<=n;i++) ans=(ans%mo+f[i]*jc[i-1]%mo)%mo;
  84. 	printf("%lld\n",ans);
  85. 	return 0;
  86. }


版权声明：本文为WindZR原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/WindZR/p/15255271.html