火车迷

时间限制：3000MS
内存限制：589824KB
题目描述：
小美是一个火车迷，最近她在观察家附近火车站的火车驶入和驶出情况，发现火车驶入和驶出的顺序并不一致。经过小美调查发现，原来这个火车站里面有一个类似栈的结构，如下图所示：

例如可能1号火车驶入了火车站中的休息区s，在驶出之前2号火车驶入了。那么在这种情况下，1号火车需要等待2号火车倒车出去后才能出去（显然被后面驶入的2号火车挡住了，这个休息区s只有一个出入口）。
出于好奇，小美统计了近些天的火车驶入驶出情况，开始统计和结束统计时休息区s中均是空的。由于中途疏忽，小美觉得自己好像弄错了几个驶入驶出顺序，想请你帮她验证一下。值得注意的是，小美虽然可能弄错了顺序，但对火车的记录是不重不漏的。
形式化地来形容休息区s,我们视其为一个容量无限大的空间，假设两列火车i和j同时处于休息区s中，驶入时刻T_in满足T_in(i) < T_in(j)，则驶出时间T_out(i) > T_out(j)，即,先进后出。

输入描述：
第一行一个整数T表示数据组数
对每组测试而言：
第一行一个整数n，表示观察到的火车数量
第二行n个整数，x_1,x_2,…,x_n，表示小美记录的火车驶入休息区s的顺序
第三行n个整数，y_1,y_2,…,y_n，表示小美记录的火车驶出休息区s的顺序
对每一组数据输出一行：如果小美记录的驶入和驶出顺序无法被满足则输出“NO”，否则输出“YES”。

用例一：

1
2
3
4
5
6
7
8
9
10
3
3
1 2 3
1 2 3
3
1 2 3
3 2 1
3
1 2 3
3 1 2

输出：

1
2
3
Yes
Yes
No

