NOI

感觉难度和今年 D2T2 差不多。 首先一个很显然的事情是，每一步得到的分数的分子分母都是互质的，证明参考 SBT。而最后答案要求我们将分子分母都求出来而不是求分数值，所以可以很明显的想到将分数当成一个二元组然后维护变换。 考虑从右往左扫，假设当前分数为 $\dfrac{x}{y}$，那么扫过 $a ......

好吧，作为一道绿题，我还是没能够自己做出来。 我做这道题时思路：利用并查集，对于 M 询问，如果不在同一集合则将两者所在集合合并，对于 C 询问 ，如果不在同一集合很好解决，如果在同一集合，我们需要解决的首要问题是如何计算出两者之间的数量 。 所以就从这道题出发，学习一下带权并查集吧！ **思路：通 ......

显然将权值离散化是没有问题的，因为必然存在一组最优解，满足每个 $a_i$ 都取自于某个 $V_i$，于是不管三七二十一先将 $V_i$ 离散化了再说。 考虑从部分分入手逐步分析这道题： - 特殊性质 A：$V_i=1$ 相当于这个区间中的数必须是 $1$，先将这些数去掉不管，紧接着考虑 $V_i= ......

## 题目描述 小 A 被选为了 ION2018 的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。 由于 ION 已经举办了很多届，所以在题目命名上也是有规定的，ION 命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名 ......

# [NOI2021] 路径交点 题解 ## 题意 给定一张 $k$ 层的有向图，第 $i$ 层有 $n_i$​ 个顶点，第 ​$1$ 层与第 $k$​ 层**顶点数相同**。对于第 ​ ​$j$ $(1 \leq j using namespace std; const int N = 205; ......

