昨天做作业时,翻到了这道题目: 不知道有没有大佬愿意帮忙一下,谢谢!

大家好! 如果你看到并点击了这个帖子，那么你一定有兴趣 《JOJO的奇妙冒险》 大家可以聊聊自己对JOJO的看法！ 等待你的评论........

我是位认真的小宝宝，可惜被网课坑了，老师说“现在我们写一下代码……是不是过不了？”，气死我了

3 4 5：这不就是勾股定理吗？！

巅峰赛34题解 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 午枫的宝石容器 普及− T2 午枫的城市路线 普及/提高− T3 午枫的对称字符 普及/提高− T4 午枫的小队评分 普及/提高− T5 午枫的平衡调整 普及/提高− T6 午枫的路线封闭 普及+/提高 T1 午枫的宝石容器 题目大意 有 nnn 颗宝石，大小为 AiA_iAi ，以及 n−1n-1n−1 个容器，容量为 BiB_iBi 。现在可以额外购买一个容量为 xxx 的容器，使得总共有 nnn 个容器。要求每个容器最多放一颗宝石，且宝石大小不超过容器容量。求最小的 xxx 使得所有宝石都能放入容器中，若无法实现输出 −1-1−1。 题解思路 贪心匹配即可。为了尽量让大的宝石优先匹配大的容器，先将宝石数组 aaa 和容器数组 bbb 都按从大到小排序。 然后用双指针从大到小匹配：指针 iii 枚举宝石，指针 jjj 枚举容器。如果当前宝石 ai≤bja_i \le b_jai ≤bj ，说明可以用这个容器装下，指针 jjj 向后移动；否则说明当前宝石无法被任何已有容器容纳，只能依赖新买的容器，于是记录这个宝石。 统计这种“装不下”的宝石个数： * 如果为 000，说明原有容器已经够用，此时新容器可以取最小值，即 ana_nan ； * 如果为 111，说明只有一个宝石需要新容器，答案就是这个宝石的大小； * 如果超过 111，说明至少有两个宝石需要新容器，但我们只能买一个，因此无解。 这个贪心是正确的，因为总是优先让大宝石匹配大容器，可以保证不会浪费容量。 时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)。 参考代码 T2 午枫的城市路线 题目大意 给定一张有向图，从节点 111 出发，问是否存在一条路径可以回到节点 111（即形成一个包含 111 的环）。如果存在，求这样的路径中边数最少的一条长度；否则输出 −1-1−1。 题解思路 由于所有边权为 111，要求最短路径，直接使用 BFS。 从节点 111 出发进行广度优先搜索，用数组 d[i]d[i]d[i] 记录从 111 到达节点 iii 的最短距离。每次从队列中取出一个节点，遍历它的所有出边，如果某个节点还没访问过，就更新距离并入队。 在 BFS 过程中，如果某条边可以从当前节点走回 111，那么就找到了一个回环，其长度就是当前节点的距离加 111。由于 BFS 按层扩展，第一个找到的回环一定是最短的。 如果最终没有办法回到 111，说明不存在这样的路径，输出 −1-1−1。 时间复杂度为 O(n+m)O(n+m)O(n+m)。 参考代码 T3 午枫的对称字符 题意简述 给定一个仅由大写英文字母组成的字符串 SSS，要求计算三元组 (i,j,k)(i,j,k)(i,j,k) 的数量，使得 1≤i<j<k≤∣S∣1 \le i < j < k \le |S|1≤i<j<k≤∣S∣ 且 SiSjSkS_iS_jS_kSi Sj Sk 是回文串。由于长度为 333 的回文串唯一的条件是首尾字符相同，即 Si=SkS_i = S_kSi =Sk ，中间字符可以是任意字符，因此本题实质上就是统计所有首尾字符相同的三元组数量。 解题思路 可以采用前缀计数的方法，遍历字符串时维护一个数组记录每个字母已经出现的次数，同时维护一个数组记录以每个字母为首字符的可形成组合数量。在遍历每个字符作为中间字符时，将当前字符对应的组合数量累加到结果中，然后更新以每个字母为首字符的组合数量，最后更新当前字符的出现次数。这样就能在一次遍历中统计出所有满足条件的三元组，时间复杂度为 O(n⋅26)O(n \cdot 26)O(n⋅26)，空间复杂度为 O(26)O(26)O(26)，足够应对 ∣S∣≤2×105|S| \le 2 \times 10^5∣S∣≤2×105 的情况。 参考代码 T4 午枫的小队评分 题意简述 有 NNN 名选手，每位选手都有实力值 AiA_iAi 和消耗值 BiB_iBi 。需要从中选出一个大小为 KKK 的小队 SSS，小队评分定义为： score(S)=(max⁡i∈SAi)×(∑i∈SBi)\text{score}(S) = \left(\max_{i \in S} A_i\right) \times \left(\sum_{i \in S} B_i\right) score(S)=(i∈Smax Ai )×(i∈S∑ Bi ) 目标是选择一个小队，使得评分尽可能小，并输出最小评分。 解题思路 首先将选手按照实力值 AiA_iAi 从小到大排序。然后考虑当某个选手 iii 的实力值成为小队中最大实力值时，如何选择另外 K−1K-1K−1 名选手以使得消耗值之和最小。为了高效计算，可以使用一个大根堆维护当前已选择的 K−1K-1K−1 个消耗值最大的选手，如果当前堆中超过 K−1K-1K−1 个元素，就弹出最大的，这样保证堆中始终保存消耗值最小的 K−1K-1K−1 个候选成员。每遍历一个选手，将其作为最大实力值候选时，累加堆中消耗值与自身消耗值，然后计算评分并更新最小值。这样遍历一次即可得到最优解，时间复杂度为 O(Nlog⁡K)O(N \log K)O(NlogK)，空间复杂度为 O(K)O(K)O(K)。 参考代码 T5 午枫的平衡调整 题意简述 给定 NNN 名成员，每名成员属于三个小组之一并有一个贡献值。希望通过调整部分成员的小组归属，使得三个小组的总贡献值完全相等。每次调整只能将某个成员移动到另一个已有的小组中，目标是判断是否可以实现平衡，如果可以，则输出最少需要调整的人数，否则输出 −1-1−1。 解题思路 首先计算所有成员贡献值之和，如果不能被 333 整除，则无法实现平衡，直接输出 −1-1−1。设每组的目标贡献值为总和的三分之一。使用三维动态规划，状态为 dp[i][j][k]dp[i][j][k]dp[i][j][k]，表示前 iii 个成员中，第一组总贡献为 jjj，第二组总贡献为 kkk 时所需的最少调整人数。遍历每个成员时，可以选择将其分配到任意一组，累加调整次数（若成员当前组与选择组不同则加一），更新状态。最终 dp[N][target][target]dp[N][target][target]dp[N][target][target] 即为最少调整人数，如果无法达到则为无穷大，输出 -1。 参考代码 T6 午枫的路线封闭 题意简述 给定 NNN 个地点和 MMM 条双向路线，每条路线有通行代价。随后有 QQQ 个操作，包含封闭某条路线或询问两点间最小通行代价。封闭操作总次数不超过 300300300。要求按操作顺序处理，每次询问输出当前未封闭路线下的最短路径，若无法到达输出 −1-1−1。 解题思路 由于地点数量 N≤300N \le 300N≤300，可以使用 Floyd 算法处理所有点对最短路径。关键是封闭操作较少，因此可以采用离线处理策略：先将所有封闭操作标记，并从最终状态的图出发，计算全局最短路径。然后逆序处理操作序列，每遇到一次封闭操作就“恢复”对应边，并更新受影响的最短路径；遇到查询操作直接读取当前最短路径表即可。这样只需在逆序处理时更新路径，而不必每次从头计算，保证在 O(N3+Q)O(N^3 + Q)O(N3+Q) 时间内完成。最终按正序输出查询结果即可。 参考代码

