贝壳找房2021届校招算法卷2

牛牛的杂货铺要新进一种糖，这种糖只能一盒一盒的进货，一盒糖里面有块糖。
已知接下来天中，牛牛在第天需要卖出块糖，同时第天糖的进货价为元/盒。
如果一天中进货的糖没有全部卖出去，可以留到之后继续卖。
现在牛牛想知道自己在达成目标的情况下，最少要在进货糖方面花多少钱。 输入描述： 第一行两个空格分隔的正整数。
第二行个空格分隔的正整数。
第三行个空格分隔的正整数。
含义如题面所述。
输入样例： 3 2 10 1 2 5 1 1000 输出描述： 一行一个正整数代表答案。输出样例 27

 一天牛牛整理旧物时发现了一张家谱（家谱可以看做一棵树）。由于年代久远，家谱已经模糊了，现在只能看见人与人之间有直接关系，但是看不出来直接关系是什么了（就是说现在还能直接看出u与v之间有父子关系，但是看不出来是u是v的父亲还是v是u的父亲了）。牛牛还不知道他们家族的最大祖先（根节点）是谁，这样显然就不知道家谱中任意两个人是什么关系了，但是牛牛的爷爷告诉了牛牛家每个人都有多少个孩子（显然叶子节点的孩子数为0），这样就可以推出人与人之间的关系了。家谱中一共有n个人，编号为1~n。牛牛现在有q次询问，对于每个询问，有两个数u和v。对于每组询问输出一行表示他们之间关系。 输入描述： 第一行一个正整数n分别表示家谱中人数
接下来n-1行每行两个正整数w，r，表示w，r是父子关系（但不知道谁是谁的父亲）（即w，r在家谱上有一条边相连）。
接下来一行有n个整数，第i个数代表标号为i的人的孩子的个数
接下来一行一个正整数q表示询问次数
接下来q行，每行两个正整数u，v

输入样例： 4 3 4 1 2 3 1 2 0 1 0 3 1 2 4 1 2 4 输出描述： 对于每组询问
如果u是v的祖先，输出“ZZZZ”；（引号不输出）
如果v是u的祖先，输出“SSSS”；（引号不输出）
如果u，v互相都不是另一个人的祖先，则输出他们的最近公共祖先的编号
每组询问输出一行
输出样例 ZZZZ SSSS 1

牛牛的吉他老师牛妹告诉他，吉他初学者需要熟练弹奏三个旋律：，即：吉他从下到上一共 根弦，依次编号为 ~ ，然后右手分别用相应的手指按照上述顺序拨动对应的弦。

牛牛为了测试牛妹老师的专业性，特意弹奏了若干段，希望牛妹听完后告诉它，其中包括了几次上述基本旋律。 输入描述： 本题为多组测试数据，第一行输入一个正整数 ，代表测试数据组数。

对于每组测试数据，一行输入一个仅包含数字 ~ 的字符串 ，代表牛牛弹奏的旋律。输入样例： 3 165432313236 632313225323 666653231323 输出描述： 对于每段旋律，一行输出一个整数，代表这段旋律一共包含了多少次基本旋律。输出样例 1 0 1

牛牛非常想要购买某种产品，但是囊中羞涩，无奈之下，只好去工地搬砖。

工地老板规定：搬一车砖，牛牛可以获得 元，一天可以搬 次，但一天的工作不能半途而废，一旦定下了目标，就势必达成。工资日结。

牛牛辛勤劳作了 天之后，来到了超市售卖相关产品的区域，里面一共有 件产品，编号为 ~ ，且已知每件产品的价格，牛牛想知道，他能承担得起的最贵的产品编号以及价格是多少？如果有多种产品价格相同，那么，牛牛会更偏向于编号较小的一个。 输入描述： 本题为多组测试数据，第一行输入一个正整数 ，代表测试数据组数。

对于每组测试数据，第一行输入一个正整数 ，代表产品数量。
第二行按照编号顺序，输入 个正整数 ，分别代表每个产品的价格。
第三行输入一个正整数 ，代表询问次数。
每个询问独立，接下去 行，每行三个正整数 ，分别代表牛牛搬一车砖的工资，一天能搬几次以及一共工作了几天。输入样例： 1 6 3 6 9 66 66 99 2 1 1 1 10 4 2 输出描述： 对于每组询问，一行输出两个正整数，依次代表牛牛购买的产品编号以及其价格。特殊的，如果牛牛不能购买产品，则直接输出 .输出样例 -1 4 66