NOI算法竞赛大纲

数字代表难度分级。向上的箭头代表提高阶段需掌握的算法。奖杯代表NOI级

【题解】Planning(起飞计划)

Helen知道第i架飞机起飞时刻每延误一分钟机场所需支付的额外花费$c_i$是多少。帮助她找到额外花费最小的方案。

【题解】糟糕的一天

题面翻译农夫约翰有N(N≤80000)N (N \leq 80000)N(N≤80000)头奶牛正在过乱头发节。每一头牛都站在同一排面朝东方，而且每一头牛的身高为hih_ihi​。第NNN头牛在最前面，而第111头牛在最后面。对于第iii头牛前面的第jjj头牛，如果hi>hi+1h_i>

【题解】玉蟾宫

题目背景有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。题目描述这片土地被分成 N×MN\times MN×M个格子，每个格子里写着 ‘R’ 或者 ‘F’，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐

悬线法处理最大子矩阵问题

适用场景可用于求解给定矩阵中满足某条件的极大矩阵（最大子矩阵）。设矩阵为N×MN\times MN×M ，算法复杂度为O(N×M)O(N\times M)O(N×M) 。悬线法思想及实现若在一个矩形区域内寻找满足某条件的最大子矩阵。

ST表算法与代码实现

对于区间最值也就是 RMQ（Range Minimum/Maximum Query）问题，可以使用ST表（稀疏表）的方式进行离线预处理。ST表思想与原理ST表的核心思想是倍增。

【题解】平衡队列

题目描述For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of U

【题解】求和

题目背景NOIP2015 普及组 T3题目描述一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色coloricolor_icolori​用[1,m][1,m][1,m]当中的一个整数表示），并且写了一个数字numberinumber_inumberi​。定义一种特殊的三

【题解】直播获奖

题目描述NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 w%，即当前排名前 w% 的选手的最低成绩就是即时的分数线。更具体地，若当前已评出了 p个选手的成绩，则当前计划获奖人数为 max⁡(1,⌊p∗w%⌋)\max(1, \