HNOI

[HNOI2009] 梦幻布丁 一种很暴力，很容易想到，但时间复杂度不对的做法： 既然每一次修改是以颜色作为单位的，那就用set或者链表(vector)维护每一个颜色出现的位置。将颜色\(x\)改为\(y\)的时候，遍历\(list_x\)的每一个点，判断其左右是否为\(y\)，更新ans(不同颜色 ......

[HNOI2016] 序列 题解：\(ST\)表 + 莫队 设莫队维护区间\([l,r]\)的答案\(ans\)，我们考虑右端点\(r\)向右扩张时\(r:=r+1\)对\(ans\)的影响，设\(min[l,r]\)代表区间\([l,r]\)中的最小值 \(ans :=ans+min[r,r]+m ......

# luogu P2322 [HNOI2006] 最短母串问题 [题目链接](https://www.luogu.com.cn/problem/P2322) 思路比较的简单的 dp 题。 首先看数据范围，$n \leqslant 12,len\leqslant50$ 应该是状压没跑了。 考虑设 $f ......

**P5540 [BalkanOI2011] timeismoney | 最小乘积生成树** 考虑检出平面直角坐标系，以 $\sum a_i$ 为 x 轴，$\sum b_i$ 为 y 轴。 考虑先求出 $A, B$ 分别为 $x$ 轴最小的点，离 $y$ 轴最小的点，这个我们可以使用最小生成树来解 ......

# P4729 [HNOI2009] 积木游戏 ## Solution 2023.09.06。八个月前做这个题调了六个小时。现在看来，除开欧拉定理的部分，整道题的思路极其清晰易懂，虽然码量大，但并不难码。尽管如此，融合了数据结构、图论（模型构建 + 三元环计数）、拓扑论（欧拉定理）多方面知识点，而且 ......

题目链接：[https://www.luogu.com.cn/problem/P2292](https://www.luogu.com.cn/problem/P2292) 题目大意： 给定 $n(\le 20)$ 个模式串 $s_i(|s_i| \le 20)$，有 $m(\le 50)$ 次询问， ......

链接：[P6604 [HNOI2016] 序列 加强版](https://www.luogu.com.cn/problem/P6604 "P6604 [HNOI2016] 序列 加强版") 首先，像这种题可以转化为计算贡献，即计算每一个元素成为最小值的次数。 这个次数怎么求呢？显然单调栈模板，对于每 ......

分享例题两则主要是分享一种 $\text{trick}$ 。 ## $\text{UVA1608}$ ### 题目描述 给定一个长度为 $n$ 的序列 $a$ ，如果 $a$ 的每一个子串都存在至少一个元素只出现了一次，输出 $\text{Non-boring}$ 。反之，输出 $\text{Bor ......

[Problem](https://www.luogu.com.cn/problem/P2285) ### Analysis 我们初始可以任意决定机器人的位置，状态很多，暴力显然会寄掉。 不妨先贪心的思考一下。我们肯定希望机器人初始在最先出现鼹鼠的洞，因为出现在没有鼹鼠的洞是无效的。 题目保证输入数 ......

（[题目传送门](https://www.luogu.com.cn/problem/P3203)） 虽然是 $\rm LCT$ 板子，但用来做分块入门 如果没有修改操作，可以 $O(n)$ 求出每个点的答案 对于每个块里的点，预处理出它跳出这个块的步数，那么查询时就可以 $O(1)$ 跳过这些块，查 ......

##**题目描述** 给你一个$n$元一次方程，判断是否有解，方程给出的格式为 $a-b=c$ ##**思路** 这道题看上去是一道题目看上去就是判断给出条件是否有矛盾，所以就自然而然的可以使用带权并查集 但是因为~~我太懒了并且~~这道题目要求使用**差分约束系统**进行求解，于是就需要将题目转化 ......

##**题目描述** 给你一个$n$元一次方程，判断是否有解，方程给出的格式为 $a-b=c$ ##**思路** 这道题看上去是一道题目看上去就是判断给出条件是否有矛盾，所以就自然而然的可以使用带权并查集 但是因为~~我太懒了并且~~这道题目要求使用**差分约束系统**进行求解，于是就需要将题目转化 ......

[Problem](https://www.luogu.com.cn/problem/P3205) ### Analysis 一道分类讨论dp 我们发现本题满足大区间包含小区间，区间之间可以互相推导，符合区间dp。 再看看我们需要记录什么？我们发现哪一个数最后放会影响到决策，所以我们需要记录这一层状 ......

PS 国是一个拥有诸多城市的大国。国王 Louis 为城市的交通建设可谓绞尽脑汁。Louis 可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。 Louis 希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变。Louis 会不断得 ......

# P4426 [HNOI/AHOI2018] 毒瘤 题解 非常好虚树题目，融合了容斥的内容。 ## 简化题意 给定一张 $n$ 个点、$m$ 条边的图，求图的独立集个数。其中 $n \leq 10^5$，$n-1 \leq m \leq n+10$。 独立集：对于图 $G(U, E)$ 的一个点集 ......

# [P3243 [HNOI2015] 菜肴制作](https://www.luogu.com.cn/problem/P3243) ## 题目描述 知名美食家小 A 被邀请至 ATM 大酒店，为其品评菜肴。ATM 酒店为小 A 准备了 $n$ 道菜肴，酒店按照为菜肴预估的质量从高到低给予 $1$ 到 ......

[题目传送门](https://www.luogu.com.cn/problem/P3244) 感觉这题挺有意思的，遂写。 ## 题目大意 给出一个有向无环图，再给定两个点 $s$ 和 $t$，表示在点 $s$ 和 $t$ 间加上一条边。求这个图有多少种生成树。 ## 题目分析 首先考虑不加边之前的 ......

https://www.luogu.com.cn/problem/P3244 题目简述 有一个$n$个点，$m$条边的DAG，现在向这个图中添加一条$l到r$的有向边，问有多少种以1为根的外向树方案。 数据范围 $1\le n\le 10^5,n-1 \le m \le min(2*10^5,\fr ......

posted on 2021-06-01 12:15:15 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/337504) 这题一看就知道是个模拟。 做模拟题的时候，一定要先确保你的程序能跑出正确的结果，再去想优化时间。 这道题还是 ......

题目传送门：[P3203 [HNOI2010] 弹飞绵羊](https://www.luogu.com.cn/problem/P3203) # 题意 $n$ 个数，满足 $i #define int long long using namespace std; const int N = 2e5 + ......

**[HNOI2012] 集合选数** [TOC] ## 题目描述 《集合论与图论》这门课程有一道作业题，要求同学们求出 $\{ 1, 2, 3, 4, 5 \}$ 的所有满足以下条件的子集：若 $x$ 在该子集中，则 $2x$ 和 $3x$ 不能在该子集中。 同学们不喜欢这种具有枚举性质的题目，于 ......

有意思的题，927ms 拿下最优解。 点数最多 $10^{10}$ 个，没法暴力拼接，考虑简化大树。 每次拼接，我们记录 $x$，$to$ 和 $to$ 所在大树的根节点 $rt$。然后连两条边： $(rt,to)$ 和 $(to,x)$。本质上相当于把每次接上来的子树缩成一个点。 这样大树的点数最 ......

首先可以观察出一颗 $n$ 个节点的二叉树，当其字典序最小的时候，其形态为一条向右偏的链，当其字典序最大的时候，是一条向左偏的链。 由于每一种编码对应唯一的一颗二叉树，我们可以先建树。 然后考虑树上分治，尝试以下三种方式： 1. 变大右子树的字典序 2. 变大左子树的字典序，并将右子树变成一条链 3 ......

很难得遇到细节题 打码5分钟调试两小时 感谢游老师送出的1.5h调试，感激 (争取每天用我的代码训练老师的该题能力） 细节/思路见注释 ```c++ #include #define int long long using namespace std; /* 本题细节很多！！！ 1.注意要把‘0’放 ......

# [HNOI2012]集合选数 ## 题目描述 《集合论与图论》这门课程有一道作业题，要求同学们求出 $\{ 1, 2, 3, 4, 5 \}$ 的所有满足以下条件的子集：若 $x$ 在该子集中，则 $2x$ 和 $3x$ 不能在该子集中。 同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问 ......

# P3227 [HNOI2013]切糕 ## 题意 给定一个 $P \times Q$ 的平面，平面上每一个点上都有一个高度为 $R$ 的竖条。 竖条上每一个点都有一个不和谐度 $f(x,y,z)$ ，对于每一个竖条选一个点，要求与周围的点的高度差不超过 $d$ (四联通)，求最小不和谐度。 ## ......

每当我们看到“最大值最小”“路径上的最大最小值”等字眼时，我们就可以考虑并查集。 我们可以尝试把这些问题转化为某种意义上按单调顺序的合并，利用并查集求解答案。以下时两例并查集的巧妙应用。 CF1213G Path Queries 注意“最大权值不大于q”，加上允许离线，我们可以把边按照权值排序，并一 ......

# [HNOI2012] 排队 ## 题目描述 某中学有 $n$ 名男同学，$m$ 名女同学和两名老师要排队参加体检。他们排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，那么一共有多少种排法呢？（注意：任意两个人都是不同的） ## 输入格式 只有一行且为用空格隔开的两个非负整数 $n$ ......

# [HNOI2012]永无乡 ## 题目描述 永无乡包含 $n$ 座岛，编号从 $1$ 到 $n$ ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 $n$ 座岛排名，名次用 $1$ 到 $n$ 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 $a$ 出发经过若干 ......

# P5288 [HNOI2019]多边形 ## Solution - 先进行大量的模拟。 - 最终所有线段的端点均为点 $n$。 - 第一问答案为 $(n - 1 - 与 n 相连的线段数量)$。 - 可以把线段看成节点，将原图转为若干棵二叉树组成的森林。 这里只建那些不与点 $n$ 相连的 ** ......