NOI

06:笨小猴 描述 笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！ 这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是 ......

> 给定串 $S,T_{1,\cdots,q}$，每次询问是 $S[l_i,r_i]$ 的子串但不是 $T_i$ 的子串的本质不同子串个数。 > > $|S|\le5e5,q\le1e5,\sum|T|\le1e6$。 我们先考虑 $l=1,r=|S|$ 怎么做。 显然我们使用 SAM 可以简单计算 ......

## NOI2016 循环之美 首先要求数值互不相同，就相当于要求分子分母互质（不互质就会重复） 考虑怎么转化纯循环小数这个条件： 设 $\frac{x}{y}$ 循环节为 $l$ 位，这意味着 $\frac{x}{y}$ 向左平移 $l$ 位后，小数点后的部分不变，即： $$ xk^l\equiv ......

# [[NOI2014] 动物园](https://www.luogu.com.cn/problem/P2375) 这题看题目描述就知道一定是跟 `KMP` 扯上关系了。首先，如果不考虑长度超过 $\dfrac{1}{2}$ 的限制的话，那么就很简单，每次求出一个新的 $ne_i$ 时，如下图所示 ......

4:谁拿了最多奖学金 描述 某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同： 1) 院士奖学金，每人8000元，期末平均成绩高于80分（>80），并且在本学期内发表1篇或1篇以上论文的学生均可获得； 2) 五四奖学金，每人4000元，期末平均成绩高于85分（> ......

**描述** 某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同： 1) 院士奖学金，每人8000元，期末平均成绩高于80分（>80），并且在本学期内发表1篇或1篇以上论文的学生均可获得； 2) 五四奖学金，每人4000元，期末平均成绩高于85分（>85），并且班 ......

**描述** 输出一个整数序列中最大的数和最小的数的差。 **输入** 第一行为M，表示整数个数，整数个数不会大于10000； 第二行为M个整数，以空格隔开，每个整数的绝对值不会大于10000。 **输出** 输出M个数中最大值和最小值的差。 **样例输入** ``` 5 2 5 7 4 2 ``` ......

