屯题

本地

复读机专场

迷路的复读机 [√]

暴力， 或BFS

这天，一个复读机因为复读次数太多导致智商下降，不幸在迷宫中迷路了。
幸好，他得到了一个地图。地图上标明了他现在的位置，和迷宫的目标出口，并且标明了前往迷宫出口的最优路径。

复读机决定按照地图的指示前行。
但这个复读机智商实在是有点低，他真的看不懂地图。他希望你能帮他把地图翻译成简单的指令：向上走U，向下走D，向左走L，向右走R。复读机就会复读你的指令，从而走出这个迷宫。

等等，这个复读机好像中暑了，不如我们……

Input:
    仅有一组数据。
    第一行两个正整数 N，M，代表迷宫的行数和列数。 1 <= N <= 100, 1 <= M <= 100
    下面是这个迷宫。
    . 代表不能走的地方
    # 代表可以走的地方
    s 代表出发点
    t 代表终点

Ouput:
    输出给复读机的指令。指令长度应尽可能短。
    保证从s到t的最短路径唯一。

Sample 1:
    In:
        6 13
        .............
        ..########t..
        ..#..........
        ..#......#s..
        ..########...
        .............
    Out:
        LDLLLLLLLUUURRRRRRRR

数学天才复读机 [√]

暴力，直接检查O(N^2)

这是一个很喜欢研究数学的复读群。群里的每个复读机都有一个自己的编号。禁言复读机的群规则是这样的：如果一个复读机复读了，但如果这个复读机前面有复读机的编号的平方加上他自己的编号的平方是一个完全平方数，复读机就能幸运地免于禁言。

现在，又有一轮刺激的复读开始了！到底复读之后会不会被禁言呢？作为一名数学天才，你肯定知道自己什么时候复读才不会被禁言！

复读机1：我们群主敢日仙人球！
复读机9：我们群主敢日仙人球！
复读机12：我们群主敢日仙人球！
复读机4：我们群主敢日仙人球！
...
复读机N：我们群主敢日仙人球！

Input:
    一组数据。
    第一行一个数字N，N是复读机复读的句子的数量。1 <= N <= 100 
    接下来N行为复读记录，每行是一个复读机编号，代表现在是编号几的复读机在复读。
    接下来一行一个数字Q，代表有Q个询问。 1 <= Q <= 100
    接下来Q行，每行两个数字，第一个数字是当前询问的复读机编号，第二个数字是它想在第几条复读记录之后进行复读。
    复读机编号范围：1 <= id <= 1e9
Output:
    针对每个询问，输出一行"YES"（无引号）表示此时复读很安全，或一行"NO"（无引号）表示此时复读会被禁言。

Sample 1:
    In:
        4
        1
        3
        4
        2
        2
        4 1
        4 2
    Out:
        NO
        YES
Hint:
    样例中，第一次询问是编号为4的复读机是否能在第一条记录之后进行复读，而4的平方加1的平方不是完全平方数，输出NO；第二个询问是编号为4的复读机能否在第二条记录之后进行复读，因为3的平方加4的平方是完全平方数，输出YES。

部分复读机 [√]

暴力，直接检查

复读机老了，老的有点耳背。常常听不全前一个复读机复读的话，只复读了其中的一部分。
现在请你判断一下，复读机是不是复读了前一个复读机说的话的其中一部分。（要求：连续相同的才算，比如hel是hello的部分复读，但hlo和Hel都不是）
每个复读机的发言占一行。

Input:
    一组数据，第一行两个正整数，分别是聊天记录条数N，询问数Q
    接下来N行，每行是一个复读机的发言。
    接下来Q个询问，每个询问占据一行，为一个正整数X，让你判断第X条记录是否是上一条的部分复读。保证 2 <= X <= N.

Output:
    对每个询问输出一行，如果是部分复读输出Yes，否则输出No

Sample 1:
    In:
        6 3
        Hello World
        Hello
        Hel
        hel
        Yjj tql
        tql
        2
        4
        6
    Out:
        Yes
        No
        Yes

复读机暴政

