@Dmaxiya
2019-09-08T23:55:31.000000Z
字数 7207
阅读 922
小女孩又擦亮一根火柴，火光把四周照得通亮，奶奶在火光中出现了。奶奶朝着她微笑着，那么温柔，那么慈祥。
“奶奶——”小女孩激动得热泪盈眶，扑进了奶奶的怀抱，“奶奶，请把我带走吧，我知道，火柴一熄灭，您就会不见了！”
“我亲爱的孙女儿，奶奶不会离开你的。奶奶学会了一种魔法，只要你能用三根火柴拼出一个三角形，这三根火柴就永远不会熄灭！”
“真的吗？太好了！奶奶，我现在就可以拼出来。看！还是个三边相等、有三条对称轴的正三角形呢！”小女孩激动得手舞足蹈。
“傻孩子，魔法怎么会这么简单就能完成的呢，火柴的长度需要满足一定的条件，它们的长度都为整数，也必须在 [l, r] 的区间内，且任意两根火柴的长度不能相等。”
这可难倒小女孩了，你能帮她达成心愿吗？
输入包含两个正整数 l 和 r，含义如题。
如果小女孩的心愿能够达成，则在第一行输出 "YES"，并在第二行输出三个整数，表示答案，否则输出 "NO"。若有多种可能的答案，输出任意一种即可。
10 15
YES10 15 13
500 500
NO
1 <= l <= r <= 100000
首先检查 [l, r] 的区间长度至少要为 3，其次找到 r, r-1, r-2，只要满足 (r-2) + (r-1) > r（或者特判 1, 2, 3 的非法情况），就是答案，属于偏思维题，本题没有唯一解，spj 需要检查的情况比较多。
小 Byte 想在七夕当天写情书给小 Dance 表白。但是小 Byte 很害羞，不希望别人看见这封情书，于是就利用一些规则对这封情书进行了加密，并将加密后的情书和加密法则送给了小 Dance。由于情书篇幅比较大，小 Byte 的加密法则解密起来过于烦琐，小 Dance 不能看懂，这样的话小 Byte 表白就失败了。小 Byte 拜托你去帮小 Dance 解密情书，使他表白成功！
已知小 Byte 的情书内容原文为一串不加标点的英文，如 "Welcome to bytedance"。小 Byte 的加密法则为：
第一行为一个整数 n，表示情书中总共有 n 个单词，第二行为一串不带标点的字符串，单词仅包含大写字母与小写字母，每个单词之间用一个空格分隔，为加密后的情书。
利用规则解密后的情书内容。
3Wloemce to btdnecaey
Welcome to bytedance
整篇情书的字母数量之和不大于 5000。
用两个下标在单词两端扫描，一个从左往右扫，另一个从右往左扫，来填充原单词，当处于原单词奇数位的时候，取左边的下标对应的字母，当处于原单词偶数位的时候，取右边的下标对应的字母，两个下标不断往中间靠拢，直到填满整个单词。
字节跳动的笔试马上就要开始了，小 Byte 从一周前就开始紧张，他祈祷自己能够拿到满意的分数——这时候上帝出现了，告诉他其实每个人都有一个 RP 值，并且以周为单位，在一周的开始，上帝给每个人每天都设了一个 RP 值，RP 值越高，他在这天就越幸运。
上帝给了小 Byte 一个机会，允许他调整自己的 RP 值，若他将自己一周中某一天的 RP 值增加 1，在另一天他的 RP 值必须要减少 1，他有无数次调整的机会，但是一旦确定下来，就不能改变，他接下来这一周就必须按照这个 RP 值生活。在调整的过程中 RP 值必须始终保持在区间 [0, 9] 以内，不能超出这个范围，且每天的 RP 值都必须为整数。若小 Byte 每天严格遵守这样的 RP 值生活，到笔试当天，他的分数就等于过去 7 天每一天 RP 值的乘积，否则他将受到惩罚得到 0 分。
第一行为一个整数 T，表示有 T 组数据，接下去 T 行，每行 7 个整数 a_i，第 i 个整数表示第 i 天小 Byte 的 RP 值。
输出小 Byte 能得到的最大的笔试分值。
21 1 1 1 1 1 10 1 1 1 1 1 2
11
1 <= T <= 100, 0 <= a_i <= 9
由于对其中 1 个数字加 1 就要对另 1 个数字减 1，因此 7 个数字的总和始终不变。
- 由基本不等式拓展可以得到，要使得乘积最大必须要尽量平均分这 7 个数字。令 sum=a_1+a_2+……+a_7, mod=sum%7，可知 7 个数中有 mod 个数被分配为 floor(sum/7) + 1，有 7-mod 个数字被分配为 floor(sum/7)，因此答案为：
ans = pow(floor(sum/7) + 1, mod) × pow(floor(sum/7), 7-mod)- 定义 dp[i][j] 表示前 i 个数字的和为 j 时能得到的最大乘积。第 i 个数字可以取的合法范围为 [0, min(9, j)]，枚举第 i 个数字可能的取值 k，可以得到递推式：
dp[i][j] = max(dp[i-1][j-k] × k) k∈[0, min(j, 9)], j-k <= 9(i-1)
初始条件为 dp[1][j] = j, j∈[0, 9]，最后的答案就是 dp[7][sum]，也就是前 7 个数字的和为 sum 时乘积的最大值。
给定一个 n 个节点的多叉树，树的根节点编号为 1，第 i 个节点权值为 w_i，总共有 q 次询问，每次询问树上任意两个节点 u, v，对于所有包含这两个节点的子树，找到节点数最少的，并求出该子树中，所有其他节点权值的最大公约数。
第一行为两个整数 n 和 q，表示有 n 个节点和 q 次询问。
第二行为 n 个整数，w_1, w_2, ..., w_n，分别表示每个节点的权值。
接下来的 n-1 行，每行两个整数 u, v，表示节点 u 与节点 v 之间有一条连边。
接下来的 q 行，每行为两个整数，即询问的两个节点编号。
对于每次询问，输出题目所求答案，每次询问的输出占一行。若除去被询问的节点后不存在其他节点，则输出 0。
6 420 30 15 10 1 1002 13 45 65 31 34 55 25 35 6
155100
对于 50% 的数据，2 <= n, q <= 1000
对于 100% 的数据，2 <= n, q <= 1000000，1 <= w_i <= 10^9，1 <= u, v <= n, u != v
数据保证结构为一棵树
题目所求子树即被询问的两个节点的最近公共祖先所对应的子树，求最近公共祖先可以用树链剖分或 LCA 在 O(log n) 内求得，对整棵树 dfs，按照 dfs 的顺序对每个节点从 1 到 n 编号，即可将整棵树展开成一个一维数组，每一个子树对应数组内一段连续的区间，将被询问的两个节点从数组中去掉，即求三段连续区间的 gcd，gcd 满足可加性，且整棵树不带修改，可以用 ST 表预处理，以 rmq 的方式计算连续区间内的 gcd，最后求三段连续区间的 gcd，将答案的初始值设为 0 即可（0 和其他任意整数 x 的 gcd 为 x）。总时间复杂度为 O(n + 2 * n log n + n log n log n + q(log n + 3 * log n))。
为了庆祝字节跳动七周年，活动台前幕后的工作人员们开了一场香槟酒会。
所有酒杯被摞成一个金字塔，接着由主持人从最顶层的酒杯往下倒酒，如果顶层的酒杯被倒满了酒，多出来的酒就会溢出到第二层（向左右两边溢出的速率相等，如下图）。现在我们按照从上到下、从左到右的顺序对酒杯从 1 开始编号，第 i 层第 j 个酒杯的编号为 (i, j)，例如顶层的酒杯编号为：(1, 1)。
每一个酒杯的容积都相同，我们设为一个单位体积，问如果想要把酒杯 (i, j) 装满，最少需要多少单位体积的香槟酒？
输入为两个正整数 a, b，表示被询问的酒杯编号。
输出一个实数，表示至少需要向最顶端的酒杯倒多少单位体积的香槟，才能倒满酒杯 (a, b)。
如果你的输出与标准输出的绝对值不超过 10^(-6)，则认为你的程序是正确的。
1 1
1
2 2
3
1 <= b <= a <= 30
可以发现，如果已知要倒多少香槟酒到顶端的酒杯，就可以 O(n^2) 地计算出酒杯 (i, j) 最终含有的香槟酒的体积（用一个二维数组保存对应位置酒杯的酒的体积，模拟一遍倒酒的过程，注意没有被倒满的酒杯无法溢出）。
并且：往顶端的酒杯倒越多的香槟酒，酒杯 (i, j) 内香槟酒的体积可能就越大，如果把香槟酒的总体积作为变量，酒杯 (i, j) 内的香槟酒体积作为函数值，就是一个单调非递减的函数，满足二分性质，因此可以用二分来求满足函数值等于 1 的变量的最小值。
由找规律可以得到，要倒满 (30, 30) 位置的酒杯需要最大的体积，最大值为 2^30 - 1，因此二分的初始区间为 [1, 2^30 - 1]。
数据注意
一定要包含一组 30 30 的数据。
小 Byte 和小 Dance 在玩一种叫“开火车”的纸牌游戏，游戏规则如下：
1. 初始给两人随机平分 52 张扑克牌，每个人 26 张；
2. 小 Byte 先开始，将第一张牌放下；
3. 随后两人轮流按顺序（按从第 1 张到最后 1 张的顺序出牌，手牌中的顺序不可以被打乱）放置扑克牌，后一张扑克牌压在前一张扑克牌上；
4. 如果出现之前放下的某张扑克牌 s 与将要放下的扑克牌 t 点数相同，则当前玩家获得从 s 到 t 之间的所有牌（包括 s 和 t 这两张牌）；
5. 玩家手上的 26 张牌都出完后，游戏结束。并清点双方获得的牌数，牌数多的玩家获胜，若两名玩家牌数相同，则平局。
输入包括两行，每行 26 个数字，分别表示两位玩家初始被随机分配到的牌的点数，第一行为小 Byte 被分到的牌。
若平局则输出 “Draw”，否则输出获胜玩家的名字（“Byte” 或者 “Dance”）。
10 2 5 6 13 11 11 4 10 8 12 5 4 1 8 1 7 12 4 13 6 9 9 9 5 76 3 13 8 2 3 7 3 2 2 12 11 10 6 10 1 1 12 3 5 7 11 13 4 8 9
Byte
对于样例输入，最终小 Byte 获得 31 张牌，小 Dance 获得 19 张牌，剩下两张点数为 6、9 的牌。
所有数字都在区间 [1, 13] 内。数据保证所有点数分布与扑克牌点数相同。
按题意模拟即可。
2019 年 3 月 12 日，全球的 Bytedancer 共同庆祝字节跳动成立七周年。七年前的今天，初创团队把营业执照领回锦秋家园，七年后的今天，字节跳动在不断地快速成长，吸纳全球优秀的人才加入。
为了纪念 2012 年 3 月 12 日这个重要的日子，我们希望能够对于之后的任何一个日期，计算出公司已经成立了多少天。人工计算或者 Excel 表操作是费时的，我们希望你能实现这个功能，并期待优秀的你加入我们。
第一行为一个整数 T，表示有 T 组数据，接下去 T 行，每行三个整数 y, m, d，分别表示年、月、日。
对于每组数据，输出 1 个整数，表示从 2012 年 3 月 12 日到给出的日期经过了多少天。
22012 3 132019 3 12
12556
1 <= T <= 100, 2012 <= y <= 9999, 1 <= m <= 12, 1 <= d <= 31
数据保证给出的日期合法，且在 2012 年 3 月 12 日之后。
2012/3/12 距 2011/12/31 有 72 天，计算给出的日期距 2011/12/31 有多少天，这样可以按整年、整月地计算，将计算得到的值减去 72 就是答案。
最后注意平年闰年的二月份。
Bytedance 决定对所有新人展开一次针对性的培训。公司有很多新人，每个人想学的内容都不一样。限制每个人只能在本次培训中学习一门课程，经过统计，新人们总共想学 n 门课程，每门课程报名的人数分别为 a_1, a_2,……, a_n。为了保证公平与方便管理，公司决定采用小班教学模式，所有的小班内人数相同，同一班级内的课程内容相同。由于人力有限，我们期望在满足以上前提条件的同时，班级数量尽可能地少，问：最少需要开多少个小班。
第一行为一个整数 n，表示有 n 门课程，第二行为 n 个整数，每个整数之间用一个空格分隔，分别为 a_1, a_2,……, a_n，表示门课程的报名人数。
输出最少需要开多少个小班。
31 1 2
4
对于 50% 的数据，1 <= n <= 10000, 1 <= ai <= 1000
对于 70% 的数据，1 <= n <= 10000, 1 <= ai <= 1000000
对于 100% 的数据，1 <= n <= 1000000, 1 <= ai <= 2^31-1, 答案不超过 int 能表示的范围
- 暴力解法是枚举所有可能的每个班级的人数，由班级人数计算需要分班的数量，取最小值，完全暴力枚举的做法可以通过 50% 的数据，如果及时加一些 break 剪枝可以通过 70% 的数据，最后 30% 的数据每个数字都有至少 1000 个约数，所以有 1000 个数字无法通过 break 优化；
- 由于每个班级的人数越多，分班数量越少，而且要求满足每门课程的分班人数都相等，所以每个班的人数都要能整除每一门课程的人数，因此每个分班的最大人数就是这 n 个数字的最大公约数，求最大公约数用辗转相除法，暴力枚举最大公约数的话，也无法通过最后的 30% 数据。
最后注意 n 个数字的和爆 int。
在一个交通非常便捷的城市，总共有 n 座建筑，建筑有 A 和 B 两种类型，建筑之间存在 m 条相互连通的双向道路，任意两个城市之间可以直接或间接地通过道路相互到达，经过长时间的调研市长发现建筑之间的通道过多导致维护成本远高于收益，因此决定尽可能多地停用一些道路。
停用道路之后，城市之间仍然要保持便捷的交通，最终决定剩余的道路应满足以下要求：
1. n 个建筑之间仍然可以直接或间接地相互到达；
2. 同类型的建筑之间不能直接到达，即：A 类建筑只能直接到达 B 类建筑，B 类建筑只能直接到达 A 类建筑；
3. 在满足以上条件的前提下，停用道路的数量应尽可能多。
现在将规划的任务交给你，请给出一个合理的方案。
第一行为两个整数 n 和 m，表示有 n 座建筑和 m 条道路，第二行为一个长度为 n 的字符串，字符串只包含 A 和 B，第 i 位字母表示第 i 座建筑的类型，接下去 m 行每行两个整数 u, v，表示第 u 座建筑和第 v 座建筑之间有一条道路可以直接到达。
第一行为一个整数 k，表示要继续运营的道路数量，第二行为 k 个整数，每个整数表示一个道路编号，道路按照输入顺序从 1 开始编号。如果有多解输出任意一个即可，注意输入的编号必须在区间 [1, m] 内，且两两互不相等。
4 6AABB3 42 14 23 11 42 3
35 3 4
对于 70% 的数据，1 <= n,m <= 1000
对于 100% 的数据，1 <= n <= 100000, 1 <= m <= min(n(n-1)/2, 100000), 1 <= u,v <= n, u != v
数据中不存在重复的无序对 (u, v)，保证至少存在一组解。
选择任意一个节点开始搜索（bfs 或者 dfs），搜索过程中若相邻节点类型相同则不搜索对应边，已经搜索到的节点不再继续搜索，最后必然得到一个 n-1 条边的树形结构，将搜索过程中跑过的边的编号输出，就是答案。
用邻接矩阵可以通过 70% 的数据，用邻接链表或 vector 数组或链式前向星等结构可以通过 100% 的数据。
在一个树形的网络结构中，总共有 n 个节点，它们在传输数据的过程中会产生各种时延，如节点处理时延、排队时延、传输时延、传播时延等，我们将所有传输过程中产生的时延求和取均值统一为一个数值。
为估计整个网络的效率，现在需要抽取某些网络节点，并计算在所有可能传输到的其他节点中，最长的总时延，如节点 A 到节点 B 的时延为 x 毫秒，节点 B 到节点 C 的时延为 y 毫秒，则节点 A 到节点 C 的总时延为 x+y 毫秒，由于网络中存在大量的节点以及多次的抽样，你的程序需要用尽可能高效的方式运行以得到结果。
第一行为一个整数 n，接下去 n-1 行每行三个整数 u v w，表示节点 u 与节点 v 之间的时延为 w。第 n+1 行为一个整数 q，表示有 q 次抽样，接下去 q 行每行一个整数 pos，表示被询问的节点编号。
对于每个被抽样的节点，输出该节点到网络中所有其他节点的最大总时延。
41 2 101 3 54 1 3224
1513
对于 50% 的数据，1 <= n <= 1000, 1 <= q <= 1000
对于 70% 的数据，1 <= n <= 1000, 1 <= q <= 1000000
对于 100% 的数据，1 <= n <= 1000000, 1 <= q <= 1000000, 1 <= u,v,pos <= n, 1 <= w <= 100000
数据保证结构为一棵树。
- 直接暴力对每个点 bfs 或 dfs 能通过前 50% 的数据；
- 先对每个点暴力 bfs 或 dfs 预处理，将答案存到每个点上，可以通过 70% 的数据；
- 用 dp[i] 记录到达节点 i 的最大时延，首先有 dp 公式：
dp[i] = max(dp[j] + dis[i][j]) j 为所有与节点 i 相邻的节点
然后对整棵树进行两次 dfs，第一次从叶子节点往根节点 dp，可以得到所有节点到其子树上所有节点的最大时延，第二次从树根往叶子节点 dfs，将父节点的信息传到子节点，相当于将兄弟节点的信息传给该子节点，这里需要注意如果是从父节点 f 传到子节点 pos，则需要取的是 f 所记录的 pos 的兄弟节点子树的信息（不能包含 pos 所在子树的信息，否则会出错），这里需要预处理所有子节点的前缀 Max 与后缀 Max 以 O(1) 求解得到该值，暴力求解的话其中一组数据返回超时（某个节点与所有其他节点相邻的情况，会被卡成 O(n^2)）。