1.完成大量橙题 2.完成一些分治黄题 3.重新复习逆元，完成T4部分分 4.复习对拍 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 达成成就1：终于学会了在赛场上用较短时间写黄题！ 达成成就2：忘掉了部分橙题怎么写！ P11246 与完全平方数/平方数/倍数有关的n=1e5，要么是O(nlogn)要么是O(nsqrt(n)) n=1e5.sqrt(n)的可能性更大（由于评测集性能的提升，现在O(nlogn)似乎更流行5e5或者是1e6） O(nsqrt(n))就考虑双重循环之类的吧。 比如动态规划。 单独加练三道动态规划。 其实，到黄题绿题阶段，很单纯的O(n^2)动态规划我已经很久没有见过了（当然，我见得也比较少） 我的意思是，如果提高组T1出现了O(nm)差不多时间复杂度的算法，可以往动态规划上去想一想。 因为，一道题目是否需要动态规划，我自己也无法直接分清。 大部分除了二分这种非常明显的提示性算法，想要得出正解似乎就是要往时间复杂度和题目大意去分析。 注意 dp很容易爆long long

核桃、ZDZL同步更新 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目描述 有 N 个正整数，现对 N 个正整数进行不同方式的排列，每次排列后都会按照以下规则进行一次计算： 计算规则： 第一次：第一个数乘以第二个数乘以第三个数，结果记录为M(1)； 第二次：第二个数乘以第三个数乘以第四个数，结果记录为M(2)； 第三次：第三个数乘以第四个数乘以第五个数，结果记录为M(3)； 第N-2次：第N-2个数乘以第N-1个数乘以第N个数，结果记录为M(N-2) 最后计算M(1)+M(2)+M(3)......M(N-2)的数值。 聪明的小蓝发现，排列方式不同，最后计算出的结果也不相同。请找出一种排列方式使这个数值最大。 例如：N=4，4个正整数分别为1，2，3，4，那么排列方式就会有24种；其中排列方式为1，3，4，2时，按照规则计算2次： 134=12 342=24 乘积相加：12+24=36 这种排序方式是所有乘积相加的数值最大，为36。 输入描述 输入N个正整数(3≤N)，正整数之间一个英文逗号分开 输出描述 找出所有乘积相加的数值最大的排列方式，并输出数值 输入示例 1,2,3,4 输出示例 36 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3 行代码征服蓝桥杯：一道贪心算法题的深度解析 前言 2022 年蓝桥杯青少组 Python 编程省赛中，有一道题以其极简的代码实现和深刻的算法思想令人印象深刻。题目要求对 N 个正整数进行排列，使得连续三个数的乘积之和最大。而最让人惊叹的是，这道省赛真题的最优解只有 3 行代码。本文将带你从问题分析、思路推导、代码解析等多个维度，完整解读这道题的来龙去脉。 一、问题理解与初步分析 1.1 题目核心 给定 N 个正整数，我们需要将它们排列成一个序列。排列完成后，按照特定规则进行计算：第一个数乘以第二个数乘以第三个数得到 M(1)，第二个数乘以第三个数乘以第四个数得到 M(2)，依此类推，直到第 N-2 个数乘以第 N-1 个数乘以第 N 个数得到 M(N-2)。最终目标是计算 M(1) 加 M(2) 加 M(3) 一直加到 M(N-2) 的总和，并找出使这个总和最大的排列方式。 1.2 示例验证 以 N=4，数字为 1、2、3、4 为例。如果排列为 1、3、4、2，那么计算过程如下：第一次计算是 1 乘以 3 乘以 4 等于 12，第二次计算是 3 乘以 4 乘以 2 等于 24，最终总和是 12 加 24 等于 36。经过验证，这个排列方式确实能得到所有 24 种排列中的最大值。 二、从暴力枚举到规律发现 2.1 暴力枚举的困境 面对这道题，最直观的想法是枚举所有可能的排列，计算每种排列的乘积和，然后取最大值。Python 的 itertools 模块提供了 permutations 函数可以轻松实现这一点。然而，当 N 增大时，排列数量呈指数级增长。N=4 时有 24 种排列，N=6 时有 720 种，N=8 时有 4 万多，N=10 时更是达到 360 多万。对于竞赛题目来说，N 可能达到几十甚至上百，暴力枚举完全不可行。 2.2 手动分析小例子 既然暴力枚举行不通，我需要从手动分析小例子中寻找规律。我尝试了 N=4 时的多种排列，发现最优排列并不是简单的正序或逆序。正序 1、2、3、4 的结果是 30，逆序 4、3、2、1 的结果也是 30，而最优排列 1、3、4、2 的结果是 36。这个发现让我意识到，最优排列具有某种特殊的结构。 2.3 关键洞察：位置权重的发现 我仔细分析了每个位置上的数在计算中参与了多少次乘法运算。第一个数只参与了 M(1) 的计算，第二个数参与了 M(1) 和 M(2) 的计算，第三个数参与了 M(1)、M(2) 和 M(3) 的计算。继续分析下去，我发现了一个重要规律：中间位置的数参与 3 次运算，次边缘位置的数参与 2 次运算，而两端的数只参与 1 次运算。 这个发现是解题的关键。既然中间位置的数参与运算的次数最多，那么为了让总和最大，就应该把最大的数放在中间位置。同理，两端位置的数参与次数最少，应该放最小的数。这就是典型的贪心思想：在每一步都选择当前最优的决策，从而得到全局最优解。 三、贪心策略的构建 3.1 策略的核心思想 基于位置权重的分析，我得出贪心策略的核心思想：让参与次数越多的位置，放置越大的数。具体来说，排序后的数组中，最大的数应该放在参与 3 次运算的中间位置，最小的数应该放在只参与 1 次运算的两端位置。 3.2 构造最优排列 如何构造这样的排列呢？我尝试了多种方案，最终发现了一个简洁有效的方法：将排序后的数组分成两部分，偶数索引位置的数按正序排列，奇数索引位置的数按逆序排列，然后将两部分合并。 以 N=4，排序后为 1、2、3、4 为例。偶数索引位置是 0 和 2，对应的数是 1 和 3。奇数索引位置是 1 和 3，对应的数是 2 和 4。将奇数索引的数反转后得到 4 和 2。合并后得到 1、3、4、2，这正是最优排列。 3.3 策略的验证 为了验证这个策略的正确性，我测试了多个例子。N=5 时，排序后为 1、2、3、4、5，构造出的排列是 1、3、5、4、2，计算结果是 115。而原序排列 1、2、3、4、5 的结果是 90，新构造的排列明显更优。N=3 时，构造出的排列是 1、3、2，计算结果是 6，这也是最优解。 四、代码实现的诞生 4.1 第 1 行：数据准备 代码的第一行负责读取输入并排序。输入是逗号分隔的字符串，需要先按逗号分割，再转换为整数，最后排序。我使用了 map 函数将分割后的字符串列表转换为整数列表，然后用 sorted 函数进行排序。这样一行代码就完成了数据准备的所有工作。 4.2 第 2 行：核心算法 代码的第二行是最关键的部分，它实现了贪心策略的构造。a:2 表示从索引 0 开始，每隔一个取一个数，得到偶数索引位置的数。a[1::2] 表示从索引 1 开始，每隔一个取一个数，得到奇数索引位置的数。:-1 表示将奇数索引位置的数反转。最后将两部分合并，就得到了最优排列。 这个切片操作非常巧妙，它用一行代码完成了复杂的排列构造。理解这个操作需要熟悉 Python 的切片语法，但一旦理解，就会发现它既简洁又高效。 4.3 第 3 行：结果计算 代码的第三行负责计算最终结果。我使用生成器表达式遍历所有可能的连续三个数的组合，计算它们的乘积，然后用 sum 函数求和。range(len(d) – 2) 确保了遍历的起始位置不会超出范围，自动处理了边界情况。 使用生成器表达式而不是列表推导式，虽然在这个场景下内存差异不大，但这是良好的编程习惯，体现了对内存效率的意识。 五、算法正确性的深入理解 5.1 数学直觉 从数学角度看，乘积运算有一个重要特性：大数乘以大数再乘以大数，结果远大于小数乘以小数再乘以小数。因此，在加权求和中，参与次数越多的位置，放置越大的数，收益就越高。这就是贪心策略成立的数学基础。 5.2 与其他排列的对比 为了更直观地理解最优性，我对比了多种排列方式。原序排列 1、2、3、4 的结果是 30，逆序排列 4、3、2、1 的结果也是 30，而最优排列 1、3、4、2 的结果是 36。这个对比清楚地展示了贪心策略的优势。 六、性能分析 6.1 时间复杂度 整个算法的时间复杂度主要由排序操作决定，为 O(N log N)。切片构造和求和计算都是线性时间操作，不会成为瓶颈。这个时间复杂度已经是最优级别，因为任何算法至少需要 O(N log N) 来完成排序。 6.2 空间复杂度 算法的空间复杂度为 O(N)，主要用于存储排序后的数组和构造的排列。这个空间占用是线性的，对于大多数应用场景来说完全可以接受。 6.3 与暴力枚举的对比 暴力枚举的时间复杂度是 O(N! × N)，当 N 增大时，运行时间呈指数级增长。而本解法的时间复杂度是 O(N log N)，当 N=10 时，运行时间不到 1 毫秒，而暴力枚举根本无法完成。这个对比清楚地展示了贪心算法的优势。 七、代码优势与改进建议 7.1 代码优势 这段代码的最大优势是简洁性。3 行代码完成了复杂逻辑的实现，体现了 Python 语言的特有魅力。同时，代码的效率优秀，时间复杂度和空间复杂度都是最优级别。此外，代码充分利用了 Python 的内置函数和语法特性，如 sorted、map、切片和生成器表达式，这些都是 Python 编程的精髓。 7.2 改进建议 虽然这段代码在竞赛场景下已经非常优秀，但如果用于教学或生产环境，可以考虑添加注释以提升可读性，添加输入验证以处理异常情况，以及将计算逻辑封装成函数以便于测试和复用。 八、给学习者的建议 8.1 遇到类似题目时的思考路径 遇到这类优化问题时，建议按照以下路径思考：先尝试暴力枚举理解问题，然后手动分析小例子寻找规律，接着分析每个元素的权重或贡献，最后设计贪心策略并实现代码。这个思考路径可以帮助系统地解决类似问题。 8.2 Python 竞赛技巧 在 Python 竞赛中，善用内置函数如 sorted、map、sum 等可以大幅减少代码量。理解切片语法 a:2、a:-1 等可以写出更简洁的代码。使用生成器表达式可以节省内存。保持代码简洁可以减少出错概率，提高竞赛效率。 8.3 心态建议 不要害怕写看起来”看不懂”的代码，只要自己能理解、能验证，就是好代码。赛后可以优化代码的可读性，但竞赛中要追求效率和正确性。算法竞赛的魅力在于找到最优的解决方案，而不是写出最”漂亮”的代码。 九、总结 这道题是贪心算法的经典应用，核心思想是让参与次数越多的位置，放置越大的数。通过巧妙的切片操作，我们可以在 O(N log N) 的时间内构造出最优排列，得到最大乘积和。 学习这道题，可以掌握以下几个要点：理解每个位置参与运算的次数，掌握贪心算法的核心思想，熟练运用 Python 切片操作，学会对比不同解法的优劣。这些能力对于提升算法水平和编程能力都大有裨益。

