CodeM 2017美团编程大赛初赛B轮

输入两个字符串a和b，合并成一个串c，属于a或b的字符在c中顺序保持不变。如"ACG"和"UT"可以被组合成"AUCTG"或"ACUGT"等。
我们定义字符串c的价值如下：令n为字符串c的长度，分界线k(1<=k<=n-1)将c分为两个子串u=c[1..k]，v=c[k+1..n]。u、v中字符的任意排列，使得u、v的最长公共前缀最大，这就是分界线k的价值，而所有分界线k价值最大的一个为字符串c的价值。
比如，字符串c=ACGTTTGCAT的价值为5，因为将该串分成两半得到u=ACGTT，V=TGCAT，重新排列后可以使得u=v，即最长公共前缀为5。
你需要求出所有可能的c中价值最大的字符串，输出这个最大价值即可。 输入描述： 第一行一个整数T(T &le 500)。 接下来2T行，每行一个字符串，每两行代表一对字符串a和b（|a|,|b|<=100,000；∑(|a|+|b|)<=500,000），字符串的字符集为{A,C,G,T}。输入样例： 2 ACGT ACGT AACCGGTT ACACAGAT 输出描述： 对于每组数据输出一行，一个整数表示价值最大的c的价值。输出样例 4 7

一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。
你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。 输入描述： 第一行一个整数n (1 &le n &le 10^5) 接下来n-1行，每行一个整数，依次为2号点到n号点父亲的编号。 最后一行n个整数为k[i] (1 &le k[i] &le 10^5) 样例解释: 对节点3操作，导致节点2与节点3变黑 对节点4操作，导致节点4变黑 对节点1操作，导致节点1变黑输入样例： 4 1 2 1 1 2 2 1 输出描述： 一个数表示最少操作次数输出样例 3

美团旅行团队最近打算推出一项新服务，为景区的各个景点规划游览路线，提升游客满意度。其中一个重要的问题是对于一个景区道路网，求出游客的满意度的期望值。基于用户的喜好差异，我们需要对男性游客和女性游客的满意度分别计算。
景区被描述成一张n个点、m条边的无向图（无重边，无自环）。每个点代表一个景点，第i个景点游览需要耗费ci分钟，会让男性游客和女性游客的满意度分别增加h1i和h2i（满意度初始值都为0）。每条边代表一条路，第i条边连接编号为xi,yi的两个景点，从景点xi走到yi和从yi走到xi的时间都是ti分钟。
每个游客在景区中最长可以游览k分钟，最开始会随机的通过不同大门进入到一个景点开始游览，每游览完一个项目，游客会等概率随机选择一个可以从当前景点直达且来得及游览的景点作为下一个游览目标（已经游览过的景点也会因为有各种新活动而让游客再次考虑，所以我们这里不区分景点是否已经游览过）。如果游览完一个景点后，周围没有来得及游览的景点，本次游玩就结束了。
请你分别计算小y和妹子在游玩结束后开心度的期望。 输入描述： 第一行给出三个空格隔开的整数，分别表示n, m, k(0 < n &le 100, 1 * 60 &le k &le 8 * 60) 接下来的n行，每行三个空格隔开的整数，分别表示ci, h1i, h2i (10 &le ci &le 60，0 < h1i, h2i &le 100) 接下来的m行，每行三个空格隔开的整数，分别表示xi, yi, ti (0 < ti &le 15)输入样例： 5 4 60 25 12 83 30 38 90 16 13 70 22 15 63 50 72 18 2 1 7 3 1 7 4 3 1 5 3 10 输出描述： 两个用空格隔开的实数，分表表示小y和妹子开心度的期望，精确到小数点后5位。输出样例 39.20000 114.40000

给定四个正整数a,b,c,k，回答是否存在一个正整数n，使得a*n在k进制表示下的各位的数值之和模b为c。 输入描述： 第一行一个整数T(T <= 5,000)。
接下来T行，每行四个正整数a,b,c,k（1 &le a &le 10^18 2 &le k &le 10^18 0 &le c < b &le 10^18）表示一个询问，所有输入都是十进制的。输入样例： 2 3 9 5 10 7 3 1 10 输出描述： 对于每组数据输出一行，Yes表示存在，No表示不存在。输出样例 No Yes

美团外卖日订单数已经超过1200万，实时调度系统是背后的重要技术支撑，其中涉及很多复杂的算法。下面的题目是某类场景的抽象。

一张  个点  条有向边的图上，有  个配送需求，需求的描述形式为(  )，即需要从点  送到 ， 在时刻  之后（包括 ）可以在  领取货物，需要在时刻  之前（包括 ）送达  ，每个任务只需完成一次。 图上的每一条边均有边权，权值代表外卖配送员通过这条边消耗的时间。在时刻  有一个配送员在 点  上，求他最多能完成多少个配送任务。
在整个过程中，我们忽略了取餐与最后给用户递餐的时间（实际场景中这两个时间是无法省略的），只考虑花费在路程上的时间。另外，允许在一个点逗留。

输入描述： 第一行，三个正整数 n , m , q (2 ≤ n ≤ 20, 1 ≤ m ≤ 400, 1 ≤ q ≤ 10)。 接下来 m 行，每行三个正整数 u_i , v_i , c_i (1 ≤ u_i,v_i ≤ n, 1 ≤ c_i ≤ 20000)，表示有一条从 u_i 到 v_i 耗时为 c_i 的有向边。 接下来 q 行，每行四个正整数 s_i , t_i , l_i , r_i (1 ≤ s_i,t_i ≤ n, 1 ≤ l_i ≤ r_i ≤ 10^6)，描述一个配送任务。输入样例： 5 4 3 1 2 1 2 3 1 3 4 1 4 5 1 1 2 3 4 2 3 1 2 3 4 3 4 输出描述： 一个整数，表示最多能完成的任务数量。输出样例 2

给出一个正整数n，我们把1..n在k进制下的表示连起来记为s(n,k)，例如s(16,16)=123456789ABCDEF10, s(5,2)=11011100101。现在对于给定的n和字符串t，我们想知道是否存在一个k(2 ≤ k ≤ 16)，使得t是s(n,k)的子串。 输入描述： 第一行一个整数n(1 &le n &le 50,000)。 第二行一个字符串t(长度 &le 1,000,000)输入样例： 8 01112 输出描述： "yes"表示存在满足条件的k，否则输出"no"输出样例 yes