[JOISC 2017] 自然公园 / Natural Park
NOIPlus 模拟赛 T4 放这个……
题目链接： [JOISC 2017] 自然公园 / Natural Park 。
题目描述：
有一个未知的 nnn 个点 mmm 个边的无向连通图，点编号 000 到 n−1n-1n−1 。
每次你可以调用 Ask(A,B,Place[]) 来询问只经过 Place[]Place[]Place[] 中的点时是否能从 AAA 到 BBB 。需满足 AAA 和 BBB 在点集中且 A<BA<BA<B 。 Place[]Place[]Place[] 是一个数组， Place[i]=1Place[i]=1Place[i]=1 表示可以经过 iii ， Place[i]=0Place[i]=0Place[i]=0 表示不可以经过 iii 。
Ask 操作调用次数不能超过 450004500045000 次。
你需要还原出这个无向连通图的每一个边，你可以调用 Answer(A,B) 来报告一条边，需满足 A<BA<BA<B 。
你需要实现函数 Dete ...
HDU20260723F 合成大 HDU
waw ，这是被出题人认为最难的一档题，我们居然做出来了。
题目描述：
构造仅包含 h ， d 和 u 的字符串 SSS ，满足 ∣S∣≤3001|S|\le3001∣S∣≤3001 且 SSS 里恰包含 nnn 个 hdu 子序列。
n≤109n\le10^9n≤109
神奇的写题历程。
这题是我和 WaterM 一起解决的。
一下是无聊的对话（回忆的，不保证百分百一样）：
……
WaterM ：你们对 F 有什么想法？
wzh ：根据 n 大小分类讨论。
WaterM ：详细点？
wzh ：大概就是如果 n<1e6n<1e6n<1e6 时固定一个右边的 u ，剩下全用 hd ，变为 hd 子序列计数。 nnn 大的时候就多搞点 uuu ，然后再调整。
WaterM ：想想……
wzh ：大概就把 nnn 按照 1,3,6⋯1,3,6\cdots1,3,6⋯ 拆分。
WaterM ：不对，达不到 1e9 。
wzh ：那就在末尾补一些 hhh...ddd...uuu... 。
WaterM ：想想……
WaterM ...
期望势能函数及其应用
定义
对于样本 X∈ΩX\in \OmegaX∈Ω ，定义其势能函数为 ϕ(X)\phi(X)ϕ(X) 。
若势能函数 ϕ\phiϕ 满足对于任意样本 Xt∈ΩX_t\in\OmegaXt∈Ω ，有：
E[ϕ(Xt+1)∣Xt]=ϕ(Xt)−1E[\phi(X_{t+1})|X_t]=\phi(X_t)-1
E[ϕ(Xt+1)∣Xt]=ϕ(Xt)−1
则从样本 sss 到样本 ttt 的期望操作次数为 ϕ(s)−ϕ(t)\phi(s)-\phi(t)ϕ(s)−ϕ(t) 。
证明好像要用到一个叫做 鞅的时停定理 的东西，很复杂，不过这里给一个不那么完善的简单证明。
特别的，这个势能函数往往需要根据题目猜测。
证明
让我们看看势能函数的条件到底是什么。
E[ϕ(Xt+1)∣Xt]=∑XPr[Xt+1=X∣Xt]ϕ(X)ϕ(Xt)=1+E[ϕ(Xt+1)∣Xt]=1+∑XPr[Xt+1=X∣Xt]ϕ(X)\begin{aligned}
E[\phi(X_{t+1})|X_t] &=\sum_{X}Pr[X_{t+1}=X|X_t]\phi(X)\\ ...
CF1019E Raining season
一辈子也不写闵可夫斯基和了。
题目链接： CF1019E Raining season 。
题目描述：
给一棵树，边权是一次函数 aix+bia_ix+b_iaix+bi 的形式。求当 x=0,1,⋯ ,m−1x=0,1,\cdots,m-1x=0,1,⋯,m−1 时的树的直径。
n≤105,m≤106n\le10^5,m\le10^6n≤105,m≤106 。
首先对于某一个路径的一次函数 kx+bkx+bkx+b ，为了求在 x=0,1,⋯ ,m−1x=0,1,\cdots,m-1x=0,1,⋯,m−1 时的最值，我们应该把他表示为平面直角坐标系的 (k,b)(k,b)(k,b) ，那么最后的答案就是所有路径的点对的凸包。
然后对于路径，我们应该点分治。那么对于一次的分治中心 xxx ，我们应该求出他的分治子树的所有点到 xxx 的路径的点对所形成的凸包。最后在把每个分治中心得到的凸包暴力合并就行了。问题在于如何合并两条从 xxx 出发路径。容易发现原来的 (k1,b1)(k_1,b_1)(k1,b1) 和 (k2,b2) ...
[WC2018] 通道
genlib 真是太好用了。
题目链接： [WC2018] 通道 。
题目描述：
给你三棵树 T1,T2,T3T_1,T_2,T_3T1,T2,T3 。
求 maxa,b{dist1(a,b)+dist2(a,b)+dist3(a,b)}\max\limits_{a,b}\{dist_1(a,b)+dist_2(a,b)+dist_3(a,b)\}a,bmax{dist1(a,b)+dist2(a,b)+dist3(a,b)} 。
n≤105n\le 10^5n≤105 。
这一看就是一个类似树的直径的东西。于是考虑边分治。在 T1T_1T1 上边分治后会得到左右两个点集，不妨记为 A,BA,BA,B 。设这些点到其中一个中心边的端点的距离为 valaval_avala ，那么就有 dist1(a,b)=vala+valbdist_1(a,b)=val_a+val_bdist1(a,b)=vala+valb ，其中 a∈A,b∈Ba\in A,b\in Ba∈A,b∈B 。
此时式子变为最大化 vala+valb+dist2(a, ...
「Daily OI Round 1」Memory
考试考三道题目都是线段树题目，写爽了。
考完试发现是自己场切两个紫题\textcolor{purple}{紫题}紫题 ，写一篇题解纪念。
题目链接： 「Daily OI Round 1」Memory 。
题目内容：
有 nnn 条线段 [li,ri][l_i,r_i][li,ri] ，每条线段有颜色 cic_ici 和权值 wiw_iwi 。
一个由线段构成的集合 MMM 合法当且仅当对于任意两条不同的线段 i,j∈Mi,j \in Mi,j∈M ，有 ci=cjc_i=c_jci=cj 或 [li,ri]∩[lj,rj]=∅[l_i,r_i]\cap [l_j,r_j]=\varnothing[li,ri]∩[lj,rj]=∅ 。这个集合的权值为 ∑i∈Mwi\sum\limits_{i\in M}w_ii∈M∑wi 。
求权值最大的集合的权值。
n≤105n\le 10^5n≤105 。
显然 DP 题目。
为了处理交集为空的限制，先按右端点排序，然后定义 fi,jf_{i,j}fi,j 为前 iii ...
[ICPC 2023 Jinan R] 向未来说你好
对你说再见。
题目链接： [ICPC 2023 Jinan R] 向未来说你好 。
题目内容：
给定长度为 nnn 的序列 aaa 的一个合法的子段划分为：设第 iii 个子段左右端点为 li,ril_i,r_ili,ri ，则需满足：
∀i, ∀j∈[li,ri], ,aj≤ri−li+1\forall i,\ \forall j\in [l_i,r_i],\ ,a_j\le r_i-l_i+1
∀i, ∀j∈[li,ri], ,aj≤ri−li+1
对于任意一个 iii ，求当 aia_iai 变为 111 ，合法子段划分数。
先考虑不带修改的情况。
设 fif_ifi 为以 iii 为结尾的合法字段划分总数，初始 f0=1f_0=1f0=1 ，则有：
fi=∑{fj ∣ ∀k∈[j+1,i], ak≤i−j}f_i=\sum\{f_j\ |\ \forall k\in[j+1,i],\ a_k\le i-j\}
fi=∑{fj& ...
值域有交平衡树合并及复杂度证明
以下内容理论上对多种平衡树都成立，但是此处假设这个只是对 FHQ Treap 成立。
合并
对于两棵树 l,rl,rl,r ，设 lll 树根的优先级大于 rrr ，那么先判断他们值域是否有交，如果没有交那么直接用 FHQ 的合并就行。如果有交就按照 lll 的权值将 rrr 分裂后将 lll 的两个儿子分别和分裂出来的子树合并。
例如如下代码：
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253void split(int p,int x,int &l,int &r){ if(!p)return (void)(l=r=0); down(p); if(val[p]<=x){ l=p; split(son[p][1],x,son[p][1],r); } else{ r=p; split(son[p][0] ...
CF1175G Yet Another Partiton Problem
人生中第三次写出特别强的黑题。
题目链接： CF1175G Yet Another Partiton Problem 。
题目描述：
给定一个数组 a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an，你需要将其分成 kkk 个子段（每个元素恰好属于一个子段）。
一个子段 al,al+1,…,ara_l, a_{l+1}, \dots, a_ral,al+1,…,ar 的权值定义为 (r−l+1)⋅maxl≤i≤r(ai)(r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)(r−l+1)⋅l≤i≤rmax(ai)。一个划分的权值是所有子段权值之和。
请你找到权值最小的划分方案。
n≤2×104,k≤100n\le 2\times 10^4,k\le 100n≤2×104,k≤100 。
时限 5s5s5s ，空间限制 500MB500MB500MB 。
根据范围可以猜测正解时间为 O(nklogn)O(nk\lo ...
[APIO2013] 出题人
难得我会写的构造。
题目链接： [APIO2013] 出题人 。
题目描述：
当今世界上各类程序设计竞赛层出不穷。而设计一场好比赛绝非易事，比如给题目设计测试数据就是一项挑战。一组好的测试数据需要对不同的程序有区分度：满足所有要求的程序自然应该得到满分，而那些貌似正确的程序则会在某些特殊数据上出错。
在本题中，你在比赛中的角色反转啦！作为一名久经百战的程序员，你将帮助 Happy Programmer Contest 的命题委员会设计这次比赛的测试数据。本次比赛命题委员会选择了两个图论问题，分为 888 个子任务。委员会写了一些貌似可以解决这些子任务的代码。在给任务设计数据的时候，命题委员会期望其中的一些源程序能够得到满分，而另外的一些则只能得到 000 分或者少许的部分分。现在你将会获得这些源程序（C, C++, Pascal 版本）。对于每个子任务，你需要去产生一组数据 XXX 使得它能将该任务给定的 222 种源程序 AAA 和 BBB 区分开来。更具体地说，生成的数据必须满足如下两个条件:
输入 XXX 对于源程序 AAA 一定不会出现超出时间 ...