求大致难度以及做法 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T827753 [模拟赛 #1] 百鸟朝凤 题目描述 群鸟和鸣，百鸟来朝。为了迎接凤凰，山林中的鸟儿正在演练朝凤阵列。 山林中有 nnn 群鸟从左到右依次排列。我们用一个正整数序列 (v1,v2,…,vn)(v_1,v_2,\ldots,v_n)(v1 ,v2 ,…,vn ) 表示当前的鸟群排列，其中第 iii 个数 viv_ivi 表示从左到右第 iii 群鸟的数量。我们称这样的序列为一个鸟群序列。初始鸟群序列为 (v1,v2,…,vn)(v_1,v_2,\ldots,v_n)(v1 ,v2 ,…,vn )。 你可以按任意顺序指挥鸟群进行若干次合并。每次操作可以选择当前鸟群序列中两个相邻且鸟数相同的鸟群，将它们合并为一群，合并后的鸟数为原来两群鸟数之和，其余鸟群的相对顺序保持不变。例如，鸟群序列 (2,2,4,8)(2,2,4,8)(2,2,4,8) 可以经过一次合并变为 (4,4,8)(4,4,8)(4,4,8)，还可以继续合并为 (8,8)(8,8)(8,8)。每进行一次合并，鸟群序列的长度减少 111。你可以进行任意次合并，也可以一次都不合并。 从初始鸟群序列出发，通过若干次合并，可以得到若干种不同的鸟群序列。同一个鸟群序列可能由不同的合并顺序得到，但只计算一次。两个鸟群序列相同，当且仅当它们的长度相同，并且对应位置上的鸟数全部相同；否则认为它们不同。 请你求出，从初始鸟群序列出发，一共能够得到多少种不同的鸟群序列。由于答案可能很大，请输出答案对 998244353998244353998244353 取模后的结果。 输入格式 第一行一个正整数 nnn，表示初始鸟群序列的长度。 第二行 nnn 个正整数 v1,v2,…,vnv_1,v_2,\ldots,v_nv1 ,v2 ,…,vn ，依次表示初始鸟群序列中从左到右各群鸟的鸟数，相邻两个数之间用一个空格隔开。 输出格式 输出一行一个整数，表示能够得到的不同鸟群序列的数量对 998244353998244353998244353 取模后的结果。 输入输出样例 #1 输入 #1 输出 #1 输入输出样例 #2 输入 #2 输出 #2 输入输出样例 #3 输入 #3 输出 #3 输入输出样例 #4 输入 #4 输出 #4 说明/提示 样例解释 样例 1 解释 下图给出了从初始鸟群序列 (1,1,1,1,1,1)(1,1,1,1,1,1)(1,1,1,1,1,1) 出发能够得到的鸟群序列，以及其中的部分合并关系： 包括初始序列本身在内，共可得到 181818 种不同的鸟群序列。 数据规模与限制 对于 10%10\%10% 的数据，n≤10n\le 10n≤10。 对于另外 20%20\%20% 的数据，n≤2000n\le 2000n≤2000。 对于另外 15%15\%15% 的数据，所有 viv_ivi 相等。 对于另外 15%15\%15% 的数据，所有 viv_ivi 均为 222 的非负整数次幂。 对于 100%100\%100% 的数据，1≤n≤1061\le n\le 10^61≤n≤106，1≤vi≤1091\le v_i\le 10^91≤vi ≤109。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T827752 [模拟赛 #1] 卡农 题目描述 在卡农中，一个声部奏出旋律后，其他声部会按一定规则依次模仿并与之呼应。为了记录一首特殊作品中各段旋律的演奏次序，乐谱采用了一棵满二叉树来组织这些音符。 这棵树的高度为 hhh，共有 n=2h−1n=2^h-1n=2h−1 个结点。结点编号为 1∼n1\sim n1∼n，其中 111 号结点为根。对于每个非叶结点 uuu，它的左儿子为 2u2u2u，右儿子为 2u+12u+12u+1。 每个结点上放着一个用正整数表示的音符。设结点 uuu 上的音符为 aua_uau ，保证 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 恰好构成 1∼n1\sim n1∼n 的一个排列。 演奏时，音符按照这棵树的中序遍历顺序依次奏出：对于任意结点 uuu，先演奏它左子树中的所有音符，再演奏结点 uuu 上的音符，最后演奏它右子树中的所有音符。 图：以 h=3h=3h=3 为例：结点上的音符与中序遍历 如果最终听到的音符依次恰好为 1,2,…,n1,2,\ldots,n1,2,…,n，则称这次演奏是完美的。 为了调整各段旋律的先后次序，你可以对任意非叶结点 uuu 进行一次调整：交换结点 uuu 的整棵左子树和整棵右子树。进行这次调整需要付出 cuc_ucu 的代价。 排练过程中，乐谱会发生 qqq 次修改。每次修改给出两个结点 x,yx,yx,y，交换这两个结点上的音符（并不交换结点本身）。每次修改都会永久保留，并影响之后的修改。 在每次修改之后，请你求出：至少需要付出多少总代价，才能通过若干次调整使演奏变得完美。如果无论怎样调整都无法得到完美的演奏，输出 −1-1−1。 注意，调整仅用于计算当前这次修改后的答案，不会保留到之后的修改中。处理下一次修改时，树的左右儿子关系恢复为初始状态，仅此前对结点上音符的修改会保留。 输入格式 第一行两个整数 h,qh,qh,q，分别表示树的高度和修改次数。 第二行 nnn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an ，其中 aua_uau 表示初始时结点 uuu 上的音符。 第三行 2h−1−12^{h-1}-12h−1−1 个整数 c1,c2,…,c2h−1−1c_1,c_2,\ldots,c_{2^{h-1}-1}c1 ,c2 ,…,c2h−1−1 ，其中 cuc_ucu 表示对非叶结点 uuu 进行一次调整的代价。当 h=1h=1h=1 时，这一行为空行。 接下来 qqq 行，每行两个整数 x,yx,yx,y，表示一次修改：交换结点 xxx 与结点 yyy 上的音符。xxx 可能等于 yyy。 输出格式 输出 qqq 行，第 iii 行一个整数，表示第 iii 次修改之后使演奏变得完美所需的最小总代价；若无法使演奏变得完美，输出 −1-1−1。 输入输出样例 #1 输入 #1 输出 #1 输入输出样例 #2 输入 #2 输出 #2 输入输出样例 #3 输入 #3 输出 #3 输入输出样例 #4 输入 #4 输出 #4 说明/提示 样例解释 样例 1 解释 树高 h=4h=4h=4，共 151515 个结点，非叶结点为 1∼71\sim 71∼7。下图每一行对应一次修改：左侧为修改后的乐谱，右侧为进行调整后的结果。圆内的数字为结点上的音符，圆下方的数字为结点编号；加粗的结点及音符为本次修改中交换的音符所在位置，灰色的结点为需要调整的结点。 图：样例 1 中各次修改及调整后的乐谱 * 第 111 次修改交换结点 8,98,98,9 上的音符。此时调整结点 1,3,4,51,3,4,51,3,4,5 即可使演奏变得完美，总代价为 5+8+2+6=215+8+2+6=215+8+2+6=21，输出 212121。 * 第 222 次修改交换结点 10,1110,1110,11 上的音符。此时调整结点 1,3,41,3,41,3,4 即可，总代价为 5+8+2=155+8+2=155+8+2=15，输出 151515。 * 第 333 次修改交换结点 2,32,32,3 上的音符。此时无论怎样调整，都无法使演奏变得完美，输出 −1-1−1。 样例 2 解释 该组样例满足 h≤10h\le 10h≤10，q≤1000q\le 1000q≤1000。 样例 3 解释 该组样例满足 h≤10h\le 10h≤10，q≤1000q\le 1000q≤1000，且每次修改中 xxx 与 yyy 至少有一个等于 111。 样例 4 解释 该组样例满足 h=18h=18h=18，q=105q=10^5q=105。 数据规模与限制 对于 15%15\%15% 的数据，h≤4h\le 4h≤4，q≤10q\le 10q≤10。 对于另外 20%20\%20% 的数据，h≤10h\le 10h≤10，q≤1000q\le 1000q≤1000。 对于另外 20%20\%20% 的数据，所有 cuc_ucu 相等。 对于另外 15%15\%15% 的数据，每次修改中 xxx 与 yyy 至少有一个等于 111。 对于 100%100\%100% 的数据，1≤h≤201\le h\le 201≤h≤20，1≤q≤3×1051\le q\le 3\times 10^51≤q≤3×105，1≤cu≤1091\le c_u\le 10^91≤cu ≤109，1≤x,y≤2h−11\le x,y\le 2^h-11≤x,y≤2h−1。

洛谷上 WA ACGO 上 AC

if(k<0 || k>n) { cout << 0; return 0; } cout << a[n][k]; return 0; }

