题解
「CQOI2018」异或序列-莫队
· ✏️ 644 words · ☕ 2 mins read

已知一个长度为 $n$ 的整数数列 $a_1,a_2,…,a_n$ ,给定查询参数 $l$ 、 $r$ ,问在 $a_l,a _ {l+1},…,a_r$ ​区间内,有多少子序列满足异或和等于 $k$ 。也就是说,对于所有的 $x,y$ $(l \leq x \leq y \leq r)$ ,能够满足 $a_x \bigoplus a _ {x+1} \bigoplus … \bigoplus a_y = k$ 的 $x,y$ 有多少组。


「JSOI2007」字符加密-后缀数组
· ✏️ 525 words · ☕ 2 mins read

喜欢钻研问题的 $JS$ 同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法:把需要加密的信息排成一圈,显然,它们有很多种不同的读法。

例如 JSOI07 ,可以读作: JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 ,把它们按照字符串的大小排序:

  • 07JSOI
  • 7JSOI0
  • I07JSO
  • JSOI07
  • OI07JS
  • SOI07J

读出最后一列字符:I0O7SJ,就是加密后的字符串。 但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?


「SDOI2011」计算器-快速幂+扩展欧几里得+BSGS算法
· ✏️ 569 words · ☕ 2 mins read

你被要求设计一个计算器完成以下三项任务:

  1. 给定 $y,z,p$ ,计算 $y^z \bmod p$ 的值;

  2. 给定 $y,z,p$ ,计算满足 $xy \equiv z \pmod p$ 的最小非负整数 $x$;

  3. 给定 $y,z,p$ ,计算满足 $y^x \equiv z \pmod p$ 的最小非负整数 $x$。

保证 $p$ 为质数。


「SDOI2013」随机数生成器-BSGS算法
· ✏️ 987 words · ☕ 2 mins read

小 $W$ 喜欢读书,尤其喜欢读《约翰克里斯朵夫》。最近小W准备读一本新书,这本书一共有 $P$ 页,页码范围为 $0 … P-1$。

小 $W$ 很忙,所以每天只能读一页书。为了使事情有趣一些,他打算使用 $\text{NOI2012}$ 上学习的线性同余法生成一个序列,来决定每天具体读哪一页。

我们用 $X_i$ 来表示通过这种方法生成出来的第 $i$ 个数,也即小 $W$ 第 $i$ 天会读哪一页。这个方法需要设置 $3$ 个参数 $a,b,X_1$ ,满足 $0 \leq a,b,X_1 \leq p-1$ ,且 $a,b,X_1$ 都是整数。按照下面的公式生成出来一系列的整数:$X _ {i+1} =(aX_i+b)\bmod p$ 其中 $\bmod$ 表示取余操作。

但是这种方法可能导致某两天读的页码一样。

小 $W$ 要读这本书的第 $t$ 页,所以他想知道最早在哪一天能读到第 $t$ 页,或者指出他永远不会读到第 $t$ 页。


「SDOI2008」仪仗队-欧拉函数
· ✏️ 454 words · ☕ 1 mins read

作为体育委员, $C$ 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 $N \times N$ 的方阵,为了保证队伍在行进中整齐划一, $C$ 君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。

现在, $C$ 君希望你告诉他队伍整齐时能看到的学生人数。


「HNOI2004」L语言-AC自动机
· ✏️ 667 words · ☕ 2 mins read

一段文章 $T$ 是由若干小写字母构成。一个单词 $W$ 也是由若干小写字母构成。一个字典 $D$ 是若干个单词的集合。我们称一段文章 $T$ 在某个字典 $D$ 下是可以被理解的,是指如果文章 $T$ 可以被分成若干部分,且每一个部分都是字典 $D$ 中的单词。

给定一个字典 $D$ ,你的程序需要判断若干段文章在字典 $D$ 下是否能够被理解。并给出其在字典 $D$ 下能够被理解的最长前缀的位置。


「Luogu 2801」教主的魔法-分块
· ✏️ 459 words · ☕ 1 mins read

给定一个长度为 $N$ 的数列,每次一个操作或询问:

  • 把闭区间 $[L, R]$ 内的数全部加上一个整数 $W$
  • 问闭区间 $[L, R]$ 内有多少英雄身高大于等于 $C$

「HEOI2016/TJOI2016」排序-线段树
· ✏️ 1001 words · ☕ 2 mins read

在 $2016$ 年,佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题,需要你来帮助他。这个难题是这样子的:给出一个 $1$ 到 $n$ 的全排列,现在对这个全排列序列进行 $m$ 次局部排序,排序分为两种:

  • $(0,l,r)$表示将区间 $[l,r]$ 的数字升序排序
  • $(1,l,r)$表示将区间 $[l,r]$ 的数字降序排序
    最后询问第 $q$ 位置上的数字。

「NOI2007」货币兑换-Splay+斜率优化
· ✏️ 1928 words · ☕ 4 mins read

