P15743题解 作者：WHAT_ARE_YOU_DOING(洛谷UID:1908713) 未经允许，禁止发布在任何平台。 Apple_pieYES (洛谷Uid:1412516) 可以使用 此图为证 本题使用到了两个算法： 差分和前缀和 这两个算法可以说是一对兄弟，十分相似，也经常用到，我先讲前缀和吧。 前缀和： 有一个数组sum={5,7,2,9,3}sum = \{5,7,2,9,3\}sum={5,7,2,9,3}，我们要求出 sum[2]∽sum[4]sum[2] \backsim sum[4]sum[2]∽sum[4]的和，我们可以这样写： cpp 这样子写虽然方便，但是如果要执行10510^5105次求和、10610^6106次求和，甚至是10910^9109次求和，弊端这不就出来了吗？？？为了我们的代码运行时间更加的快，我们可以使用前缀和。 使用前缀和要定义一个数组，这个数组我们把他叫作 "ansansans"，ans[i]ans[i]ans[i]表示sum[0]∽sum[i]sum[0] \backsim sum[i]sum[0]∽sum[i]的和，即 {ans[0]=sum[0]ans[i]=sum[i]+ans[i−1] \begin{cases} ans[0] = sum[0] \\ ans[i] = sum[i]+ans[i-1]\\ \end{cases} {ans[0]=sum[0]ans[i]=sum[i]+ans[i−1] 这时候，有的同学就要问了：“前缀和有什么用呢，与求和有什么关系吗？” 问得好！奖励一朵小红花。 回到我们最开始的问题，我们可以把求sum[2]∽sum[4]sum[2] \backsim sum[4]sum[2]∽sum[4]的和的问题转化一下，可以变成求 (sum[0]∽sum[4])−(sum[0]∽sum[1])(sum[0] \backsim sum[4])-(sum[0] \backsim sum[1])(sum[0]∽sum[4])−(sum[0]∽sum[1]) 的值，简化了以后，也就是 sum[2]+sum[3]+sum[4]sum[2]+sum[3]+sum[4]sum[2]+sum[3]+sum[4] 的和。 而我们已经求出了 sum[0]∽sum[4]sum[0] \backsim sum[4]sum[0]∽sum[4] 和 sum[0]∽sum[1]sum[0] \backsim sum[1]sum[0]∽sum[1]的值。分别储存在了 ans[1]ans[1]ans[1] 和 ans[4]ans[4]ans[4] 里了，直接访问就可以了。 于是，我们可以写出如下代码： cpp 这时，有同学又要问了：“如果题目给我们一个前缀和数组，让我们求原数组，我们要怎么办呢？” 真棒！再奖励一朵小红花。 这时候，就到了差分出场了。 差分： 差分是前缀和的逆运算，前缀和是加，而差分是减，比如这个前缀和数组 sum={5,12,14,23,26}sum=\{5,12,14,23,26\}sum={5,12,14,23,26} 使用查分前也要定义一个数组，这个数组我们把他叫作 "ansansans"，ans[i]ans[i]ans[i]表示数组原来的值，即 {ans[0]=sum[0]ans[i]=sum[i]−sum[i−1] \begin{cases} ans[0] = sum[0] \\ ans[i] = sum[i]-sum[i-1]\\ \end{cases} {ans[0]=sum[0]ans[i]=sum[i]−sum[i−1] 把我们之前的代码改一下，我们可以写出如下代码： cpp 输出： 与前缀和不同的是：前缀和可以在原数组上做出更改，但是差分不可以在原数组上更改，运行下面的两个代码就可以知道了。 代码如下(CPP) 前缀和代码 输出： 差分代码 输出： 而正确的输出是： 所以，我们在使用差分时要注意哦！！！ 这时有同学提问了：“差分又有什么用呢？” 你真是太棒了！奖励一朵小黄花！！！ 我们新建一个数组 ans[5]ans[5]ans[5]，把 ansansans 清000，然后我们把ans[0]ans[0]ans[0] 加111。 这个时候，数组ansansans为： 而这个数组的前缀和数组为： 我们只用把ans[i]ans[i]ans[i]加111,ans[i]ans[i]ans[i]后面的所有值也都自动加111了。 所以： 把ans[i]ans[i]ans[i]加222,ans[i]ans[i]ans[i]后面的所有值也都自动加222了; 把ans[i]ans[i]ans[i]减111,ans[i]ans[i]ans[i]后面的所有值也都自动减111了。 我们再把ans[3]ans[3]ans[3]减去111，这时候，前缀和数组变为： 利用这个性质，我们就可以解决这道题了。 题目传送门 因为怪物会经过每一个格子，所以我们先计算出经过每一个格子，怪物会受到的伤害总数。 因为怪物在士兵的攻击范围内，都会受到111点伤害，所以我们用一个初始值全部为零的数组ansansans存伤害，每次输入两个数（LiL_iLi 和RiR_iRi ）时，我们将ans[Li]+1ans[L_i]+1ans[Li ]+1，ans[Ri+1]−1ans[R_i+1]-1ans[Ri +1]−1，在输入完成后，我们只用算一下前缀和，就可以得出怪物经过每一个格子所受到的伤害了。 剩下的代码，我相信你们会写。 对了，我要提醒一句： 十年ＯＩ一场空，不开LONG LONG 见祖宗 话不多说，上代码： 谢谢参考题解，如果有建议，欢迎各位大佬提出！！！ 广告： 我的洛谷团队

·cout<<"原神万岁"; 队长： @G.R.W_原神限定版(关必回) ·TLE 兵团 队长：@TLE君(必回关） ·༺ཌༀཉི༒社畜༒༃ༀད༻ 队长：@༺ཌༀཉི༒社畜鼠༒༃ༀད༻ ·COCR / COCI联合命题委员会 队长：@CuSn ·RE 队长：zyyÆ挜‱ ·AC局————无限进步 队长：小殳殳 其他有想成为合作团队的同学可以私信@AC君

一、初等数论 初等数论是GESP五级考试中的重要考点之一，主要包括素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性等内容。 1. 素数与合数 素数是大于1的自然数，只能被1和自身整除；合数是能被其他数整除的数。判断素数的方法有试除法和线性筛法等。 2. 最大公约数与最小公倍数 最大公约数（GCD）和最小公倍数（LCM）是数论中的基本概念。欧几里得算法（辗转相除法）是求解GCD的高效方法。（我更倾向于使用__gcd()和__lcm()） 3. 同余与模运算 同余是指两个数对模m的余数相同，模运算在密码学、哈希算法等领域有广泛应用。 4. 质因数分解 质因数分解是将一个正整数表示为若干个质数的乘积。唯一分解定理指出每个大于1的整数都可以唯一地表示为质数的乘积。 二、高精度计算 在C++中，当整数超出普通数据类型的范围时，需要使用高精度计算。高精度计算通常通过数组模拟实现。（有些时候用int_128也不是不行） 1. 数组模拟高精度加法 高精度加法的思路类似于手工加法，从个位开始逐位相加，并处理进位。数组中存储数字时，通常将个位放在数组下标为0的位置。 2. 数组模拟高精度乘法 高精度乘法通过模拟手工乘法实现，即将一个大数的每一位与另一个大数的每一位相乘，然后将结果累加。 3. 数组模拟高精度减法与除法 减法和除法的实现方式与加法和乘法类似，分别模拟手工减法和除法的过程。 三、链表 链表是一种动态数据结构，具有插入和删除操作高效的特点。GESP五级要求掌握单链表、双链表、循环链表的基本操作。 1. 单链表 单链表的每个节点包含数据和指向下一个节点的指针。插入和删除操作需要修改指针。 2. 双链表 双链表的每个节点包含数据和指向前后两个节点的指针，支持双向遍历。 3. 循环链表 循环链表的最后一个节点指向第一个节点，形成一个环。 四、算法复杂度估算 掌握算法复杂度估算方法是GESP五级考试的重点之一。包括多项式、对数等复杂度的分析。 1. 时间复杂度 时间复杂度用来衡量算法执行时间随输入规模增长的变化趋势。例如，线性时间复杂度为O(n)，对数时间复杂度为O(log n)。 2. 空间复杂度 空间复杂度用来衡量算法所需存储空间随输入规模增长的变化趋势。 五、其他算法与数据结构 1. 二分查找与二分答案 二分查找是一种高效的查找算法，适用于有序数组。二分答案则是在答案空间上进行二分，常用于优化问题。（这东西应该没人不会吧） 2. 贪心算法 贪心算法在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的。 3. 递归算法 递归是函数调用自身的编程技术。递归算法的实现需要明确基础情况和递归情况。 4. 分治算法 分治算法将问题分解为若干个规模较小的子问题，递归求解子问题，然后合并子问题的解得到原问题的解。（这玩意儿应该都懂的） 另外，我写这东西花了1个小时，留下一个免费的赞赞和收藏吧 ！！！！！！！！！！！！！！！！！！！！！！🎉🎉🎉🎉🎉

火影单挑来：世一美白洲梓

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 团队 求关=（

https://www.acgo.cn/application/1971120674621140992

谁懂研究代码半天结果发现是没打换行时是有多么绝望

为什么像cjj dream92143 AK不了IOI这些大佬不升分数呢？明明还可以参加竞赛，却没人升呢？真的有人升到传奇王者吗这个问题困扰我好久了

666

nb666

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 小广告

堵桥无敌

这个竞赛还有78小时才结束，我该怎么办？ ACGO挑战赛#29

二、C++ STRING 常用操作整理 操作 说明 使用例子 s2 = s1 将 s1 的内容赋给 s2（若 s2 原来有内容，则直接覆盖） string s1 = "hello"; string s2; s2 = s1; // s2 变为 "hello" s1 + s2 把 s1 和 s2 连接成一个新字符串，返回新生成的字符串 string a = "abc"; string b = "def"; string c = a + b; // c = "abcdef" s1 += s2 把 s2 拼接在 s1 后面 string s = "hello"; s += " world"; // s = "hello world" s1 == s2 比较 s1 与 s2 的内容，相等则返回 true，否则返回 false if (s1 == s2) cout << "相等"; // 比较两个字符串内容是否相同 !=, <, <=, >, >= 保持这些操作符惯有的含义，比较大小时按照字典序进行比较 if (s1 < s2) cout << "s1 排在前面"; // "abc" < "abd" 返回 true s.size() / s.length() 返回 s 中字符的个数，也称为字符串的大小 string s = "hello"; int len = s.size(); // len = 5 int len2 = s.length(); // 也是 5 s.empty() 如果 s 为空串，则返回 true，否则返回 false string s; if (s.empty()) cout << "字符串为空"; // 输出"字符串为空" s.insert(pos, s2) 在 s 下标为 pos 的元素前插入 string 类型 s2 string s = "hello"; s.insert(2, "123"); // s 变为 "he123llo" s.substr(pos, len) 返回一个 string 类型，它包含 s 中下标为 pos 起的 len 个字符 string s = "hello world"; string sub = s.substr(6, 5); // sub = "world" s.erase(pos, len) 删除 s 中下标为 pos 开始的 len 个字符 string s = "hello world"; s.erase(5, 6); // s 变为 "hello" s.replace(pos, len, s2) 删除 s 中下标为 pos 的 len 个字符，并在下标为 pos 处插入 s2（即替换） string s = "I like C"; s.replace(7, 1, "C++"); // s 变为 "I like C++" s.find(s2, pos) 在 s 中下标为 pos 的位置起查找 s2 第一次出现的下标，若查找不到返回 string::npos string s = "hello world"; int pos = s.find("world", 0); if (pos != string::npos) cout << "找到了，位置：" << pos; // 输出：找到了，位置：6 s.clear() 清空 s 中的内容 string s = "hello"; s.clear(); // s 变为空字符串 "" reverse(s.begin(), s.end()) 将字符串 s 反转（需要包含 <algorithm> 头文件） #include <algorithm> string s = "hello"; reverse(s.begin(), s.end()); // s 变为 "olleh" ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

49篇题解全没：

给点赞吧

最标准的答案是【一秒退化！头，甲，枪，胸挂，背包，鼠来！】o((>ω< ))o

就算是cstsio，内存也会超出1M

·专攻难题团队（1号附属团） ·专攻难题团队（2号附属团）

发帖前请仔细阅读：acgo讨论发帖规范、社区公约，如有违规行为可能会被删帖或禁言