原文链接：[[sol] P1587 [NOI2016] 循环之美 - icyM3tra's Blog](https://www.luogu.com.cn/blog/38785/sol-p1587-noi2016-xun-huan-zhi-mei) 此为备份。 [题目传送门](https://www. ......

[题面传送门](https://www.luogu.com.cn/problem/P8497) 不好评价？ 首先我们考虑最基础的情况，当 $k=0,l_i=r_i$ 时，相当于我们需要判定一个状态能不能被消完。 这相当于我们要执行若干次 $2$ 操作，使得每个位置要么大于等于 $2$，要么为 $0$ ......

# [NOI2021] 量子通信 ## 题目背景 由于评测性能差异，本题时限 +0.5s。 ## 题目描述 小 Z 正在自学量子计算机相关知识，最近他在研究量子通信章节，并遇到了一个有趣的问题。在该问题中，Alice 和 Bob 正在进行量子通信，它们的通信语言是一个大小为 $n$ 的字典 $S$， ......

# 题目 [点这里](https://www.luogu.com.cn/problem/P2179)看题目。 __题目描述__ 蛋蛋非常热衷于挑战自我，今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。 川藏线的沿途有着非常美丽的风景，但在这一路上也有着很多的艰难险阻，路况变化多端，而蛋蛋的体力十分有 ......

[合集链接](https://www.cnblogs.com/acceptedzhs/p/oi-2022-2023-tour.html) 搞笑选手来了，也许是金勾最低分。 ### Day 1 CSUST 的电脑怎么这么垃圾... 进场先看题，T1 小清新，T2 计数，T3...黄金矿工？ T1 感觉 ......

描述 在一个正方形的灰度图片上，肿瘤是一块矩形的区域，肿瘤的边缘所在的像素点在图片中用0表示。其它肿瘤内和肿瘤外的点都用255表示。现在要求你编写一个程序，计算肿瘤内部的像素点的个数（不包括肿瘤边缘上的点）。已知肿瘤的边缘平行于图像的边缘。 输入 只有一个测试样例。第一行有一个整数n，表示正方形图像 ......

Round XLIX 开场看B想了3h假回去想A1h切。 A. 守序划分问题 容易想到一个必要条件，对于任意集合 $S$，需要满足 $\max_{i\in S}A_i>\min_{i\notin S}A_i$。然后用你的大脑构造一下发现这东西也充分。 于是思考如何计数，即不能将数列割裂成两个部分。于 ......

13:图像模糊处理 1.描述 给定n行m列的图像各像素点的灰度值，要求用如下方法对其进行模糊化处理： 1. 四周最外侧的像素点灰度值不变； 2. 中间各像素点新灰度值为该像素点及其上下左右相邻四个像素点原灰度值的平均（舍入到最接近的整数）。 2.输入 第一行包含两个整数n和m，表示图像包含像素点的行 ......

NOI2023训练赛12 NOI2023训练赛12 门把手集合 每个点的价值是子树中与自身距离不超过 $k$ 的点权两两异或的平方和。 异或想到拆位，平方只与两个为有关，枚举两个位置，合并子节点权值，实时删去距离大于 $k$ 的节点，可以做到 $O(n\log^2 V)$。 本题卡空间，dsu on ......

提供一个来自 CF 大佬 adament 的有趣思路。 首先我们知道的是一个只增加的 $b$ 进制整数计数器，如果 $b$ 是常数那么复杂度是均摊 $O(1)$ 的。证明只需要考虑将 $b$ 进制中为 $b-1$ 的所有位的位数当成势能，那么每一次进位一定是 $b-1\to 0$ 一定会消耗势能函数 ......

鸽了三年的东西。 [NOI Online #1 入门组] 文具订购 枚举即可。 [NOI Online #1 入门组] 魔法 感觉是道不错的dp。 令 $f_{k,i,j}$ 表示使用 $k$ 次魔法后，$i,j$ 间的最短路的长度。 当 $k=0$ 时，裸的 floyd。 当 $k=1$ 时，可以 ......

11:图像旋转 1.描述 输入一个n行m列的黑白图像，将它顺时针旋转90度后输出。 2.输入 第一行包含两个整数n和m，表示图像包含像素点的行数和列数。1 <= n <= 100，1 <= m <= 100。接下来n行，每行m个整数，表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开，每个元素 ......

描述 输入一个n行m列的黑白图像，将它顺时针旋转90度后输出。 输入 第一行包含两个整数n和m，表示图像包含像素点的行数和列数。1 <= n <= 100，1 <= m <= 100。 接下来n行，每行m个整数，表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开，每个元素均在0~255之间。 ......

注：本文不写证明。 一、剩余类环 $\mathbb{Z}/n\mathbb{Z}$ 记号：$\overline{x}$ 在$\mod n$ 意义下代表一个集合：${\dots,x-2n,x-n,x,x+n,x+2n,\dots}$ 加法逆元：$a: \overline{-a} \text{ or } ......

文化课补完了，所以来改题。 T1 涂色 paint 弱智签到题，维护时间戳。 Submission - 洛谷 T2 幂次 power 近似原题：CodeForces-955C Sad Powers *2100 一个数可能会被统计多次，例如 $2^{12}=4^6=8^4=16^3=64^2$，考虑只 ......

总体思路其实跟用线段树维护区间最大字段和差不多，不过唯一麻烦的地方在于要算上自己。 然后我们可以开一个队列来回收那些被delete的点，这样可以节省空间，特别需要注意的是release的时候，标记什么的一定记得清空。 本来insert我是直接一个个merge的，这样就会导致特别慢，因此我们可以借助笛 ......

Day -N 下午去机房训练，回去的时候邱大大说 "我$，lj，szy$ 可以去参加 NOI 2023省选"。我瞬间就惊了。作为一个 $CSP—S$ 只有 $91pts$，$NOIP$ 只有 $108pts$ 的菜狗。竟然能去打 NOI 2023省选。~~一时不知该如何是好~~。 反正既然我有这一个 ......

[NOI2011] 阿狸的打字机 /* 其实也就是动态建树的问题，如果这个点有，那就把这个点给激活。 如果这个点消失了，对应的把他的值取消掉就可以了 这样就可以在对应的树下进行查询。 然后就是单点修改，对树的子树大小进行查询，用树状数组进行维护就可以了 首先根据fail建立子树 在fail树上查找某 ......

文化课补完了，但是考试考炸了，所以来补题。 D1T1 火车站 station 实际上只需要判断从 $x$ 能否一直向一个方向移动且每个位置能不能作为这个方向的终点站。 区间覆盖差分一下即可。 点击查看代码 int n,m,x; int st[maxn][2],cov[maxn]; bool vis[ ......

文化课补完了，但是考试考炸了，所以来补题。 D1T1 火车站 station 实际上只需要判断从 $x$ 能否一直向一个方向移动且每个位置能不能作为这个方向的终点站。 区间覆盖差分一下即可。 点击查看代码 int n,m,x; int st[maxn][2],cov[maxn]; bool vis[ ......

一个新坑，先把真题都刷一下大概就知道会考什么和难度怎么样了。 2013 向量内积 给定一个 $n$ 个 $m$ 维向量，求出一组不同的向量 $p,q$ 使其内积（点乘）在模 $k$ 意义下为 $0$。 $k=2,1\le n\le 2\times 10^4, 1\le m\le 100$ 或 $k= ......

描述 给定n*n由0和1组成的矩阵，如果矩阵的每一行和每一列的1的数量都是偶数，则认为符合条件。 你的任务就是检测矩阵是否符合条件，或者在仅改变一个矩阵元素的情况下能否符合条件。 "改变矩阵元素"的操作定义为0变成1或者1变成0。 输入 输入n + 1行，第1行为矩阵的大小n(0 < n < 100 ......

前言 这次比赛去了广大附中，也是我初中最后一场比赛了吧 Day- DY的由于里的太近了，住在学校里，感到惋惜。训练量有点少，不知道因该干什么，于是随便看了几个简单数学知识。譬如拉格朗日，三维计算几何。比较冷门，考试没有太大用途，只能赌一把，看看它考不考。 Day 1 第一天早上6点20起来，酒店的早 ......