题意描述

HydroOJ 链接

Tim 正在摆弄着他设计的“计算机”，他认为这台计算机原理很独特，因此利用它可以解决许多难题。 但是，有一个难题他却解决不了，是这台计算机的输入问题。新型计算机的输入也很独特，假设输入序列中有一些数字（都是自然数——自然数包括 \(0\) ），计算机先读取第一个数字 \(s_1\) ，然后顺序向后读入 \(s_1\) 个数字。接着再读一个数字 \(s_2\) ，顺序向后读入 \(s_2\) 个数字……依此类推。不过只有计算机正好将输入序列中的数字读完，它才能正确处理数据，否则计算机就会进行自毁性操作！

Tim 现在有一串输入序列。但可能不是合法的，也就是可能会对计算机造成破坏。于是他想对序列中的每一个数字做一些更改，加上一个数或者减去一个数，当然，仍然保持其为自然数。使得更改后的序列为一个新型计算机可以接受的合法序列。

不过 Tim 还希望更改的总代价最小，所谓总代价，就是对序列中每一个数操作的参数的绝对值之和。

写一个程序：

1. 从文件中读入原始的输入序列；
2. 计算将输入序列改变为合法序列需要的最小代价；
3. 向输出文件打印结果。

\(100\%\) 的数据满足：\(n < 1 \times 10^6 + 1\)

题意描述

洛谷链接

LibreOJ 链接

Kiana 最近沉迷于一款神奇的游戏无法自拔。
简单来说，这款游戏是在一个平面上进行的。有一架弹弓位于 \((0, 0)\) 处，每次 Kiana 可以用它向第一象限发射一只小鸟，小鸟们的飞行轨迹均为形如 \(y = ax ^ 2 + bx\) 的曲线，其中 \(a\)，\(b\) 是 Kiana 指定的参数，且必须满足 \(a < 0\)。当小鸟落回地面（即 \(x\) 轴）时，它就会瞬间消失。

在游戏的某个关卡里，平面的第一象限中有 \(n\) 只猪，其中第 \(i\) 只猪所在的坐标为 \((x_i, y_i)\)。如果某只小鸟的飞行轨迹经过了 \((x_i, y_i)\)，那么第 \(i\) 只猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；如果一只小鸟的飞行轨迹没有经过 \((x_i, y_i)\)，那么这只小鸟飞行的全过程就不会对第 \(i\) 只猪产生任何影响。 例如，若两只猪分别位于 \((1, 3)\) 和 \((3, 3)\)，Kiana 可以选择发射一只飞行轨迹为 \(y = -x ^ 2 + 4x\) 的小鸟，这样两只猪就会被这只小鸟一起消灭。
而这个游戏的目的，就是通过发射小鸟消灭所有的猪。

假设这款游戏一共有 \(T\) 个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的猪。由于她不会算，所以希望由你告诉她。

数据范围：\(1 \leq n \leq 18\)，\(0 \leq m \leq 2\)，\(0 < x_i, y_i < 10\)，\(1 \leq T \leq 30\)。

题意描述

洛谷链接

小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星人发来的信息。

虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高低电平将接收到的信号改写为由 0 和 1 构成的串， 并坚信外星人的信息就隐藏在其中。他认为，外星人发来的信息一定会在他接受到的 01 串中重复出现，所以他希望找到他接受到的 01 串中所有重复出现次数大于 \(1\) 的子串。

但是他收到的信号串实在是太长了，于是，他希望你能编一个程序来帮助他。

对于 \(100\%\) 的数据，满足 \(0 \le N \le 3000\)

题意描述

洛谷链接

贝茜正在领导奶牛们逃跑．为了联络，奶牛们互相发送秘密信息．

信息是二进制的，共有 \(M\)（\(1 \le M \le 50000\)）条，反间谍能力很强的约翰已经部分拦截了这些信息，知道了第 \(i\) 条二进制信息的前 \(b_i\)（\(l \le b_i \le 10000\)）位，他同时知道，奶牛使用 \(N\)（\(1 \le N \le 50000\)）条暗号．但是，他仅仅知道第 \(j\) 条暗号的前 \(c_j\)（\(1 \le c_j \le 10000\)）位。

对于每条暗号 \(j\)，他想知道有多少截得的信息能够和它匹配。也就是说，有多少信息和这条暗号有着相同的前缀。当然，这个前缀长度必须等于暗号和那条信息长度的较小者。

