- 2024-04-21[ZJOI2019] 语言 题解
不愧是\(ZJOI\),《最可做的一道题》都让人一头雾水……首先将问题转化到链上。可以将总共的组数转化为每个点可以到达的城市。明显给每个点建一棵动态开点线段树,维护可以和他通商的点。很明显,可以通商的点的标号连续的一段。我们可以将可以将每一次传播语言的工作当作区间修改
- 2024-04-10P5327 [ZJOI2019]语言 解题报告
oj:https://gxyzoj.com/d/gxyznoi/p/P35树上差分+线段树合并+树链剖分1.暴力从最基础的方法开始,暴力统计s-t上的点,然后用map直接统计,显然会T,20pts2.特殊性质测试点5,6保证了数据是一条链,将链上每一个节点编号为1-n对于每一次操作,可以记录其覆盖情况,设共有x个节点,有y个节
- 2023-09-25ZJOI2019 语言
Day00010101。考虑对每个点\(u\)计算贡献,求出所有经过它的路径的两个端点,包含这些点的最小连通块大小就是以\(u\)为端点的\((u,v)\)答案数对的个数。根据经典结论,对于\(m\)个点的点集\(u_1,u_2,\cdots,u_m\),钦定\(u_0=u_m\)且根据DFS序排序,则以任意点为根,包含它
- 2023-09-15【线段树合并、虚树】P5327 [ZJOI2019] 语言
终于1kAC了家人,感动吧。贺了很久,很累。前置题目:P3320[SDOI2015]寻宝游戏虚树的边权和:\[\sumdep_{a_x}-\sum_{x<n}dep_{a_x,a_{x+1}}-dep_{a_{1},a_{n}}\]考虑转化贡献,求过该点的链的并,最后再除以二即可。那么我们可以考虑维护以该点的子树的所有关键点以及
- 2023-05-30[ZJOI2019]麻将
dp套dp经典例题。这种题一般都是给你一个奇怪的合法条件,然后去做一些计数之类的东西,直接设计状态很不好做。我们考虑先设计一个判定合法的dp,以这个dp的状态和结果作为状态去dp。更一般的,我们发现dp的过程有初始状态和终止状态,转移看成有向边,可以建出一个自动机来。dp
- 2023-04-21【题解】P5327 [ZJOI2019] 语言
P5327[ZJOI2019]语言题目描述九条可怜是一个喜欢规律的女孩子。按照规律,第二题应该是一道和数据结构有关的题。在一个遥远的国度,有\(n\)个城市。城市之间有\(n-1\)条双向道路,这些道路保证了任何两个城市之间都能直接或者间接地到达。在上古时代,这\(n\)个城市之间处
- 2023-02-20【ZJOI2019】线段树
【ZJOI2019】线段树Description九条可怜是一个喜欢数据结构的女孩子,在常见的数据结构中,可怜最喜欢的就是线段树。线段树的核心是懒标记,下面是一个带懒标记的线段树的伪
- 2023-02-01luogu P5326 [ZJOI2019]开关
题面传送门直接优化高斯消元似乎不是很可做,可以换一种思路。我们先来考虑一个弱化版的问题:求某个时刻为当前局面的答案。这个东西长得一脸指数生成函数,不妨列出来,设\(F_
- 2022-10-31【ZJOI2019】开关(PGF)
听说这玩意叫PGF?方便起见,令\(p_i=\frac{p_i}{\sum_jp_j}\)。设\(F_i(x)\)表示对于第\(i\)个开关而言,对其进行\(k\)次操作之后,它达到目标状态的概率的EGF(其实文
- 2022-08-21[ZJOI2019]语言
先讲一个智障3log做法,听说考场上不止一个人写还都过了。树剖,转化为\((u,v)\)的\(dfs\)序若都在一个区间内则它们可以开展贸易活动。相当于求矩形总面积,可以扫描线。