Rain杯No.1 初见篇
本系列故事以及人名地名等纯属虚构，如有雷同，纯属巧合
在极东之地，有一个岛国，与岛国隔了一个海域有一个古老的国度，天朝。天朝T镇有个少年叫小S，故事从小S与少女Rain的相遇说起。
初见
(first_meet.pas/cpp)
题目描述：
在一个下雨的早晨，小S在大街上撑伞走着，路过一个便利店时，小S遇到了一个避雨的少女，少女不高，短发，小S在T镇从来没见到过这个少女，于是小S主动说道：“Hello , nice to meet you , are you new here , what’s
your name ?”
少女疑惑地看着小S，说出了一大串小S听不懂的话，小S表示十分痛苦，还好小S的记忆力超群，他能记住少女说的全部n句话和其中的每一个字母，小S认为最长的、在每句话中至少出现两次且不重叠的子串可能是少女的名字，小S想尽快知道少女的名字，请你求出这个长度。
输入描述：
第一行一个整数t，表示测试数据组数。对于每组测试数据：
第一行一个整数n，表示少女说了n句话。
接下来n行每行一个字符串，为少女说的话，仅包含’a’~’z’，忽略行尾空格。
输出描述：
对于每组测试数据，输出最长的字符串的长度。
输入样例：
1
4
abbabba
dabddkababa
bacaba
baba
输出样例：
2
数据范围：
l t<=10,n<=10,每个字符串长度为2~10000
光喷泉
(fountain.pas/cpp)
题目描述：
“好奇怪的语言，”小S自言自语道，“她叫什么名字呢？”
“我叫Rain。”少女弱弱地说道。
“晕，你会说汉语呀，可你怎么说奇怪的语言？”
“是你先说的。”
“好吧。。。”
经过一番亲切的交谈，小S知道了Rain新搬来小镇，父母在外地工作，留她一个人住，父母整理好屋子就走了，她是来买东西的，被困在雨中。
“你怎么没买把伞啊？”小S问。
“手拎着东西拿不了伞。。。”
“。。。”
“你看便利店钱有高科技产品——光喷泉！”小S为了活跃气氛说道，“我们面前有一个数轴上面有一些光喷泉孔，其中n个正在发光，一个光喷泉孔可以发射出多束光，我们在这里可以对它们远程操作，把第p束光移动到k位置，多么漂亮啊！便利店还有任意多个可移动摄影机，可以拍摄长度为L的一段，包括两端。”
“那我来远程操作光喷泉，你来告诉我最少需要多少摄影机才能拍摄到全部的光吧！”Rain说道。
小S瞬间回答说：“这不是很简单吗？”
“哦，我一共会进行m次操作哦”
“好吧。。。”
输入描述：
第一行，三个整数n，m，l，n表示同时有n个喷光孔喷光，m表示Rain有m次操作，l表示一架摄影机的视野。
第二行n个整数，表示初始每束光线排序后的位置。
接下来m行，每行两个整数p，k表示将第p束光移动到k位置。
输出描述：
共m行，每行一个整数，表示需要的最小摄像机数目。
输入样例：
4 5 10
10 15 17 20
2 16
1 25
3 35
0 38
2 0
输出样例：
1
2
2
2
3
数据范围：
l 对于10%的数据n=2，m<=100，初始、操作后每束光位置不同。
l 对于26%的数据1<=n<=100，m<=100，初始、操作后每束光位置不同。
l 对于50%的数据1<=n<=50,000，m<=50,000，操作后每束光位置不同。
l 对于97%的数据1<=n<=70,000，m<=70,000。
l 最后3%的数据，防AK。
整理房间
(tidy.pas/cpp)
题目描述：
雨停了，小S帮Rain拎着东西回到了Rain家，此时Rain家已经被整理得井井有条，但是，Rain的房间还有些乱。
Rain的房间可视为一张n*m的网格图，无序地放着tot个娃娃，Rain也决定有tot个放娃娃的位置，每个娃娃可以放进任意一个位置，一个位置也只能放一个娃娃。
小S自告奋勇帮Rain整理娃娃，每携带一个娃娃走1单位（只能沿着网格走）需要1单位体力，不携带娃娃走路不消耗体力，当然你可以携带一个娃娃经过一个存放位置而不存放。
输入描述：
多组测试数据。对于每组测试数据：
第一行包括两个整数n和m，表示地图是n行m列。
接下来n行每行m个字符，’.’表示普通位置，’H’表示放置位置，’m’表示娃娃位置。
输入数据以0 0结束
输出描述：
对于每组测试数据，输出一行，一个整数，表示最小体力消耗。
样例输入：
2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0
样例输出：
2
10
28
数据范围：
l 2<=n,m,tot<=100
题目名 | 初见 | 光喷泉 | 整理房间 |
程序名 | first_meet .pas/cpp | fountain .pas/cpp | Tidy .pas/cpp |
输入文件 | first_meet.in | fountain.in | tidy.in |
输出文件 | first_meet.out | fountain.out | tidy.out |
时间限制 | 1s | 10s | 1s |
空间限制 | 512MB | 512MB | 512MB |