在输入文件中，位的总数（即 \(\sum b_i + \sum c_i\)）不会超过 \(500000\)。

题意描述

洛谷链接

LibreOJ 链接

Bob 喜欢序列。

有一个长度为 \(n\) 的非负整数序列 \(a_1, a_2,\cdots, a_n\)。每一步你可以从以下三种操作中选择一种执行：

• 选择一个区间 \([l, r]\)，将下标在这个区间里的所有数都减 \(1\)。
• 选择一个区间 \([l, r]\)，将下标在这个区间里且下标为奇数的所有数都减 \(1\)。
• 选择一个区间 \([l, r]\)，将下标在这个区间里且下标为偶数的所有数都减 \(1\)。

求最少需要多少步才能将序列中的所有数都变成 \(0\)。

对于所有的数据，\(1 \leq n \leq 100000, 0 \leq a_i \leq 10^9, 1 \leq T \leq 10\)。

题意描述

洛谷链接

有一种音游的计分方式为在一首歌中有 \(n\) 次点击要做，成功了就是 o，失败了就是 x，分数是按 combo 计算的，连续 \(a\) 个 combo 就有 \(a\times a\) 分，combo 就是极大的连续 o。

Sevenkplus 闲的慌就看他打了一盘，有些地方跟运气无关要么是 o 要么是 x，有些地方 o 或者 x 各有 \(50\%\) 的可能性，用 ? 号来表示。

那么的期望得分是多少？

数据范围：\(n\le3\times10^5\)

题意描述

洛谷链接

LibreOJ 链接

最近 \(\text{lxhgww}\) 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。

通过一段时间的观察，\(\text{lxhgww}\) 预测到了未来 \(T\) 天内某只股票的走势，第 \(i\) 天的股票买入价为每股 \(AP_i\)，第 \(i\) 天的股票卖出价为每股 \(BP_i\)（数据保证对于每个 \(i\)，都有 \(AP_i \geq BP_i\)），但是每天不能无限制地交易，于是股票交易所规定第 \(i\) 天的一次买入至多只能购买 \(AS_i\) 股，一次卖出至多只能卖出 \(BS_i\) 股。

另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 \(W\) 天，也就是说如果在第 \(i\) 天发生了交易，那么从第 \(i+1\) 天到第 \(i+W\) 天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过 \(\text{MaxP}\)。

在第 \(1\) 天之前，\(\text{lxhgww}\) 手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，\(T\) 天以后，\(\text{lxhgww}\) 想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？

\(0\leq W<T\leq 2000,1\leq\text{MaxP}\leq2000,1\leq BP_i\leq AP_i\leq 1000,1\leq AS_i,BS_i\leq\text{MaxP}\)

题意描述

洛谷链接

LibreOJ 链接

给定整数 \(g\)，\(n\)（\(1 \leq q, n \leq 10^9\)），计算：

\[ g^{\sum_{d|n}{C_{n}^{d}}} \operatorname{mod} 999911659 \]

题意描述

洛谷链接

\(N\) 个柱子排成一排，一开始每个柱子损伤度为 0。

接下来勇仪会进行 \(M\) 次攻击，每次攻击可以用 4 个参数\(l\),\(r\),\(s\),\(e\)来描述：

表示这次攻击作用范围为第 \(l\) 个到第 \(r\) 个之间所有的柱子（包含 \(l\)，\(r\)），对第一个柱子的伤害为 \(s\)，对最后一个柱子的伤害为 \(e\)。

攻击产生的伤害值是一个等差数列。若 \(l = 1\)，\(r = 5\)，\(s = 2\)，\(e = 10\)，则对第 1 ~ 5 个柱子分别产生 2, 4, 6, 8, 10 的伤害。

鬼族们需要的是所有攻击完成之后每个柱子的损伤度。

题目描述

Codeforces 链接

Treeland 国有 \(n\) 个城市，这 \(n\) 个城市连成了一颗树，有 \(n - 1\) 条道路连接了所有城市。每条道路只能单向通行。现在政府需要决定选择哪个城市为首都。假如城市 i 成为了首都，那么为了使首都能到达任意一个城市，不得不将一些道路翻转方向，记翻转道路的条数为 \(k\)。你的任务是找到所有满足 \(k\) 最小的首都。