太难了.

#include <bits/stdc++.h> using namespace std; int a,b,c,d; int main(){ }

#include <bits/stdc++.h> using namespace std; int a,b,c,d; int main(){ } 测试点信息： PE PE❌

赛事估分100+56+56+9 实际分数100+56+56+0 最后一题捆绑我不知道为什么第一个部分分坠机了一个点导致-9. T1 还行。正常发挥 T2 花了一个小时想赌正解结果**失败。 T3 还行，稳定发挥。 T4 不知道怎么了。我把考试时间记成8:00-12：00了。应该是8:30-12:30 我以为马上要结束了给我急死了。结果没有。 可以优化的点：下次考试把筹码拿齐了再**。不要做没有准备的事情。

Deep欠揍AI，正式出世！ 上面看到的是我8月中所发布的一篇帖子，讲述了我做的一个AI。 看过的都知道，我当时做的可谓是拉完了，乱说神秘文字，语句极不通顺。 而经过一个半月的沉淀，我，又回来了！！ 废话不多说，先上链接： https://www.showyourcode.app/zh/share/7padnimur4rld1 这次我十分的信心十足，先说说我更新了啥： 数学：数值搞到了-2^255 ~ 2^255-1，小数位数搞到20位，并且新增无穷级数求和。 语文：依旧拉完了，但毕竟是纯前端，没有API，语文肥肠难搞。 历史：会了点中国历史和世界史，后续会持续更新。 科学（物化生）：就会点物理学家名人，依旧会持续更新。 英语：这次是提升最大的一个，建了一个单词表（隐藏彩蛋：mj->蜘蛛侠），还专门搞了中文/英语模式，会英语缩写（如I'm. I can't），开头字母大写也能自动识别。 其次，这里再来宣传一下我的工具大全，链接： https://www.showyourcode.app/zh/share/nemvi2mur1kp11 现在急需要一个会后端的来帮帮忙，有意向的可以在评论区报名。 随机AT一波： @《渡鸦》 @豆瓣 @༺ཌༀཉི 花༒竹༃ༀད༻ @Deep某帅黑客919轩辕少族长 @B&G @某黑 @复仇者_x ‮@XXX@🥥@蒋一瑞

