题目为：

[NOIP2002 提高组] 均分纸牌

影子

键盘

字符串

图论

数据结构

1.

题目描述

有NN堆纸牌，编号分别为 1,2,…,N1,2,…,N。每堆上有若干张，但纸牌总数必为 NN 的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为 11 堆上取的纸牌，只能移到编号为 22 的堆上；在编号为 NN 的堆上取的纸牌，只能移到编号为 N-1N−1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如 N=4N=4 时，44 堆纸牌数分别为 9,8,17,69,8,17,6。

移动 33 次可达到目的：

• 从第三堆取 44 张牌放到第四堆，此时每堆纸牌数分别为 9,8,13,109,8,13,10。
• 从第三堆取 33 张牌放到第二堆，此时每堆纸牌数分别为 9,11,10,109,11,10,10。
• 从第二堆取 11 张牌放到第一堆，此时每堆纸牌数分别为 10,10,10,1010,10,10,10。

输入格式

第一行共一个整数 NN，表示纸牌堆数。
第二行共 NN 个整数 A_1,A_2,\cdots,A_NA1​,A2​,⋯,AN​，表示每堆纸牌初始时的纸牌数。

输出格式

共一行，即所有堆均达到相等时的最少移动次数。

输入输出样例

输入 #1复制

4
9 8 17 6

输出 #1复制

3

说明/提示

对于 100\%100% 的数据，1 \le N \le 1001≤N≤100，1 \le A_i \le 100001≤Ai​≤10000。

【题目来源】

NOIP 2002 提高组第一题

2.
 

题目描述

相比 wildleopard 的家，他的弟弟 mildleopard 比较穷。他的房子是狭窄的而且在他的房间里面仅有一个灯泡。每天晚上，他徘徊在自己狭小的房子里，思考如何赚更多的钱。有一天，他发现他的影子的长度随着他在灯泡和墙壁之间走到时发生着变化。一个突然的想法出现在脑海里，他想知道他的影子的最大长度。 

输入格式

输出格式

输出文件共 T 行，每组数据占一行表示影子的最大长度，保留三位小数。

输入输出样例

输入 #1复制

3
2 1 0.5
2 0.5 3
4 3 4

输出 #1复制

1.000
0.750
4.000

说明/提示

3.

题目描述

给定一个 rr 行 cc 列的在电视上的「虚拟键盘」，通过「上，下，左，右，选择」共 55 个控制键，你可以移动电视屏幕上的光标来打印文本。一开始，光标在键盘的左上角，每次按方向键，光标总是跳到下一个在该方向上与当前位置不同的字符，若不存在则不移动。每次按选择键，则将光标所在位置的字符打印出来。
现在求打印给定文本（要在结尾打印换行符）的最少按键次数。

输入格式

第一行输入 r,cr,c。
接下来给出一个 r\times cr×c 的键盘，包括大写字母，数字，横线以及星号（星号代表 Enter 换行）。
最后一行是要打印的文本串 SS，SS 的长度不超过 1000010000。

输出格式

输出打印文本（包括结尾换行符）的最少按键次数。保证一定有解。

输入输出样例

输入 #1复制

2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ

输出 #1复制

19

输入 #2复制

5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015

输出 #2复制

160

说明/提示

样例解释 1

1. 键入 A 11 次
2. 下（X）右（*）右（Y）左（*）上（Z），移动 55 次
3. 键入 Z 11 次
4. 下（*）左（X）上（A），移动 33 次
5. 键入 A 11 次
6. 从 A 移动到 Z 55 次
7. 键入 Z 11 次
8. 下（*），移动 11 次
9. 键入 * 11 次

数据范围与提示

对于 100\%100% 的数据，1\le r,c\le 501≤r,c≤50，SS 的长度不超过 1000010000。

4.

题目描述

「Madoka，不要相信 QB！」伴随着 Homura 的失望地喊叫，Madoka 与 QB 签订了契约。

这是 Modoka 的一个噩梦，也同时是上个轮回中所发生的事。为了使这一次 Madoka 不再与 QB 签订契约，Homura 决定在刚到学校的第一天就解决 QB。然而，QB 也是有许多替身的（但在第八话中的剧情显示它也有可能是无限重生的），不过，意志坚定的 Homura 是不会放弃的——她决定消灭所有可能是 QB 的东西。现在，她已感受到附近的状态，并且把它转化为一个长度为 nn 的字符串交给了学 OI 的你。

