0%
「HNOI2006」公路修建问题 - 二分答案 + 最小生成树
题意描述
OI island 是一个非常漂亮的岛屿，自开发以来，到这儿来旅游的人很多。然而，由于该岛屿刚刚开发不久，所以那里的交通情况还是很糟糕。所以，OIER Association 组织成立了，旨在建立 OI island 的交通系统。
OI island 有 \(n\) 个旅游景点，不妨将它们从 \(1\) 到 \(n\) 标号。现在，OIER Association 需要修公路将这些景点连接起来。一条公路连接两个景点。公路有，不妨称它们为一级公路和二级公路。一级公路上的车速快，但是修路的花费要大一些。
OIER Association 打算修 \(n-1\) 条公路将这些景点连接起来（使得任意两个景点之间都会有一条路径）。为了保证公路系统的效率， OIER Association 希望在这 \(n-1\) 条公路之中，至少有 \(k\) 条 \((0 \le k \le n-1)\) 一级公路。OIER Association 也不希望为一条公路花费的钱。所以，他们希望在满足上述条件的情况下，花费最多的一条公路的花费尽可能的少。
而你的任务就是，在给定一些可能修建的公路的情况下，选择 \(n-1\) 条公路，满足上面的条件。
「BZOJ 2259」新型计算机 - 最短路
题意描述
Tim 正在摆弄着他设计的“计算机”，他认为这台计算机原理很独特，因此利用它可以解决许多难题。 但是，有一个难题他却解决不了，是这台计算机的输入问题。新型计算机的输入也很独特，假设输入序列中有一些数字（都是自然数——自然数包括 \(0\) ），计算机先读取第一个数字 \(s_1\) ，然后顺序向后读入 \(s_1\) 个数字。接着再读一个数字 \(s_2\) ，顺序向后读入 \(s_2\) 个数字……依此类推。不过只有计算机正好将输入序列中的数字读完，它才能正确处理数据，否则计算机就会进行自毁性操作！
Tim 现在有一串输入序列。但可能不是合法的，也就是可能会对计算机造成破坏。于是他想对序列中的每一个数字做一些更改，加上一个数或者减去一个数，当然，仍然保持其为自然数。使得更改后的序列为一个新型计算机可以接受的合法序列。
不过 Tim 还希望更改的总代价最小，所谓总代价，就是对序列中每一个数操作的参数的绝对值之和。
写一个程序：
- 从文件中读入原始的输入序列；
- 计算将输入序列改变为合法序列需要的最小代价；
- 向输出文件打印结果。
\(100\%\) 的数据满足：\(n < 1 \times 10^6 + 1\)
「NOIP2016」愤怒的小鸟 - 状压 DP
题意描述
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\)。
「洛谷 P4341」外星联络 - Trie
题意描述
小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星人发来的信息。
虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高低电平将接收到的信号改写为由
0 和 1 构成的串，
并坚信外星人的信息就隐藏在其中。他认为，外星人发来的信息一定会在他接受到的
01 串中重复出现，所以他希望找到他接受到的 01 串中所有重复出现次数大于
\(1\) 的子串。
但是他收到的信号串实在是太长了，于是，他希望你能编一个程序来帮助他。
对于 \(100\%\) 的数据，满足 \(0 \le N \le 3000\)
「洛谷 P2922」Secret Message - Trie
题意描述
贝茜正在领导奶牛们逃跑．为了联络，奶牛们互相发送秘密信息．
信息是二进制的，共有 \(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\)。
「ZJOI2020」序列 - 贪心
题意描述
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\)。
「SCOI2010」股票交易 - 背包 DP + 单调队列
题意描述
最近 \(\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}\)
「SDOI2010」古代猪文 - 数论 + Lucas 定理
题意描述
给定整数 \(g\)，\(n\)（\(1 \leq q, n \leq 10^9\)），计算：
\[ g^{\sum_{d|n}{C_{n}^{d}}} \operatorname{mod} 999911659 \]