给定一个长度为 $n$ 的字符串，你需要在任意位置添加尽量少的字符，使新串是回文串。输出最少添加的字符个数以及新串。

有 $n$ 个仓库，让 $m$ 个人来看管。一个仓库只能由一个人来看管，一个人可以看管多个仓库。
每个人有一个能力值 $p_i$，如果他看管 $k$ 个仓库，那么所看管的每个仓库的安全值为 $\lfloor \frac {p_i} {k}\rfloor$
如果某个仓库没有人看管，那么它的安全值为 $0$。所有仓库的安全值 $L$ 为所有仓库安全值的最小值
如果雇佣一个人的工资等于他的能力值 $p_i$。
从 $m$ 个人中选择一些人雇佣，问所有仓库的安全值最高是多少，在安全值最高的情况下，求雇佣的最少价钱。

有一个 $n \times m$ 的矩阵，请你选出其中 $k$ 个子矩阵，使得这个 $k$ 个子矩阵分值之和最大。注意：选出的 $k$ 个子矩阵不能相互重叠。

给出一个字符串，输出其字典序最小的最长回文子序列。

给出一个字符串，把它分成 $k$ 块，块内可以任意排序，连续的相同字母算作一段，求最终字符串中的最小段数。

给定一个初始集合和目标集合，有两种操作：

1. 合并集合中的两个元素，新元素为两个元素之和
2. 分裂集合中的一个元素，得到的两个新元素之和等于原先的元素

要求用最小步数使初始集合变为目标集合，求最小步数。

Pine 开始了从 $ S $ 地到 $ T $ 地的征途。
从 $ S $ 地到 $ T $ 地的路可以划分成 $ n $ 段，相邻两段路的分界点设有休息站。
Pine 计划用 $ m $ 天到达 $ T $ 地。除第 $ m $ 天外，每一天晚上 Pine 都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine 希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助 Pine 求出最小方差是多少。

设方差是 $ v $，可以证明，$ v \times m ^ 2 $ 是一个整数。为了避免精度误差，输出结果时输出 $ v \times m ^ 2 $。

给出一些数字串作为模式串，求 $[l, r]$ 中第 $k$ 个包含至少一个模式串的串。

求 $[l, r]$ 中平衡数的个数，平衡数就是一某一位为支点，两侧的力矩相等。

P 教授有编号为 $1 \sim N$ 的 $N$ 件玩具，第 $i$ 玩具经过压缩后变成一维长度为 $C_i$ 为了方便整理，P 教授要求在一个一维容器中的玩具编号是连续的。如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中，那么容器的长度将为 $$x = j - i + \sum\limits_{k = i} ^ j C_k$$。如果容器长度为 $x$。其制作费用为 $(x - L) ^ 2$。其 $L$ 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$。但他希望费用最小。

二维坐标系中有 $n$ 个矩形，第 $i$ 个矩形在水平方向上覆盖 $[l_i, r_i]$，在竖直方向上覆盖 $[i - 1, i]$，我们要水平移动这些矩形使得它们全部连通，水平移动的花费是移动的距离，求最小费用。

将 $n_1$ 个 $A$，$n_2$ 个 $B$，$n_3$ 个 $C$，$n_4$ 个 $D$ 排成一个序列。求问有多少种排列方案使得排成的序列任意相邻的两个字母不同。

给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。

对于一个非空集合{$a_i$},我们称一个集合是 $magical$ 的,当且仅当它满足以下两个条件。

1:$a_1$ & $a_2$ &…& $a_n$ =0(&表示 $and$)

2:{$a_i$} 的任意一个除它本身外的非空子集不满足1。

小 $A$ 有一个很大很大的集合。很显然这个集合的子集数量是一个天文数字。

小 $A$ 现在想要知道这个集合的 magical 的非空子集数量是多少。

为了防止不必要的麻烦,请将答案 $mod$ $1e9+7$ 后输出。

计算数字

题目描述

当连续写下从十进制整数 1 开始到某个整数 N 之间的所有整数时，能得到如下的数字序列：
12345678910111213141516171819202122 \cdots \cdots
编写一个程序，计算这个序列中的数字个数。

输入格式

输入的第一行且是唯一的一行包含：一个整数 N，1 \leq N \leq 100,000,000。

输出格式

输出的第一行且是唯一的一行应包含：由给定的整数所产生的序列的数字个数。

老旧的机器

题目描述

伟大的工程师阿克蒙德买了一台机器，为了维持这台机器的正常运作，他每年必须花费一定的费用来维修这台机器。但是随着这台机器的使用，机器会损坏更快以至于每年用来维修这台机器的费用都是上一年的 1.5 倍。已知第一年仅需花费 1 元。现在阿克蒙德想知道，如果他想用 n 年，他总共需要花费多少钱来维修这台机器。

没有上司的晚会

题目背景

poj2342

题目描述

Ural 大学有N 个职员，编号为 1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。

输入格式

第一行一个整数 N (1<=N<=6000)。
接下来 N 行，第i+1行表示i 号职员的快乐指数Ri(-128<=Ri<=127) 。
接下来 N-1 行，每行输入一对整数 L 和 K。表示 K 是 L 的直接上司
最后一行输入0 0。

输出格式

输出最大的快乐指数。

麻烦的聚餐

题目描述

为了避免餐厅过分拥挤，FJ要求奶牛们分3批就餐。每天晚饭前，奶牛们都会在餐厅前排队入内，按FJ的设想，所有第3批就餐的奶牛排在队尾，队伍的前端由设定为第1批就餐的奶牛占据，中间的位置就归第2批就餐的奶牛了。由于奶牛们不理解FJ的安排，晚饭前的排队成了一个大麻烦。
第i头奶牛有一张标明她用餐批次 D_i(1 <= D_i <= 3) 的卡片。虽然所有 N (1 <= N <= 30,000) 头奶牛排成了很整齐的队伍，但谁都看得出来，卡片上的号码是完全杂乱无章的。 在若干次混乱的重新排队后，FJ找到了一种简单些的方法：奶牛们不动，他沿着队伍从头到尾走一遍，把那些他认为排错队的奶牛卡片上的编号改掉，最终得到一个他想要的每个组中的奶牛都站在一起的队列，例如 111222333 或者 333222111。哦，你也发现了，FJ不反对一条前后颠倒的队列，那样他可以让所有奶牛向后转，然后按正常顺序进入餐厅。
你也晓得，FJ是个很懒的人。他想知道，如果他想达到目的，那么他最少得改多少头奶牛卡片上的编号。所有奶牛在FJ改卡片编号的时候，都不会挪位置。