NOIp越来越水了，题目还没大家的模拟赛出得好。我感觉从来没有这么垃圾的题目，一二题完全是送分题，三题估计多数人都会，只有四题或许会难住一些人。本来还想写题解的……算了，不用写了，节约点时间赶我的高数作业。

第一题：count 统计数字
    输入一个数n(n<=200000)和n个自然数（每个数都不超过1.5*10^9），请统计出这些自然数各自出现的次数，按顺序从小到大输出。输入数据保证不相同的数不超过10000个。

样例输入：
8
2
4
2
4
5
100
2
100
样例输出：
2 3
4 2
5 1
100 2

第二题：expand 字符串的展开
    我们可以用减号对连续字母或数字进行缩写，于是字符串a-dha3-68就可以展开为abcdha34568。
    输入三个参数p1,p2,p3，再输入一个仅由数字、小写字母和减号组成的字符串（长度不超过100），请按参数展开此字符串
    各个参数的意义如下：

• 参数p1=1 -> 所有填充的字母都写成小写；
• 参数p1=2 -> 所有填充的字母都写成大写；
• 参数p1=3 -> 所有填充的字母和数字都用星号代替；
• 参数p2=k -> 同一个填充字符连续写k遍；
• 参数p3=1 -> 顺序填充；
• 参数p3=2 -> 逆序填充。

    另外，如果减号两边的字符一个是数字一个是字母，或者减号右边的ASCII码没左边的大，则该处不变

样例输入1：
1 2 1
abcs-w1234-9s-4zz
样例输出1：
abcsttuuvvw1234556677889s-4zz

样例输入2：
2 3 2
a-d-d
样例输出2：
aCCCBBBd-d

样例输入3：
3 4 2
di-jkstra2-6
样例输出3：
dijkstra2************6

第三题：game 矩阵取数游戏
    一个n行m列的矩阵，每次你需要按要求取出n个数，m次正好将所有数取完。每取出一个数你都会有一个得分，请求出最终的得分最大是多少。
    每一次取数的要求：每一行中恰好取一个数，且只能取剩下的数中最左边或最右边位置上的数
    每取一个数的得分：所取数的数值乘以2^i，i表示这是第i轮取数。
    矩阵中的数为不超过100的自然数，1<=n,m<=80

样例输入：
2 3
1 2 3
3 4 2
样例输出：
82
样例说明：
1*2+2*2 + 2*4+3*4 + 3*8+4*8 = 82

第四题：core 树网的核
    树上的任两点间都有唯一路径。定义某一点到树上某一路径的距离为该点到路径上所有点的路径长度中的最小值。定义树中某条路径的“偏心距”为所有其它点到此路径的距离的最大值。定义树的直径为树的最长路径（可能不唯一）。给出一个有n个节点的无根树，请找出某个直径上的一段长度不超过s的路径（可能退化为一个点），使它的偏心距最小。请输出这个最小偏心距的值。
    题目已经告诉你如下定理：树的所有直径的中点必然重合（这个中点可能在某条边上）。其实这个结论很显然嘛，因为如果中点不重合的话必然可以找到一条更长的路。
    5<=n<=300，0<=s<=1000，边权是不超过1000的正整数

只是大致读了一下题目，若有写错的地方请指正
感谢huyue第一时间发布题目照片

1. 我在Vijos的第二次NOIp模拟赛是2006年10月5日，正好是一年前。

2. 那次模拟赛的第一题也是Matrix67的情书。两次题目的样例数据所用的情书是一样的。

3. 第一题最初的想法是：Matrix67喜欢美剧24，它希望在一串数字中统计有多少个子序列（所构成的10进制数）能被24整除。

4. 我的幸运数字不是28。我的幸运数字是23。我的第二任女友昵称23，05年2月23日认识她，同年12月23日分手。我去年7月23日参加第23届NOI，不算笔试的话是23名。

5. 你可以从lovelttr4.in看出，我是9月19日出的第一题。

6. lovelttr5.in是在Google中搜索porn得到的前500个结果。

7. 我曾经完整地读过lovelttr7.in的中文版。

8. 有人知道John Titor吗？lovelttr8.in完整地记录了这次事件。

9. 为了增加句子的个数，我把lovelttr9.in的D:和E:全部替换为?: （结果导致数据出错）

10. 我的StarCraft目录下有很多RPG地图，因为很多文件名包含题目中不允许出现的字符，于是从数据中删除了。

11. 我曾经认真地想过在最后一个数据中添加F:Adult Video目录，最后没有添加，原因同上。

12. 我真的是因为想制造极限数据（凑齐1000000字节）才添加的Sentimental Shooting目录。

13. Worms World Party是我最喜欢的游戏之一。

14. 我第二题的标程写错了，修正数据后重新评测了一遍，因此评测结果迟迟没有公布。

15. 我把我们系的一个MM的生日写错了。我写的是10月11日，后来才知道她的生日是10月12日。

16. 我曾经认真地想过把第二题换掉，因为我觉得这道题太简单了。

17. 前两题都是我在史纲课上突然想到的，于是有了举办模拟赛的想法。

18. 第四题的构思和数据来源于这里。

19. 最后两题的标程和数据是在比赛前一天晚上赶出来的，因为那天白天和清北学堂的OIer出去吃饭去了。

20. 我仍然认为这是我个人举办的所有模拟赛中最简单的一次。

