- 2024-07-25[lnsyoj538/luoguP3628/APIO2010]特别行动队
题意原题链接给定序列\(a\)和自定义二次函数\(f(x)=ax^2+bx+c(a<0)\),要求将\(a\)分为几段(不妨设为\(k\)段),使得\(\sum_{i=1}^{k}f(\sum_{j=l_i}^{r_i}a_j)\)的值最大,求最大的值sol设计状态转移方程。显然,\(dp_i\)可以由\(dp_j\)转移当且仅当\(j<i\),这表示
- 2023-09-25P3629 [APIO2010] 巡逻
原题可以发现,当\(K=0\)时,答案为\(2(n-1)\),而当在两端点连了一条边后,则操作方法为如果这条路径上的某条边被标记过,则取消这条边标记;否则把这条边标记为标记过,答案即为未被标记的边*2+标记过的边+连边的个数当\(K=1\)时:答案显然为树的直径当\(K=2\)时:我们还是考
- 2023-07-25洛谷P3629 [APIO2010] 巡逻题解
题目链接P3629[APIO2010]巡逻-洛谷|计算机科学教育新生态(luogu.com.cn)思路n个村庄,n-1条道路,原图为树1.若k=0(不修建道路)那么答案为(n-1)*2 每个道路会走两遍2.若k为1(修建一条道路)设修建的道路(r1)所在的环长度为L那么答案为(n-1)*2-L+2可以看到r1所在环的道路只走了
- 2023-03-28【题解】[APIO2010] 信号覆盖
题目分析:其实就是涉及四个点之间的位置关系,三个点形成圆判断是否包含另一个点。考虑四个点之间形成的多边形只可能是凸四边形或者是凹四边形,如下图所示:(上图为凸多边形)
- 2022-11-05[APIO2010] 特别行动队
Statement传送门Solution先考虑最暴力的\(dp\),也就是\(f_i=\max_{j=0}^if_j+a(s_i-s_j)^2+b(s_i-s_j)+c\),其中\(s_i\)表示\(x_i\)的前缀和.那么此时我们可以把式子拆
- 2022-10-10[APIO2010]巡逻
做题时间:2022.10.10\(【题目描述】\)给定一棵\(N(N\leq10^5)\)个点的树,现在可以在这些点之间建立\(k(1\leqk\leq2)\)条边,使得从编号1的点便利一遍所有的边后返回
- 2022-10-04做题记录整理图论1 P3629 [APIO2010] 巡逻(2022/10/3)
P3629[APIO2010]巡逻写一道题顶写三道题系列,为了写这道题专门去学习了树的直径的两种求法,可以说是血赚了https://www.luogu.com.cn/blog/lscsznmhw/solution-p3629