王大爷不就是在对小明下毒吗

不活了

不是我说白了 这题样例没输出，没过很正常。我算是放弃了。 ACGO出来发个题解吧!!!

你们觉得难不难？

/* * * * * * * * * * * * * * * * * * -.____-._/.-`__.-' * * * ............................................. * * * */

咱就说小明真的这么爱玩游戏，会被抓到10000次吗？估计那时小明的手都残了，毕竟要写658370828570650267011634913685583077661753954522443510101162953451471481397324238853358735573194421730677927270965901100961364214530654776880594935759178690609239091544195219383253136191779976552178152868300379280902784079200397454621799470580957621306986166529654305380073897509070511754212638784378108806152428189247856554543075763690519956354661759335912420595778145173617065104163541658024168714070560588145992308680557751697696838095132507102002003205343666434509903708447753990211085832449498156826518228970595003695207036463808539927043482107564155241230995221079312727537331188003468411676846689519413319241408595484147532380936167427289605277256656061046619008598741590034685045933442335494590970037128396966253598457165788944026848593296713080441212252861071845255744567189276254322764387976375246650995766565321860245520376442763323854030712385399074770458398665961601968709356066696744151600683336948343392912771680377483774611544997043380823138151935104986139718962011789279413078049817252291263398248154794642635954824895796678006405911043004095194325429344347614358433107938230114697299313512635505405290602549118584607936031771978772102762448613375317871958317360825290138951572296312780195937259806676171648654912228331580685030699900577875705714861215758433044967358635168832966520937883304868016704639429531528326486675471876294230118407354729419926787194570169126322190745530414039432462909241503678297546951912364114167245886179495138929823843172712811598015124603496024586837006261261613154864669249445584041549493850445244978952536339074521860793476207546879422145026293481968072289116141358466912962036528941818034083167406615696030169094938536328148597808852639647084847533423240632450650926531899810712845739450058028338162964845668688674411671314375839350532279892284975395279056705406782572617694945291851235864751213944792690674249168293365593303255733336785528502795572227881288363367237765411506142302772450676923117056148467393563222374900036645927421421987654995954237216561901712382675050237308144066045882973556461582319924482933991060478815515484330056860033897245973998341420998811324041446452012481964464827679449403470636153451249987194499009306309338208274587181282130451183534914611971649504884785055943169494772266158092902277642855240805362204115397641875829761398092263713130191748461900510776291161265686970638061377509578179391005155166988527961818217066862018963259209506502722739103595772098284678889027034247953009974483797167814762691467270984871480019775270594694797392303246075935687664063951734463396849781510459973934536883164177895575056362537719766526625797843950807931727913930164007910960223065468762386197682052008123673406280474143774947233983400660952255045468915255395880370896115059954756004408441693759528269248773201918202229081171113037024514171182477269814773159599575456170263663147852423214760962664513045193492289201606793851109229820261304900065811964708342626763521159797656440285041512755289342975663430085952650919885498552058155691409408次“小明”

