NOI

[ T312819 命题工作 ](https://www.luogu.com.cn/problem/T312819) 直接容斥。 总方案 - 一题出现四次 - 一题出现三次 - 一题出现两次。 一题出现两次的情况略有不同，注意考虑周全。 复杂度 $O(n)$。 [code](https://www. ......

观察数据范围，$T$ 很大，$n$ 很小，用矩乘。 对于一条边 $(u,v,w)$，我们将 $u$ 拆成 $w-1$ 个点，并连接 $(u_0,u_1,0),(u_1,u_2,0)...(u_{w-2},u_{w-1},0)$ 和 $(u_{w-1},v_0,c_{v})$，总点数 $5n$。 将美 ......

求解下列同余方程组， $$\begin{cases} b_1 x \equiv a_1 \pmod{m_1} \\ b_2 x \equiv a_2 \pmod{m_2} \\ \dots \\ b_n x \equiv a_n \pmod{m_n} \\ \end{cases}$$ ......

## [NOI2022] 众数 首先看到题面第一句话发现这玩意跟摩尔投票一样。然后我们知道摩尔投票有结合律。于是我们如果不考虑前两个操作，那每个序列开个动态开点线段树维护一下摩尔投票，然后合并可以线段树合并，查询直接查每个序列摩尔投票的和，然后再统计一下这个答案在所有序列里的出现次数是否合法即可。 ......

[P6775 NOI2020 制作菜品](https://www.luogu.com.cn/problem/P6775) 给定正整数 $n$，$m$，$k$。 有一个 $m$ 行 $k$ 列网格，每个网格可以被涂上 $n$ 种颜色之一，要求： - 一行最多出现两种颜色。 - 第 $i$ 种颜色必须恰 ......

## [NOI2021] 轻重边 转化一下题意：每次给一条链染色，查一条链从 $x$ 到 $y$ 有几条边两端颜色相同。那这个随便树剖线段树就好了。也可以 LCT，码量可能要小点。 ```cpp #include #include #include #include #include using n ......

import base64 import json import requests import time arr = ['戚朗瑞','王相文'] headers= { "accept": "*/*", "accept-language": "zh-CN,zh;q=0.9", "cache-cont ......

# NOI 2023 考前知识点总复习 其实就是把熟悉或不熟悉的东西再过一遍，防止考场上出现会了做法却因为忘了算法而写不出来的问题。 可能会一句话概括，也可能附上一点代码片段。 如果不想复习知识点，只想要一点考前提示，可以直接翻到本文最底部。 ## 目录 [I. 数据结构、树上问题](#ch01) ......

[空降锣鼓](https://www.luogu.com.cn/problem/P2024 "空降锣鼓") [空降OJ](http://oj.tfls.net/p/576 "空降OJ") 题解： ```c++ #include using namespace std; int n,k; int d, ......

由于重启电脑以后所有东西都没了因此还要重写一遍。 每天使用的算草数量确实是上了个数量级。 “你都敢拿小刀往胳膊上划为什么不敢吃这个（指魔芋爽）”——H_Kaguya 睿频 gtm1514。不过我觉得吃辣也不会让人精神状态 ++ 吧。不过我的小刀现在彻底成为破伤风之刃了，我就扔了。 吗了，吃了四分之一 ......

### [NOI2007] 社交网络 [Link](https://www.luogu.com.cn/problem/P2047)&[Submission](https://www.luogu.com.cn/record/114129998). ### [NOI2009] 管道取珠 [Link](h ......

abbrlink: '' categories: [] date: '2023-03-05 16:08:12' tags: - tourism title: 「Summary」 NOI 春测游记 toc: true updated: Sat, 15 Apr 2023 01:17:09 GMT 终究是 ......

abbrlink: '' categories: [] date: '2023-02-19 21:00:00' tags: - 记录 - review title: 「Summary」 NOI 春测前复习记录 toc: true updated: Sat, 15 Apr 2023 01:17:18 ......

abbrlink: '' categories: [] date: '2023-02-19 21:00:00' tags: - 记录 - review title: 「Summary」 NOI 春测前考试记录 toc: true updated: Sat, 15 Apr 2023 01:17:23 ......

没做 NOI 的现实主义者在 NOI 前最现实的做法当然是做 CNOI 系列。我 NOI 居然没做几个题。 房屋老师来拜访 hzoi 了，拜谢。 我这个实力能不能 Ag 暂时不好说。那先尽量签。 ## [NOI2022] 众数 本场签到题。但是赛时坑了许多人。平心而论这题赛后做比赛时做简单许多，因为 ......

我只会签到题.jpg。 显然可以使用二维线段树优化建图拿到一定的部分分，但是这并不优秀。 考虑从值域上来入手 dijkstra。看做是装置间的最短路顺带更新节点，那么我们可以写一个树套树来维护这一些待更新的点，因为 dist 是递增的，所以可以更新后删去这些点，然后就可以 $n\log n$ 的空间 ......

### 题意 给定 $n,m,k$ ($1\le n,m\le10^9$，)问在 $k$ 进制下有多少个分数值不同的 $\frac{x}{y}$ 满足 $x\le n,y\le m$ 且其小数形式的循环节从小数点后第一位开始。 ### sol 因为要求不同分数值，我们只考虑既约分数。类比十进制，故要 ......

## 美食家 很显然可以写出矩阵。 发现相当于有 $q$ 次询问 $A^k$，预处理矩阵的 $2^0,2^1,\cdots,2^w$ 次幂然后用向量乘矩阵即可做到 $O(n^3\log T+qn^2\log T)$。 ## 命运 没发现链是祖先-后代这样的，想了一年不会做 有这个性质就可以直接 dp ......

看错题以为操作一删恰好 $2$ 个卡了好久=_=。~~虽然看对之后还是不会做。~~~ 这种神秘的条件让你计数，要么发挥人类智慧找神秘充要条件之类的，要么直接设计判断合法的自动机然后 dp 套 dp。后者稍微靠谱一些，所以我先想的后面的。 一个简单的人类观察是操作二不会重复进行，否则我们换成一。 另一 ......

# P2305 [NOI2014] 购票 ## 题意 今年夏天，NOI 在 SZ 市迎来了她三十周岁的生日。来自全国 $n$ 个城市的 OIer 们都会从各地出发，到 SZ 市参加这次盛会。 全国的城市构成了一棵以 SZ 市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 $n ......

分块。设分出来左散块 $A_1$，中间块 $B_1,\cdots,B_k$，右散块 $A_2$。那么贡献有 $A_1\leftarrow A_1$ 即散块对自己，$A_1\leftarrow A_2$ 即散块对散块，$A_i\leftarrow B_j$ 即散块对整块，$B_i\leftarrow ......

# P3980 [NOI2008] 志愿者招募 ## 题意 申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要 $n$ 天才能完成，其中第 $i$ 天至少需要 $a_i$ 个人。布布通过 ......

CCF NOI 2023 徽章信息收集工作已经开始。目前 @[zhiyangfan](https://www.luogu.com.cn/user/137603) 和我 @[云浅知处](https://www.luogu.com.cn/user/307453) 正在负责河南省的收集工作。 我们的 QQ ......

首先可以注意到题面中的这个条件： > 对于三座城市 $x$，$y$，$z$，若 $x\Rightarrow z$ 且 $y\Rightarrow z$，那么有 $x\Rightarrow y$ 或 $y\Rightarrow x$。 这就代表着如果存在边 $x\rightarrow z$ 和 $y\ ......

# luogu P2050 [NOI2012] 美食节 ## 题意 CZ 市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。 作为一个喜欢尝鲜的美食客，小 M 自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小 ......

**描述** 给定一个非负整数数组，统计里面每一个数的出现次数。我们只统计到数组里最大的数。 假设 Fmax （Fmax using namespace std; int main(){ int n,x; int fmax=0;//数组里最大的数 int a[10000]={0}; cin>>n; ......

# luogu P1963 [NOI2009] 变换序列 ## 题意 对于$N$个整数$0, 1, \cdots, N-1$，一个变换序列$T$可以将$i$变成$T_i$，其中 $T_i \in \{ 0,1,\cdots, N-1\}$ 且 $\bigcup_{i=0}^{N-1} \{T_i\} ......

去年写过新加坡 NOI 2022 的题解，当时感觉那套题还挺有趣的……但数据结构题怎么这么多。 脱离文化课苦海之后发现 2023 的题也有了，所以就有了这篇题解。 和去年一样 E 只翻译了题面而没有题解，因为 E 是个交互，最近暂时没有练习交互题的打算。而且我估计我也不会做。 ## 题面 注：所有题 ......

[题面传送门](https://www.luogu.com.cn/problem/P7740) 一个 bitset 值 52 分？ 首先样例让你容斥你就容斥，枚举哪些位是可以的，计算每一位的 $p_0,p_1,q_0,q_1$ 表示是否被要求最后是 $0/1$，是否有最终值是开始值异或 $0/1$。 ......

# [NOI2014] 动物园 ## 题目描述 近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。 某天，园长给动物们讲解 KMP 算法。 园长：“对于一个字符串 $S ......