NOI

从最朴素的 \(\mathcal O(qn^2)\) 做法开始，即暴力枚举每个 \(s[i : i + l - 1]\) 和 \(\operatorname R(s[i + l : i + 2l - 1])\) 并统计答案。 发现没有啥合适的字符串算法来直接地进行优化，考虑 容斥 出答案。 令 \( ......

2023.7.2x 开考了。 2023.7.2x 考完了。 2023.7.2x 退役吗..? ... ... 其实记忆早以模糊，为何还要来回忆这一切呢？ ... 2023.6.29 被隐□的博□ 有趣的是，我在这个博中提到了 dx，我并不知道我什么样的想法下提起的 dx，在分数相差近 100 分的情 ......

NOI2024省选训练赛01 时间：2023.9.16 目录NOI2024省选训练赛01A.t3DescriptionConstraintsSolutionB.LifeDescriptionConstraintsSolution A.t3 Time Limit: 4 sec / Memory Lim ......

快考试了，临时报一下佛脚，祝各位 \(RP ++\) ! Linux ls : list show 显示当前目录内容 ls -l 长列表显示 ls -a 显示隐藏文件 cd : change directory 改变目录 cd .. 返回上一级 cd ../.. 返回上一级的上一级 cd /home ......

Copper Loser 的题解…… Day1 T1 方格染色 有一个 \(n\times m\) 的网格，有 \(Q\) 次操作，每次形如有三种：将 \((x_i+j,y_i)\)/\((x_i,y_i+j)\)/\((x_i+j,y_i+j)\) 染色，其中 \(j=0,1\dots L_i-1 ......

前情提要 tj D类 什么垃圾不用我说了吧。 Day -1 到场了，挺热的。 和两位同校巨佬分到了一个宿舍 还有一位 E 类 都比我强 /kel 中午和三位同校巨佬还有教练去外面吃了一顿火锅，选的微辣但是我还是有点接受不了。 北方人没吃过油碟。没有麻酱我们都有点奇怪。 幸亏有冰红茶解辣。 成七的伙食 ......

其实是我 Li-Chao-Tree 哒！！ 考虑转移 \(f_x = \min f_{anc} + (d_{x} - d_{anc})p_x + q_x\) 其中 \(anc\) 为 \(x\) 的祖先，然后满足 \(d_{anc} \geq d_{x} - li_{x})\)。 考虑如果用权值线段 ......

图中不存在横插边，$u \rightsquigarrow v$ 可拆成 $u \rightsquigarrow \operatorname{lca}(u, v) \rightsquigarrow v$ 计算。 对 $u \rightsquigarrow \operatorname{lca}(u, v ......

## 题目描述 C 国是一个繁荣昌盛的国家，它由 $n$ 座城市和 $m$ 条有向道路组成，城市从 $1$ 到 $n$ 编号。如果从 $x$ 号城市出发，经过若干条道路后能到达 $y$ 号城市，那么我们称 $x$ 号城市可到达 $y$ 号城市，记作 $x\Rightarrow y$。C 国的道路有一 ......

# P2305 [NOI2014] 购票 ## Solution 记 $f_{i}$ 表示 $i$ 节点处的答案。$f_1 = 0$。记 $d_i$ 表示根节点到点 $i$ 的距离，容易得到 $O(n^2)$ 的 dp 转移： $$ f_{i} \xleftarrow{\min} f_j + (d_ ......

### $36pts$ $O(tqn^2)$暴力即可 ### $40pts$ 对于最朴素的暴力优化，从头到尾扫，如果已经当前位字符比出优先级，那么直接能判断了，没必要往后跑了，第15个性质B的也给跑过了，我没料到，不过数据强一点其实和20pts没区别 ### $性质A(60pts)$ 没有想出来 # ......

[题目传送门](https://www.luogu.com.cn/problem/P7735) 一眼数据结构 考虑树上有什么数据结构支持 $x$ 到 $y$ 节点的修改和查询，那就是：树链剖分。 那么这道树链剖分的题有个 $trick$：**边点转换&染色法，对于每次修改，考虑将修改路径上的点全部染 ......

省流：D 类银牌，两天会零个题。 ### Day -2 抵达天府之国 成都！走在小巷间，教练突然停下来，停顿了几秒钟，若有所思地看着我们，清了清嗓子，发出了他对成都的第一句也是唯一一句评价： > 这里的老板好像都光着膀子呀 ### Day -1 抵达成都最高层，成都七中！太美丽了七中，当我拉着行李箱 ......

一个月前的事情捏，因为今天刚好在摸鱼就想起来写写。 ## Day 1 开题，先总的过一遍，好像比较传统。 T1 基本上是一眼题了，简单容斥一下就可以解决。很快开始写，写好过了小样例。但是这个时候还没有大样例。而我对这份代码并不太自信，感觉一车细节，所以开拍。 果然 WA 了。然后开始艰难地调试，毕竟 ......

昨天一时兴起弄的表，是在 CCF 的获奖名单基础上编辑的。 其中选手类别数据来源为 noi.cn 公告，不在公示名单中，且不为女生竞赛获 B 类名额（表中标为 B*）的正式选手视为 C 类；不在公示名单中的非正式选手视为 D 类。 初次获奖指选手首次获得正式比赛奖项的年级（不包括 NOI Onlin ......

[P6302 [NOI2019] 回家路线 加强版](https://www.luogu.com.cn/problem/P6302) 斜率优化好题。 观察后猜想应该是 dp。经过思考发现如果以点为状态，在时间这一维上是存在后效性的，而如果开二维数组 $f_{i,j}$ 表示在第 $j$ 个时刻到了 ......

第一次做站外题的题解/jd [题目传送门](http://noi.openjudge.cn/ch0113/41/) 为什么要写这一篇题解呢，是因为它卡了我很久，好不容易AC了（我太蒟，大佬勿喷） 我们开始吧！ ## 一.审题 题目描述很清楚了，大家自己看吧 ## 二.代码&讲解 这里我会给大家上几个 ......

### D1T1 很憨的题目。前两个操作扫描线直接维护，后者直接暴力和前面每个操作求交。 就是这种格子题长宽变量应该设置为 `nn,mm` 之类的，数目才用 `m,n`，写的时候容易顺手写上去还调不出来。然后就是 `unique` 之前是要 `sort` 的。傻逼。 ### D1T2 考虑使用更加优 ......

链接：[P4768 [NOI2018] 归程](https://www.luogu.com.cn/problem/P4768 "P4768 [NOI2018] 归程") 观察一下题目，如果没有车，求一个单源最短路就行了（但不要使用一种广为人知的最短路算法） 现在考虑有车的情况，显然最优策略是坐车到离 ......

https://loj.ac/p/508 贼牛逼的题目。想了两天才想明白。网上大多数题解都讲得很烂啊。 对于部分分的情况，我相信是较为容易想到的。因此，我只会阐述正解的思考过程及一些证明。 首先，考虑路径这东西太泛了。能否将其特殊化、具体化。 先观察一些性质。 1. 对于一个环，我们可以走若干圈，会 ......

#### 本次情况 ##### Day1 很认真去打的一场，但是我是真的菜，分根本不够看 T1是一道博弈论，开局很有信心地去看，推，一个半钟头砸出去，最后只拿了暴力分，因为实在推不出什么 T2是一道多项式题，这块的知识面尚未触及，因而不懂，然后有10分的贪心，打了 T3是一道DP，有贪心的思路和数据 ......

## 题目描述 跳蚤国有 $n$ 座城市，分别编号为 $1 - n$，$1$ 号城市为首都。所有城市分布在一个$w \times h$ 范围的网格上。每座城市都有一个整数坐标 $(x, y) (1 \leq x \leq w, 1 \leq y \leq h)$，不同城市的坐标不相同。 在跳蚤国中共 ......

[原题](https://www.luogu.com.cn/problem/P1371) 题目要求的很简单，就是问一个任意加了 $ N,O,I $ 三个字母中的任意一个打的字符串里面能组成几个 $ NOI $ 。 先考虑不加字母的情况，直接枚举每一个 $ O $ 的前后 $ N $ 和 $ I $ ......

# P3825 [NOI2017] 游戏 题解 首先解决没有 `x` 的情况，这种情况下 每个事件有两种选择，例如 `a` 可以选择 `b, c`，所以这就是一个 `2-SAT` 问题，但是这题比较特殊，除了题目中给的命题，还需要建立原命题的逆否命题所对应的边，最后跑一遍 $\text{Tarjan ......

## Description [传送门](https://www.luogu.com.cn/problem/P9483) ## Solution ### Part 1 考虑一棵合并树，令 $ls_u,rs_u$ 表示 $u$ 的左右儿子，$d_u$ 表示 $u$ 子树的最大深度，$c_u$ 表示 $ ......

T1 太简单了，T6 太赛博了，那就写一下 T2,3,4,5 吧。 题解风格仍然意识流。 ### *loj3980. 「NOI2023」桂花树 tag：DP，计数。 送我出队的题。 先考虑 $k=0$ 的情况。使用类似树背包的方法是可以做的，但是单次插入一棵子树过于笨重，所以只能考虑单次插一个点。然 ......

# 银河英雄传说TJ ## 题目背景 公元5801年，地球居民迁至金牛座第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。 宇宙历799年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特(B)率领十万余艘战舰出征，气吞山河集团点名将杨 ......

## 题目链接 [洛谷](https://www.luogu.com.cn/problem/P2168) [LOJ](https://loj.ac/p/2132) ## 题目分析 哈夫曼编码模板题。 使用 k 进制，即编码时将 k 个点合并为一个。 最后要求的就是哈夫曼编码的长度，以及哈夫曼树最深的 ......

> [[NOI2014] 起床困难综合症 洛谷](https://www.luogu.com.cn/problem/P2114 "[NOI2014] 起床困难综合症 洛谷") 题目描述 $21$ 世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。作为一名青春阳光好少 ......

# P6772 [NOI2020] 美食家 题解（矩阵加速图上dp常用思路） ## 简要题面 给定一张 $n$ 个点 $m$ 条单向边的图，走这条边需要花费 $w_i$ 的时间（以天为单位），现在有一个人从 $1$ 号点出发，最后回到 $1$ 号点，要求走了 **恰好** 为 $T$ 天。 每经过一 ......