王大爷：“你礼貌吗？你以为我的鸭子是从天上掉下来的吗？“； 没有写题的绝望，只看到了一个绝望的王大爷；

椰汁不能乱喝

#include <bits/stdc++.h> using namespace std; int n,m1,m2,ans = 150000; int i,j; int s[10001],f[10001]; bool p[30001]; int prime[501][3],size = 0; int main(void) { memset(p,1,sizeof(p)); memset(f,0,sizeof(f)); scanf("%d%d%d",&n,&m1,&m2); if (m1 == 1) { printf("0"); return 0; } // If the number of tubes is 1, the conditions are met directly 若试管数为1，直接符合条件 for (i = 1; i <= n; i++) scanf("%d",&s[i]); int xx = floor(sqrt(m1)); for (i = 2; i <= xx; i++) { // Quality finding factor 找质因数 if (p[i]) { if (m1 % i == 0) { prime[size][1] = i; prime[size][2] = 1; } } int tim = 2; while (tim * i <= m1) { p[tim * i] = 0; tim; } } for (i = 1; i <= size; i++) // Number of quality finding factors 找质因数个数 { int num = prime[i][1]; while (m1 % (num * prime[i][1]) == 0) { num *= prime[i][1]; prime[i][2]; } prime[i][2] *= m2; } if (size == 0) // If it is a prime number, the prime factor is itself 若为质数，质因数为本身 { prime[size][1] = m1; prime[size][2] = m2; } for (i = 1; i <= n; i) { for (j = 1; j <= size; j) { if (s[i] % prime[j][1] != 0) // If there is no certain factor, break directly { f[i] = 150000; // Maximum: 10000 * log 2 30000 break; } int tim = 1; long long num = prime[j][1]; while (s[i] % (num * prime[j][1]) == 0) { num *= prime[j][1]; tim++; } int an = (prime[j][2]-1) / tim + 1; // Equivalent to ceil function if (an > f[i]) f[i] = an; } } for (i = 1; i <= n; i++) if (ans > f[i]) ans=f[i]; if (ans == 150000) printf("-1"); else printf("%d",ans); return 0; }

发出你的三角洲名

本篇文章只是玩梗，请不要在意 这道题一看上去非常简单，但实际上非常难！ 难在哪呢？ 这道题非常考验大家的： 输入输出、基础格式，这两个东西可是非常难的！ 在我们成为信奥人之前，这两个知识点是必须得要学会的。所以这一道题是非常重要的，几乎是比赛前的必刷题！ 那么我们来看看这道题到底该怎么写： 这道题用的是#include<iostream>的头文件（万能头也可以），和using namespace std的命名空间； 还有cin（输入函数）,cout（输出函数）。 怎么样，一共足足8行代码，结果讲解，是不是对这道题有了新的认知？快点自己也去试一下吧！ 题目链接 如有讲错，欢迎指出！感谢观看

