11.16模拟赛 简记

概述

本场为综合真题模拟赛，T1为【CCO2015Day1T1（加拿大OI）】，T2为【POI2011（波兰OI）】，T3为【CEOI2017（中欧OI）】，T4为【BalkanOI2018】。
本场比赛相邻两题难度梯度跨度较缓，四题难度依次递增。T1为简单贪心，需要一定分类讨论和较为严密的思维；T2为困难数论，考察数学推理能力、数论知识储备（群的性质，gcd，质因数分解，质数筛法）；T3为高难度树形动态规划；T4为贪心+套路兼思维+数据结构维护。

订正情况

[100AC] T1
[97TLE] T2
[100AC] T3
[没有充分理解题解] T4

简记

题目链接

T1饥饿的狐狸
T2保险箱
T3追逐
T4字符串

题解

T3最有必要记录。临近NOIP还没打板子，因此只写T3题解了。

image.png

且看上图（示意图，不妨将 1 看成树根）。我们会发现在这条路径上，会有三种不同身份的点，分别如上图红、绿、蓝所示：绿点是起点，它的收益是 4,13,14,15 四个点上的铁球数；红点是往上走的点，它的收益是所有与它连接的点上的铁球数减去它的前一个点 3 上的铁球数，为什么要减去呢，因为 3 这个点上的铁球是两个人都会遇到的；蓝点是向下走的点，它的收益是它的儿子的铁球数总和，其实本质和红点是一样的，但是没有办法，一条路径上可能有向上走的也可能向下走，我们都需要考虑；那么 7 为什么要打阴影，就是 7 这个既可以算向上走又可以算向下走的点来把两段路径合并计入答案。

有了以上的分析，我们大致能想到这是一个树形 DP。

状态：\(f_{i,j,0/1}(g_{i,j,0/1})\)，\(f(g)\) 表示从 \(i\)（\(i\) 的儿子） 走到 \(i\) 的儿子（\(i\)），把以 \(i\) 为根的子树看成世界，半条路径的最大收益，\(j\) 表示放多少个磁铁，\(0/1\) 表示在 \(i\) 放不放磁铁。

设儿子为 \(son\)，\(i\) 的所有儿子铁球数之和为 \(v\)，\(i\) 的父亲为 \(p\)，某点 \(x\) 的父亲铁球数为 \(a_x\)。

最简单的：\({f_{i,j,0}}^\max_{\longleftarrow}\max(f_{son,j,0},f_{son,j,1}),{g_{i,j,0}}^\max_{\longleftarrow}\max(g_{son,j,0},g_{son,j,1})\)

第二简单的（是起点的情况）：\(f_{i,1,1}=v+a_p\)

继续得出

\[{f_{i,j,1}}^\max_{\longleftarrow}\max(f_{son,j-1,0},f_{son,j-1,1})+v\\ {g_{i,j,1}}^\max_{\longleftarrow}\max(g_{son,j-1,1},g_{son,j-1,1})+v-a_{son}+a_p \]

解释：\(v\) 和 \(v-a_{son}+a_p\) 都是表达”\(i\) 周围的铁球数和减前一个点的铁球数“，只是由于路径方向不同而表达形式不同。

DP 一难点是边界，注意 \(f_{i,0,1},g_{i,0,1}\) 是违法的，设成 \(-\infty\)。

知道如何递推，那怎么计算答案。为了保证不重复经过一条边我们考虑这样计算，对于将要用来更新 \(f_{i,×,×}\)的这个 \(son\)，我们在用它更新之前来计算一下由当前的 \(f(g)_{i,j_1,0/1}\) 和 \(f(g)_{son,j_2,0/1}\)（\(\forall j_1+j_2\le v\)）能不能更新答案 \(ans\)。

那么

\[ans^\max_{\longleftarrow}\max(f_{i,j_1,0},f_{i,j_1,1}+a_p-a_{son})+\max(g_{son,j_2,0},g_{son,j_2,1}),\forall j_1+j_2\le v\\ ans^\max_{\longleftarrow}\max(g_{i,j_1,0},g_{i,j_1,1})+\max(f_{son,j_2,0},f_{son,j_2,1}),\forall j_1+j_2\le v \]

解释：

  1. 为什么要 \(+a_p-a_{son}\)。因为我们当初算 \(f\) 的是候是当向下走来算的，默认了是从一个父亲节点走下来，那么现在这条路是↑到 \(i\) 又↓，所以需要加上没有算完整的 \(i\) 的收益 \(a_p\)，再减去原来算多的 \(a_{son}\)（因为现在是从 \(son\) 走过来）。
  2. 第一个式子是 \(\swarrow i\nwarrow son\) 的情况，第二个式子是 \(\nearrow i\searrow son\) 的情况。
  3. 这一部分如果通过 \(\forall0\le j_1\le v,0\le j_2\le v\) 的枚举实现复杂度 \(O(v^2)\)，难以承受。考虑倒序（从 \(v\) 到 \(0\)）枚举 \(j_2\)，实时用 \(f(g)_{i,j_1=v-j_2,×}\) 来更新记录 \(\max f(g)_{i,j_1=0\to j_2,×}\) 的前缀最大值变量，既可以只通过 \(O(v)\) 来解决。具体见代码。

据此已经解决了此题，总复杂度 \(O(nv)\)，是一道思维难度较大的树形 DP。

本篇题解参考 @zero4338 的题解，鸣谢

#include 
#define int long long
//typedef long long ll;
using namespace std;
inline int read(){
	register char ch=getchar();register int x=0;
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
const int N=1e5+5,V=105;
int n,v,ans,a[N],f[N][V][2],g[N][V][2];
vectorG[N];
void dfs(int x,int p){
	f[x][0][1]=g[x][0][1]=-1e16;
	int sum=0;
	for(int i=0;i=0;j--){
			mxf=max(mxf,max(f[x][v-j][0],f[x][v-j][1]+a[p]-a[y])),
			mxg=max(mxg,max(g[x][v-j][0],g[x][v-j][1]));
			ans=max(ans,mxg+max(f[y][j][0],f[y][j][1]));
			ans=max(ans,mxf+max(g[y][j][0],g[y][j][1]));
		}
		for(int j=1;j<=v;j++){
			f[x][j][0]=max(f[x][j][0],max(f[y][j][0],f[y][j][1])),
			g[x][j][0]=max(g[x][j][0],max(g[y][j][0],g[y][j][1]));
			f[x][j][1]=max(f[x][j][1],max(f[y][j-1][0],f[y][j-1][1])+sum),
			g[x][j][1]=max(g[x][j][1],max(g[y][j-1][0],g[y][j-1][1])+sum-a[y]+a[p]);
		}
	}
}
signed main(){
	n=read(),v=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1,u,v;i

相关

标签