原题解链接：https://ac.nowcoder.com/discuss/149984 其实本来所有的手办是WifeWifeWife的中文翻译的 设f(x)f(x)f(x)为整除xxx的(a∗b)(a * b)(a∗b)的有序对数 g(n)g(n)g(n) 为 ∑i=1nf(i)\sum_{i=1}^{n} f(i)∑i=1n​f(i) 有了这个求和就简单了 另a∗b∗c=xa*b*c= xa∗b∗c=x对于f(x)f(x)f(x)我们需要求的就是三元组(a,b,c)(a, b, c)(a,b,c)的个数 那么g(x)g(x)g(x)求的就是(a∗b∗c)≤x(a* b*c)\leq x(a...

T1 音标 考虑模拟。 每次读取一行字符串，从头到尾枚举，判断这个字母应该变为哪一个字母，然后直接替换并输出即可。 这样，我们就可以通过这道题目。 T2 躲藏 设原字符串数组为sss，模数200012042001012220001204200101222000120420010122为ModModMod,将字符串中所有的大写字母预先变为小写 字母。 考虑动态规划。 令f[i][j],(j=1,2,3,4)f[i][j],(j=1,2,3,4)f[i][j],(j=1,2,3,4)表示前iii个字符中，匹配了字符串"ewbe"的前多少位，那么有转移方程: f[i][1]=(f[i−1][1]+(...

T1 三角形 首先将木棍按长度排序，于是可以确定组成的最大三角形的三根木棍，这三根木棍在排序后的数组中下标显然是连续的，如果偷走的木棍不是这三根木棍中的其中一个，那么答案显然，否则分类处理一下这三种情况即可。 T2 博弈论 答案不可能超过100001000010000，因为数列生成的四位数只有O(n)O(n)O(n)个，所以从小到大枚举答案暴力判断即可。 T3 病菌感染 事实上答案永远是NONONO，以下是一个简单的证明： 当一个方格被感染时，该方格至少会有两条边进入到感染区域内，最多会有两条边加到感染区域的边界上，因而，感染区域的周长不会增加，既然整个区域的周长为4*n，那么最终要想全部感染...

T1 鲲 典型的追及问题，其中值得注意的是，HtBest反向游回起点时有可能被在起点等待的鲲抓到。 T2 鹏 考虑保存⼀下前⼀座⼭之后最低点，这时如果遇到下坡，就判断⼀下下坡后的点是否≥之前保存的最低点，如果是，则需要多翻越⼀次。 T3 桃花 两遍dfs，第⼀遍从任⼀点开始，找到距这个点最远的点，他⼀定是直径的⼀端，然后从这个点开始再dfs，找到最远的距离，输出即可。 T4 字符串丝带 考虑用⼀个数组保存下每个字母的最后出现位置，然后用⼀个数组f，f[i]f，f[i]f，f[i]表示第iii个位置的该字母之前出现的次数即可。 T5 对弈 模拟下棋，下⼀步棋判断⼀下这个新落的⼦是否会影响胜负即可...

T1 送分题 直接把代码复制提交并不能通过此题。 但是如果你仔细分析代码的递归过程，可以发现： 当 n≥20180001n ≥ 20180001n≥20180001 时，答案永远是 201820172018201720182017。 T2 ***游戏 将必胜态和必败态的转移用 DP 递推或者记忆化搜索出来即可。 一个必败态的后继状态全部是必胜态，一个必胜态的后继存在比败态。 T3 谁是神射手 先手获胜的概率是：先手和后手均失败了nnn次后先手成功。即 α∑i=0∞(1−α)i(1−β)i=α1−(1−α)(1−β)\alpha \sum_{i=0}^{\infty}(1-\alpha)^{i}...

T1 病毒感染 求出一张图，上的能从它出发一直覆盖整张图的所有点 说人话,其实我所给定的图的类型全部是树,所以说这个问题也就相应的转化为求树的重心,而树的重心的求法,我就不过多赘述了,详见代码 T2 切题之路 阅读理解题 T3 神秘钥匙 水题，显然可知答案是 ∑i=1nCni∗i\sum_{i=1}^{n} C_{n}^{i} * i∑i=1n​Cni​∗i 将样子改变一下可以得到 ∑i=1nCni=∑i=1nn!i!(n−i)!∗i=∑i=1n−1Cn−1i∗n=n∗2n−1\sum_{i=1}^{n} C_{n}^{i}=\sum_{i=1}^{n} \frac{n !}{i !(n-i)...

T1签到 显然答案是 1−Πi=1n(1−pi)1-\Pi_{i=1}^{n}\left(1-p_{i}\right)1−Πi=1n​(1−pi​) 注意当n=0n=0n=0的时候，被砸到的概率为000。 T2法法 显然答案就是 (∑i=1n[2∤i]×(n−1)!) mod 2={1n=11n=20n>2\left(\sum_{i=1}^{n}[2 \nmid i] \times(n-1) !\right) \bmod 2= \begin{cases}1 & n=1 \\ 1 & n=2 \\ 0 & n>2\end{cases}(∑i=1n​[2∤i]×...

T1 找一找 统计一下 111 到 100000010000001000000 的数字分别有多少个。对于每个数字，看看原来的集合中有没有他的倍数，若有就更新答案。复杂度 O(nlogn)O(nlogn)O(nlogn)。 T2 数一数 假如一个字符串的长度不是所有字符串中最短的，那么其答案一定为 000，因为它在最短的字符串中没有出现过。找出任意一个长度最短的字符串，用 kmpkmpkmp 算法把它和每个串进行匹配，求出它在每个串中出现了多少次，乘起来就是答案。所有长度最短的字符串答案都相同，不需要重复匹配。 T3 列一列 选择一些素数，计算输入的数模这些素数的值，再一个一个计算斐波那契数列的...

T1 小Y和小B睡觉觉 模拟题，先把秒数 /86400/ 86400/86400，再看看余数能不能凑够一天。 T2 LBJX的三角形 答案为 a∗b∗ca * b * ca∗b∗c，因为满足条件的三角形一定是从红点、蓝点和绿点中分别取一个点。 T3 小C打比赛 令 f[S][j]f[S][j]f[S][j] 表示已经做的题的集合是 SSS，一共用了 jjj 分钟的情况下，期望还能再做几道题。枚举做哪道题以及做完的时间即可。时间复杂度： O(2n∗n∗m2)O(2^n*n*m^2) O(2n∗n∗m2) T4 Alice和Bob赌糖果 ​ 随机游走题http://www2.math.uu.se/...

T1 codeJan与恐怖分子 ​ 可以根据 codeJan 的位置，将方格矩阵分成四个子矩阵分别考虑。对于每个子矩阵如果存在边长为 0 00 的话，就不用考虑。如果存在边长小于 K 那一定不能完成任务，否则依次按照行列炸毁。因为要炸毁所有区域且允许重复炸一个区域，所以对于 a∗b a ∗ ba∗b 的子矩阵行上需要 [aK⌉\left[\frac{a}{K}\right\rceil[Ka​⌉ 排炸弹，列上需要 ⌈bK⌉\left\lceil\frac{b}{K}\right\rceil⌈Kb​⌉ 排炸弹。注意结果会爆 intintint。时间复杂度：O(1)O(1)O(1)。 T2 code...

T1 codeJan与恐怖分子 ​ 可以根据 codeJan 的位置，将方格矩阵分成四个子矩阵分别考虑。对于每个子矩阵如果存在边长为 0 00 的话，就不用考虑。如果存在边长小于 K 那一定不能完成任务，否则依次按照行列炸毁。因为要炸毁所有区域且允许重复炸一个区域，所以对于 a∗b a ∗ ba∗b 的子矩阵行上需要 [aK⌉\left[\frac{a}{K}\right\rceil[Ka​⌉ 排炸弹，列上需要 ⌈bK⌉\left\lceil\frac{b}{K}\right\rceil⌈Kb​⌉ 排炸弹。注意结果会爆 intintint。时间复杂度：O(1)O(1)O(1)。 T2 code...

T1无关 一道经典的容斥原理题目。 对于3030%30的数据，可以用暴力骗一波分。 对于100100%100的数据，L-R可以达到101810^{18}1018，对于暴力来说太大了。但是k≤20k\leq 20k≤20,相对来说是极小的。 于是我们想到了容斥原理： ∣A1∪A2∪⋯∪Am∣=\left|A_{1} \cup A_{2} \cup \cdots \cup A_{m}\right|=∣A1​∪A2​∪⋯∪Am​∣= ∑1≤i≤m∣Ai∣−∑1≤i<j≤m∣Ai∩Aj∣+∑1≤i<j<k≤m∣Ai∩Aj∩Ak∣−⋯+(−1)m−1∣A1∩A2∩⋯∩Am∣\sum_{...