现在你从她的话中知道，所有形似于 A+B+AA+B+A 的字串都是 QB 或它的替身，且 |A|\ge k,|B|\ge 1∣A∣≥k,∣B∣≥1 （位置不同其他性质相同的子串算不同子串，位置相同但拆分不同的子串算同一子串），然后你必须尽快告诉 Homura 这个答案——QB 以及它的替身的数量。

注：对于一个字符串 SS，|S|∣S∣ 表示 SS 的长度。

输入格式

第一行一个字符串 SS，第二行一个数 kk。

输出格式

仅一行一个数 \text{ans}ans，表示 QB 以及它的替身的数量。

输入输出样例

输入 #1复制

aaaaa
1

输出 #1复制

6

输入 #2复制

abcabcabc
2

输出 #2复制

8

说明/提示

对于全部数据，1\le |S|\le 1.5\times 10^4,1\le k\le 1001≤∣S∣≤1.5×104,1≤k≤100，且字符集为所有小写字母。

5.

题目描述

由于外国间谍的大量渗入，国家安全正处于高度危机之中。如果 AA 间谍手中掌握着关于 BB 间谍的犯罪证据，则称 AA 可以揭发 BB。有些间谍接受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。

我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有 nn 个间谍，每个间谍分别用 11 到 nn 的整数来标识。

请根据这份资料，判断我们是否可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。

输入格式

第一行只有一个整数 nn。第二行是整数 pp。表示愿意被收买的人数。

接下来的 pp 行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。

紧跟着一行只有一个整数 rr。然后 rr 行，每行两个正整数，表示数对 (A,B)(A,B)，AA 间谍掌握 BB 间谍的证据。

输出格式

如果可以控制所有间谍，第一行输出 YES，并在第二行输出所需要支付的贿金最小值。否则输出 NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。

输入输出样例

输入 #1复制

2 
1 
2 512 
2 
1 2 
2 1

输出 #1复制

YES
512

说明/提示

1 \le n \le 3000,1 \le p \le n,1 \le r \le 80001≤n≤3000,1≤p≤n,1≤r≤8000，每个收买的费用为非负数且不超过 2000020000。

6.

题目描述

小A喜欢步行游历各国，顺便虐爆各地竞赛。小A有一条游览路线，它是线型的，也就是说，所有游历国家呈一条线的形状排列，小A对每个国家都有一个喜欢程度（当然小A并不一定喜欢所有国家）。

每一次旅行中，小A会选择一条旅游路线，它在那一串国家中是连续的一段，这次旅行带来的开心值是这些国家的喜欢度的总和，当然小A对这些国家的喜欢程序并不是恒定的，有时会突然对某些国家产生反感，使他对这些国家的喜欢度 \deltaδ 变为 \sqrt \deltaδ​（可能是小A虐爆了那些国家的 OI，从而感到乏味）。

现在给出小A每次的旅行路线，以及开心度的变化，请求出小A每次旅行的开心值。

输入格式

第一行是一个整数 NN，表示有 NN 个国家；

第二行有 NN 个空格隔开的整数，表示每个国家的初始喜欢度 \delta_iδi​；

第三行是一个整数 MM，表示有 MM 条信息要处理；

第四行到最后，每行三个整数 x,l,rx,l,r，当 x=1x=1 时询问游历国家 ll 到 rr 的开心值总和，也就是 \sum\limits_{i=l}^r \delta_ii=l∑r​δi​ ，当 x=2x=2 时国家 ll 到 rr 中每个国家的喜欢度 \delta_iδi​ 变为 \sqrt {\delta_i}δi​​ 。

输出格式

每次 x=1x=1 时，每行一个整数。表示这次旅行的开心度。

输入输出样例

输入 #1复制

4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4

输出 #1复制

101
11
11

说明/提示

对于全部数据，1\le n\le 10^5,1\le m\le 2\times 10^5,1\le l\le r\le n,0\le \delta_i \le 10^91≤n≤105,1≤m≤2×105,1≤l≤r≤n,0≤δi​≤109。

注：建议使用 sqrt 函数，且向下取整

大佬们，如果有满分的可以看一下我的noi测试（很难，我40分）

 886