提示：
对第一组数据，每辆火车刚驶入便立刻驶出即可满足此记录
对第二组数据：
[ <- 休息区出口 （空 初始状态）
[ 1 <- 休息区出口 （1号驶入）
[ 1 2 <- 休息区出口 （2号驶入）
[ 1 2 3 <- 休息区出口 （3号驶入）
[ 1 2 <- 休息区出口 （3号驶出）
[ 1 <- 休息区出口 （2号驶出）
[ <- 休息区出口 （1号驶出）
记录可以被此种方案满足。
对第三组数据：
[ <- 休息区出口 （空 初始状态）
[ 1 <- 休息区出口 （1号驶入）
[ 1 2 <- 休息区出口 （2号驶入）
[ 1 2 3 <- 休息区出口 （3号驶入）
[ 1 2 <- 休息区出口 （3号驶出）
发现1号被2号堵住，无法先于2号驶出。
可以证明，亦不存在其他驶入驶出方案使得第三组数据满足要求。

代码 (AC 100%)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def match_input_output(input, output):
    stack = []
    i = 0
    for o in output:
        if stack and stack[-1] == o:
            stack.pop()
        else:
            while i < len(input) and input[i] != o:
                stack.append(input[i])
                i += 1
            if i == len(input):
                return False
            i += 1
    return not stack
data_sets = int(input())
while True:
    try:
        trains = int(input())
        in_seq = [int(x) for x in input().split()]
        out_seq= [int(x) for x in input().split()]
        if match_input_output(in_seq, out_seq):
            print('Yes')
        else:
            print('No')
    except:
        break

分糖

时间限制：3000MS
内存限制：589824KB
题目描述：
小美因乐于助人的突出表现获得了老师的嘉奖，老师允许小美从一堆n个编号分别为1,2,…,n的糖果中选择任意多个糖果作为简历（每种编号的糖果各一个），但为了防止小美一次吃太多糖果有害身体健康，老师设定了一个限制：如果选择了编号为i的糖果，那么就不能选择编号为i-1,i-2,i+1,i+2的四个糖果了。在小美看来，每个糖果都有一个对应的美味值，小美想让她选出的糖果的美味值之和最大！作为小美的好朋友，请你帮帮她。

输入描述：
第一行一个整数n，表示糖果数量
第二行n个整数a_1,a_2,…,a_n，其中a_i表示编号为i的糖果的美味值
1 <= n <= 50000, 1 <= a_i <= 10000
输出描述：
输出一行一个数，表示小美能获得的糖果美味值之和的最大值

样例输入：

1
2
7
3 1 2 7 10 2 4

样例输出：

1
14

提示：
最优的方案是选择编号为1,4,7的糖果。
如果选了编号为5的美味值为10的那颗糖果，最多能获得的美味值仅为13，不如上述方案优。

代码 (AC 63%, 答案错误)

1
2
3
4
5
6
7
8
9
10
11
12
def max_candy(n, a):
    if n <= 3:
        return a[n-1]
    dp = [0] * n
    dp[0], dp[1], dp[2] = a[0], a[1], a[2]
    for i in range(3, n):
        dp[i] = max(dp[i-1], dp[i-2], dp[i-3]+ a[i])
    return dp[-1]
candies = int(input())
candy_happiness = [int(x) for x in input().split()]

print(max_candy(candies, candy_happiness))

春游

时间限制：3000MS
内存限制：589824KB
题目描述：
小美明天要去春游了。她非常喜欢吃巧克力，希望了个够带尽可能多的巧克力在春游的路上吃。她现在有n个巧克力，很巧的是她所有的巧克力都是厚度一样的正方形的巧克力板，这n个巧克力板的边长分别为a_1,a_2,…,a_n。因为都是厚度一致的正方形巧克力板，我们认为第i个巧克力的重量为a_i^2。小美现在准备挑选一个合适大小的包来装尽可能多的巧克力板，她十分需要你的帮助来在明天之前准备完成，请你帮帮她。

输入描述：
第一行两个整数n和m, 表示小美的巧克力数量和小美的询问数量。
第二行n个整数a_1,a_2,…,a_n，表示n块正方形巧克力板的边长。注意你不能将巧克力板进行拆分。
第三行m个整数q_1,q_2,…,q_m，第i个整数q_i表示询问：如果小美选择一个能装q_i重量的包，最多能装多少块巧克力
1 <= n,m <= 50000, 1 <= a_i <= 10 ** 4, 1 <= q_i <= 10 ** 18

输出描述：
输出一行m个整数，分别表示每次询问的答案

样例输入：

1
2
3
5 5
1 2 2 4 5
1 3 7 9 15

样例输出：

1
1 1 2 3 3

提示：
包最大重量为1：能装1^2
包最大重量为3，也最多只能装1^2重量（如果添加2^2就超载了）
包最大重量为7，能装1^2+2^2
包最大重量为9，能装1^2+2^2+2^2(因为有两块巧克力板边长为2)
包最大重量为15，能装1^2+2^2+2^2+4^2（如果添加了4^2就超载了）

代码 (AC 81%, 时间超限)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n,m = [int(x) for x in input().split()]
chocos = [int(x) for x in input().split()]
bags = [int(x) for x in input().split()]

def max_choco(chocos, max_weight):
    chocos.sort()
    count = 0
    for choco in chocos:
        if max_weight >= choco ** 2:
            max_weight -= choco ** 2
            count += 1
        else:
            break
    return count

res = []
for bag in bags:
    res.append(str(max_choco(chocos, bag)))
print(' '.join(res))

解释器

时间限制：3000MS
内存限制：589824KB
题目描述：
小美因为自己差劲的表达能力而苦恼，小美想制作一个解释器，这样她可以在无法表达的情况下让解释器帮她解释。好巧不巧小美翻开了编译原理的书，找到了解释器的制作方法，她决定先制作一个书上习题中描述的小小解释器试试。
小美需要读入一行字符串，其格式为”key_1=val_1;key_2=val_2;…;key_n-1=val_n-1;key_n=val_n”（不包括引号）这样的n对key.value对，其中key_i和val_i为第i对key,value对，且均为仅包含大小写字母、数字与斜杠的非空字符串。例如对于字符串”SHELL=/bin/bash;HOME=/home/xiaomei;LOGNAME=xiaomei;”那么其中包含三对key,value对，以(key,value)形式展示，分别以（SHELL，/bin/bash）,（HOME，/home/xiaomei) , (LOGNAME, xiaomei）.
接下来，小美的解释器需要接受q次询问，每次询问给出一个仅包含大小写字母、数字和斜杠的非空字符串，如果存在某种key, value对的key值相同，那么输出对应的value；如果存在多对key,value对的key值与之相同，那么输出其中编号大的，也即最后一次value值；如果一对也不存在，那么输出EMPTY。

输入描述：
第一行一个字符串S，满足题中所述格式。
接下来一个整数q,表示有q个询问。
接下来q行，每行一个仅包含大小写英文字母、数字和斜杠的非空字符串，分别为S_1,S_2,…,S_q, 以此表示q此询问。令|S|表示字符串S的长度。
1 <= |S| <= 50000, 0 <= |Si| <= |S|, 1<= q <= 300, S中至少包含一对key,value对。

输出描述：
输出q行，每行一个字符串表示答案。

样例输入：

1
2
3
4
5
6
LOGNAME=default;SHELL=/bin/bash;HOME=/home/xiaomei;LOGNAME=xiaomei;
4
SHELL
HOME
LOGNAME
logname

样例输出：

1
2
3
4
/bin/bash
/home/xiaomei
xiaomei
EMPTY

提示：
第3个询问有两对满足，分别是第1对和第4对，选择编号大的（也就是后者），为xiaomei而不是default。
第4个询问不存在满足的，输出EMPTY。

糖果盛宴

时间限制：3000MS
内存限制：589824KB
题目描述：
小美特别爱吃糖果。小美家楼下正好有一个糖果专卖店，每天供应不同种类的糖果。小美预先拿到了糖果专卖店接下来n天的进货计划表，并针对每天的糖果种类标注好了对小美而言的美味值。小美当然想每天都能去买糖果吃，不过由于零花钱限制（小美零花钱并不多！）以及健康考虑，小美决定原则上如果今天吃了，那么明天就不能吃。但小美认为凡事都有例外，所以她给了自己k次机会，在昨天已经吃了糖果的情况下，今天仍然连续吃糖果！简单来说，小美每天只能吃一次糖果，原则上如果昨天吃了糖果那么今天就不能吃，但有最多k次机会打破这一原则。
小美不想浪费每次吃糖果的机会，所以请你帮帮她规划一下她的吃糖果计划，使得她能吃到的糖果的美味值最大。

输入描述：
第一行两个整数n和k, 表示拿到的进货计划表的天数和最多打破原则的次数。
第二行n个整数a_1,a_2,…,a_n, 其中a_i表示接下来第i天糖果专卖店的糖果的美味值。
1 <= n <= 2000, 1 <= k <= 1000, 1 <= a_i <= 10000

输出描述：
输出一行一个数，表示小美能吃到的糖果美味值之和最大值。

样例输入：

1
2
7 1
1 2 3 4 5 6 7

样例输出：

1
19

提示：
最优的方案是选择第2、4、6天吃糖果，并在第7天打破一次原则也吃糖果（因为第6天已经吃过，原则上不能继续吃，需要使用一次打破原则的机会）。