大模拟

复读机太猖狂啦！我们要对复读机实施禁言！还我们的ACM群一个和谐的讨论环境！

禁言规则：

• 完全一致才会被视为复读。为了简化问题，我们用一个正整数来代替这句话，当且仅当两个正整数是相同的，代表两句话是相同的。
• 当且仅当这句话至少被复读超过两次时（也就是连续重复出现了3次）才被视为复读。
• 第$X$个复读的复读机会被禁言，$X$为3的倍数。
• 连续两次领起复读的复读机将会被禁言。
• 打断复读并且没有领起复读的复读机可以获得一次免死金牌，在下一次被禁言时可触发一次免死金牌效果。
• 连续三次在复读时均没被禁言的复读机获得一次免死金牌，在下一次被禁言时可触发一次免死金牌效果。
• 每个复读机在同一时刻至多拥有一块免死金牌，不可叠加多块免死金牌。免死金牌触发后消失。

现在，给出一段聊天记录，让你按照聊天记录出现的先后顺序，输出被禁言的复读机编号。
如果没有复读机被禁言，输出FDJnb

Input:
    第一行两个正整数，分别是复读机编号范围N和记录条数M
    下面M行，每行两个正整数，第一个正整数代表复读机编号，第二个代表这个复读机的话

Output:
    如果有被禁言的复读机，顺序输出这些被禁言的复读机编号。每个编号一行。
    否则如果没有被禁言的复读机输出 FDJnb

Sample 1:
    In:
        7 10
        1 200
        2 200
        1 200
        3 200
        4 200
        5 200
        6 14
        7 33
        5 33
        6 33
    Out:
        1
        5

最多复读次数

暴力，从前往后扫

“区区禁言，怎么能难倒我呢。”失真复读机嘿嘿一笑。
自然选择下的优胜劣汰。只会+1的天真复读机终将被禁言，只有我们这些懂得变通的失真复读机才能活下来。——话不能完全照搬，这是失真复读机一贯的信条。
失真复读法：对想要复读的话进行改造，使其串长和被复读的话一样长，而两句话的汉明距离为1。

现在，给出一段聊天记录，请找出其中最长的连续失真复读次数。

注：汉明距离：两句话中，所有对应数字不同的位置数量

Input:
    仅有一组数据。
    第一行是复读机复读数 N。
    接下来N行，每行都是一句复读机说的话。保证每句话都仅含有0/1两个数字。保证各句话长度相同。

Output:
    仅一个数字，代表最长连续失真复读次数。

Sample 1:
    In:
        13
        10000
        11000
        11100
        10100
        10101
        11111
        11101
        11111
        11111
        11111
        11111
        11111
        11111
    Out:
        5

集训队的日常

詹大爷分零食 [√]

结论题

有一天，集训队要开party。詹大爷受命为大家分零食。为了方便，每个人都有一个编号，从$1$到$N$，并且零食也被打包分为不同的袋，分别标注为$1$号袋，$2$号袋，$3$号袋……$N$号袋。这时，詹大爷被通知每个人都有一样不喜欢吃的零食，并且每个人不喜欢的零食和他自己的号一定不同。这当然难不倒我们聪明的詹大爷，他顺利的完成了零食的分配。给出每个人不喜欢吃的零食，请输出使得每个人都能拿到自己喜欢的零食的方案。多种方案存在时，请输出字典序最小的方案。

Input:
    一组数据，两行。
    第一行是人数和零食数N。2 <= N <= 1000000.
    第二行是N个数，第i个数表示第i个人不喜欢的零食编号。不同编号之间以一个空格相分割。

Output:
    一行数据，分别是第i个人拿到的零食编号。不同编号之间以一个空格相分割。

Sample 1:
    In:
    3
    2 3 2
    Out:
    1 2 3

强哥打电话 [√]

模拟或数学，需要写时分秒转换

众所周知，作为情侣队的一名成员，强哥像超大瓦数的电灯泡一样闪闪发光。本着低调和朴实的原则，强哥尽可能不打扰两个情侣队友的恩爱时光。