难受香菇😇

这是一道构造题。 构造题的突破口就是多找找特殊情况，推规律，或者……看大样例！ 还有，一般题目给出的部分分里也会包含一些特殊的情况，而剩下的就是大众情况。 其实是带着一点贪心思想的。 我们肯定希望弄出来的序列是有同色阻碍的。 并且，题目给出简单图的限制，也就是说没有环。 那我们就可以这样想：我们希望异色的点之间相互到达不了，同色的点聚集在一块。 我们可以先用完一个颜色的点，并且是BFS式的涂色而不是DFS式的涂色。 那么一个想法就出来了：我们将点1和与其相连的点都尽量染成一个颜色。 此时有两种情况： 1.点1出度>红色数量 那么我们需要做的就是把点一和与它直接相连的点全部都染成红色。 2.点1出度<红色数量 我们依然把点1和它直接相连的点染成红色，剩下的红色定点随机安排即可。

我擦懒得跑了太无语了[:流汗][:流汗][:流汗][:流汗]流汗

每日一题 A70081号题解 t题目： Description of the question Given three positive integers representing the lengths of three line segments, determine whether these three segments form a triangle. If a triangle can be formed, output "yes"; otherwise, output "no". Input format The input consists of one line containing three positive integers, each representing the length of three line segments, separated by a space. Output format If a triangle can be formed, output "yes"; otherwise, output "no". t题解 记得三连哦！！！

