这是本文档旧的修订版！
2020-05-09 洛谷多校Day 1
通过情况 3/6 200min
题号 A B C D E F G H 状态 125/3 86/1 锅 119/2
A 给出了一个具有n个顶点和m条边的加权连通无向图。你知道的 有人在顶点1点点燃了火，它会立即把当前位置烧成灰烬 以每秒1英里的速度扩展到相邻的地方。火将在所有这些顶点处分裂 没有被点燃的边缘，当至少两个火在同一点相遇时会引起爆炸。 革命者喜欢爆炸。他们要你数一数爆炸的次数
第一行包含整数n，m（1≤n≤3×105，0≤m≤106）-顶点数。 接下来的m行中的每一行包含3个整数ui，vi，wi（1≤ui，vi≤n，1≤wi≤9）-i-th的末端 边和第i边的重量。 保证图是连通的。 图可以包含自循环和多条边。示例1显示了处理它们的方法。 输入文件的大小可能很大。请不要读得太慢。 输出将在图形上以单行方式发生的爆炸数。
B “好吧，但如果我马上给了一大笔钱，那就不是什么好交易了。所以，我今天会给你0美元，但我会每天增加1美元。也就是说，我明天给你1美元，后天给你2美元……” “然而，只有聪明的人才可能富有，所以当你成为亿万富翁时，你应该立即回答我。” 对温妮来说并不难，因为她善于计算。目前，她在银行账户上有M个美元，她准确地告诉lamp，如果她不使用账户上的钱，她将成为亿万富翁的日期。 现在你也是个聪明人。所以你会知道这个问题的答案：给定M和今天的日期，她成为亿万富翁的日期是什么？ 第一行包含整数T（1≤T≤105）-测试用例数。 每个测试用例描述只包含四个整数M，y，m，d（0≤M<109， 1900≤y≤2050，1≤m≤12，1≤d≤31）-她现在拥有的钱，以及现在的时间。 保证y，m，d形成相应的日期。 对于每个测试用例，在单独的行上打印三个表示答案日期的整数。 请不要打印月份和日期的前导零。请参阅示例输出以了解清楚信息。
从今天开始，每天拿到的💰有 日子 今天 明天 钱数 0 1 2 3 4 5 6 7 8 每天增加 1
输入：第一行组数，每组第一个是现在已经有的钱数、后面是现在的年月日 输出：到有1 000 000 000块钱的时候的日期
C k进制数是以k为基数的数，表示为（A）k。例如，（15）10=（f）16=（17）8=（1111）2个。大于9的数字用小写英文字母a···f表示，表示10<k≤16。 回文数是一个非负数，在某些确定的基址k，它向前或向后读取相同的数据。例如，（121）10，（abba）16，（0）2是回文数字，但是（00）2，（010）10不是。 今天汤米太伤心了，连他最喜欢的k元回文数都数不出来，这些回文的长度是n，而且可以被p整除 你能帮他数一数汤米最喜欢的数字吗？ 注意，答案可能非常大，您只需要告诉答案模块998244353-另一个汤米最喜欢的素数。
输入包含3个整数n，p和k（1≤n≤1018，2≤p≤1000，2≤k≤16）-回文长度、质数和基数。 可以保证p是质数。 输出应答模块998244353。
D 双城是一个一切都是双胞胎的地方，除了他们的硬币。他们使用两种硬币，其价值相当于A和B克黄金。那里的人很了解欧几里德算法，所以我们保证A和B的最大公约数是1。他们会告诉你为什么硬币系统是有效的：通过求解线性不定方程Ax+by=C，每一个可能的整数C都会有一个结果。 但当它进入现实时，事情变得更加复杂。事实上，改变-换句话说，负的x或y-是很麻烦的，在双土地上的人根本不喜欢它。所以当有必要改变的时候，他们总是多付一点钱。 一个叫伊尼的骗子，住在一个地方，恨恶两个地方的人。他知道当没有合适的非负x，y作为C的价格时，人们会付出更多的代价，于是决定用这样不方便的价格来骗钱。他买了很多货，把它们送到了双人间土地，并以各种价格定价-当然，所有这些价格都是不方便的人在双重土地。 但是艾尼不是很聪明-也许这就是他现在不得不住在一个地方的原因。他发现很难计算出第K个最小的不公平价格。你能帮他吗？他愿意和你分享他从双面人那里骗取的钱！
第一行包含整数T（1≤T≤10）-测试用例数。 每个测试用例描述只包含一行三个整数，A，B，K（1≤A，B≤107， 1≤K≤1018）-两种硬币的值，以及所需的K。 保证了gcd（A，B）=1，且存在第K个最小不公平价格。 对于每个测试用例，在单独的一行上打印一个表示第K个最小不公平价格的整数。
E
在熊王国，国王有一个非常奇怪的爱好：他不喜欢所有长度小于10的名字！事实上，每次他看到谁的名字很短，他都会非常生气，以至于在接下来的998244353天内拒绝发言！ 但是，国王对熊王国来说是必不可少的，所以民政部长，肺炎支原体矽肺孢子虫病，宣布：每只熊都应该有一个长长的名字！熊很难改名，因此肺孢子虫病用一系列方法来显示改名规则如下：
（超长的规则）
if (first letter/last letter/length ==/!= 条件) { ,操作, } else { 操作. }
（比如） If first letter of the name is not 'g', reverse the name, else append 'h' after the name.
但是对于熊来说，精确的变换仍然是非常困难的。所以他们要求你——一个可以使用计算机程序的人——来解决这个问题。你能帮他们吗？
输入包含单个字符串s（1≤| s |≤50）由小写英文字母组成-您的程序需要操作的原始名称。 在一行中输出所需的名称。 word翻译题（或者手搓？）
F
勒克斯计划消灭隐形不动的敌人蒂莫，蒂莫的位置由甲骨文镜头探测到。她决定立即施放一个终极技能，如果被击中，将杀死蒂莫，因为勒克斯有很高的能力。 勒克斯的终极技能，最后的火花，是一个强大的技能，可以伤害敌人的直线光束无限长和w米宽。它将对至少与光束共用一个点的人造成损害。 但是提莫——敏捷的侦察兵——是一个训练有素的士兵。他会对勒克斯的动作迅速做出反应，并试图通过选择一个均匀随机的方向来躲避光线，并沿着这个方向奔跑。从Lux的第一个动作到光线最终探出的那一刻，Lux需要时间来引导终极，在引导过程中，Teemo可以跑s米——注意Teemo总是沿着直线跑。 她应该在采取任何行动之前选择最后火花的方向。在勒克斯使用最佳策略施展终极技能之前，她想知道这个技能怎么可能击中蒂默。她回忆说，蒂莫可以被认为是半径为r米的圆，而现在蒂莫距离勒克斯只有d米。 勒克斯很难计算。你能回答Lux在她使用最佳策略时打Teemo的可能性吗？
勒克斯计划消灭隐形不动的敌人蒂莫，蒂莫的位置由甲骨文镜头探测到。她决定立即施放一个终极技能，如果被击中，将杀死蒂莫，因为勒克斯有很高的能力。 勒克斯的终极技能，最后的火花，是一个强大的技能，可以伤害敌人的直线光束无限长和w米宽。它将对至少与光束共用一个点的人造成损害。 但是提莫——敏捷的侦察兵——是一个训练有素的士兵。他会对勒克斯的动作迅速做出反应，并试图通过选择一个均匀随机的方向来躲避光线，并沿着这个方向奔跑。从Lux的第一个动作到光线最终探出的那一刻，Lux需要时间来引导终极，在引导过程中，Teemo可以跑s米——注意Teemo总是沿着直线跑。 她应该在采取任何行动之前选择最后火花的方向。在勒克斯使用最佳策略施展终极技能之前，她想知道这个技能怎么可能击中蒂默。她回忆说，蒂莫可以被认为是半径为r米的圆，而现在蒂莫距离勒克斯只有d米。 勒克斯很难计算。你能回答Lux在她使用最佳策略时打Teemo的可能性吗？
第一行包含整数T（1≤T≤105）-测试用例数。 每个测试用例描述只包含一行四个整数，w，r，s，d（0≤w，r，s≤1000， 1≤d≤3000）-光束的宽度、Teemo的半径、Teemo在Lux引导其最终火花时可以运行的距离、Lux和Teemo之间的距离。 保证了w+r+s<d，因此Teemo不能通过Lux，光束的开始不能接触Teemo。 对于每个测试用例，在单独的行上打印一个表示最大可能性的数字。绝对误差不应超过10-6。 正式地说，让你的答案是A，陪审团的答案是B。只有当且仅当A-B≤10-6时，你的答案才被接受。
G
大于2的偶数可以表示为两个素数之和。 2019年初，普罗万“证明”了戈德巴赫的猜想，并将其发表在智湖。 不管他的证明多么荒谬，你——数学天才——都知道戈德巴赫的猜想在你那神圣的数学直觉中是正确的。你知道这很难证明，但是你可以用你非凡的编程技巧来证明这一点。你决定写一个程序来证明它的正确性， 你也要感谢普罗姆先生勇敢地向真理迈进了一步，尽管他失败了，被许多人嘲笑。 请注意，我们不能像您那样提供超级计算机，这样您的程序将使用109以下的数字进行测试。
输入包含一个偶数整数n（2<n≤109）-你需要证明满足戈德巴赫猜想的数字。 输出两个素数，在一行中用一个空格隔开。素数之和应该等于n。 如果有多个答案，请打印所有答案。
哥德巴赫猜想：大于2的每个偶数整数都可以表示为两个素数之和。 输入 单个偶数整数n（2 <n≤1e9) 输出 在一行中输出两个素数，以一个空格分隔。 素数之和应等于n。 如果有多个答案，请打印任何答案。
H
为了准备潜在的病毒传入，H国需要调查每个行政部门的危害评分。抽象地说，H国的等级构成了一棵根茎树，每个顶点都是一个行政级别，如省、市、县、镇等。根茎是顶点1。每个顶点都有自己的颜色，这表明当地居民的生活习惯-人们更可能在同一颜色的顶点之间进行交通。 每个顶点的危险度得分计算为具有相同颜色的顶点子树中所有不同顶点对的距离之和。两个顶点之间的距离计算为它需要在两个顶点之间传输的最小边数。 时间就是生命。你被雇来尽可能快地计算H国每一个vectex的危险分数。
第一行包含整数n（1≤n≤105）-顶点数。 第二行包含n个整数，第i个数ci（1≤ci≤n）表示顶点i的颜色。 接下来的n-1行中的每一行包含2个整数ui，vi（1≤ui，vi≤n）-第i条边的末端。 它保证了边形成一个包含n个顶点的树。 输出n行，在第i行打印一个整数，表示子树i的危险分数。
AC代码