Problem 1: Matrix67的情书（二）
    大家都知道，看一个数是否能被2整除只需要看它的个位能否被2整除即可。可是你想过为什么吗？这是因为10能被2整除，因此一个数10a+b能被2整除当且仅当b能被2整除。大家也知道，看一个数能否被3整除只需要看各位数之和是否能被3整除。这又是为什么呢？答案或多或少有些类似：因为10^n-1总能被3整除。2345可以写成2*(999+1) + 3*(99+1) + 4*(9+1) + 5，展开就是2*999+3*99+4*9 + 2+3+4+5。前面带了数字9的项肯定都能被3整除了，于是要看2345能否被3整除就只需要看2+3+4+5能否被3整除了。当然，这种技巧只能在10进制下使用，不过类似的结论可以推广到任意进制。
    注意到36是4的整数倍，而ZZZ…ZZ除以7总是得555…55。也就是说，判断一个36进制数能否被4整除只需要看它的个位，而一个36进制数能被7整除当且仅当各位数之和能被7整除。如果一个数同时能被4和7整除，那么这个数就一定能被28整除。于是问题转化为，有多少个连续句子满足各位数字和是7的倍数，同时最后一个数是4的倍数。这样，我们得到了一个O(n)的算法：用P[i]表示前若干个句子除以7的余数为i有多少种情况，扫描整篇文章并不断更新P数组。当某句话的最后一个字能被4整除时，假设以这句话结尾的前缀和除以7余x，则将此时P[x]的值累加到最后的输出结果中（两个前缀的数字和除以7余数相同，则较长的前缀多出来的部分一定整除7）。
    上述算法是我出这道题的本意，但比赛后我见到了其它各种各样新奇的算法。比如有人注意到36^n mod 28总是等于8，利用这个性质也可以构造出类似的线性算法来。还有人用动态规划（或者说递推）完美地解决了这个问题。我们用f[i,j]表示以句子i结束，除以28余数为j的文本片段有多少个；处理下一句话时我们需要对每一个不同的j进行一次扫描，把f[i-1,j]加进对应的f[i,j']中。最后输出所有的f[i,0]的总和即可。这个动态规划可以用滚动数组，因此它的空间同前面的算法一样也是常数的。
    如果你完全不知道我在说什么，你可以看看和进位制、同余相关的文章。另外，我之前还曾出过一道很类似的题(VOJ1090)，你可以对比着看一看。
    另外，非常抱歉地告诉大家，这道题的最后一个数据是错的。这个数据的第一个句子是一个空句子（感谢Ai.Freedom的提醒）。很多第一题只得了90分的好同志估计都是由于我的失误造成的，这里再次表示歉意。如果去掉最前面的那个问号，输出应该是19511110。

Problem 2: 送给MM的生日礼物
        
    我们用f[i,j,k]表示以第i行第j列的格子为右下角，边长为k的正方形是否符合要求。要想f[i,j,k]=True，首先必须满足f[i-1,j-1,k-2]为True（灰色部分满足要求）。另外，我们还需要保证图中两块蓝色区域相等，两块绿色区域相等，并且这四个区域自身还必须是对称的。由于动态规划的状态已经是三方的了，因此判断后面的这些条件必须在常数时间里完成。为此，我们可以在动态规划前进行以下6个预处理：

以同列不同行的两个格子(i,j)和(i',j)为右端点，同时向左扩展可以得到多长的相等区域
以同行不同列的两个格子(i,j)和(i,j')为最底端，同时向上扩展可以得到多长的相等区域
以格子(i,j)为中心，向左右扩展可以得到多长的对称区域
以格子(i,j)为中心，向上下扩展可以得到多长的对称区域
以两个横向相邻的格子(i,j-1)和(i,j)为中心，向左右扩展可以得到多长的对称区域
以两个纵向相邻的格子(i-1,j)和(i,j)为中心，向上下扩展可以得到多长的对称区域

    上面的每个预处理都可以在三方的时间里完成，动态规划的决策降到常数级别，因此总的复杂度还是三方。

    同样地，这也只是我出这道题的本意。我事先已经想到，这道题应该还有很多其它的算法，只是没想到会有那么多。一个比较容易想到的算法是，执行与上面相同的预处理后，枚举某个格子（或某个交叉点）为中心，向外一层一层地进行扩展。虽然这样的复杂度仍然是三方的，并且与前面的算法实质相同，但它的效率显然更高，因为你可以在无法再向外扩展时停止最里面的那个循环，继续枚举下一个中心点。
    同样是枚举正方形的中心点，只使用上面的后4个预处理也可以解决这个问题。我们可以在线性的时间内找出，以某个格子（或交叉点）为中心的最大的合法正方形。假如这个最大的正方形边长为k，这相当于我们同时找到了(k+1) div 2个正方形来。至于如何找到这个最大的正方形，还是留给大家思考吧。
    Cockhorse想到了一个非常巧妙的算法，预处理结束后它可以在常数时间内判断任一个给定的小正方形是否满足题目要求。用f[i,j,k]表示，以第i行中(i,j)及其右边相邻的k-1个格子（共k个格子）来作为底边，所能得到的左右对称的矩形其最大高度是多少。则当f[i,j+1,k-2]为True且(i,j)格与(i,j+k-1)格花色相等时f[i,j,k]=f[i-1,j,k]+1（否则f[i,j,k]=0）。同样地，再用g[i,j,k]表示以(j,i)..(j+k-1,i)作为右边界，使矩形上下对称的最大宽度。这样，判断任意一个正方形是否满足题目要求，只需要检查它的底边和右边能够产生的最大对称区域是否可以覆盖该正方形即可。
    当然，这道题目还有很多其它的算法，这里就不一一列举了。

Problem 3: 流言的传播
    给定一个图，把图中所有点构成的点集叫做U，另指定一个不等于全集的子集S，那么所有一个顶点在S里另一个顶点在U-S里的边就叫做S点集的“割边”，因为去掉所有这样的边后S集将孤立出来。这道题就是需要你找出一个边集E，使得不管S集是什么，对应的割边中权值最小的那一条一定在边集E中。这样的边集肯定是存在的，比如所有边构成的集合就是一个满足条件的边集。这道题希望你找到的边集E里所含的边尽可能的少。
    一个错误的贪心法是，去掉每个点的邻接边中权值最小的那一条。这种算法显然不对，比如下面就是一个鲜活的反例：

o—–o—–o—–o
   2     3     1

    在上图中，每个点的邻接边中权值最小的不是1就是2，这样的话中间那条边就被保留了下来，于是令S集为左边两个点（或右边两个点），割边仍然一条不少。很容易想到，要想让任意S集的割边中权值最小的被去掉，首先得保证边集E连通了所有的点，否则令S等于任一连通分量，边集E里都不会包含任何一条割边。这样，边集E至少要有n-1条边。
&n
bsp;   考虑到最优解至少是n-1条边，这n-1条边必须连通所有的点，而所选边的权值都应该很小，于是想到最后的答案很可能就是最小生成树。现在假设我们已经选择了某些边，这些边形成了若干个连通分量。考虑所有连接两个不同的连通分量的边（两顶点不在同一连通分量的边）中权值最小的一条，那这条边必须要选，否则令S集为其中一个连通分量，题目条件就不能达到了。这不就是Kruskal算法吗？
    且慢，我们还没有证明，对任意一个S集，最小生成树都符合条件。证明其实很简单，假设权值最小的割边e不在最小生成树E中，添加割边e将形成一个回路。这条回路将从S集的某个点出发，经过e跑到U-S里，最后必须还要回到S集。回到S集必然要经过另一条割边e'，而显然e'>e（因为e是权值最小的割边，且题目说了没有权值相同的边），于是边集E+{e}-{e'}就成了更小的生成树。

Problem 4: 表白机器人
    第四题是整个模拟赛中最简单的题，它不需要你构造任何算法，你只需要按照题目意思进行模拟即可。和去年的NOIp一样，纯粹考编程能力的题目并没有放在第一道题的位置上。这提示大家拿到题目后要先看完所有的题，特别是看到最后一道题时千万别慌，很可能把它的衣服扒光了一看，发现它居然是一道赤裸裸的送分题。
    为了加快速度，先预处理出一个数组wall[i][j][k]，表示第i行第j列往k(1<=k<=4)方向上走是否走得通。然后枚举所有可能的命令序列，模拟机器人的行走过程，看它是否能到达终点。在模拟过程中，你需要用一个数组hash[i][j][k]表示机器人曾在序列的第k个命令后到达第i行第j列的位置，并在模拟过程中不断更新hash数组；当某一次命令后机器人还没走到右上角，而对应的hash值已经为True了，则机器人的行动将从这里开始循环，永远也到不了右上角了。
    虽然这道题不需要任何剪枝，但我还想再说一句。这道题有一个非常有趣的剪枝：命令序列的第一个指令只能是U或R，最后一个指令也只能是U或R。大家想想这是为什么。

lyt                     AAAAAAAAAA      AAAAAAAAAA      ??????????      AAAAAAAAAA      300
lyt (1)                 AAAAAAAAAA      AAAAAAAAAA      ??????????      AAAAAAAAAA      300
nothing                 WWWWWWWWWW      AAAAAAAAAA      AAAAAAAAAA      AAAAAAAAAA      300
coolerzxw (1)           AAAAAAAATT      AAAAAAAAAT      AAWWWWWWWW      AAAAAAAAAA      290
coolerzxw               AAAAAAAATT      AAAAAAAAAT      AAWWWWWWWW      AAAAAAAAAA      290
SubRaY                  WAAAAAAAAA      AAAAAAWWTT      ??????????      AAAAAAAAAA      250
wangbicheng1            WWWWWWWWWW      AAAAATTTTT      AAAAAAAAAA      AAAAAAAAAA      250
xyr                     WAAAAAAWBB      AAAAAWAATT      AAWWWWWWWW      AAAAAAAAAA      250
didiao                  ??????????      AAAAAAAATT      AAAAAAABBB      AAAAAAAAAA      250
猪都可以来虐我          AAAAAAAAAA      AAAAATTTTT      ??????????      AAAAAAAAAA      250
zxf_sheep               WWWWWWWWWW      AAAAWWWWWW      AAAAAAAAAA      AAAAAAAAAA      240
oldherl                 AAAAAAAAAA      AWAAAWWWWW      ??????????      AAAAAAAAAW      230
cockhorse               AAATTTTTTT      AAAAAAAAAA      ??????????      AAAAAAAAAA      230
latioswang (1)          WAAAAAAWTT      AWAAAAWWWT      AAWWWWWTTT      AAAAAAAAAA      230
latioswang (2)          WAAAAAAWTT      AWAAAAWWWT      AAWWWWWTTT      AAAAAAAAAA      230
latioswang              WAAAAAAWTT      AWAAAAWWWT      AAWWWWWTTT      AAAAAAAAAA      230
TangGingQ               AAAAAAAAAW      AWWAWWWWWW      AWWWWWWTTT      AAAAAAAAAT      210
宇智波然                AAAAAATTTT      AAAAWWWWWT      WWWWWWWWWW      AAAAAAAAAA      200
Avalon                  AAAAAAAAAA      AAAAAAAAAA      ??????????      ??????????      200
onion                   WWWWWWWWWW      AAAAAAAAAA      ??????????      AAAAAAAAAA      200
xc_bb                   AAAAAATTTT      AWAAAWWWWW      WWWWWWWWWW      AAAAAAAAAA      200
tang_of_fjsdfz          AAAAAAAAAW      AWWAWWWWWW      ??????????      AAAAAAAAAT      200
ztz                     AAAAAAAAAW      ??????????      ??????????      AAAAAAAAAA      190
ztz (1)                 AAAAAAAAAW      ??????????      ??????????      AAAAAAAAAA      190
inatial_D (1)           ??????????      AAAAAAAATT      AWWWWWWWWW      AAAAAAAAAA      190
AlexRay                 AAAAAAAAAA      AWWAWWWWWT      ??????????      AAAAAAATTT      190
Fp-hhh1                 WWWWWWWWWW      AAAAAAATTT      AAWWWWWWWW      AAAAAAAAAA      190
robot                   ??????????      AAAAAAAATT      ??????????      AAAAAAAAAA &
nbsp;    180
claire                  WWWWWWWWWW      AAAAAAAATT      ??????????      AAAAAAAAAA      180
star                    ??????????      AAAAAAAATT      ??????????      AAAAAAAAAA      180
我是菜鸟                ———-      AAAAAAAATT      ??????????      AAAAAAAAAA      180
star (1)                ??????????      AAAAAAAATT      ??????????      AAAAAAAAAA      180
robot (1)               ??????????      AAAAAAAATT      ??????????      AAAAAAAAAA      180
fengyi                  ??????????      AAAAAAAATT      YYYYYYYYYY      AAAAAAAAAA      180
fengyi (1)              ??????????      AAAAAAAATT      ??????????      AAAAAAAAAA      180
桃の11 (1)              WWWWWWWWWW      AAAAAAAATT      ??????????      AAAAAAAAAA      180
桃の11                  WWWWWWWWWW      AAAAAAAATT      ??????????      AAAAAAAAAA      180
tt (1)                  AAAAAAAAAA      AAAAAAAATT      ??????????      TTTTTTTTTT      180
tt                      AAAAAAAAAA      AAAAAAAATT      ??????????      TTTTTTTTTT      180
Jason911的Cheat程序     WWWWWWWWWW      AAAAAAWWWT      AWWWWWWWWW      AAAAAAAAAA      170
skyinde2                AAAAAWAATT      AAAAAAAATT      AAWWWWWTTT      ??????????      170
2wsx2wsx2wsx            WWWWWWWWWW      AAAAAAWWTT      ??????????      AAAAAAAAAA      160
ly                      WAAAAAAAAA      AAAAAAWWWW      ??????????      AWWWWWWWWW      160
PigTree                 ??????????      AAAAAAWWTT      ??????????      AAAAAAAAAA      160
ly (1)                  WAAAAAAAAA      AAAAAAWWWW      ??????????      AWWWWWWWWW      160
AC+AC                   AAAAAAAAAA      AWAAAAWWTT      ??????????      AWWWWWWWWW      160
zerg                    AAAWAAAAAT      AAAAAAAATT      ??????????      ??????????      160
fs                      ??????????      AWAAAAWWWW      ??????????      AAAAAAAAAA      150
fs (1)                  ??????????      AWAAAAWWWW      ??????????      AAAAAAAAAA      150
maoshengyang            ??????????      AAAAAWWWTT      ———-      AAAAAAAAAA      150
FP-hhh2                 WWWWWWWWWW      AWAAWWWWWT      AAWWWWWWWW      AAAAAAAAAA      150
windwind                WWWWWWWWWW      AAAAAAAATT      WWWWWWWWWW      AAAAAAATTT      150
Ice_Msk                 ??????????      AWAAWBBBTT      WWAWWWWWWW      AAAAAAAAAA      140
cy_super                ??????????      AWAAAWTTTT      WWWWWBBWWW      AAAAAAAAAA      140
lucylala                WWWWWWWWWW      AWAAWAWWTT      WWWWWWWWWW      AAAAAAAAAA      140
Firewood            &
nbsp;   ??????????      AAWAAWWWTT      ??????????      AAAAAAAAAA      140
lsz                     AAAAAAAAAA      AWAAAWWWWW      ??????????      YYYYYYYYYY      140
x_cRP版                 WWWAAAWWWA      ??????????      ??????????      AAAAAAAAAA      140
littlekfc               ??????????      AWAWWWAATT      ??????????      AAAAAAAAAA      140
jackchen                WWWWWWWWWW      AAAAAAAATT      WWWWWWWWWW      AAAAATTTTA      140
yyysb                   AAAAAAAATT      AAWAAAAWTT      ??????????      ??????????      140
xx&xx                   **********      AWAAWWWWWT      ??????????      AAAAAAAAAA      130
Takuma                  MMMMMMMMMM      AWWWWTTTTT      AAWWWWWWWW      AAAAAAAAAA      130
victor2100              WWWWWWWWWW      AWAAWWWWWW      ??????????      AAAAAAAAAA      130
victor2100 (1)          WWWWWWWWWW      AWAAWWWWWW      ??????????      AAAAAAAAAA      130
yk000123                ??????????      AAAAAAAATT      ??????????      AAAAWWWAWW      130
落叶归根                WWWWWWWWWW      AWAAWWWWWW      ??????????      AAAAAAAAAA      130
绝望了                  ??????????      AAAAAAAATT      ??????????      AAAAABBBBB      130
Pru.Lite                WWWWWWWWWW      AAAAAAAATT      WWWWWWWWWW      AWAAAWWWWA      130
sobeit                  ??????????      AAAAAAAATT      ??????????      AWAAAWWWWA      130
Fp-tens                 ??????????      ATTATTTTWW      ??????????      AAAAAAAAAA      120
落枫                    ??????????      AWAWWWTTTT      ??????????      AAAAAAAAAA      120
俺不玩了                WWWWWWWWWW      AWWAWWWWWW      ??????????      AAAAAAAAAA      120
laj (1)                 AAAAAAAAAW      ??????????      ??????????      AAAWWWWWWW      120
laj                     AAAAAAAAAW      ??????????      ??????????      AAAWWWWWWW      120
lydia                   WWWWWWWWWW      AAAAATTTTT      ??????????      AAAAAAATTT      120
hu                      AAAAAATTTT      AAAAAATTTT      WWWWWWWTTT      ??????????      120
mt_j                    TTTTTTTTTT      AWAAAWWWTT      WWWWWWWWWW      AAAAAAATTT      110
mt_j (1)                TTTTTTTTTT      AWAAAWWWTT      WWWWWWWWWW      AAAAAAATTT      110
hamo (1)                WWWWWWWWWW      AAWAWWWWWT      ??????????      AAAAAAAWAW      110
thbourlove              WWWWWWWWWW      AWWWWBBBBB      WWWWWWWWWW      AAAAAAAAAA      110
hamo                    WWWWWWWWWW      AAWAWWWWWT      WWWWWWWWWW      AAAAAAAWAW      110
hiroger (1)             WWWWWWWWWW      AW
WWWWWWWW      WWWWWWWWWW      AAAAAAAAAA      110
hiroger                 WWWWWWWWWW      AWWWWWWWWW      WWWWWWWWWW      AAAAAAAAAA      110
骑士                    WWWWWWWWWW      AWWWWBBBBB      WWWWWWWWWW      AAAAAAAAAA      110
fp-hxl                  WWWTTTTTTT      AAAAAAAATT      ??????????      AAAWWWWTWT      110
lwt1231234              WWWWWWWWWW      AWAAAAWWTT      WWWWWWWWWW      AAAAATATTT      110
zqqdtc                  WWWWWWWWWW      AWWWWWWWTT      WWWWWWWWWW      AAAAAAAAAA      110
Jason                   AAAAAAAATT      AWAAWWWWWW      ??????????      ??????????      110
wuxifan88               ??????????      ??????????      ??????????      AAAAAAAAAA      100
ufotalent               ??????????      ??????????      ??????????      AAAAAAAAAA      100
灰谜瞳                  WWWWWWWWWW      AAAAAAAATT      WWWWWWWWWW      AWAWWWWWWW      100
wasyyyy                 WWWWWWWWWW      AAAAAAAATT      AAWWWWWWWW      WWWWWWWWWW      100
叉叉叉叉                WWWWWWWWWW      AAAAAAAATT      AAWWWWWWWW      WWWWWWWWWW      100
BCSim                   *******TTT      AAAAAAAATT      WWWBWBBBBB      AWAWWWWWWW      100
追心子                  WWWWWWWWWW      AAAAAAAATT      WWWWWWWWWW      AWAWWWWWWW      100
Anthony                 WWWTTTTTTB      AAAAAAAATT      WWWWWWWWWW      AWAWWWWWWW      100
战役第一章              WWWWWWWWWW      AAAAAAAATT      WWWWWWWWWW      AWAWWWWWWW      100
zzy2007                 AAAAAATTTT      AAAAWTTTTT      ??????????      ??????????      100
lonely_knight           ??????????      AAAAAAAATT      ??????????      ATAWWTWTTT      100
luoshibo (1)            AAAAAAAAAA      MMMMMMMMMM      ??????????      ??????????      100
luoshibo                AAAAAAAAAA      MMMMMMMMMM      ??????????      ??????????      100
Xcheng                  WWWWWWWWWW      AAAAAAWWTT      ??????????      AWAAWWWW*W      90
monster_chen            ??????????      AAAAAAAATT      MMMMMMMMMM      *A*BBWB*WB      90
monster_chen (1)        ??????????      AAAAAAAATT      MMMMMMMMMM      *A*BBWBWWB      90
inatial_D               ??????????      AAAAAAAATT      AWWWWWWWWW      ??????????      90
koko                    WWWWWWWWWW      AAAAAAAATT      ??????????      AWWWWWWWWW      90
qqqjhjh                 ??????????      AAAAAAAATT      AWWWWWWWWW      ??????????      90
flyfox                  ??????????      ??????????      ??????????      AAAAAAAAAT      90
flyfox (1)              ??????????      ??????????      ??????????      AAAAAAAAAT      90
flyfox (2)              ??
????????      ??????????      ??????????      AAAAAAAAAT      90
xiaq                    AWWWAWWATT      AAAAAAWWTT      WWWWWWWWWW      WWWWWWWWWW      90
梦ぁ逍遥                AAAAAAAATT      AWWWWWWWTT      ??????????      ??????????      90
woac                    ———-      AAAAAAWWTT      ??????????      AWAWWWWWWW      80
MemoryBank              WWWWWWWWWW      AAAAAAWWTT      AAWWWWWWWW      ———-      80
zhang                   ??????????      AAAAATTTTT      WWWWWWWTTT      AAABBBBBBB      80
swj05652                ??????????      AAAAAAAATT      ??????????      ??????????      80
doris-king              ??????????      AAAAAAAATT      ??????????      WWWWWWWWWW      80
fp-hwh                  WWWWWWWWWT      AAAAAAAATT      ??????????      ??????????      80
zhouye                  ??????????      AAAAAAAATT      ??????????      ??????????      80
ayou                    WWWWWWWWWW      AAAAAAAATT      WWWWWWWWWW      ??????????      80
林添                    WWWWWWWWWW      AAAAAAAATT      ??????????      ??????????      80
meowkingdom             ??????????      AAAAAAAATT      ??????????      ??????????      80
纯白的守护              WWWWWWWWWW      AAAAWAWWTT      WWWWWWWWWW      AWAWWWWWWW      70
死亡山谷                WWWWWWWWWW      AAAAAAATTT      ??????????      ??????????      70
qweeo                   TTTTTTBBBB      AAAAAATATT      TTTTTTTTBT      ??????????      70
mwj                     WWWWWWWWTT      MMMMMMMMMM      ??????????      AWAAAWAAWW      60
lirczx                  ??????????      AAAAWBBBTT      AAWWWWWWWW      WWWWWWWWWW      60
mwj (1)                 WWWWWWWWTT      MMMMMMMMMM      ??????????      AWAAAWAAWW      60
cqbzzlg                 WWWWWWWWWW      AAAAAAWWTT      ??????????      ??????????      60
zjk                     WWWWWWWWWW      AWAAAAWWTT      ??????????      AWWWWWWWWT      60
tjbwyk                  WAAAAAAWTT      ??????????      ??????????      ??????????      60
初三小朋友来垫底        WWWWWWWWTT      AAAAAWWWTT      ??????????      ??????????      50
章亚中                  WWWWWWWWWW      AAAAWBBBBB      WWWWWWWWWW      ATTTTTTTTT      50
章亚中 (1)              WWWWWWWWWW      AAAAWBBBBB      WWWWWWWWWW      ATTTTTTTTT      50
gift                    ??????????      AAAAATTTTT      ??????????      ??????????      50
ice_bear                ??????????      AAAAABBBTT      ??????????      ??????????      50
sweetjuice              ??????????      AAAAWWAWWT      WWWWWWW
BBB      ??????????      50
Skyfan                  WWWWWWWWWW      AAAAWAWWTT      ??????????      ??????????      50
MAjia                   ??????????      AAAAATTTTT      ??????????      ??????????      50
1742                    TTTTTTTTTT      AAAAWWWWTT      ??????????      ———-      40
O'Element               WWWWWWWWWW      AWAWWWTTTT      WWWWWWWWWW      AWAWWWWWWW      40
ZeroZerg (1)            ———-      AWWWWBBBBB      ??????????      AWAAWWWWWW      40
wjx (1)                 WWWWWWWWWW      AWAAWAWWWW      ??????????      WWWWWWWWWW      40
wjx                     WWWWWWWWWW      AWAAWAWWWW      ??????????      WWWWWWWWWW      40
ZeroZerg                ———-      AWWWWBBBBB      ??????????      AWAAWWWWWW      40
fp_wzm                  ??????????      AAAAWTTTTT      ??????????      WWWWWWWWWW      40
fp_wzm (1)              ??????????      AAAAWTTTTT      ??????????      ??????????      40
我爱丁贝莉～！          ??????????      AAAATTTTTT      ??????????      ??????????      40
国庆快乐！              ??????????      AAAAWWWWWT      ??????????      ??????????      40
garfield175             WWWWWWWWWT      AWAAWWWWTT      WWWWWWWWWW      WWWWWWWWWW      30
iamworm                 WWWWWWWWWW      AWWWWWWWWW      WWWWWWWWWW      AWAWWWWWWW      30
gongbanban              ———-      AWWWWWWWWW      WWWWWWWWWW      AWAWWWWWWW      30
154315284               WWWWWWWWWW      AWAAWWTTWT      *****BBBBB      WWWWWWWWWW      30
yoy                     ??????????      AAAWTTTTTT      BBBBTBBTTT      ??????????      30
asdf                    ??????????      AAWAWWWWTT      ??????????      ??????????      30
政治课来做了一道        AWAATTTTTT      ??????????      ??????????      ??????????      30
111                     WWWWWWWWTT      AWWAWWWWTT      ??????????      ??????????      20
FREEDOM                 ??????????      AAWWWWWWTT      ??????????      ??????????      20
hudqmh                  ??????????      AWWAWWWWTT      ??????????      WWWWWWWWWW      20
ke_ma                   WWWWWWWWWW      WWWWWWWWWW      WWWWWWWWWW      AWAWWWWWWW      20
ke_ma (1)               WWWWWWWWWW      WWWWWWWWWW      WWWWWWWWWW      AWAWWWWWWW      20
tom                     **********      WWWWWWWWWW      ??????????      AWAWWWWWWW      20
我是周杰伦              WWWWWWWWWW      WWWWWWWWWW      WWWWWWWWWW      AWAWWWWWWW      20
101                     ??????????      ??????????      AAWWWWWWWW      ??????????      20
mart               &
nbsp;    WWWWWTTTTT      **********      WWWWWWWWWW      AWAWWWWWWW      20
fp-HRT                  TTTTTTTTTT      AWWAWWWWTT      ??????????      ??????????      20
mart (1)                WWWWWTTTTT      **********      WWWWWWWWWW      AWAWWWWWWW      20
GriffinHeart            MMMMMMMMMM      MMMMMMMMMM      AWWWWTBBBB      ??????????      10
huaimao                 WWWWWWTTTT      AWWWWTTTTT      ??????????      ??????????      10
hxuzuma2                ??????????      YYYAYYYYTT      ??????????      YYYYYYYYWY      10
ssggwwhh                WWWWWWWWWW      WWWWWWWWTT      WWWWWWWWWW      AWW****WWT      10
乱醒                    ??????????      AWWWWTTTTT      ??????????      WWWWWWWWWW      10
乱醒2号                 ??????????      AWWWWTTTTT      ??????????      WWWWWWWWWW      10
弱死我了                WWWWWWWWWW      AWWWWWWWTT      ??????????      ??????????      10
adventure               WWWWWWWWWW      AWWWWTWWTT      ??????????      ??????????      10
BW                      WWWWWTTWTT      AWWWTTTTTT      ??????????      WWWWWWWWWW      10
ly16                    ??????????      AWWWWWWWTT      ??????????      ??????????      10
ssggwwhh (1)            WWWWWWWWWW      WWWWWWWWTT      WWWWWWWWWW      AWW****WWT      10
WeiTony                 WWWWBWBBBB      ??????????      ??????????      ATWWWTWTWT      10
windyvov                ??????????      AWWWWWWWTT      ———-      WWWWWWWWWW      10
lijian                  WWWATTTTTT      ??????????      ??????????      WWWWWWWWWW      10
BillWSY                 MMMMMMMMMM      RRRRRRRRRR      ??????????      ??????????      0
CAO                     ??????????      YYYYYYYYYY      ??????????      ??????????      0
coycooper               YYYYYYYYYY      YYYYYYYYYY      YYYYYYYYYY      YYYYYYYYYY      0
coycooper (1)           YYYYYYYYYY      YYYYYYYYYY      YYYYYYYYYY      YYYYYYYYYY      0
dkz                     ??????????      ??????????      YYYYYYYYYY      ??????????      0
hraikkonen              ??????????      ———-      MMMMMMMMMM      ??????????      0
jht                     ??????????      YYYYYYYYYY      ??????????      ??????????      0
Leser                   ??????????      ———-      ??????????      ??????????      0
matrix                  ??????????      ??????????      ??????????      ??????????      0
matrix (1)              ??????????      ??????????      ??????????      ??????????      0
MissingInTheSeason      WWWWWWWWWW      ———-      ———-      TTTTTTTTTT      0
yy123                   WWWWWWWWTT      WWWWWWWWTT      ??????????      ??????????      0
zjfhzdy                 ??????????      ———-      WWWWWWWWWW      ??????????      0
麦迪迷                  ??????????      YYYYYYTTTT      ??????????      ??????????      0
                                                
"R=无法运行
T=超时
M=超内存
Y=运行时错误
B=崩溃
A=正确
W=错误的答案
P=得部分分
*=程序无输出
[=缺标准输入
]=无标准输出
?=无程序
^=自定义评测错误
-=编译错误"

2007年10月5日，我举办了一次NOIp模拟赛。现在比赛已经顺利结束了，以下是这次比赛的题目

题目一览

题目名称    Matrix67的情书（二）  送给MM的生日礼物   流言的传播         表白机器人
题目类型    传统                  传统               传统               传统
源文件名称  lovelttr.(pas/c/cpp)  gift.(pas/c/cpp)   rumor.(pas/c/cpp)  robot.(pas/c/cpp)
输入文件名  lovelttr.in           gift.in            rumor.in           robot.in
输出文件名  lovelttr.out          gift.out           rumor.out          robot.out
时间限制    1秒                   1秒                1秒                1秒
内存限制    64M                   64M                64M                64M
测试点      10个                  10个               10个               10个
分值        100分                 100分              100分              100分

Problem 1: lovelttr
Matrix67的情书（二）

问题描述
    28是一个很特别的数字。它是一个完全数，是一个三角形数，是前五个素数的和。天上有28星宿，人有28颗牙齿；土星绕太阳公转一周需要28年，从一只猴子的释放到整座城市的沦陷只需28天。当然，Matrix67偏爱这个数字是有原因的：这是一个关心MM身体和计算安全期都必须用到的数字。总之，Matrix67非常喜欢数字28，他甚至希望数字28能够出现在他给MM写的情书里。
    Matrix67的情书只由数字、大小写字母、空格、换行符和各种英文半角标点符号组成。除去所有其它的字符，仅保留文本中的数字和字母，则整个情书可以看作是一个36进制数。比如，句子“I Love you!”可以转化为1457771337246，因为(ILOVEYOU)36 = (1457771337246)10。Matrix67希望从情书中截取一个或若干个连续的句子，使得它所对应的十进制数能够被28整除。Matrix67希望知道他的情书中有多少个文本片段满足这样的条件。
    我们认为，只有句号、感叹号、问号三种符号才是句子结束的标志（当然整篇文章的结束也标志着最后一句话结束，即使文章最末尾没有任何标点符号）。Matrix67的情书里保证没有不能表示任何数字的“空句子”，即任意两个句子结束标志之间至少会出现一个数字或字母。

输入数据
    输入数据是一篇合法的英文文章，包括英文大小写字母、数字、空格、回车和半角的标点符号。

输出数据
    输出满足要求的文本片段个数。一个满足要求的文本片段是指一个或若干个连续的句子，将它们当作36进制后得到的数可以被28整除。

样例输入

I WILL SHOW YOU

Yes, I am still amazed that I have you. It's still hard to understand how you chose me. How after just one short conversation you knew I was meant for you. But now I know the truth of your conviction. I've never been with someone who suited me so perfectly. You seduced me with your sexy body and strong spirit, and you've kept me with your tender heart. I know you that I can't have you completely and maybe not even for much longer. But I'm still happy. A part of you has become part of me and that is enough.

You'll laugh when I say this, but I dream about you every night. Probably because I can't see you often enough. But when I'm awake I know that you are the furthest thing from a dream. Sometimes I imagine that you are built from solid rock: a moving statue and an indestructible human being. You absolutely contain yourself and then again much more than yourself. Your confidence is consuming and your perspective is huge. You have no place in your life for jealousy or complaints. My friends seem so small in comparison, with their problems always spilling over onto everyone else.

I want you to know how much you've opened my eyes and helped me truly see myself. Until now, my life has been an undecided back-and-forth, and now I know that I've wasted too much time. But now my direction seems clear, and I have confidence in my future. The past doesn't seem to matter anymore. You've made me see possibilities I would never have imagined before.

Yes, I want to please you. But it's through pleasing you that I'll become a better and stronger person. There is nothing I want more than to transform myself through you. You challenge me to grow beyond myself and leave my weaker self behind. I will show you how beautiful I can be, and I will show you how brilliant I can become. This way, I know I'll always have your love.

Forever yours,

Matrix67

样例输出
6

数据规模
    对于30%的输入数据，输入文件大小不超过50KB；
    对于100%的输入数据，输入文件大小不超过1MB。

Problem 2: gift
送给MM的生日礼物

问题描述
    10月11日是MM的生日，Matrix67打算自己DIY一些抱枕送给MM。Matrix67手中有一块矩形花布，花布分成了M x N个小格子，有些格子的花色相同，有些格子的花色不同。为了使最终成品更美观，Matrix67希望用于DIY的布匹都是正方形的，并且满足布匹花色上下对称且左右对称。为此，他希望能计算出这块花布里一共包含有多少个上下对称且左右对称的小正方形。
    举例来说，Matrix67手中的花布大小为6 x 4，上面共有5种花色：

ABACDA
DCDEAA
ABABAA
DDCBBA

    则这块布里一共有26个上下对称且左右对称的正方形，其中包括最左上角的3×3正方形、右边4个A组成的2×2正方形，当然还有24个1×1的小正方形。

输入数据
    第一行输入两个用空格隔开的正整数M,N，表示Matrix67手中的格子布分为M行N列。
    以下M行每行N个字符，描述布匹的花色。我们用26个大写字母来区别不同的花色，相同的字母代表相同的花色，不同的字母代表不同的花色。

输出数据
    输出在Matrix67的格子布中切出一块花色左右对称且上下对称的正方形共有多少种方案。

样例输入
4 6
ABACDA
DCDEAA
ABABAA
DDCBBA

样例输出
26

数据规模
    对于30%的数据，M,N<=10；
    对于100%的数据，M,N<=200。

Problem 3: rumor
流言的传播

问题描述
    昨天下午，Matrix67陪MM出去逛街，走累了后去咖啡店歇了歇脚；再后来MM陪Matrix67去了一趟书店，之后两人去电影院看了一场电影。从电影院出来后已经很晚了，考虑到MM的安全问题，Matrix67先送MM回到宿舍，然后自己才回去。第二天Matrix67起床后发现问题严重了：昨天和MM出去玩本来什么都没发生，但现在一些不堪入耳的流言正疯狂传播，很多细节都说得有鼻子有眼的。在澄清事实并抓出元凶的同时，Matrix67希望切断一些流言传播的路径，尽可能减缓流言传播的速度。
    除去Matrix67和他的MM，学校里还有N个人。这N个人形成了M对双向的朋友关系，这些朋友关系连通了所有N个人。不同的朋友间传递消息的速度各不相同。如果A和B是第i对朋友，那么当其中一个人听到流言后，他会在Ti的时间内传给另一个人。现在，Matrix67只知道流言并没有传遍整个学校，但他不知道哪些人已经听说了这个流言。他希望切断尽可能少的朋友关系，使得无论是哪些人已经获知了流言，流言都无法以原来的速度传给一个新的人（即新的得知此流言的人的出现将变得更晚）。换句话说，Matrix67希望找到一个最小的边集E，使得对任意一个不等于全集的点集S，恰好只有一个顶点在S里的边中权值最小的那一条在边集E中。

输入数据
    第一行输入两个用空格隔开的正整数N和M，分别表示学校的人数和朋友关系数。
    以下M行每行有三个用空格隔开的正整数，其中第i行的三个正整数为Ai, Bi, Ti，表示Ai和Bi是第i对朋友，它们之间传递消息需要Ti的时间。输入数据保证0<Ai≠Bi<=N，0<Ti<=2 000 000 000，且对任意i≠j都有Ti≠Tj。

输出数据
    你需要输出你所得到的最小值和具体的方案。
    输出文件的第一行是一个正整数，代表你的最优方案中需要切断的朋友关系数。
    以下若干行每行一个正整数，表示你的方案里需要切断的朋友关系在输入数据中的编号（即你需要切断的是输入数据中给的第几条边）。这些数必须按照增序排列输出。
    如果有多种最优方案，你只需要输出其中一种即可。我们的评测系统会自动判断你的输出数据的正确性。

样例输入
4 4
1 2 2
4 3 4
2 3 3
1 3 1

样例输出
3
1
2
4

样例说明
               (1)
                o
               /
            1 /   2
             /    
(4) o——-o——-o (2)
        4  (3)  3  

    首先，(3)—(4)这条边必须去掉，否则若只有4号同学得知流言，流言将以相同的速度传给下一个人。对于其它三条边，只需要去掉权值较小的两条即可，这样不论获知流言的是哪个（些）人，所有可以继续向外传播流言的边中最小的那一条一定已经被去掉了。可以证明，去掉三条边已经是最优的答案了。

数据规模
    对于30%的数据，N<=10，M<=20；
    对于50%的数据，N<=100，M<=1 000；
    对于100%的数据，N<=10 000，M<=100 000。

Problem 4: robot
表白机器人

问题描述
    永远不要以为Matrix67就是传说中的情圣。很少有人知道，Matrix67竟然不好意思主动向MM表白！为此，Matrix67派出他的表白机器人，帮他完成这一项光荣而艰巨的任务。
    Matrix67和MM所在的地方可以看作是一个封闭的平面空间，里面分成了M x N个房间，某些房间之间可能有墙。Matrix67总在最左下角的那个房间，MM总在最右上角的那个房间。Matrix67需要给它的机器人输入一系列方向指令，控制机器人避开墙壁到达MM所在的位置。如果L表示向左移一格，R表示向右移一格，U表示向上移一格，D表示向下移一格，那么在下图所示的4×4平面地图里，命令序列RURUUR可以让机器人从起点（左下角）到达终点（右上角）。

#—#—#—#—#
|       |     F |
#   #   #   #—#
|       |       |
#   #   #   #—#
|   |           |
#   #   #   #   #
| S             |
#—#—#—#—#

    但问题远远没有这么简单。由于设计上的缺陷，Matrix67的机器人只能记忆K条指令。这就意味着，当机器人的行走路线过长时，指令不一定能完整地输入机器人。这怎么办呢？Matrix67想到一个好办法：如果让机器人反复执行预先给定的K条指令，那么恰当的指令序列也能使机器人到达终点（虽然这样可能会走很多重复的路）。机器人会忽略所有命令它撞墙的指令。也就是说，如果下一个指令对应的方向上是一面墙的话，机器人将跳过该指令。Matrix67希望知道，是否存在一个长度为K的命令序列，若机器人反复执行这段指令，最终会到达MM所在的地方。对于上面给出的例子，当K=4时，RRLU是一个合法的答案。

输入数据
    第一行输入四个用空格隔开的正整数M、N、W和K，表示该平面区域内有M行N列小房间，房间与房间之间共有W面墙，Matrix67需要给机器人输入的指令长度为K。
    以下W行每行四个数Ai, Aj, Bi, Bj，表示第Ai行Aj列的房间与Bi行Bj列的房间之间有一面墙。

输出数据
    你的输出数据应该是一个由L、R、U、D四种字符组成的长度为K的字符串，表示一个合法的指令序列。机器人反复执行这串指令后最终可以到达右上角的房间。
    输入数据保证有唯一解，因此你不用考虑多解或无解的情况。

样例输入
4 4 5 4
1 2 1 3
2 2 2 3
1 4 2 4
2 4 3 4
3 1 3 2

样例输出
RRLU

数据规模
    对于30%的数据，K<=4；
    对于100%的数