GESP六级T2合影（（（ 原题是https://www.luogu.com.cn/problem/AT_dp_e

要是正开的话，结果会不一样吗？ 做题顺序：C->A->C->B。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意解析：给定一个初始长度为 nnn 的数组 AAA。你需要对 AAA 进行 n−1n-1n−1 次操作。每次操作如下： * 你可以选择 A1A_1A1 或 A2A_2A2 。 * 如果你选择 A1A_1A1 ，将得分增加 A1A_1A1 ，并删除 A1A_1A1 。 * 如果你选择 A2A_2A2 ，将得分增加 −A2-A_2−A2 ，并删除 A2A_2A2 。 * 将剩余元素重新编号。 求最大得分。 n≤2×105,1≤−109≤Ai≤109n\le 2\times 10^5,1\le\red{-10^9}\le A_i\le 10^9n≤2×105,1≤−109≤Ai ≤109。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 思考半小时贪心无果，于是先打个 DP 再说。 注意到最终会剩一个元素，而那个元素是最终的 A1A_1A1 。 所以我们可以记 dp[i][j]\text{dp}[i][j]dp[i][j] 为前 i−1i-1i−1 操作后 A1A_1A1 是原来的 AjA_jAj ，于是就有了很显然的 DP： dp[i][j]={max⁡k=1i−1(dp[i−1][k]+Ak)j=idp[i−1][j]−Aij<i\text{dp}[i][j]= \begin{cases} \max_{k=1}^{i-1}(\text{dp}[i-1][k]+A_k) & j=i\\ \text{dp}[i-1][j]-A_i & j<i\\ \end{cases} dp[i][j]={maxk=1i−1 (dp[i−1][k]+Ak )dp[i−1][j]−Ai j=ij<i 注意到这个很可以优化的样子！ 首先滚动数组一下，记第 i−1i-1i−1 次操作前的 DP 数组为 dp\text{dp}dp，操作后的 DP 数组为 dp′\text{dp}'dp′，则有如下： dp′[j]={max⁡k=1i−1(dp[k]+Ak)j=idp′[j]=dp[j]−Aj  j<i\text{dp}'[j]= \begin{cases} \max_{k=1}^{i-1} (\text{dp}[k]+A_k) & j=i\\ \text{dp}'[j]=\text{dp}[j]-A_j\space\space & j\lt i \end{cases} dp′[j]={maxk=1i−1 (dp[k]+Ak )dp′[j]=dp[j]−Aj    j=ij<i 显然我们需要一个方法可以快速求出 max⁡dp[k]+Ak\max \text{dp}[k]+A_kmaxdp[k]+Ak ，还要将它整体减 AjA_jAj 。 考虑一个新的 DP，dp[j]\text{dp}[j]dp[j] 为原来的 dp[j]+Aj\text{dp}[j]+A_jdp[j]+Aj ，这样就转化成了： dp′[j]={max⁡k=1i−1dp[k]j=idp′[j]=dp[j]−Aj  j<i\text{dp}'[j]= \begin{cases} \max_{k=1}^{i-1} \text{dp}[k] & j=i\\ \text{dp}'[j]=\text{dp}[j]-A_j\space\space & j\lt i \end{cases} dp′[j]={maxk=1i−1 dp[k]dp′[j]=dp[j]−Aj    j=ij<i 最终答案： ans=max⁡i=1ndp[i]−Ai\text{ans}=\max_{i=1}^n \text{dp}[i]-A_i ans=i=1maxn dp[i]−Ai 注意这样最开始的 dp[1]\text{dp}[1]dp[1] 应该为 A1A_1A1 而不是 000。 好了，顺眼多了。那就可以用线段树维护了。 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一些广告 欢迎大家在评论区一起写

“操作大师”谁来试试

A+B problem 梦开始的地方

x=x+1x2=(x+1)2x2=x2+2x+12x+1=0x=−12 x=x+1\\ x^2=(x+1)^2\\ x^2=x^2+2x+1\\ 2x+1=0\\ x=-\frac{1}{2} x=x+1x2=(x+1)2x2=x2+2x+12x+1=0x=−21

#include<iostream>//头文件 using namespace std;//命名空间 int main(){//主函数 int a,b;//定义a与b cin>>a>>b;//读入 cout<<(a+b);//输出它们的和 return 0; }

一、排序算法 算法名称 时间复杂度（平均/最坏） 空间复杂度 适用场景 std::sort O(n log n) / O(n log n) O(1) 基本类型排序 std::stable_sort O(n log n) / O(n (log n)²) O(n) 需保持相等元素顺序 std::partial_sort O(n log k) / O(n log k) O(1) 获取前k个最小元素 std::nth_element O(n) / O(n) O(1) 找到第n小元素 二、搜索算法 算法名称 时间复杂度 适用场景 std::find O(n) 未排序序列 std::binary_search O(log n) 已排序序列 std::lower_bound O(log n) 已排序序列，返回第一个≥val的迭代器 std::upper_bound O(log n) 已排序序列，返回第一个>val的迭代器 三、其他常用算法 算法名称 时间复杂度 适用场景 std::for_each O(n) 遍历容器 std::transform O(n) 搬运元素并应用函数 std::copy O(n) 拷贝元素 std::remove O(n) 删除元素 std::unique O(n) 删除相邻重复元素 四、STL容器操作复杂度对比表 1. 序列容器 操作 std::vector std::list std::deque 随机访问 O(1) O(n) O(1) 头部插入/删除 O(n) O(1) O(1) 尾部插入/删除 O(1) O(1) O(1) 中间插入/删除 O(n) O(1) O(n) 2. 关联容器 操作 std::set std::multiset std::map std::multimap 插入 O(log n) O(log n) O(log n) O(log n) 删除 O(log n) O(log n) O(log n) O(log n) 查找 O(log n) O(log n) O(log n) O(log n) count O(log n) O(log n) O(log n) O(log n) lower_bound O(log n) O(log n) O(log n) O(log n) upper_bound O(log n) O(log n) O(log n) O(log n) 3. 哈希容器 操作 std::unordered_set std::unordered_multiset std::unordered_map std::unordered_multimap 插入 O(1) O(1) O(1) O(1) 删除 O(1) O(1) O(1) O(1) 查找 O(1) O(1) O(1) O(1) count O(1) O(1) O(1) O(1) 五、算法选择建议 * 数据规模：小规模数据可选简单算法，大规模数据需考虑时间复杂度。 * 是否已排序：已排序序列优先用binary_search、lower_bound等O(log n)算法。 * 是否需稳定排序：需保持相等元素顺序时用stable_sort。 * 内存限制：空间敏感场景避免高空间复杂度算法。 * 具体需求：如只需前k个最小元素，用partial_sort更高效。

太师了，顶疯了 感谢༺ཌༀ 神威 ༀད༻给图 @徐老帅

@༺ཌༀ 神威 ༀད༻ 给图致谢

数列分块入门 1 数列分块入门 2 数列分块入门 3 数列分块入门 4 数列分块入门 5 数列分块入门 6 数列分块入门 7 数列分块入门 8 数列分块入门 9（普通莫队版本，会 TLE）

各位关心[LZM's Blog]的用户： 大家好。 首先，对于原定维护结束后仍无法正常访问，以及由此给大家带来的巨大不便和困扰，我们团队致以最诚挚的歉意。这完全违背了我们服务大家的初衷，我们对此负全部责任。 【发生了什么】 在本次计划的安全升级过程中，我们遭遇了预期之外的严重技术故障。此故障由核心系统层级的复杂冲突引发，已导致服务完全中断，并存在数据存取异常的风险。 在故障发生后，我们立刻停止了所有自动化修复流程，并启动最高级别的应急响应预案。目前，技术团队正在以人工介入方式，对存储系统进行逐项检查和数据完整性校验。我们当前唯一且首要的任务，是确保每一位用户数据的绝对安全与完整，所有操作均以此为最高准则。 【当前状态】 目前，我们的正在全力处理此问题。整个处理过程比预想中更为复杂，因为我们正采取最审慎的方案，在彻底根除安全隐患的同时，尽全力保障大家的数据不受任何损失。这也是服务恢复时间远超预期的主要原因。 【我们的承诺】 1. 数据安全是第一优先级：我们承诺，将不惜一切代价保护用户数据安全。在确认所有数据完好无损之前，不会贸然恢复服务。 2. 透明沟通：我们将至少每12小时通过这里更新一次处理进展，直到服务完全恢复。 3. 补偿与感谢：为感谢大家在特殊时期的理解与等待，服务恢复后，我们将为所有受影响用户提供[补偿800积分与500经验]。 【预计时间】 根据当前进展，我们预计还需要24-48小时完成修复工作。下一次进度更新将在明天12:00前发布。 再次为此次严重延误致以最深切的歉意。我们深知辜负了大家的信任，此刻任何言语都显得苍白。请给我们一点时间，让我们用最终安全、稳定的服务来弥补过失。 LZM 本抱歉的告知大家，数据全部丢失

自创的？

T1 nnn 个点，mmm 条边的带权无向图。 其中，猫窝在 aaa 点，老鼠洞在 bbb 点。 定义一个节点 uuu 是安全的，当且仅当： * 可以找到一条从 uuu 到 bbb 的路径，为了方便描述，定义这条路径为 S,S,S, 其路径长度为 LLL (S1=u,SL=b)(S_1=u,S_{L}=b)(S1 =u,SL =b)。使得从对于每个 1≤i≤L,1\le i \le L,1≤i≤L, aaa 到 SiS_iSi 的 最短路 严格大于 沿着这条路径走到第 iii 个节点的路径总长度。 第 i(1≤i≤n)i(1\le i \le n)i(1≤i≤n) 个节点有 cic_ici 个积分，求所有安全节点的积分总和。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第一行 n,m,a,bn,m,a,bn,m,a,b。 第二行 c1∼nc_{1\sim n}c1∼n 接下来 mmm 行，每行三个正整数 u,v,wu,v,wu,v,w 描述一条 u<>v,u<>v,u<>v,长度为 www 的边。 输出安全节点积分和。 输入 5 5 1 2 1 2 4 8 16 1 2 4 3 1 8 2 5 2 2 3 3 3 4 3 输出 22 1≤n,m≤105,u≠v,1≤ci,wi≤109,1≤a,b≤n1\le n,m \le 10^5,u\ne v,1\le c_i,w_i\le 10^9,1\le a,b\le n1≤n,m≤105,u=v,1≤ci ,wi ≤109,1≤a,b≤n。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2 给定一个长度为 nnn 的 环形数组 aaa。 有一个给定的数 mmm，满足 1≤ai≤m1\le a_i \le m1≤ai ≤m。 要求分割这个数组，使得分出来的每一段都包含 1,2,3...m1,2,3...m1,2,3...m。 求最多分割几段。 n,mn,mn,m a1∼na_{1\sim n}a1∼n 输出答案。 输入1 6 2 1 2 1 2 1 2 输出1 3 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 输入2 7 3 3 1 3 1 2 1 2 输出2 2 SJFW 1≤n≤105,2≤m≤n,1≤ai≤m,1\le n \le 10^5,2\le m \le n,1\le a_i\le m,1≤n≤105,2≤m≤n,1≤ai ≤m, 保证 1∼m1\sim m1∼m 都至少在 aaa 中出现过一次。

666

有人参加过星光复试吗？ 感觉有 亿 —————————————————————— 点点难。

> 个人学习笔记，非正常贴 低脂团队 低脂团队2 低脂团队3 低脂团队4 低脂水帖 一只菜狗 > 正文 功能符/函数区 写法 功能 实战格式 注意 __gcd(,) 求出两个数的最大公约数 __gcd(a,b); 仅限两个数，若多个数可套娃 endl 换行 cout<<" "<<endl; 不需要"" break 跳出循环 for(int i=0;;i++){n++;if(n==0){break;}} 尽量少用 continue 跳到下一次循环 for(int i=0;;i++){n++;if(n==a){continue;}} 尽量少用 \n 换行 cout<<" "<<"\n"; 需要加"" string 自带数组的字符型变量 string ch; 暂无 sqrt() 开根号 sqrt(s) 暂无 cin.getline 整行输入 cin.getline(n,10000) 会读取空格 length 遍历 s.length() 暂无 ceil() 向上取整 ceil(3/2) - floor() 向下取整 floor(3/2) - fabs() 取绝对值 fabs(-1.11111111) - pow() -的-次方 ```pow(x,y)`` - cbrt() 开了3次根号 ```cbrt(x) 整形输入进去出来是浮点数，其他变量类型不变 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 头文件 函数 名称 其他 <bits/stdc++.h> - 万能头 - <iostream> 输入输出库 - <cmath> - 数学库 - <string> length 字符串库 - <algorithm> sort 算法库 - ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 变量类型 其他 void 无返回值 struct 结构体

#include <iostream> #include <cstdio> using namespace std; int main() { double r ; cin >> r; printf("%.4f",2r ); printf(" " ); printf("%.4f",2r3.14159 ); printf(" " ); printf("%.4f",rr*3.14159 ); return 0; }