但是这一天，强哥因为有重要的事情需要和队友沟通，不得不向队友打电话。可是，两个情侣队友正在煲电话粥。

由于事情很重要，强哥必须打通队友的电话。但强哥不知道他什么时候才能接通队友的电话。他决定每隔一段时间打一次队友的电话，并等待一会儿。如果过了一段时间后队友仍然没有接通，他就挂掉电话继续等待。

现在给出两个情侣队友的通话记录，每段记录有一个起始时间和结束时间。同时，给出强哥开始打电话的时刻和两次拨打电话的时间间隔，以及开始拨打电话后的等待时间，让你求出强哥最早什么时候能成功打通队友的电话。如果不能接通，输出-1。

注意：每段通话记录为左闭右开的区间，也就是说情侣队友挂电话的那一刻落在强哥的等待时间上，强哥是可以打通电话的（参考Sample 3）

Input:
    每个时间数据均以 时：分：秒 的形式给出，为正常的24小时表示法。（最早时刻是00:00:00，最晚时刻是23:59:59）保证时间是合法的。
    第一行一个正整数，为情侣队友的电话粥时间段数量N。 0 <= N <= 20.
    接下来N行，每行两个时间，分别是情侣队友开始电话粥时间和结束电话粥时间。保证时间段没有重合，且给出的时间段顺序是递增的。
    接下来三行，第一行是强哥开始打电话时间。第二行是强哥两次电话拨出时刻之间的时间间隔。第三行为强哥开始拨打电话后的等待时间。只要在等待时间内接通电话，强哥就算打通了电话。

Output:
    一行，以 时：分：秒 的形式输出强哥最早接通电话的时间。若强哥这一整天都不能接通电话，则输出-1。

Sample 1:
    In:
        1
        12:30:00 15:00:00
        12:30:00
        01:00:00
        00:00:10
    Out:
        15:30:00

Sample 2:
    In:
        1
        00:00:00 23:59:59
        01:00:00
        00:10:00
        00:00:10
    Out:
        -1

Sample 3:
    In:
        2
        05:00:00 06:00:00
        09:00:00 09:00:10
        09:00:00
        01:00:00
        00:00:11
    Out:
        09:00:10

欧阳大爷抢AC [√]

简单博弈

这天，欧阳大爷和彭大爷打赌，谁能抢到这道难题的AC。两人约定轮流使用电脑写代码，并且使用时间不超过$T$分钟。已知这道题会在$K$分钟的时候被AC，并且欧阳大爷先使用电脑。欧阳大爷和彭大爷都很聪明，他们都想抢到这道题目的AC。

问题来了，究竟是谁抢到了呢？

Input:
    一行，两个正整数，分别是轮流使用的时间上限T，和这道题被AC的时间K。
    1 <= T <= 1e9
    0 <= K <= 1e9

Output:
    彭大爷抢到AC输出 PDYnb!
    欧阳大爷抢到AC输出 OYDYnb!

Sample 1；
    In:
        3 6
    Out:
        OYDYnb!

Sample 2:
    In:
        3 4
    Out:
        PDYnb!

饺子切水题

暴力O(N!)，或考虑组合数学优化至O(2^N)

饺子是集训队的一名手速选手。只要读懂了题，就能飞快做出来。但是，每道题都有读题时间和做题时间。有时候出题人写的题面太差劲啦，就会导致饺子读不懂题，不得不花费很长的时间读题。

现在饺子在参加一场竞赛，持续时长为$T$。他不知道题面的情况，但我们了解的很清楚，甚至估计出了饺子读每道题和做每道题的时间。因为时长是有限的，所以饺子不一定切的完所有的题。那么让我们预测一下，在规定时间内，饺子做出的题数的期望是多少呢？假设饺子开题是随机且等概率的，并且做完一道题后立马随机并等概率地开下一道题。

Input:
    一组数据。
    第一行两个整数，是题数N和竞赛时长T
    下面N行每行两个整数，分别是饺子切这道题的读题时间和做题时间