1.十分的动态规划基础部分分 完全应该想到的部分，但是没有想到。解决方法：完成相似的动态规划一题。 最长上升子序列 这两中做法应该是相似的吧。 同样是以xxx为结尾，满足xxx条件的xxx 而这边由于我们的数字就是在1~10^6的范围之内的，所以我们可以直接将数值作为下标。 那么我们就可以得出一个定义：设g[a][b]为最后两项是a<b的合法序列数。 先用长度为2的序列初始化g[a][b]=1，再按b从小到大转移，枚举c>b且需要满足条件abc!=0（这里^是异或）。 哦。补充一下为什么是这样设计状态的：最长上升子序列中，约束条件其实是两两之间的（即，要求a[i]<a[j]） 而那时，我们只需要一个维度。 而现在约束状态存在于三者之间，所以最简单的，我们会想到要使用二维动态规划。 刚刚在完成这部分代码的时候稍微调试了一下：注意注意注意一定要注意！异或的优先级特别特别低！一定要在异或运算时加括号！！！ 2.正难则反 这是一个非常经典的解题技巧，在很多方面都能用到：包括但不限于：绿题核心思路，绿题难度以上题目的部分分优化方案。 这是在题目方面的，那什么情形能够用到它？ 1.求合法方案数 当直接求取合法方案数太过困难，我们可以反向求取不合法方案数（这种方案似乎一般叫做容斥） 2.两者相互制约 当题目给出两种东西：比如拿串子串烤肉，用脚踩草地，吃草 这种一方答案与另一方息息相关的情况下，我们需要学会转变思路。 与其想串子串了哪串烤肉，不如想哪串烤肉被串起。 那么这道题目也是相同的。我们与其计算枚举符合要求的数列，不如去计算不符合要求的数列。 设f[x]为以x结尾的合法序列数，s[x]=f[1]+f[2]+f[3]+...+f[x] 那么此时我们有：f[x]=s[x-1]+1-接上之后不符合要求的数 （那个1是x本身） 那么，我们如何去计算接上之后不符合要求的数？ 我们已经完成了一个类似于最长上升子序列的问题，那么现在的约束条件就是异或。 原先是合法的序列，连接上x之后变得不合法，那么只有可能是最后三项不合法，不合法的条件： abx=0，b=a^x （我们一般选特殊项都选中间的，应为它左右两边都有数值） 现在x已经定下来，我们去枚举a，可以看出当x和b都已经确定，a是唯一的。 这里需要一个证明：任意以a结尾的合法序列，连接上b之后都是合法的。 那么我们可以得知，最后包含a,b的不合法最后三项一定是(a,b,x) 但是由于大小关系的约束，它们的顺序能且只能是a,b,x。 那么最后，a的范围就是1<=a<(a^x)<x 补充一个想到一维动态规划的思路： 我们可以发现，在最长上升子序列的基础上，这道题目还给出了额外的约束条件。 那么我们就可以先做一个普通的最长上升子序列，而后再搞出不满足另一个约束条件的序列数量，将它们相减。 特别补充：负数取模要(+P)%P！！！已经错过好多次啦！！！

