腾讯笔试

1.字典序最小

牛牛有个无环的单链表， 牛可以不停的旋转这个链表，比如链表: 1->2-> 3->4
经过旋转后可以变成以下4种链表:
4->1->2-> 3
3->4-> 1-> 2
2->3->4-> 1
1->2->3->4

牛牛想找到一个旋转的链表，它表示序列的字典序最小。

我们定义序列{a的字典序小于序列{b}:存在一个位置， 满足对于所有la<bj

个例子代表的字典序最小的就是1->2->3->4.
示例1输入输出示例仅供调试，后台判题数据般不包含示例
输入
{2,2,5,2,2}
输出
{2,2,2,2,5}
说明

序列(2,2,2,2,5)的字字典序是最小的

比如:

序列{a): 2 2 2 2 5

序列{b}:2 2 5 2 2

在第.到第2个位量的时候，a-b3 :在第3个位置的时候，25即aj<bj’即序列(a)<序列{b},返回{2,2,2,2,5}

2.分发广告

牛中是家广告公司的员工，天的工作很固定， 就是将k条新的广告，按照注册用户所设定的时间顺字发放到用户的邮箱。

由于牛牛近期自学了编程的相关知识，他知道，如此重复性的工作，可以交给程序来自动完成。但是，牛牛只自了相关酒法， 并不会如此高级的操作，于是，牛牛将用户信息交给了你，希望你能帮帮他。

牛牛会告诉你，每个用户所设定的时间，如果某用户设定的时间为t那么，这位用户接收第一封广告的时刻为t.接收第二封广告的时刻为2*t,接收第三封广告的时刻为3"t …以此类推。

本题为ACM模式，请通过代码实现题目，过程中的输入输出请自行处理，处理方式请参考题目输入输出描述或左侧例题。

输入描述:

第一行输入两个正整数口，n, k (1<=n<=k<=10^6， 依次代表用户数里，以及今天需要发放的广告数量。

第2到第n+1行，每行一个正整数t((1<=t<=1000)，其中，第1+1 行输入的正整数，代表编号为i的用户，所设定的时间t

输出描述:

输出一共k行，按照发放广告的时间顺序，依次输出用户的编号，特殊的，如果某一个时间，有多个用户可以接收广告，则优先给用户编号小的发放。
示例1输入输出示例仅供调试，后台判置数据般不包金示例
输入
3 3
3
6
9

输出
6

说明

第一位用户的第一.封广告邮件接收时刻为3,第二位用户的第一封广告邮件接收时刻为6,第三位用户的第一封广告邮件接收时刻为9

第一位用户的第二封广告邮件接收时刻为6,第二位用户的第一封广告邮件接收时刻为12, 第三位用户的第一封广告邮件接收时刻为18

第一位用户的第三封广告邮件接收时刻为9，第二位用户的第一封广告邮件接收时刻为18， 第三位用户的第一封广告邮件接收时刻为27

当x=3时，按照时间顺序，第一封广告邮件在时刻3应该发给编号为1的用户，第二封广告邮件在时刻6本来应该同时发放给编号为1和2的用户，但是如果某一个时间，有多个用户可以接收广告，则优先给用户编号小的发放。所以第二封发给1,第三封才发给2

所以发放顺序为1, 1, 2

3.最少扣分

游戏俱乐部，正如其名，是个由数个小游戏构成的俱乐部，当玩家进入俱乐部时，会得到张游戏清单，列举了俱乐部内今日开放的n个小游戏，其中第i个小游戏必须在ti时刻内完成(假设玩家进入俱乐部时为0时刻，开始游玩某游戏时只需要个单位时间即可完成， 不计阅读游戏清单以及俱乐部内路上行走时间)否则，就会扣除wi点荣耀积分。

每天，俱乐部都会向最优顺序选择者授予纪念勋章，所谓的最优顺序，即为:最终扣除的荣耀积分最少的玩家。

牛牛十分想要枚纪念勋章， 但是自己又不擅长毫无目的地安排，所以希望你能始出理论上最少会披扣除多少点荣疆积分，给牛牛个目标

本题为ACM模式，请通过代码实现题目，过程中的输入输出请自行处理，处理方式请参考题目输入输出损述或左创例题。

输入描述:

本题为多组测试数据，第一行输入一个正整数T(1<=T<=100，代表测试数据的数组。对于每组测试数据，第行输入一个正整数n(1<=n<=1000) ，代表今日开放的游戏数量。

第二行输入n个正整数t1, t2, … , tn，依次代表各个游戏的规定完成时间
第三行输入n个正整数w2 w2, …wn(1 <= wi<=100) ，依次代表各个游戏未在规定时间内完成时，需要扣除的荣耀积分点数。

输出描述:

对于每组测试数据，一行输出一个整数代表理论上可以达到的最小的被扣除的荣耀积分点数。

示例1输入输出示例仅供调试，后台判题数据股不包含示例
1
3
3 1 1
3 6 9

输出
6

说明
首先完成游戏3，此时，游戏2未在规定时间内完成，扣除6点荣耀积分:接着，只需要在时刻3之前完成游戏1即可。
这种安排方案，只需要被扣除6点荣耀积分。

4.判断字符串

题目描述
牛牛有独特的判断两个字符串是否相等的方法，他看到了两个长度为n由小写字母构成的字符串a和b.如果两个字符串的长度为奇数的话，就一个字符一个字符比对看是不是相等，若是偶数，可以字符串a等分为a1，a2，字符串b等分为b1，b2，他认为两个字符串是相等的只要a1== b1 && a2b2或者a1b2 && a2==b1满足其中一个即可，注意这里判断等号是递归定义的，参见样例一。现在牛牛想你告诉他这两个字符串是不是相等的。若是输出YES,反之输出NO.

本题为ACM模式，请通过代码实现题目，过程中的输入输出请自行处理，处理方式请参考题目输入输出描述或左侧例题。

输入描述:

第一行为一个t，表示有t组数据。

接下来有2*t行，每两行为长度相等的字符串a,b大1 <=t<=10, 1<=lal, |bI <=10^5

输出描述:

输出为t行，每行表示一个答案。
输入
4
aaba
abaa
aabb
abab
aaabbb
bbbaaa
cba
abc

输出
YES
NO
YES
NO

说明
第一组样例，长度为偶数，所以可以判断aaaa与baab,且ba和ab又都是偶数，又可以比较，bb, aa,所以他们在定义下是相等的，输出YES
第二组样例，长度为偶数，但是aa!=ab,输出NO
第三组样例，长度为偶数，但是划分之后为奇数也相同，aaaa, bbbbbb,所以输出YES第四组样例，长度为奇数，只能逐个比较，不相同，输出NO

5.打地鼠

题目描述

有一个n*m个格子的矩阵mp时不时会冒出一些地鼠。 mp[i][j]表示每过mp[i][j]的时间第i行第j列的格子会冒出一只地鼠。

初始时，时间为0.你在第1行第1列格子处，每秒你必须向上下左右四个方向移动格，不能走出矩阵外。作为个合格的打地鼠玩家，如果这秒你从格子a走到格子b.下一秒你不能从格子b走到格子a.

如果你走到一个格子的时候，这里刚好冒出只地鼠，你就可以打一下地鼠。

你的终点是第n行第m列的格子，给你t秒时间，问你最多打几下地鼠。

最后你必须到达终点，如果第t秒时你不在终点，算作打了0次地鼠。

本题为ACM模式，请通过代码实现题目，过程中的输入输出请自行处理，处理方式请参考题目输入输出描述或左侧例题.

输入描述:

第一行三个整数n,m,t

接下来n行，每行m个整数表示矩阵mp[i[j]。
2 <= n,m <= 10，1<-=t ,mp[i][j] <= 1000

输出描述:
输出一行一个整数表示答案。

示例1输入输出示例仅供调试，后台判题数据一般不包含示例
输入
2 2 6
1 1
1 1

输出
6

说明

一种行走的方案是 (1, 1) -> (1,2) ->(2,2)->(2,1)-> (1,1)-> (1,2) ->(2,2)，每步都可以打一下地鼠。

示例2输入输出示例仅供调试，后台判题数据一般不包含示例
输入
2 2 5
1 1
1 1

输出
0

说明
最后无法走到终点，答案是0。