请输入文本

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 导入 很多老师都会教自己的学生背高斯求和公式(Gauss Summation): 1+2+3+4+...+n=n(n+1)21 + 2 + 3 + 4 + ... + n = \frac{n(n + 1)}{2} 1+2+3+4+...+n=2n(n+1) 现在，我将以由简到难的顺序用多种方法来告诉大家为什么是这样的。 方法1：举例验证法 假设 nnn 的值为 777 ： 1+2+3+4+5+6+71 + 2 + 3 + 4 + 5 + 6 + 7 1+2+3+4+5+6+7 然后我们发现第一个数和倒数第一个数的和与第二个数和倒数第二个数的和相同，以此类推： (1+7)+(2+6)+(3+5)+4(1 + 7) + (2 + 6) + (3 + 5) + 4 (1+7)+(2+6)+(3+5)+4 再将式子改写为有 nnn 的式子： n−12(n+1)+n+12\frac{n - 1}{2} (n + 1) + \frac{n + 1}{2} 2n−1 (n+1)+2n+1 然后对式子进行因式分解 (n−1)(n+1)+(n+1)2\frac{(n - 1)(n + 1)+ (n + 1)}{2} 2(n−1)(n+1)+(n+1) n2−1+n+12\frac{n ^ 2 - 1 + n + 1}{2} 2n2−1+n+1 n2+n2\frac{n ^ 2 + n}{2} 2n2+n n(n+1)2\frac{n(n + 1)}{2} 2n(n+1) 再给 nnn 赋一个偶数值，这里用 666 举例： 1+2+3+4+5+61 + 2 + 3 + 4 + 5 + 6 1+2+3+4+5+6 依旧首尾相加： (1+6)+(2+5)+(3+4)(1 + 6) + (2 + 5) + (3 + 4) (1+6)+(2+5)+(3+4) 将式子改写为有 nnn 的式子： n2(n+1)\frac{n}{2}(n + 1) 2n (n+1) 化简后得出： n(n+1)2\frac{n(n + 1)}{2} 2n(n+1) 最终得出结论： 1+2+3+...+n=n(n+1)21 + 2 + 3 + ... + n = \frac{n(n + 1)}{2} 1+2+3+...+n=2n(n+1) 方法2：倒序相加法 先设 1+2+3+...+n1 + 2 + 3 + ... + n1+2+3+...+n 为 SSS： S=1+2+3+...+(n−2)+(n−1)+nS = 1 + 2 + 3 + ... + (n - 2) + (n - 1) + n S=1+2+3+...+(n−2)+(n−1)+n 用加法交换律可以得出： S=n+(n−1)+(n−2)+...+3+2*** = n + (n - 1) + (n - 2) + ... + 3 + 2 + 1 S=n+(n−1)+(n−2)+...+3+2+1 然后我们发现交换前的第一项和交换后的第一项的和与交换前第二项和交换后第二项的和相同，以于是我们将交换前的 SSS 与交换后的 SSS 相加： 2S=(1+n)+(2+n−1)+...+(n−1+2)+(n+1)2S = (1 + n) + (2 + n - 1) + ... + (n - 1 + 2) + (n + 1) 2S=(1+n)+(2+n−1)+...+(n−1+2)+(n+1) 化简一下等号右边的式子： 2S=(n+1)+(n+1)+...(n.times)2S = (n + 1) + (n + 1) + ...(n.times) 2S=(n+1)+(n+1)+...(n.times) 2S=n(n+1)2S = n(n + 1) 2S=n(n+1) n(n+1)2n(n + 1) \over 2 2n(n+1) 最终得出结论： 1+2+3+...+n=n(n+1)21 + 2 + 3 + ... + n = \frac{n(n + 1)}{2} 1+2+3+...+n=2n(n+1) 方法3：方块画图法 先画一个图表示 1+2+3+..+n1 + 2 + 3 + .. + n1+2+3+..+n： 然后复制一个并反转： 发现我们得出了一个长 (n+1)(n + 1)(n+1) 宽 nnn 的长方形，将这个正方形的面积 ÷2\div 2÷2： 最终得出结论： 1+2+3+...+n=n(n+1)21 + 2 + 3 + ... + n = \frac{n(n + 1)}{2} 1+2+3+...+n=2n(n+1) 方法4：画图分割法 还是画一个图表示 1+2+3+..+n1 + 2 + 3 + .. + n1+2+3+..+n： 然后分割出一个三角形： 发现这是一个底 nnn 高 nnn 的三角形，计算得出这个三角形的面积为 n22\frac{n ^ 2}{2}2n2 再计算剩余三角形的面积，发现有 nnn 个底 111 高 111 的三角形，经计算得出这些三角形的面积和为 n2\frac{n}{2}2n 然后化简这个式子： 最终得出结论： 1+2+3+...+n=n(n+1)21 + 2 + 3 + ... + n = \frac{n(n + 1)}{2} 1+2+3+...+n=2n(n+1) 总结 以上就是高斯求和公式的四种直观推导方法啦，‌从举例验证到几何直观，从代数推导到图形分割‌，用不同思路都推导出了同一个结论，是不是很巧妙？这个从小学就开始接触的公式，背后其实藏着代数与几何结合的数学思维，希望这些不同角度的推导，能帮你更透彻地理解这个经典公式，感受到数学推导的乐趣。 感谢你愿意花时间跟着这些思路重新梳理这个经典公式，也希望这些多元推导能给你之后的数学学习带来一点启发～

？

请输入0MB