稻花香里说丰年,听取WA声一片 我仍感叹于世界之大，也沉醉于儿时情话。不剩真假，不做挣扎，无谓笑话

太难了

路过的DALAO帮帮我 谁能帮我优化一下 时间复杂度有亿点点大

#include<iostream> using namespace std; int main(){ cout<<""<<endl; cout<<"* ******* "<<endl; cout<<" * * "<<endl;cout<<" * * "<<endl;cout<<" ******* *"<<endl;cout<<""<<endl; }

啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦

很简单 无答案

前言 三分不在 CSP 考纲内，但是还是挺有用的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 正文 作用 最简单的，三分函数可以求单峰函数[1]的最大值。[2] 这时候学过一些高级货的同学就要问了：为什么不通过求导函数零点来求极值点？ > 客观上，求出导数后，通过二分法求出导数的零点（由于函数是单峰函数，其导数在同一范围内的零点是唯一的）得到单峰函数的极值点是可行的． > 但首先，对于一些函数，求导的过程和结果比较复杂． > 其次，某些题中需要求极值点的单峰函数并非一个单独的函数，而是多个函数进行特殊运算得到的函数（如求多个单调性不完全相同的一次函数的最小值的最大值）．此时函数的导函数可能是分段函数，且在函数某些点上可能不可导． > -- OI Wiki[3] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 过程 我们令当前求解的区间为 [l,r][l,r][l,r] ，求解要求精度至少为 epsepseps。[4] 在区间内任取[5]两点 lmid,rmidlmid,rmidlmid,rmid 。 如果 f(lmid)<f(rmid)f(lmid)<f(rmid)f(lmid)<f(rmid)，则有两种可能： 1. 极值点在 rmidrmidrmid 右侧，即在 [lmid,rmid][lmid,rmid][lmid,rmid] 内 f()f()f() 的值单调递增； 2. 极值点在 [lmid,rmid][lmid,rmid][lmid,rmid] 中。 对于这两种情况，显然极值点不可能存在于 [l,lmid)[l,lmid)[l,lmid) 区间内，所以可以直接令 l=lmidl=lmidl=lmid 舍去这一区间。 当 f(lmid)>f(rmid)f(lmid)>f(rmid)f(lmid)>f(rmid) 时，也是两种可能： 1. 极值点在 lmidlmidlmid 右侧，即在 [lmid,rmid][lmid,rmid][lmid,rmid] 内 f()f()f() 的值单调递减； 2. 极值点在 [lmid,rmid][lmid,rmid][lmid,rmid] 中。 显然对于这两种情况，(rmid,r](rmid,r](rmid,r] 区间内不可能存在极值点，我们直接令 r=rmidr=rmidr=rmid 舍去该区间。 > 由于三分法一般求的极值是小数，所以不用考虑等于，只需要把 epsepseps 拉高就行。 当 r−l<epsr-l<epsr−l<eps 时，误差已经小到满足题目要求，可以直接输出 lll。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 例题 P1883 【模板】三分 / 函数 / [ICPC 2010 Chengdu R] Error Curves / 无ACGO版本 题目大意 给出 nnn 个二次函数 f1(x),f2(x),⋯ ,fn(x)f_1(x),f_2(x),\cdots ,f_n(x)f1 (x),f2 (x),⋯,fn (x)（形如 ax2+bx+cax^2+bx+cax2+bx+c ），定义F(x)=max(f1(x),f2(x),⋯ ,fn(x))F(x)=max(f_1(x),f_2(x),\cdots ,f_n(x))F(x)=max(f1 (x),f2 (x),⋯,fn (x)) ，求 FFF 在 [0,1000][0,1000][0,1000] 上的最小值。 思路 三分。这个 FFF 函数应该是单峰函数，不会证明但是肯定是[6]，不然这题就是模拟退火了。 三分板子，但是是单谷函数，把求解的大于和小于换换就过了，注意多测和题目要求输出的是 F(ans)F(ans)F(ans)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 引申——黄金分割优化法 注意到，三分每次操作都要调用两次 f()f()f() ，如果调用代价很高那么就容易炸掉。 那么要优化调用，我们就要使用黄金分割优化法。 首先，这是黄金分割比： ϕ=5−12\phi=\frac{\sqrt{5}-1}{2} ϕ=25 −1 黄金分割有一个性质： 考虑一根线段 ABABAB ，其中 CCC 是 ABABAB 靠 AAA 的黄金分割点，DDD是靠 BBB 的黄金分割点。 那么对于线段 CBCBCB ，DDD 此时就是 CBCBCB 的靠 CCC 的黄金分割点。反之亦然。 容易想到，利用这个性质，可以取 lmidlmidlmid 和 rmidrmidrmid 为当前区间的黄金分割点，那么之后每次都可以复用一个点，降低了调用 fff 的次数。 取黄金分割点的公式： lmid=ϕl+(1−ϕ)rrmid=(1−ϕ)l+ϕrlmid=\phi l + (1-\phi)r \\ rmid=(1-\phi)l+\phi r lmid=ϕl+(1−ϕ)rrmid=(1−ϕ)l+ϕr 只需要在开始时计算这两个点对应的 fff 值 lanslanslans 和 ransransrans。 之后在每次循环中，如果 l=lmidl=lmidl=lmid，就令 lmid=rmidlmid=rmidlmid=rmid，lans=ranslans=ranslans=rans 然后再次计算一个 rmidrmidrmid；反之亦然。 全文完。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 引用 OI Wiki - 三分法 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 也可以是单谷函数的最小值。当求单谷函数最小值时，只需要把后文中提到的求解方式里的大于改成小于小于改成大于即可。若无特殊说明，本文中只讨论单峰函数。 ↩︎ 2. 不一定是函数，只要是满足单峰/单谷性质的问题都可以这样求解。 ↩︎ 3. https://oi-wiki.org/basic/binary/#引入“为什么不通过求导函数的零点来求极值点？” ↩︎ 4. 实际上为了减少误差，一般 epsepseps 会比题目要求小 333 ~ 444 个数量级，例如题目要求精度为 10−510^{-5}10−5 时一般 epsepseps 会设置为 10−810^{-8}10−8 左右。 ↩︎ 5. 不管取哪个点三分都能运行（在端点上除外），但是会显著影响到三分的运行速度。一般除非需要使用黄金分割优化，否则在中点偏移一个极小值的效率最高。当然，也有一些题目必须取三等分点——这种要求常见于几何题目，尤其是平面直角坐标系上。 ↩︎ 6. 其实也可能退化为一个一次函数，但是题目规定了求最小值的范围，所以没有这个问题。 ↩︎