Output:
    饺子总共做出的题数的期望。结果四舍五入，保留六位小数。

Sample 1:
    In:
        5 100
        1 1
        1 1
        1 1
        1 1
        1 1
    Out:
        5.000000

秦皇炒饭真好吃 [√]

熊大爷是个很喜欢点外卖的肥宅选手。他非常喜欢吃秦皇炒饭。这家秦皇炒饭最大的好处就是可以随意点想要在炒饭中加入什么配菜，比如zs，zxy，mzy，都是非常好的也非常有营养的配料。

“将zxy裹上蛋液，放入金黄的油中，隔壁小孩都馋哭了……”——秦皇炒饭宣传词。

现在，熊大爷突然发现他支付宝只剩了$N$元，于是他很不幸只能点$N$元以内的外卖了。熊大爷想要尽可能好好搭配配菜，以尽可能获取多的营养。那么问题来了，怎么搭配才能营养最佳？

这家炒饭店的规矩是这样的：
1. 当价格小于$A$元时，原价；
2. 当价格大于等于$A$元但小于$B$元时，所购炒饭价格打九折；
3. 当价格大于等于$B$元时，所购炒饭价格打八五折。
4. 米饭基础价格$X$元，有$N$种可选配菜，每个配菜$Y_i$元，营养值$V_i$。
5. 只能选不超过4种配菜。米饭必点，不点米饭不配送。

Input:
    单组数据。
    第一行是四个正整数，分别代表熊大爷的钱数N(0 <= N <= 1e9)，配菜种数K(0 <= K <= 30)，炒饭打折价格线A和B(0 <= A < B <= 1e9)。
    第二行是米饭的价格X和米饭的营养价值Y。(0 <= X, Y <= 1e9)
    接下来K行，每行两个正整数，第一个是配菜的价格price(0 <= price <= 1e9)，第二个是配菜的营养值value(0 <= value <= 1e9)。
Output:
    每组数据输出一行，即熊大爷能够获得的最大营养值。

Sample 1:
    In:
        10 3 10 11
        0 1
        3 6
        3 6
        5 6
    Out:
        19

集训队的姐姐

姐姐排座位

高考难度组合数学题，插空法

这一天，集训队的姐姐们在聚餐。他们聚餐的是一个长条状的桌子。但是姐姐们有一个特别的习惯，她们希望两个姐姐之间要至少间隔1个空座位，这样坐起来才比较舒服。

她们邀请你来计算一下可能的方案数。如果两个方案中至少存在一个姐姐坐了不同的位置，那么这两种方案就被视为不同的。

Input:
只有一行数据，该行上有N K，代表这个桌子有N个座位，姐姐有K个。 1 <= N <= 40, 1<= K <= 20

Output:
一行，可能的方案数。

Sample 1
    In:
        1 1
    Out:
        1

Sample 2:
    In:
        4 2
    Out:
        6

Sample 3:
    In:
        1 9
    Out:
        0

姐姐调参数

暴力

姐姐有句名言：“数学题，找规律嘛。+1不行就-1，-1不行就再+1。”
现在，姐姐打出了一道数学题的表。她开始运用加一减一大法进行调试，试图凑出答案来。
你能帮姐姐判断一下能否用加一减一大法调试出来吗？
如果能，请输出任意一种调试后得到的满足条件的公式。如果不能，输出sad。

Input:
    一组数据。
    第一行是未知数个数N，和打出的表的数量K
    接下来K行，每行N + 1个数，前N个数代表这N个变量的初始值，最后一个数代表这N个数的预期乘积

Output:
    一行，N个数，给出每个数应该在原来的基础上+1/0/-1中的哪一个
    输入保证解唯一

Sample 1:
    In:
        1 3
        5 6
        4 5
        2 3
    Out:
        1

Sample 2:
    In:
        2 3
        3 4 2 20
        4 5 2 36
        5 7 1 32
    Out:
        -1 1 0

姐姐买彩票

线代，高斯消元