小 $Y$ 最近在一家金券交易所工作。该金券交易所只发行交易两种金券:$A$ 纪念券(以下简称 $A$ 券)和 $B$ 纪念券(以下简称 $B$ 券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动,两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 $K$ 天中 $A$ 券 和 $B$ 券的价值分别为 $A_K$ 和 $B_K$(元/单位金券)。为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法。比例交易法分为两个方面:

(a)卖出金券:顾客提供一个 $[0,100]$ 内的实数 $OP$ 作为卖出比例,其意义为:将 $OP%$ 的 $A$ 券和 $OP%$ 的 $B$ 券以当时的价值兑换为人民币;

(b)买入金券:顾客支付 $IP$ 元人民币,交易所将会兑换给用户总价值为 $IP$ 的金券,并且,满足提供给顾客的 $A$ 券和 $B$ 券的比例在第 $K$ 天恰好为 $Rate_K$ ;

注意到,同一天内可以进行多次操作。小 $Y$ 是一个很有经济头脑的员工,通过较长时间的运作和行情测算,他已经知道了未来 $N$ 天内的 $A$ 券和 $B$ 券的价值以及 $Rate$ 。他还希望能够计算出来,如果开始时拥有 $S$ 元钱,那么 $N$ 天后最多能够获得多少元钱。


「NOI2015」寿司晚宴-状压dp
· ✏️ 1428 words · ☕ 3 mins read

为了庆祝 $NOI$ 的成功开幕,主办方为大家准备了一场寿司晚宴。小 $G$ 和小 $W$ 作为参加 $NOI$ 的选手,也被邀请参加了寿司晚宴。

在晚宴上,主办方为大家提供了 $n−1$ 种不同的寿司,编号 $1,2,3,⋯,n-1$ ,其中第种寿司的美味度为 $i+1$(即寿司的美味度为从 $2$ 到 $n$ )。

现在小 $G$ 和小 $W$ 希望每人选一些寿司种类来品尝,他们规定一种品尝方案为不和谐的当且仅当:小 $G$ 品尝的寿司种类中存在一种美味度为 $x$ 的寿司,小 $W$ 品尝的寿司中存在一种美味度为 $y$ 的寿司,而 $x$ 与 $y$ 不互质。

现在小 $G$ 和小 $W$ 希望统计一共有多少种和谐的品尝寿司的方案(对给定的正整数 $p$ 取模)。注意一个人可以不吃任何寿司。


「NOI2009」诗人小G-动态规划+决策单调性
· ✏️ 996 words · ☕ 2 mins read

小 $\text{G}$ 是一个出色的诗人,经常作诗自娱自乐。但是,他一直被一件事情所困扰,那就是诗的排版问题。

一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以放的句子数目是没有限制的。小 $\text{G}$ 给每首诗定义了一个行标准长度(行的长度为一行中符号的总个数),他希望排版后每行的长度都和行标准长度相差不远。显然排版时,不应改变原有的句子顺序,并且小 $\text{G}$ 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下,小 $\text{G}$ 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的 $P$ 次方,而一个排版的不协调度为所有行不协调度的总和。

小 $\text{G}$ 最近又作了几首诗,现在请你对这首诗进行排版,使得排版后的诗尽量协调(即不协调度尽量小),并把排版的结果告诉他。


「APIO2014」序列分割-动态规划-斜率优化
· ✏️ 670 words · ☕ 2 mins read

你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块,你需要重复下面的操作 $k$ 次:

  • 选择一个有超过一个元素的块(初始时你只有一块,即整个序列)
    • 选择两个相邻元素把这个块从中间分开,得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。


「NOI2012」魔幻棋盘-差分+树套树
· ✏️ 1480 words · ☕ 3 mins read

将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘,它是一个 $N$ 行 $M$ 列的网格棋盘,每个格子中均有一个正整数。棋盘守护者在棋盘的第 $X$ 行第 $Y$ 列(行与列均从 $1$ 开始编号)并且始终不会移动。棋盘守护者会进行两种操作:

  1. 询问:他会以自己所在位置为基础,向四周随机扩展出一块大小不定的矩形区域,向你询问这一区域内所有数的最大公约数是多少。

  2. 修改:他会随意挑选棋盘上的一块矩形区域,将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友,当你连续答对 $19930324$ 次询问后会得到一个惊喜噢!”。小 Q 十分想得到这个惊喜,于是每天都在玩这个玩具。但由于他粗心大意,经常算错数,难以达到这个目标。于是他来向你寻求帮助,希望你帮他写一个程序来回答棋盘守护者的询问,并保证 $100%$ 的正确率。

为了简化问题,你的程序只需要完成棋盘守护者的 $T$ 次操作,并且问题保证任何时刻棋盘上的数字均为不超过 $2^{62} - 1$ 的正整数。


「NOI2012」随机数生成器-矩阵快速幂
· ✏️ 286 words · ☕ 1 mins read

给定正整数 $n,m,a,c,X[0],g$ ,求按照 $X[n+1] = (a X[n] + c) \bmod m$ 生成出的第 $n$ 项 $X[n] \bmod g$ 的值。

数据范围: $n,m,a,c,X[0] \leq 10^{18}$