NOI
「NOI2015」软件包管理器-树链剖分
· ✏️ 1215 words · ☕ 3 mins read

你决定设计你自己的软件包管理器。如果软件包 A 依赖软件包 B ,那么安装软件包 A 以前,必须先安装软件包 B 。同时,如果想要卸载软件包 B ,则必须卸载软件包 A 。现在你已经获得了所有的软件包之间的依赖关系。除 0 号软件包以外,所有软件包都会依赖一个且仅一个软件包,而 0 号软件包不依赖任何一个软件包。依赖关系不存在环。

现在有一些安装或卸载软件包的操作,需要求出这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包)。


「NOI2014」动物园-KMP
· ✏️ 737 words · ☕ 2 mins read

给定一个字符串 S ,求出 num 数组——对于字符串 S 的前 i 个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作 num[i]

特别地,为了避免大量的输出,你不需要输出 num[i] 分别是多少,你只需要输出所有 (num[i]+1) 的乘积,对 109+7 取模的结果即可。


「NOI2005」维护数列-非旋Treap
· ✏️ 1513 words · ☕ 4 mins read

维护一个数列,给定初始的 n 个数字。

现有六种命令:

  • 在第 pos 个数后插入 tot 个数
  • 翻转从第 pos 个数开始的 tot 个数
  • 删除从第 pos 个数开始的 tot 个数
  • 查询从第 pos 个数开始的 tot 个数的和
  • 设定从第 pos 个数开始的 tot 个数设定为 c
  • 查询整个数列中和最大的连续子区间的和

「NOI2002」银河英雄传说-并查集
· ✏️ 724 words · ☕ 2 mins read

初始时,第 i 号战舰处于第 i(i=1,2,,30000)

有两种指令:

合并指令为 M i j ,含义为将第 i 号战舰所在的整个战舰队列,作为一个整体(头在前尾在后)接至第 j 号战舰所在的战舰队列的尾部。

询问指令为 C i j 。该指令意思询问第 i 号战舰与第 j 号战舰当前是否在同一列中,如果在同一列中,那么它们之间布置有多少战舰。


「NOI2004」郁闷的出纳员-Splay
· ✏️ 1475 words · ☕ 3 mins read

维护一个数列。

现有四种命令,新加入一个数 k ,把每个数加上 k ,把每个数减去 k ,查询第 k 大的数。如果数列中的任意数小于 min ,将它立即删除。并在最后输出总共删去的数的个数 res

如果新加入的数 k 的初值小于 min ,它将不会被加入数列。