姐姐是具有锦鲤体质的人。常常是有什么愿望就一定能实现。
这天，姐姐突然想买彩票。于是她就买了一张彩票。zsq听说了这回事，就向姐姐软磨硬泡，想知道姐姐买的彩票到底是多少，赶紧也去买一张蹭蹭姐姐的运气。
姐姐想了想，给了zsq一组方程，告诉zsq解出方程组的解就可以得到密码了。
“只有聪明的人，才能才出来密码哟。”说完，姐姐挥一挥衣袖，不带走一片云彩。

zsq看着密码，陷入了沉思。他智商不够用，不能够从方程中推出原本的号码。
现在，zsq找到了你，希望你能够帮他找到号码。他承诺万一中奖了就分给你一半。
你能不能找出号码呢？

Input:
    一组数据。
    第一行是彩票号码数N。
    下面N行是方程。每行N+1个数字。
    保证有符合题意的方程的解。

Output:
    一行，输出彩票的号码。两个号码之间以空格相分割。

Sample 1:
    In:
        3
        1 0 0 9
        0 0 1 4
        0 1 0 5
    Out:
        9 5 4

Sample 2:
    In:
        4
        2 2 2 2 20 
        1 3 2 3 25
        6 5 4 1 32
        8 3 9 4 57
    Out:
        1 2 3 4

姐姐打羽毛球 [√]

简单公式

姐姐今天要去打羽毛球。姐姐有着非常强的预感，她知道自己这次挥拍出去后球会打到哪个地方。
作为姐姐的对手，你必须能够判断好姐姐的球将会击到哪里。你从姐姐的挥拍的霎那看出了球的初速度和方向——
说时迟，那时快。请你迅速给出姐姐的球的落点。
为了简化问题，我们采取一个二维平面来模拟羽毛球场，并且假设姐姐的位置处于(0，0)，击球点恒为（0，2）。击球的水平速度和竖直速度也将分别给出，重力加速度采取 $g = 9.8 m / s^2$。现在请你输出姐姐击球的落点横坐标。

Input:
    一组数据，两个浮点数，分别是姐姐击球后球的初始水平速度Vx和初始竖直速度Vy。均保留六位小数。且有 -1000.0 <= Vx, Vy <= 1000.0
    注意： Vy取竖直向上的速度方向为正，Vx取水平向前的速度方向为正。

Output:
    输出一行表示落点横坐标。四舍五入，保留六位小数。

Sample 1:
    In:
        0.000000 1.000000
    Out:
        0.000000

Sample 2:
    In：
        2.000000 1.000000
    Out:
        1.498030

最喜欢的姐姐

从前往后暴力扫一遍

众所周知，集训队有很多姐姐。但每个姐姐都有自己独特的个性，因此他们有着不同的魅力值$X_i$。zxy是一个单纯的孩子，特别喜欢集训队的姐姐。

“我的意中人是个盖世英雄，有一天会驾着七彩祥云前来迎接我。”
“那茫茫人海中，究竟谁是我的意中人啊。”
沉浸在幻想中的zxy实在是太害羞啦，他希望你能帮他找出他最喜欢的姐姐究竟是谁。他偷偷告诉你他最喜欢魅力值为K的姐姐。如果没有的话，尽可能接近K就好啦。

注： 若存在多个满足条件的姐姐，输出名字字典序较小的姐姐。

Input:  
    多组数据
    第一行是数据组数T, 1 <= T <= 1000
    每组数据第一行N K，代表集训队姐姐有N个，zxy最喜欢魅力值为K的姐姐， 1 <= N <= 1000, 1 <= K <= 1e9
    之后N行每行一个字符串S和一个数值X，代表姐姐的名字和这个姐姐的魅力值。S长度 <= 100，1 <= X <= 1e9

Output:
    每组数据输出一行，即这个姐姐的名字。

Sample 1:
    In:
        1
        3 60
        XiongZiLiang 60
        WangXiao 50
        SongWenQi 90
    Out:
        XiongZiLiang

Sample 2:
    In:
        1
        3 200
        XiaoJianXiong 60
        WangXinYu 50
        HuangJinFa 90
    Out:
        HuangJinFa