[Problem](https://www.luogu.com.cn/problem/P1880) ### Solution 本题还有一个弱化版，见[Luogu P1775](https://www.luogu.com.cn/problem/P1775) 我们发现本题和弱化版唯一区别就是本题有环。 ......

## NOI2023 题解 应该是全网首发？ ### D1T1 方格染色 shaber 题。 首先假设只有横竖线，总答案等于横线的并 + 竖线的并 - 横竖的交。前面二者排序后容易计算，后面考虑按照 $x$ 递增顺序依次加入竖线，同时扫描线维护横线，在加入新的竖线的时候减去此时在区间的横线个数，可以 ......

考虑对合并过程建一棵树。 对于一个点 $x$，定义 $a_x$ 表示它向上合并的时候，对答案造成的重量贡献的系数。 定义一个点的层级 $d_x$ 为它的两个儿子层级的较大值 $+1$。我们称 $d$ 更小的层级为更深的层级。 那么层级为 $i$ 的非根非叶子节点会对答案造成 $2^i-1$ 的磨损值 ......

扔到 cnblogs 上。 ## Day -4 最后一场模拟赛，肯定要用力打啊！ 然而一题不会，呜呜呜。 于是开始拼暴力，写了 $90 + 60 + 60 = 210$，结果挂成 $40 + 60 + 60 = 160$。 T1 我将题目转化为：对于一个排列，每次只改动三个位置，要求某个数的出现位置 ......

打的太 shaber 了，于是补补题。 ## D1T1 扫描线。 首先我们可以容斥一下，答案为被一种操作覆盖到的减去被两种操作覆盖到的加上被三种操作覆盖到的。 首先考虑只被一种操作覆盖到的，这很简单，直接上个区间颜色段推平就好了，顺便去了个重。 接下来是有被斜线覆盖到的，这样的点数为 $O(nk)$ ......

从部分分考虑起。性质 A 看上去在很多字符串题里都有出现，因此我们从看上去比较奇怪的性质 B 入手。因为 $\forall i\in[1,n-1],s_i\ne s_{i+1}$，所以 $\forall l\in[1,r],s_{i+l}\ne s_{i+l-1}$，也就是说 $s[i,i+l-1] ......

[P1196 [NOI2002] 银河英雄传说](https://www.luogu.com.cn/problem/P1196) 使用带权并查集维护： 1. 每个战舰所属列。 2. 每个战舰到当前列第一个战舰的距离。 3. 每列的战舰数量。 - 如何求同列战舰之间相隔的战舰数量？ 使用两战舰到当前列 ......

[题目链接](https://www.luogu.com.cn/problem/P9481) 题目要求我们求出任意两点间最短路径之和，由于图比较特殊，除树边外只有祖先到其子树内的边，我们首先考虑最短路径有没有什么特殊性质。 注意到两点之间的最短路分为一下三种： 1. 节点到其祖先的最短路：直接沿着树 ......

Day1 被找规律随机区分 $35$ 分。Day2 以我现有的水平已经无力回天了，d2T3 却还挂了 $35$ 分。 连队线的边都没碰到，只混到了 $100$ 多名的 Ag。 我不愿回忆这场考试的任何细节，知道寄了就行了。 分数是从低往高排的。nfls 的众人中，我是第一个上去的。为什么在公布 Ag ......

不好评价题。 容易知道在该题目条件下 $dis[u\to v]=dis[u\to\text{LCA}(u,v)]+dis[\text{LCA}(u,v)\to v]$。其中 $dis[u\to\text{LCA}(u,v)]$ 是 $u$ 一直往父亲跳，容易预处理。现在难点在于处理出所有 $dis[ ......

[Link](https://www.luogu.com.cn/problem/P6773) **题意** 给定一棵 $n$ 个节点的有根树和 $m$ 条祖先到后代的链。问有多少种把边权设置为 $0$ 或 $1$ 的方案使得每条链上至少有一条边是 $1$。 答案对 $998244353$ 取模。 $ ......

前情提要：HE 春测+省选 rk24，D 类选手。 # 前言 之前省选游记好像说目标是拿到 D 类名额+省内高一前 $5$，虽然做到了但是 D1T2 没分析出很显然的树上做法、D1T3 没有想线段树分治以及 D2T2 选择二分图建模而不是二元组连边都是相当降智操作。结果是导致清北营不过审。 中途 $ ......

# [NOI2011] 阿狸的打字机 ## 题目描述 阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有 $28$ 个按键，分别印有 $26$ 个小写英文字母和 `B`、`P` 两个字母。经阿狸研究发现，这个打字机是这样工作的： * 输入小写字母，打字机的一个凹槽中会加入这个字 ......

想了很久，还是决定写退役记，全都要靠回忆所以应该会漏不少细节。 因为已经退役，比赛过程写的比较少，看个乐就行。 ## 7.2~7.21 2 号提前到了成都七中，打了两周多的模拟赛。基本都是垫底的，题也补的很少。感觉状态有点差的。保持手感完全靠和学弟 duel，学弟好强。 ## 7.22 报到日。 上 ......

和考试的时候思路差不多。 首先考虑钦定一部分关键点是合法的 **根** ，带上容斥系数。 对于一条非树边，要求其在任何一个钦定点作为根的时候都不是横叉边。 具体而言，对于一个钦定点集合，我们建出钦定点集合的虚树，那么符合条件的非树边有如下几类： 不妨先考虑特殊性质 $B$ ，没有横叉边的情况： - ......

对于给出的串 $S$，将其拓展成 $S+$ 特殊字符 $+rev(S)$ ，求出其后缀数组。 那么对于一个子串 $[l,r]$，合法的必要条件是 $l$ 的后缀在后缀数组的排名小于 $r$ 的前缀的排名。 之所以是必要条件，是因为会记入一些 $[l,r]$ 是回文串且 $l$ 的排名小的情况。 具体 ......

### [P9482 [NOI2023] 字符串](https://www.luogu.com.cn/problem/P9482) 限制长的很像回文串，但是是字典序关系。 定睛一看比较的是原串 $s$ 的一个后缀的前缀 和 翻转串 $s'$ 的一个后缀的前缀比字典序。 直接把 $s'$ 拼到 $s$ ......

## D1T1 #### 前置知识：扫描线 首先问题是所有线的并集大小，我们可以想到相交的两条线是可以合并的，在合并之后，第一种线和第二种线可以直接用扫描线求并集。 而第三种线最多只有 $5$ 条，我们先将第三种线的大小全部加到答案上，然后直接枚举第一种和第二种线与这 $5$ 条线求交点，直接减去就 ......

### $k=0$ 考试时脑抽，现在想一想感觉挺简单的。 从小到大依次加点，那么题目的条件等价于每次可以把点加在一条边中间，或者加入一个叶子，并且这两种方式都会导致下一个点加入时可选的方案加二。 把方案数乘起来就好了。 ### $k>0$ 需要一点观察。 除了上述两种加点的方式，还存在一种方式是，选 ......

## Day -7 坐了10h+高铁后到达成都！ ## Day -6~Day -2 赛前集训！还看了两场hdu多校的题，不过贡献几乎为 $0$。第二场的计算几何题写了一个小时，调了一个小时没过然后下播了。赛后改了一车东西才过。 成都的外卖怎么都这么辣！ ## Day -1 进校！感觉cdqz的环境和 ......

在这段时间主要在学文化课，没怎么停课，天天暴力拼盘，所以索性合在一起。感觉非常意识流，和OI关系好像也不大。pig嫌我开始写的太短，我积极听取他人建议，加了一车流水账。 联赛结束以后就退役了。因为即使NGOI也大概率会被卡“省线”，但还打算参加省选碰碰运气。遂在省选前两周申请一周半停一周全停，被年级 ......

## Before 提前若干天到成都，感觉环境很好啊。 提前参观成七，果然是别人的学校，有$NOI$那味了 ![image](https://img2023.cnblogs.com/blog/2725552/202307/2725552-20230730103005947-894380765.jpg ......

### Day ??? 来 nfls 集训~~并见证了一半的 HN 省队都在南京的奇景~~。 认真打了一个月模拟赛，感觉还不错，终于有一套比较稳定的策略了~~虽然不时过不了大众题~~，在第 14 场的时候~~因为见过原题~~首次冲进前十，太感动了！ 因为补觉错过了 UNR，保住了一点信心。最后一周的 ......

## Day -4 打 UNR，寄。 具体情况见 UNR 游记。 ## Day -3 做了近九小时的车，来到了成都。 众所周知，我是擅长睡觉的。 所以，像是往常坐车的话，基本上都有一半的时间都睡过去了。 然而这次，虽然路上很困，但是竟然全程没有睡着。 大抵就是，感觉哪里不是很舒服就是了，有点累。 想 ......

来成都之前，我一直认为自己拥有金牌的实力，也无论如何都有前 $100$ 保底。 而现实呢？$100+95+60+52+100+44+10=461$，放到正式选手中是 $\texttt{rk120}$，如此拉跨的成绩。 就算把所有会的分写上，且不挂分，也只有 $100+95+70+68+100+44+ ......