原题链接 1 题目 1.1 题目所需求出内容 对于本题，最终要求：操作次数的最小值 1.2 题目背景、允许、禁止与限制 背景：有一个长度为 nnn 的只含 −1,0,1-1,0,1−1,0,1 三种数字序列x 允许：每次操作可将 xi+1x_{i+1}xi+1 变为 xi+1+xix_{i+1}+x_ixi+1 +xi ，对于每个 xix_ixi 都可以是无限大的数字 禁止： 限制：最终要求将整个序列变为非递减序列 1.3 题目数据范围与猜测 1≤n≤1000000⟶O(n)1 \le n \le 1000000 \longrightarrow O(n)1≤n≤1000000⟶O(n) 1.4 一句话概括题意 在一个序列中进行操作，每次操作可以使 xi+1x_{i+1}xi+1 变为 xi+1+xix_{i+1}+x_ixi+1 +xi ，求这个序列转化为非递减序列所需的最小操作次数 2 题目破题推导 2.1 第一步：分情况讨论与数学计算结合 * 当前这位如果是 −1-1−1，要想变成 111，必须要前一位是 111 的情况下操作两次；要想变成 −1-1−1，不用操作；而无论用什么方式，都无法使 −1-1−1 变成 000 为什么说无论用什么方式，都无法使 −1-1−1 变成 000，因为这题中有个要求是“非递减”。要使 −1-1−1 变成 000，就必须要这一项之前是 111，但如果这一项之前是 111，这一项是 000，就不满足非递减了，因此不考虑这种方案 * 当前这位如果是 000，要想变成 111，必须要前一位是 111 的情况下操作一次；要想变成 −1-1−1，必须要前一位是 −1-1−1 的情况下操作一次；而要想变成 000 则无需操作 * 当前这位如果是 111，要想变成 −1-1−1，必须要前一位是 −1-1−1 的情况下操作两次；要想变成 111，不用操作；而要想变成 000 ，必须是前一项是 −1-1−1 的情况下操作1次 3 模型匹配 先提取关键词：前面的操作影响后面的结果、只和特定的几位有关系、求满足条件下的最小值 那不用说了，一定是 动态规划\huge{动态规划}动态规划 4 具体方案 4.1 动态规划定义（重点） 首先，先建立 dp 数组 设置 dpidp_idpi 表示以 iii 为结尾时，使序列符合条件所需的最小操作次数 但是出现了问题，我们无法确定当前考虑的这一项是什么，无法推导，因此考虑扩维 定义 dp[i][k](0≤k≤2)dp[i][k](0 \le k \le 2)dp[i][k](0≤k≤2) 表示以 iii 为结尾时并且当前这个位置的数字是 k−1k-1k−1 时，使序列符合条件所需的最小操作次数 4.2 初始化 求最大值，所以dp数组每一项都设为小值，除了 dp[i][a[1]+1]dp[i][a[1] + 1]dp[i][a[1]+1] 设置为极大值 4.3 状态转移方程 我们的定义清晰了，合法方案也清晰了，因此直接就是（懒得打latex数学公式了） 4.4 答案求取 由于这题如果没有方案就输出BARK，那么就判断一下 dp[i][1/2/3]dp[i][1/2/3]dp[i][1/2/3] 是否都是最大值 是输出 BARK，不是输出其中最小值 5 最终代码（禁止抄袭，仅用于参考） 错误点：数组开小 注意到题面描述中的 n≤10000n \le 10000n≤10000 只对于 48%48\%48% 的数据，而全部数据的范围实际上是 n≤1000000n \le1000000n≤1000000

