CodeM 2017美团编程大赛初赛A轮
时长:180分钟 总分:100分
104浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 6 |
1.
倒水
有一个大水缸，里面水的温度为T单位，体积为C升。另有n杯水（假设每个杯子的容量是无限的），每杯水的温度为t[i]单位，体积为c[i]升。
现在要把大水缸的水倒入n杯水中，使得n杯水的温度相同，请问这可能吗？并求出可行的最高温度，保留4位小数。
注意：一杯温度为t1单位、体积为c1升的水与另一杯温度为t2单位、体积为c2升的水混合后，温度变为(t1*c1+t2*c2)/(c1+c2)，体积变为c1+c2。 输入描述： 第一行一个整数n, 1 &le n &le 10^5 第二行两个整数T，C,其中0 &le T &le 10^4, 0 &le C &le 10^9 接下来n行每行两个整数t[i]，c[i] 0 &le t[i], c[i] &le 10^4输入样例： 3 10 2 20 1 25 1 30 1 输出描述： 如果非法，输出“Impossible”（不带引号)否则第一行输出“Possible"（不带引号），第二行输出一个保留4位小数的实数表示答案。 样例解释：往第二杯水中倒0.5升水 往第三杯水中到1升水 三杯水的温度都变成了20输出样例 Possible 20.0000
现在要把大水缸的水倒入n杯水中，使得n杯水的温度相同，请问这可能吗？并求出可行的最高温度，保留4位小数。
注意：一杯温度为t1单位、体积为c1升的水与另一杯温度为t2单位、体积为c2升的水混合后，温度变为(t1*c1+t2*c2)/(c1+c2)，体积变为c1+c2。 输入描述： 第一行一个整数n, 1 &le n &le 10^5 第二行两个整数T，C,其中0 &le T &le 10^4, 0 &le C &le 10^9 接下来n行每行两个整数t[i]，c[i] 0 &le t[i], c[i] &le 10^4输入样例： 3 10 2 20 1 25 1 30 1 输出描述： 如果非法，输出“Impossible”（不带引号)否则第一行输出“Possible"（不带引号），第二行输出一个保留4位小数的实数表示答案。 样例解释：往第二杯水中倒0.5升水 往第三杯水中到1升水 三杯水的温度都变成了20输出样例 Possible 20.0000
2.
二分图染色(弱化版)
给定一个完全二分图，图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿色，并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。
计算所有满足条件的染色的方案数，并对10^9+7取模。
(ps：本题数据量与实际比赛中数据量相比，少了一些)
输入描述：
二分图单边的顶点数目n(n ≤ 10^7)输入样例：
2 输出描述：
输出一个整数,即所求的答案。输出样例
35
3.
合并回文子串
输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可 输入描述： 第一行一个整数T(T ≤ 50)。 接下来2T行，每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)，A,B的字符集为全体小写字母。输入样例： 2 aa bb a aaaabcaa 输出描述： 对于每组数据输出一行一个整数表示价值最大的C的价值。输出样例 4 5
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可 输入描述： 第一行一个整数T(T ≤ 50)。 接下来2T行，每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)，A,B的字符集为全体小写字母。输入样例： 2 aa bb a aaaabcaa 输出描述： 对于每组数据输出一行一个整数表示价值最大的C的价值。输出样例 4 5
4.
身体训练
美团外卖的配送员用变速跑的方式进行身体训练。
他们训练的方式是：n个人排成一列跑步，前后两人之间相隔 u 米，每个人正常速度均为 v 米/秒。
当某个配送员排在最后的时候，他需要以当时自己的最高速度往前跑，直到超过排头的人 u 米，然后降回到原始速度 v 米/秒。每个人最初的最高速度为c[i] 米/秒，每轮衰减d[i] 米/秒，也就是说，如果i是第j个跑的，那么他的速度就是c[i]-(j-1)*d[i] 米/秒。
n个人初始以随机的顺序排列，每种顺序的概率完全相等，跑完一轮（每个人都追到排头一次，序列恢复原样）的期望需要的时间是多少？ 输入描述： 第一行整数n（<=1000）, 实数v(<=100) , 实数u(<=10) 第二行n个实数每个人的速度c[i](<=50000) 第三行n个实数值每个人衰减量d[i](<=10) 输入数据保证每个人的速度不会衰减到<=v输入样例： 10 37.618 0.422 72.865 126.767 202.680 106.102 99.516 134.418 167.952 173.646 120.210 136.571 2.941 3.664 7.363 4.161 0.246 8.046 5.521 7.473 7.178 5.649 输出描述： 答案保留3位小数。输出样例 0.815
他们训练的方式是：n个人排成一列跑步，前后两人之间相隔 u 米，每个人正常速度均为 v 米/秒。
当某个配送员排在最后的时候，他需要以当时自己的最高速度往前跑，直到超过排头的人 u 米，然后降回到原始速度 v 米/秒。每个人最初的最高速度为c[i] 米/秒，每轮衰减d[i] 米/秒，也就是说，如果i是第j个跑的，那么他的速度就是c[i]-(j-1)*d[i] 米/秒。
n个人初始以随机的顺序排列，每种顺序的概率完全相等，跑完一轮（每个人都追到排头一次，序列恢复原样）的期望需要的时间是多少？ 输入描述： 第一行整数n（<=1000）, 实数v(<=100) , 实数u(<=10) 第二行n个实数每个人的速度c[i](<=50000) 第三行n个实数值每个人衰减量d[i](<=10) 输入数据保证每个人的速度不会衰减到<=v输入样例： 10 37.618 0.422 72.865 126.767 202.680 106.102 99.516 134.418 167.952 173.646 120.210 136.571 2.941 3.664 7.363 4.161 0.246 8.046 5.521 7.473 7.178 5.649 输出描述： 答案保留3位小数。输出样例 0.815
5.
数列互质
给出一个长度为 n 的数列 { a[1] , a[2] , a[3] , ... , a[n] }，以及 m 组询问 ( l[i] , r[i]
, k[i])。
求数列下标区间在 [ l[i] , r[i] ] 中有多少数在该区间中的出现次数与 k[i] 互质（最大公约数为1）。 输入描述： 第一行，两个正整数 n , m (1 &le n, m &le 50000)。 第二行，n 个正整数 a[i] (1 &le a[i] &le n)描述这个数列。 接下来 m 行，每行三个正整数 l[i] , r[i] , k[i] (1 &le l[i] &le r[i] &le n, 1 &le k[i] &le n)，描述一次询问。输入样例： 10 5 1 1 1 1 1 2 2 2 2 2 4 7 2 4 7 3 4 8 2 4 8 3 3 8 3 输出描述： 输出 m 行，即每次询问的答案。输出样例 0 2 1 1 0
求数列下标区间在 [ l[i] , r[i] ] 中有多少数在该区间中的出现次数与 k[i] 互质（最大公约数为1）。 输入描述： 第一行，两个正整数 n , m (1 &le n, m &le 50000)。 第二行，n 个正整数 a[i] (1 &le a[i] &le n)描述这个数列。 接下来 m 行，每行三个正整数 l[i] , r[i] , k[i] (1 &le l[i] &le r[i] &le n, 1 &le k[i] &le n)，描述一次询问。输入样例： 10 5 1 1 1 1 1 2 2 2 2 2 4 7 2 4 7 3 4 8 2 4 8 3 3 8 3 输出描述： 输出 m 行，即每次询问的答案。输出样例 0 2 1 1 0
6.
最长树链
树链是指树里的一条路径。美团外卖的形象代言人袋鼠先生最近在研究一个特殊的最长树链问题。现在树中的每个点都有一个正整数值，他想在树中找出最长的树链，使得这条树链上所有对应点的值的最大公约数大于1。请求出这条树链的长度。
输入描述：
第1行：整数n（1 &le n &le 100000），表示点的个数。
第2~n行：每行两个整数x，y表示xy之间有边，数据保证给出的是一棵树。
第n+1行：n个整数，依次表示点1~n对应的权值（1 &le 权值 &le 1,000,000,000）。输入样例：
4
1 2
1 3
2 4
6 4 5 2
输出描述：
满足最长路径的长度输出样例
3