91和78 的关系

前言 雷霆吗，站内居然没有好好讲区间 DP 的。 适合 DP 初学者食用。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 正文 什么是区间 DP , 区间 DP 的性质 区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系． --OI Wiki [1] 通俗来说，区间 DP 解决一些需要合并（也有分割）子区间的题目。 在这些题目中，一般会要求你进行合并/分割操作，每次操作有一个随操作区间而变的操作价值，答案是价值和的最大/最小值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 区间DP的状态表示 我们考虑一道题，让你合并区间，每次合并有一个价值，要这个价值最大。 比如，f(i,j)f(i,j)f(i,j) 表示 [i,j][i,j][i,j] 区间的元素合并的最大值。 那么如何求 f(i,j)f(i,j)f(i,j) 呢？ 我们在 [i,j)[i,j)[i,j) 中取一个合并点 kkk ，这个点确定了两个区间 [i,k],[k+1,j][i,k],[k+1,j][i,k],[k+1,j]。 那么 f(i,j)f(i,j)f(i,j) 就是： max(f(i,k)+f(k+1,j)+cost)max(f(i,k)+f(k+1,j)+cost) max(f(i,k)+f(k+1,j)+cost) 其中 costcostcost 是合并这两个子区间的价值。 求解的时候，只需要枚举这个合并点就可以了。 对于初始状态，不同题目有不同要求，如下文例题的初始状态是没合并过，所以是 000 。 答案就是操作完的值，即 f(1,n)f(1,n)f(1,n) 。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 例题 P1775 石子合并（弱化版） / A20908.石子合并（弱化版） > 原题需要破环成链而这道简单题不用。 题目大意 给定一个包含 NNN 个元素的序列 mmm，要求把这些元素进行合并操作，每次操作的代价是两个元素的和。要求使这个元素最小。 思路 把元素视为长度 111 的序列，那么题目大意就是合并成长度 nnn 的序列。 标准区间 DP 。 注意题目要最小值，所以上文转移公式的 maxmaxmax 要变成 minminmin 。 对于长度为 111 ~ nnn 的序列都要进行操作，所以要再遍历一个长度 len(1≤len≤n)len (1\leq len \leq n)len(1≤len≤n) 表示当前合并区间的长度。 然后遍历一个区间开始点 i(1≤i≤n−len+1)i (1\leq i \leq n-len+1)i(1≤i≤n−len+1) 即可。 代码如下： 对于原版题加个破环成链然后 min 改成 max 就完了，不多赘述。 全文完。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 资料 区间 DP - OI Wiki ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 区间 DP - OI Wiki ↩︎

这次涉及十六进制，所以：

这个很难

先序遍历：根->左->右 中序遍历：左->根->右 后序遍历：左->右->根

时间复杂度：O(log⁡2(n))O(\log_2(n))O(log2 (n)) 预计得分：100pts100pts100pts

太邪恶了，太难了。

C++ 框架目录 求赞和评论 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 函数内容 使用说明 n是长度 x是数字 返回布尔值1或0 注意这个是在数组中找数字 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 找第一个 找最后一个 使用说明 返回下标 l是起点 r是终点 x是数字 注意：这个是在数组中找数字，数组需要排序

重要的事情说三遍 注意：所有框架仅供参考 注意：所有框架仅供参考 注意：所有框架仅供参考 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 基础框架 基础框架 更多框架： 前缀和框架 回文数框架 双指针框架 插入排序框架 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ cmp函数 cmp函数框架 判断质数函数 判断质数函数 更多函数框架： 二分查找函数 最大公因数和最小公倍数函数框架 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我觉得你会用到： 常用代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 赠编程题参考代码 大写小写互转 任意进制转十进制 赠随机数使用说明 说明 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 佛祖保佑：

6666666666 有人吗?

我的团队 printf 是 C 语言的标准输出函数，在 C++ 中可以直接使用（需要包含头文件 <cstdio> 或 <stdio.h>），它的优势是格式化输出灵活、简洁，适合需要精准控制输出格式的场景。 示例 2常用格式占位符（核心） 这是 printf 最常用的占位符，记住这些足够应对大部分场景： %d 输出十进制整数 printf("%d", 10); %f 输出浮点数（小数） printf("%f", 3.14); %c 输出单个字符 printf("%c", 'A'); %s 输出字符串 printf("%s", "你好"); %lf 输出双精度浮点数 printf("%lf", 2.718); %% 输出百分号本身 printf("%%"); 总结 printf 是 C++ 兼容的 C 语言输出函数，头文件 <cstdio> 核心是 **% 格式占位符 **，常用：%d(整数)、%f(小数)、%s(字符串) 支持精准控制：小数位数、输出宽度、对齐、进制转换 简洁高效，适合格式化输出场景 可以看看这个消化消化

抱歉，忘写我名字了~~~