今日评价：睡眠质量优秀，赛时状态非常好，但有一些能够拿的分没有把握到。主要原因是时间不够，时间不够的原因是题目完成不是最优解导致代码量大，调试复杂。更进方法是未来完成题目时，不能以满分为目标，而是以最优解为目标，学习简洁的做法和写法。 下午状态过差，听课效率极低。原因似乎是吃了咖啡导致虽然不困但是智力降低，还有中指拔到此拔出血了导致一直在关注。 解决方法是早上喝咖啡量减少，尽量保证中午能回去睡着。 ———————————————————————————————————————————————————————— T1 赛时判断有误。一开始认为是O(n^2logn)的二分 但是应该在看到k和倍数之后直接往质因数筛那个方面走。 而且回忆合适的筛法花费了一段时间，对这部分的知识点不太熟练。 并且因为手忙脚乱有更简单的写法没有完成。 补题需要完成的： 1.学习筛法（20min） 2.重新构思代码并完成(15min) T2 赛时由于空间复杂度判断失败导致RE爆零。 课上讲的方法有些一知半解 补题需要完成的： 1.学习如何判断空间复杂度（5min） 2.重新学习做法+完成代码（15min+15min） T3 赛时的第一部分完成的过于复杂并且错了。下次需要完成更加好的做法。 补题需要完成的： 1.重新完成第一部分部分分（10min） 2.梳理思路+完成满分（20min+10min） T4 赛时应该能够完成更高的动态规划部分分，也猜到有可能有这个方面的分数但是没有完成 补题需要完成的： 1.详细研究各部分部分分+梳理思路（40min） 2.完成正解（10min）

迷宫 求细胞数量 全排列问题 营救 高塔 滑雪 最大异或和 卡牌游戏

1.T2开了四个long long 5e3*5e3的数组，成功坠机60->0 正赛再犯这么基础的错误就可以退役了。 如何预防？学会如何计算字节数。 一个元素字节数*元素总个数=数组总字节数 char&bool : 1Byte short：2Byte int ：4Byte long long ：8Byte 单位换算：OJ一般用MiB 1Mib=1024*1024 Byte 想做点黄色二分拓扑贪心。