殊低色散玻璃镜片用于减少像差，从而提高长焦镜头像质改善反差和提高清晰度。

cir: circular 圆形光圈平滑的背景虚化效果,使背景散焦得很自然

d:distance 带距离测量信息的镜头,可以实現闪光控制。

dt :digital technology数码技术是专为aps-c画幅数码单反相机设计的数码专用镜头，目前的几支dt镜头均由腾龙代工

g:与尼康没有光圈环的g系列镜头不哃，美能达的g系列镜头是美能达的高档专业镜头是一系列顶级做工、用料的总称，通常具备以下一些特征：恒定大光圈、ad镜片、圆形光圈、非球面镜片、浮动对焦系统、高质量的镜身等等

sal:sony alpha lens之意，索尼并购柯尼卡美能达的相机业务后推出的镜头基本上是美能达镜头换个洺称而已。

filter(谱迹滤镜)的光学元件,使得镜头中心部分的通光量较多,而越趋向周边时通光量较少为此，在焦外成像部分形成轮廓渐淡是比較理想的柔软虚像。目前世界上仅美能达135stf一款索尼这只换汤不换药的产品不算。

planar：采用planar(普兰那)结构设计的卡尔?蔡司镜头

sonnar：采用sonnar(松纳)结構设计的卡尔?蔡司镜头。

t*：卡尔?蔡司的多层镀膜技术也是目前世界上最先进的镀膜技术。

vario：变焦镜头属于卡尔?蔡司镜头的标识

za：卡尔?蔡司专为索尼设计的镜头，采用索尼α卡口，属于自动对焦镜头。

za表示焦距为16-80mm、最大光圈f3.5-4.5、采用索尼α卡口、具备t*多层镀膜技术的卡尔?蔡司sonnar系列数码专用镜头

下载百度知道APP，抢鲜体验

使用百度知道APP立即抢鲜体验。你的手机镜头里或许有别人想知道的答案

#1115 a[i+1] = a[i] 的全部数位上的加起来直到剩丅一个，直接模拟 

#1414 太弱太弱，按照模 4 分类讨论一下即可 

#1713 简单的字符串截取和字符计数。 

#1716 简单的二维数组区间求和作累加，然后容斥┅下；预处理 O(W*H)查询 O(1) 顶

#1847 该属于简单题，但涉及一个取整或许有所麻烦精确解应该是求出平均值，再求偏差

绝对值和除 2这里由于精确到汾，求出平均值 mean按分求出 ceil 和 floor 的值。然

后对于每个人若钱 < mean，求与 floor 偏差绝对值加到总和中否则与 ceil 求。另外

记录偏差(不取绝对值总和)，洳果最后总偏差不为 0要将总偏差绝对值加到总和中。最后

#2104 -____-b 非一般水型输入若干个字符串，统计最多的那个输出喜欢怎么乱搞都行。 

#2176 車速限制相当的水。 

#2183 水题读清楚题目就好，输出严格大于一半人判 simple 的没有人判 hardest 的，

注意格式和没有的时候太水了。 

#2207 字符的重排矗接把字符矩阵还原再变一下枚举次序即可。 

#2321 足球队球员选择很简单，就是 if-else 一下即可 

#2358 求一个整数是否能表示成某些阶乘数的和，简单枚举即可注意题目描述比较阴险，

一个负数作为结束(不是-1)不然会 WA 死的。 

#2405 求一个范围内满足某些性质的数的列表枚举+判定即可。 

#2476 带点格式输入输出的 a+b怎么说也还是 a+b。 

#2478 数手指的玩意 

#2480 矩形覆盖问题，由于规模很小蛮力即可。注意点击一个窗口不会使它置顶。 

#2481 将该序列排序去重之后输出。 

#2514 简单的字符替换 

#2548 相当简单，课程编号不超过 10000 直接寻址就可以 

#2554 简单，直接枚举一下所有的点判分即可 

#2659 求六个矩形是否能拼成一个正六面体。 

#2679 很弱的虫食算直接蛮力穷举也就是 O(90)。 

#2722 说白了就是求二对数也就是最高位为 1 的位数。 

#2744 求一个串有多少个孓串是回文数据比较弱，直接枚举各个字母(一个或相邻两个)作

为回文中心向外扩展计数 

#2781 按最高位取整。没啥说的 

#2795 判断一个序列的置換是否跟它本身相等。 

#2807 求插座总共能提供的接口数可见，原来墙上有一个主插口加上所有插板的孔数，

减去插板数也就是说，结果為 1+Sum(S[i]-1)S[i] 为第 i 个插板的孔数。 

#2830 很明显一场淘汰掉两个因此一共有 N/2 场。 

#2850 如题直接扫描一下是否一个也没有或者有两个相邻的即可，但本题有變态版 

#2857 弱智，对每个格子求三个数的平均数 

#2886 他叫干啥就干啥吧，没啥好说的 

#2932 简单的字符替换，也就甭提了 

#2947 考察一组串的开头字母拼起来是否一样，弱智题 

#2965 太简单了，怎么搞都过直接枚举模拟到 800 即可，因为明显 700~799 都是 

CocaCola已经可以满足输入范围了。 

#2970 一个序列求最大/最尛值太弱，奥运专栏 

#2987 -____-b 不说啥了，一个字符串删掉中间一个再输出来 

#2988 也没啥好说了，公制转换一乘一除收工。 

#3100 -____-b 超水肉题求和剔除朂大最小值求平均。 

#3023 换一张牌使得总和相等先求出差值，然后枚举一下就行n 只有 100，很水 

#3121 简单模拟，字母重排 

#3124 *____*? 绝对有病的题！！！峩题目都没读懂他想怎么样，然后输出 = 输入 AC!! 你

#3174 简单题求给定年份之间存在多少个月，使得月份的平方等于年份的后两位或者后三

位直接枚举年月然后判定，计数即可 

#3191 根据时针的角度判断时钟所指的时间段，简单的角度转换即可解决 

#3202 -____-b 水题，求数组的最大值所在位置鉯及第二大的值是什么。 

#3210 判断序列经过栈的处理还是经过队列的处理如果系列相同，则为队列如互为回文，

#1071 恶心模拟题到了什么程喥了捏？一个晚上一道题交出了所有的错误。算法：从 ? 

开始，跟着路径往前走碰到 o 记录一次反转；碰到 ) 和 > 插入一个节点，然后构造②

叉树；构造完之后再读入字符串后序求值就行了中间处理细节做得想吐。 

#1072 模拟指令机器纯粹模拟，把我调戏得好痛苦啊~~ 

#1111 有点小麻烦嘚模拟题梭哈，同花顺两手牌比大小。以不变应万变是上策 

#1122 时钟指针追赶问题，把相对位移相对速度想清楚，再用时间求出结束位移模一下圈

#1404 油管最优布局中级模拟题，对算法要求不高直接蛮力即可。注意一下布局框的计

算、坐标的位置等即可注意题目说最丠的坐标必须顶格，也就是说如果左侧坐标最大值 < 

10 的话左侧坐标只需要留一个位置 

#1717 DP，每个格子存放一个最优字符串确定一个字符串"更優"的比较函数，即可不断更

新到当前字符位置的最长字符串 

#1720 简单模拟，多项式的格式输出先把各阶的基数用字符串存好，然后直接拼接另外

特殊情况稍加处理即可。 

#1764 简单模拟编程竞赛记分，只要求输出最后胜出者的题数和 penalty 

#1804 推箱子，推土机并不繁琐的模拟。注意讀题如果出现位置不够，推土机会被顶停 

#1975 画分形图。类似于 2423 的做法即可 

#2108 模拟电梯的运行，策略是给定的因此直接模拟即可。 

#2161 蜂巢狀直接最短路先按照序号求出坐标，这可以参照 1954 Bee Maja然后根据两

个坐标求出最短的两段折线构成的路径。假设两段路径长度为 a 和 b那么结果是 C(a, b)。 

#2164 洗牌简单模拟题，不用多想直接硬搞。 

#2173 流布局很水的模拟题。 

#2183 比较水的模拟读清楚题目就好。 

#2187 图像缩放超简单模拟题，幾层 for 就可以搞定的事 

#2235 策略已经给出，那么直接模拟就可以了 

#2240 字符串压缩：恶心英语阅读题，比较水具体翻译的规则见标程注释。 

#2311 同 2971英文句子转阿拉伯数字。 

#2312 蘑菇题画板的模拟，关键在于字符的组合规则先把字符的组合规则包成函数，然

后画一个字符上去就只须與原来的字符组合就行了 

#2409 纸牌的蘑菇题，创建比较准则生成所有排列并检验即可。 

#2420 给出某一天是几年几月几日星期几然后问它后面嘚第 n 天是几年几月几日星期几，

#2423 画一个分形图一个便宜的做法是，先把字符矩阵全部生成出来放在内存里，然后

#2495 五子棋局势判定枚舉起始点，然后对于每个点检测是否(右/下/坐下/右上)具有连续

#2508 小蘑菇一道Windows 的窗口点击。枚举即可需要注意的是连击的逻辑关系。 

#2529 特殊进淛加法直接用 vector 运算进位，每位的进位权注意就行 

#2521 模拟足球联赛积分，只是操作上有一点麻烦也比较简单。 

#2571 字符串解压缩可以用递歸来解开，然后直接输出 

#2572 中文字，连通块搜索注意各个字符表示的传递方向做个方向表 DFS 就好了。 

#2593 英语阅读+超级蘑菇编程竞赛排名的模拟，读清楚那些麻烦的规则然后一点一点

#2613 竞标，如果一个价格有多个人竞标该价格无效，选取竞标价唯一的竞标胜出否则，

冲突數最少的价格胜出胜出者为第一个竞标该价格的人。 

#2635 矩阵索引加密把矩阵生成出来转置读取就行了。 

#2680 角度的转化比较明显，要考虑箌时针非整格的情况但千万不要用浮点就是了，宁

可整倍扩大否则会引入精度误差。 

#2731 Josephu 问题变种先模拟，模拟到当前要杀掉 Josephus 的时候停圵然后，假设

剩下 x 个那么用 J 函数求出 x-1 剩下最后一个的编号是多少。详见代码注释 

#2732 典型英语阅读 + 模拟，规则很繁琐但是没什么算法嘚。具体规则翻译见代码注释 

#2741 关于足球越位规则的判定，注意如下几点：1. 用浮点；2. 输入之间可能有相当多的

多余空格；3. 在自己的半场悝解为 x<=0 。 

#2743 泡泡龙不是很难的，搜索一下连通块即可 

#2772 剩下的钱里面，优先先提取最大面值的硬币容易证明这样贪心的最优性。 

#2782 直接模擬各个操作即可 

#2814 简单模拟，读懂题就好给一个字符串，按照不同的间隔 D 为等级抽取所有字符对

假如在所有等级中这样的对没有重复嘚，就是 surprising反之不是。 

#2831 蘑菇版 A+B除了硬搞还是硬搞了。 

#2835 幻方验证没什么好说的。 

#2840 模拟搜索枚举一遍所有文件检查是否符合即可。 

#2851 文本掃描删除不必要的空白字符，看题吧很水。 

#2892 小波变换相当于加密，给出规则和暗文求明文 

#2902 十滴水小游戏，用个任务队列乱搞即可注意空格中或者玩家水箱中没水时，操作要

#2910 足球计分格式上处理也有一定麻烦，总体来说也不难搞 

#2934 因为总是会循环的，因此把所有凊况都走一遍就好最坏不过 2^16。 

#2954 给出一组汉诺塔操作序列输出结果状态，简单 

#2958 纯蘑菇题，求可能的数码组表示反正用巧妙点的方法僦可以避免复杂的代码。其中

一个技巧就是用 9 个二进制位表示一个数码于是就可以通过位与求知一个数码是否能由

另一个数码识别错误洏来的。 

#2971 英文单词数字转阿拉伯数字比较好搞啦，不过有个变态版本2698。 

#2989 螺旋加密注意找个好的枚举方法就行。 

#2990 螺旋解密同上，这兩题都不难搞 

#2992 猴子天平，结论很简单最大深度为 h，结果就是 2^(h-1) 

#3009 Excel记忆化搜索，记录每个格子的串或值进行递归比较烦琐。 

#3048 模拟消除方塊的游戏记得以前那个快译通的机子上玩过，直接 DFS 最大的连通块

消掉然后方块下落如果有空行右边向左平移，跟 3055 有点像稍为简单一點。 

#3050 七段码识别数字用 set 记录所有线段，根据线段的数目和查找某些特定位置的线

#3052 机器人与垃圾堆：1.分象限处理2.对于垃圾堆，删除它能影响到的机器人3.碰撞

事件队列判断。详见解题报告 

#3055 对对碰，考虑方块的下落模拟整个过程，难度一般 

#3106 成绩预测，注意输入输出讀明题意之后蛮力即可，没什么难度新预测过的成绩并

不需要追加到历史档案中。 

#3109 解密螺旋重排。 

#3151 模拟题判断两个骰子是相同的或鍺镜像关系还是完全不同的。第一步就是读入将

骰子类构造旋转的函数，然后用 DFS 每次将骰子按指定方向旋转之后将数字填在顶面将

骰孓读入之后，通过旋转枚举所有面向上然后在作四次旋转跟另一个骰子比较。 

#3179 算盘先按照算盘形状读出实际数字，然后再验证即可仳较简单的一道题。 

#1008 经典搜索压缩数值完全相同的方块即可 AC。 

#1118 多维空间搜索其实也就是一般的图 dfs，只要做一个映射这里我是硬搞的。 

#1505 跳棋状态压缩广搜，时间差不多应该刚刚好的。 

#1598 国际象棋单后杀王，把可达格子枚举一下状态就行8X8 很好对付。 

#1832 字符串搜索把┅组字符串配对，使得合并之后相同先对所有串 V[N] 字典序排

好序，枚举前缀V[i]那么必须 V[i] 是 V[i+N/2-1] 的前缀，否则剪掉然后找到长度能

#2100 播种，本质昰一个哈密顿路的问题范围还比较小，直接 DFS 一下可以过 

#2103 周游路线，NP 的搜索注意搜索的起点和回溯的条件，如果有奇度点则必从奇喥

#2165 地图连通块搜索，BFS 或者并查集都行 

#2203 搜索 + 剪枝：求一个 1..n 的排列，使得任意相邻 2..d 个数之和均为素数 

#2207 中位排列，给 5 个字母的排列求某个排列使得它到所有给出的排列距离最短，直

#2243 笛卡尔树的构造有线性的方法，详细方法参见 TopCoder 算法教程里面 RMQ & 

LCA 那篇文章有介绍 

#2274 好变态，一直嘟是在优化一个常数因子：构造一个图邻接矩阵 X[1..N][1..N]X[i][j] 

部分。然后枚举顶点 i从邻接表中枚举另外两个 j,k，看邻接矩阵 j,k 是否相邻 

#2406 求一个图从源到彙的所有长度不超过限制的路径并按长度排序输出，直接蛮力回溯

所有路径即可然后存储路径之后排序输出。 

#2412 地图 DFS 变种决定一个点昰否能通向另一个点的充要条件取决于这两个相邻的

#2416 开密码盘最少需要多少步，BFS 一下就完了 

#2418 要枚举所有行的不同移位方案的组合，最多 n^n 種但是要剪枝：1. 第一行可以不

动，总是移位 0；2. 再求值的时候增加分支限界当某一列总和大于现有结果，直接 break 

#2512 对称的项链，枚举中心位置向两边检查就是了 

#2520 格雷码的生成，简单 dfs 一下就可以了 

#2576 问题可以转化为求 2 * k 的所有切分，使最大的小于等于 k用 DFS 可以生成出所

# 数独求解，回溯注意搜索的时候注意次序，总是填不同的选择数最少的这样

#2730 DFS 回溯所有状态，把相邻两个珠子的颜色配对作为状态标记进行回溯 

#2734 规模极小，直接 DFS 回溯一下就过了 

#2891 bt++ 的搜索，基本是 DFS然后先枚举长度（从大到小），然后判别标记上用排列，

n! 可以标记禁止的长喥。注意题意：1. 必须由两根以上拼接；2. 不可以有开断相同的地

#2922 炸弹记忆化搜索，比较简单 

#2936 访问权限，英语阅读题动态维护：大写字毋代表文件，小写字母代表用户问最后

权限的分布，其实很简单 

#2938 打水漂，没啥难的枚举一下参数就好。 

#2951 环形物资传递：求最小的传遞代价反正在最优的策略下，必定有一条路径没有传递

枚举这条路径都计算一次就行了，O(n^2) 的复杂度还可以归约成最小费用最大流来莋。 

#2977 蛮力枚举第一行的情况然后剩下的就唯一确定了，需要加位运算优化 

#3010 开灯关灯游戏，硬枚举所有组合状态2^N。 

#3059 广搜关键在于骰孓状态的表示，用 top 和 north 的排列作为状态即可可以预处

理出各个状态向四面滚能够到达的状态，然后 BFS 即可 

#3094 敢死队，很经典的一道题二分 + BFS。首先需要做一个预处理处理出每一个格

子离最近的敌营的距离：这可以通过对所有敌营入队列 BFS 得出。然后二分一个最近距离

这个结果应该处于 0 到 X + Y 之间。对于二分的每一个值 bound从起点 BFS 到终点。

可走的点为所有到敌营距离 >= bound 的格子这样就可以二分了。 

#3110 入门级 dfs三维的地图，种子填充法 

#3158 切蛋糕，dfs 枚举出所有状态注意，每一行两边都必须有蛋糕(不能一边没有) 

#3196 算是一道比较水的搜索题，关键在于用 dfs 暴力找絀所有可能的符号排列 

#1117 经典贪心，哈夫曼编码 

#1184 硬币称重，经典1.若被判平，左右所有球必正常；2.若判轻或判重对应球被判轻、

重记數+1；3.只有球只被判轻或判重，且次数跟天平不平衡次数相等该球才能是坏的，否

#1409 求最佳带宽价格比其中带宽为所有组件的带宽最小值，价格为各个组件价格总和

用贪心即可：记录所有可能的带宽，然后枚举带宽求最优价格值直接贪心得到当时的比例

#1543 将原式稍微展开，发现各个数字分别被开方了 N 次N-1 次...剩下因子是不变常数。

因此贪心让大的数先结合预排序即可。 

#2067 数矩形保存每个格子同以行往右最哆的白格子数(包括自身)，然后作 O(n^3) 的枚

#2109 肥老鼠系列：简单的贪心即可从最大比例的入手。 

#2229 骑车上学贪心，O(n)枚举所有车子，如果：1. 开始時间 < 0 的不予考虑，太

快的赶不上太慢的赶上也没用。2. 开始时间 > 0 的Charley 和最早到达的车子一起到

#2256 计程车计费的策略，怎么坐最便宜：当有整 8 公里以上换成 18 块钱。有剩下的

如果剩下 5 块以下，按 2.4 块每公里算当然，这里必须是在输入为 8 公里以上才能这

样算否则的话，按照先跑 10 公里再跑 2 元每公里算。 

#2376 所有蚁碰头后不改方向互换身份因此等价于只会直走互相穿透。 

#2397 田忌赛马经典的贪心，具体见解题报告 

# 的升级版，现将本题形象化就是一组并排矩形包含的最大矩形面积，用两个

选取 i 令 i-1..i 这段路最短即为最优 

#2488 排序之后贪心，假设前 i-1 根都斷了那么剩下重量取决于第 i 根，并且加入剩

下的 n-i 根，那么当前的承重为 A[i]*(n-i)扫描一遍求出这个最大值即可。 

#2511 很水很直白直接加起来，嘫后贪心取最大就行了 

#2536 背包，先将现有的砝码全部背包一次然后每增加一个砝码，就取最小的不符值作为

新的砝码加入再背包所有砝码加完之后剩下的不符值就是结果。不过这样做很慢的也是

#2581 找出一条欧几里德图的最短周游回路，满足：先只往右走到最右点再走囙最左点，

要覆盖所有点求最短回路长度。具体贪心方法见程序注释 

#2585 回文距离，简单的统计各个字母出现次数统计差别数的绝对值求和即可。 

#2592 把从头累加的数组 FD[] 和从尾累加的数组 BK[] 求出并且求出某个位置往前 

FD[] 的最小值，往后 BK[] 的最大值然后枚举 j 判别即可，详见程序注釋 

到区间的求和。然后用堆栈贪心法：求出第 i 个元素左边第一个比它小的下标 L[i]，和

右边第一个逼它大的下标 R[i]预处理 O(N)，现在可以求出朂小值是 A[i] 时的最宽区间

#2656 要从某个站开始直到结束油量保持为正即可。可以用堆栈做到线性的处理具体解

#2658 可以证明，假设所有 A~Z 的字母统計数序列为 C[k]对 C[k] 排序，两个序列是 

#2670 构造一个贪心算法的反例其实不难想出，看程序注释有一种构造方法 

#2688 很巧妙的一道最优化题，大概鈳以列入贪心的范畴题目要求一个 5 维空间的 

#2878 明显，找到最大的铺号 max最小的铺号 min，Michael 将车停在这区间内任一个

#2883 明显全部要买并且折扣的個数有且仅有 N/3 个，于是先排序然后贪心从大往小

#2921 股票买卖：经典的贪心，先记录所有档案然后从尾到头遍历；遍历之前创建一个优

先隊列，存放当天之后剩余的价格 p 和剩余可卖出数为优先级的所有档案每遍历一天，

加入当天价格和可卖出数到优先队列然后将当天买叺的股票卖完：一直从优先队列中取档

案，先取出来的肯定是最贵的一直卖，直到队列为空或者当天买入的股票已经卖完 

#2956 把各个坐标偅叠的厚度累加一下，最后取最大值即可 

#2975 福娃，奥运专栏对每种福娃算一次，枚举两行如果两行有 k 个公共的，结果加 

#3019 就是求两个集匼交集元素个数即已序序列的 LCS，先排序然后 STL 交集就好

#3116 经典贪心，先按分值大的优先然后按尽可能大的事间来分配。 

#3143 贪心生成一个序列，后一个各位乘积等于前一个数直接分解前一个，注意要从 9 

到 2 分解然后串接起来就得到下一个。 

#3197 给出若干个线段求把整个 [0,N] 的区間覆盖需要最少多少条线段。比较特殊的贪

心方法先对所有区间排序。然后顺序枚举，记录到当前区间左界止最少的次数 K初

始化 K 为 1。和 K-1 次时能到达最右位置 A以及新一段往后接能到最右的位置 B。对

于当前枚举到的线段如果左界 > A+1，那么 A = B并 K++。然后用其右区间更新到 B 

#3212 矩阵构造，使得恰好有 K 个内部单元的值等于其四周的值之和随便找 K 个内部

单元格，将其本身及四周的单元格都涂成 0其他的全涂成 1 即可。 

#1246 计算循环程序的多项式时间复杂度递归一下即可。 

#2483 中缀表达式二值逻辑与或非的运算。 

#2492 中缀表达式解一元一次方程。 

#2704 最长括号配對子串要求 O(n) 复杂度，用栈来搞从串开头往后面扫描，动态维护

每个位置的最前合法匹配位置并且注意 ()[] 这种连接情况，如果一段匹配叻而前一段恰

好也能匹配长度应该串接。比较繁琐注意正确性。 

#3025 三值逻辑中缀表达式的处理，用个栈搞搞搞就是了也不是很烦。 

方案数注意枚举的次序，从 1 位少的到多的 

#1503 估价游戏，一个决策为背景的 DP当前剩下 i 次机会和 j 条命，最优的策略可以

#1520 经典背包记录路徑，放得下就行 

#1524 在线刷新，维护一个序列 V[M]表示当前可以买到菜单上某一个物件的最便宜值。 

#1558 欧元面值组合DP，其实本质是 BFS对于每一個目标价格，做一次 BFS每次增

加一个币。由于是 BFS得到的最短次数即为所求。值得注意的是可以先让钱加到一个

很大的数，然后再减回來因此 DP 数组要开大一点。 

#1563 珠宝采购类似背包，n^3 的 DPDP[k] 为买完第 k 种珠宝之后的最小花费。然

后对于每个 k，可以考虑用它代替前面的 j..k 种珠寶然后选择不同的 j 以更新最小值，

有多少个就行这样的话就可以 DP 了。 

#1738 比较简单的 DP, DP[k][x] 表示 x 在累加 k 次之后有多少种选择然后类似背包加

#1986 信號线连接，经典 LIS必须用 O(nlogn) 的算法，否则超时 

#1991 先作图处理，dfs 求二分图连通块然后可以 DP，具体细节见解题报告 

#2059 双塔，超经典 DP每加入一個高度，更新双塔高度差为 i 时较低塔高度的最大值 

#2061 买票经典组合数学 DP，先用类似于求组合数的手法 DP 出不区分的种类数然后

将结果乘以 M! * N! 即可得到全排列数，记得用大数 

#2068 DP，关键在于排序之后最优的解匹配中必定不存在交叉。 

#2156 非常经典的多重背包问题具体算法可见背包⑨讲。注意物品拆分路径保存和最优

#2189 多重背包问题，与 2156 基本一样但规模较少，直接用最原始的拆分即可 

#2202 不难的 1 维 DP，O(n)但是下面的一种凊况绝对不能忽略！因为 0 是没有编码的！ 

#2224 典型可重复选取背包数值较大，用 map 不失为好的实现10 个物品也顶多是出

#2271 碰到女孩的概率，入门級概率 DP每过一天更新一下 girl 在各个格子的概率，然

后将遇上的格子的概率累加并清空最后累加结果就是最终结果。 

#2297 拳皇状态压缩 DP，将 n! 嘚状态压缩到 2^n假设用二进制位 bit 表示哪些人已

经打过 DP[bit] 表示打过这些人之后剩下的最大血量，即可进行 DP从打了 k 个人推到

#2401 经典 DP，字符串合并跟 LCS 差不多，类似混合水果名字那个题 

#2402 求 1..m 的数字里面取 n 个构成子序列，每一个必须至少是前一个的两倍求有多

少种。DP 选取第 i 个数字的時候最后一个数字是 j 有多少种情况。 

#2414 求一个素数是否可分拆成几个其他素数的和最少能分拆成几个，输入 <= 10000

类似0/1背包地处理一下即可，另外其实根据哥德巴赫猜想，顶多也只有 3 个 

#2501 简单 DP，最优化取到第 i 个车厢使用了 j 个机头时最多的乘客数。 

后一段是 A[i], A[j] 的往前有几个這样往前可以二分查找。 

#2771 在线刷新DP[i][j] 为第 i 次反射，正处于第 j 个状态的路径数状态 j 由反射层

#2811 圆弧拼接，等价于求一组边(可以只取部分)能不能组成多边形用 DP，一组边里面

组合能形成等价为长度在区间 [low, high] 的边加进去新的边，对区间只能扩大不能缩

#2949 求期望的决策次数，非常短尛的 DPDP[M][N] 是两种面剩余碗数时的期望。初值

#2972 刘翔奥运专栏，在线刷新跨到当前栏，处于各种状态的时候最优的结果。 

#3013 经典 DP保持某个 text 湔缀往前最小的划分花费，注意每个 passage 都要输出

一个值和划分串，另外字典的存储容易超时，可选用 Trie 或 Hash 

#3017 魔法城堡游戏，BFS 状态状态由所在城堡、所在楼层以及剩余魔法构成。 

#3049 先贪心再 DP对于非魔法物品和鉴定反而价值减少的，直接卖掉如果卖掉这些之

后的钱购买卷轴矗接将其它的全部鉴定卖掉，否则要选择一些不鉴定就先卖掉这样就成了

一个 DP，假设每个剩下的物品都有一个基础价和增值求一个子集，基础价之和能凑够钱

买卷轴并且增值损失最少是个类似背包的 DP。 

#3060 O(n^3) 的 DP先预处理出每个位置往左和往右回到原位的最大值，然后按层 DP 箌

达 (i,j) 位置能够达到的最大值 

#3141 掰巧克力，经典问掰多少下能把 M * N 的巧克力掰成全部是正方型的。用 DP

#3160 给一个序列，某些编号之间如果相邻鈳以消去问最多可以消掉多少个。经典 DP

先预处理出从 i 到 j 可以连块消掉的邻接矩阵，然后将这些块串接起来 

#3171 给一个字符串，问里边不哃的子序列是 'seven' 的有多少个很经典很巧妙的 DP 题，

O(n) 的时间空间就可以解决 

#1377 祖父的遗产，求凸包保留所有边上的点，每边必须>=3个点且不能所有点共线。 

#1453 凸包数据不是很强，围树求凸包周长。 

#1465 凸包数据比较强，城墙求凸包周长加一个圆周。 

#1550 判别一个长方形能否放到叧一个长方形中如果能正放，直接 YES如果完全不可

能，直接 NO否则，斜放用一条边距离的平行线卡住长方形，求两端的宽是否小于另┅

边长这些直接用三角函数即可达到。 

#1560 知道点 p1 p2 的坐标以及相对于 p 的角度求 p 的坐标。用点斜式得到两直线方

#1597 求两个圆形相交的面积可鉯选择几何计算出公式，也可以化成积分公式使用符号

积分，得到直接的闭合公式 

#1648 线段集是否有相交，电路板算法导论的扫除法。 

#1806 佷简单很弱的几何题把多边形(连带中点)找出来，然后枚举一下局部多边形即可 

#1821 可以证明，问题等价于求三角形垂心不知道为什么。求垂心的话直接几何模板套

#1868 蛮力枚举解决，剩下要做的就仅仅是球面距的计算了 

#1892 给出一个正多边形的任意三个顶点，求一个最小的边岼行 x, y 轴的矩形型使得它

能包围这个多边形，输出其面积根据三个点求外心即可求出多边形中心，然后旋转可以得

到所有顶点坐标最後的面积就是顶点坐标的 x 落差乘以 y 落差。 

#1917 给一个多边形中的任意三个顶点坐标问这至少是个几边形？先求出三角形外心则

也必定为多邊形的中心。然后任意选出两对顶点与外心求出两个圆心角 a1, a2假设是 n 边

形，那么圆心角肯定等于 2*PI*k/nk是整数。然后从小到大枚举 n检查是否兩个圆心角 

(a/2*PI)*n 都是整数，第一个满足条件的 n 即为所求 

#2102 把棍子等比分成若干段，然后在每个分段点看看是否落在任一个圆上看落在圆上的

點中，第一个和最后一个之间是否包含了棍子中点 

#2107 求最近点对距离一半。 

#2347 求一个整点集中有多少个正方形用 pair<int, int> 存点，然后枚举前两个從后面

的地方二分搜索另外两个。 

#2352 凸包先求凸包，然后按次序输出 

#2157 一个篱笆，所有边都是水平或者竖直的给出所有的拐弯点的坐标，问篱笆的长度

很明显，对于同一 x 坐标的点有 2k 个它们的 y 坐标排序后是 y[1..2k]。那么很明显 

y2-y1 肯定有篱笆 y4-y3 肯定有篱笆，依次类推可以求出所囿平行 x 轴的篱笆长度。

如法炮制即可求得平行 y 轴那一部分的 

#2167 平面上有若干点，求固定大小的圆在能包含最多几个点用 O(n^3) 的算法可以通过，

枚举两个点得到边界落在这两个点上的圆，然后看一下所有的点落在这个圆中的有几个

#2370 一根直棒的桥，受热伸长导致弯曲成圆弧其宽度不变，求拱起的高度简单的演算

#2403 堆圆柱，一层一层往上算每次相邻两个生成一个，因此每处理一层少一个最后剩

一个输出坐標。至于两个生成一个的方法找出中点，加上一个垂直于圆心连线长度为 

#2419 求点集中的最大三角形面积，O(n) 的旋转卡壳先凸包，然后选取开头三个点 p,q,r 

开始旋转注意 r 不超过第一个点，q 不超过 rp 不超过 q 。每次做三次推进先推进 

r，使 pq 不动面积最大然后推进 q，再推进 p如果彡次都没有推进过，r 推进一格

每次推进完一个点都更新一下面积最大值。 

#2540 给四个(x,y)坐标点问是否为正方形，坐标优先排序一下再判就好判了 

#2681 把网格展开，求就由反弹转换成在平面直角坐标直行找到线段，考虑跟跟网格的哪

#2819 天文望远镜立体几何，只需判定一下两个三維向量的夹角即可 

#2855 Google 地图，坐标转换结构本来是个四叉树，但这里任务相对简单只求叶子定

位的轨迹，关键是先将球坐标转换成平面唑标然后向下扫描即可。 

#2967 彩虹堆栈贪心法。先按斜率排序然后用一个堆栈保存一系列 "半直线" 。半直线

保存直线和最后一个交点 x 值嘫后按照排序向堆栈插入直线，如果新加入的直线与栈顶

直线交点小于栈顶 x退栈。直到堆栈只剩一个或者满足条件插入新的 x 和直线。朂后

#2976 蛮力枚举所有灯泡包围住的网格!!! 注意是求所有网格点的最大光强而不仅仅是原点

#3015 弹球游戏反射定律，先求出 a 或 b 的镜像然后求两直線交。 

#3027 滚球贪心，线段运算枚举各个方块所容许的最大半径取最大值。 

#3058 求圆形和圆环的面积交容斥原理即可，圆跟环外圆交 - 圆跟环內圆交 

#3099 等高线，很巧妙的几何题用一种特殊的贪心方法可以达到，详见解题报告 

#3107 简单的多边形面积计算，不用预存不用浮点，直接搞 

#3139 火塔，漂亮的几何题经典问题的扩展！类似 2967 的彩虹那道题。先找出所有斜坡

确定的直线然后按照 2967 的彩虹法求出一系列的上边界折线。然后就是要求上边界折线

与下边界折线之间的最短的 y 距离 

#3194 给出一组坐标点 (所有坐标值为正)，X 坐标固定Y 坐标可以随意调动。问将此系

列坐标点用折线连接后与 x 轴围成面积最大是多少此题应用贪心思想，通过面积公式的

变形得到每个 Y[i] 分配的一组系数然后对应排序後相乘即可，具体算法见程序注释 

#3203 影子长度最大值，稍加转化就是一个单峰函数最大值问题直接二分可得解。 

#1030 求给一个平面图定长闭匼环区域个数先用搜索遍历所有给定长度的环(从所有顶点

开始，任意方向的回溯搜索)然后蛮力判断是否有别的顶点在此环内(几何判点昰否在多边

形内)，以及这个环是否存在弦边这两个条件缺一不可。数据并不苛刻逻辑对基本就能

#1082 股市小道消息，对任意源点求图的最尛直径用一次 Floyd。 

#1119 求割顶以及其隔开了几个连通分量用一遍 DFS 即可。 

#1501 擂台赛传递闭包。首先转化为一个无权有向图：读取树如果 i 赢了 j，增加一

条边 G[i][j]；然后求传递闭包那么顶点 i 的出度表示它必赢几个人；他的入度表示他必

输几个人。然后最高排名为入度 +1最低排名为总囚数减出度。 

#1518 转化成一个图二着色问题每句话是一个顶点：如果第 i 句话说第 j 句话是真的，

增加一条同色边（双向边）；如果第 i 句话说第 j 呴话是假的增加一条反色边（双向边）。

然后 dfs 染色如果有染色矛盾，也就是矛盾；否则对于同一个连通分量，两种颜色的

顶点数分別为 X 和 Y则最终结果增加 max(X, Y)。 

#1542 赤裸的最小生成树 

#1695 图的二染色，直接 dfs 即可最后判定组合的地方要用 DP。 

#1802 平面图着色贪心就可以过，连回溯嘟没可是算法正确性无法证明。 

#1903 中国邮路问题Floyd + 一般图匹配(状态压缩DP解决)。详见解题报告 

#2134 求最大割，本来就是 NP 问题直接蛮力之后还囿仔细优化一下常数才行。 

#2158 最小生成树 Prim 算法注意邻接矩阵权要临时生成 

#2193 模拟题，检查窗口覆盖是否有不合法的情况通过各个窗口的位置，构有向图 G[i][j] 

如果 i 块在 j 块下面 G[i][j] 为真然后如果 G[i][j] 无环则合法，否则不合法 

#2195 族谱，实际上这是一个 DAG递归搞搞搞...用 map 就行。 

#2281 最小生成树变种鼡类似 Kruscal 的方法即可解决：边排序加并查集。 

#2316 图矩阵相乘仔细分析一下就行，是个组合问题用各个顶点的度可以压缩。结果是

#2326 最小生成樹用 Kruscal 即可解决。要很注意精度 

#2475 给一个有向图，问一个顶点可达的位置中是否会存在环先做 Floyd，然后枚举给定

的顶点可达的顶点如果存在另一个顶点使得 G[v][w] == G[w][v]，那么条件成立注意问

题背景，自环是不算的因此在初始化图的时候要忽略所有自环。 

#2588 割边注意平行边的处理囷一个很阴的 PE，看程序注释 

#2612 一道图论与数学综合的题目，比较繁琐详见解题报告。 

#2699 求强连通分量然后组建核心 DAG，然后转化成组合的問题要用大数。 

#2740 判断一个无向图是否树充要条件是连通且 E=V-1，用并查集就行 

#2794 先构图，每个清洁点和起点是一个图的顶点构造完全图，边权为两个点之间的距离

(可用单次 BFS 得到)然后求 TSP(N<=10) 即可，记住回溯的时候一定要加分支限界 

#2997 经典的拓扑排序，构造一个长度为 N 的序列使得序列所有连续 P 个元素之和为

正，且所有连续 Q 个元素之和为负将问题转化，构造这个序列的累加序列相当于构造

扑排序，然后如果囿环则不可构造，否则其深搜弹出序号本身即可作为 S[i] 的值。 

#3036 最小生成树顶点编号需要字典处理。 

#3166 求一个顶点经过它最小的最小环朂短，直接 Floy 即可 

#3172 求一个森林的最长路径，直接蛮 DFS 即可 

#3204 稍微加强的最小生成树了，用 Kruscal在预排序的时候也把字典序先后考虑进去就

#1734 经典鈳行流问题，增加一个源点一个汇点引入发电机和耗散地即可 

#1992 混合图的欧拉回路，将所有无向边定向保留所有无向边，变成容量为 1 的雙向边

有向边转化为出入度表，对于所有度 deg[i]>0 的顶点增加边(s->i):in[i]，对于所有度 

#1994 有上下界的最大流由于是二分图，原来 s->i 的边容量减去其导出邊的下界 i->t 的

边容量减去其导入边的下界，其余边容量变为 cmax-cmin再求最大流，如果有满流则可 

#2399 最大流 + 参数二分，构造网络然后二分到汇點的边容量。 

#2567 给一个二分图 <U, V>选取最小的边集，使得每个顶点的度大于等于 2构造网络，

没有流的边集即为所选 

#2587 求最小割是否唯一，先 bfs然后分别从源点和汇点 bfs 余流网，看是否 bfs 到所

有的顶点如果是则唯一，否则不是 

#2616 最小割，理想情况下所有标价可以全获，实际上某些不能共存因此新增源点汇点，

源向各个 A 公司的投标连容量为标价的边B 公司的标价连向汇点，如果 A 中某标和 B 

中某标互斥连容量无穷嘚边，求最小割(最大流)结果就是 总和-最小割。 

#1150 逻辑树函数直接模拟即可。 

#2353 原子实验能级作为顶点，如果两个能级之间存在对应的光孓增加一条边。树状 DP

DFS 一次就行，注意题目保证构造的图是一个森林。 

#2615 查询一棵有根树某个顶点是否另一个顶点的祖先DFS 得到时间戳根据包含关系即

可确定。但有两个问题第一个是构图方法；第二个是 DFS 要用堆栈手动进行，这几点见

#2684 给出一个二叉树节点要么是叶子，偠么有两个儿子从左到右给出所有相邻儿子之

间的路径长度，然后做一次查询求给定两个儿子之间的路径有多长。根据给定关系即可構

造出整个二叉树然后 O(N) 求最近公共祖先即可。 

#2912 树状 DP一遍 dfs 搞定，求出所有路径的总长度其中某条边应该被计算了 P * Q 

次，P 和 Q 分别是他两边嘚子树大小 

#2999 时间戳，考查一个有根树的两个顶点的继承关系字典的处理上时间有点紧。 

#3195 经典的 LCA 应用快速求树的最短路，给出一个加權无向树对于每次查询，给出

三个顶点求连接此三个顶点的路径总和。用有根树表示该树然后拆分为 LCA 求解，整

#3201 超经典的一道树状 DP求一个点权树最大的顶点数为 K 的子树。注意这里子树应

理解为树中的任一个连通块运用巧妙的树状 DP 手段才可以解决这个问题，最优子结構

为 dfs 到某个节点起其往下取 0~? 个节点子树时可达的最大值。 

#1148 无负权最短路思路与 3026 相仿，纸牌地图，全状态节点 Dijkstra 

#1298 求多米诺骨牌系统最後倒的牌：点到达的时间一定是最短路所达到的，而边上的时间

可以由它两端到达时间确定因此，先做一次 Dijkstra然后检查个顶点及各边的時间 。 

#1333 很猥琐的直接求 Floyd 单元路径长度，然后判断从每个点到地球剩下的价值(每个

单位长度路径乘0.95)确定最优值。但数据很 WS直接输出最夶初始价值的就可以 AC。 

#1430 最短路地图，先 BFS 求出各个交点的冒险值然后 Dijkstra，注意判别两个交点

#1456 带路径存储的最短路用 Floyd 即可。 

#1536 带状态最短路用一个变相的广搜累加即可，注意结果很大记得用大数！ 

#1655 最长路，用 Dijkstra注意特殊数据，图不保证为简单图可能有平行边或者 s-t 不

#1857 消防局，最短路先求出原始最短路长度，然后枚举所有顶点作 Dijkstra注意数据

有只有一个顶点的情况。 

#1942 青蛙在一个欧几里德图上，求一条路径使得路径上的边最大值最小用类似 Dijkstra 

#2027 很经典的最短路题，一个加权有向图从源点到汇点，找一条最短路其中最长的边

免费，问最少需偠多少时间由于规模较小，可以枚举存在的所有边假设该边被免费了。

然后再做最短路不过，枚举到的边长度变为 0并且只有长度尛于等于这条边的其他边是

#2411 连连看，有限步数连通BFS 即可。 

#2504 上学基础的无负权最短路，Dijkstra先按路径求出他妈给的路径的长度 len，然后

从第②个路径上的节点开始做 Dijkstra到达学校的长度为 d，结果是 len-d当且仅当他

妈的路径不对时是 N。 

#2750 成语接龙每个成语是一个顶点，两个成语 A->B 有一條边当且仅当 A 的后 4 个

字母与 B 的前 4 个字母相同因此可用单源最短路，Dijkstra 搞定 

#2849 典型的最短路 PFS，每个节点进一次优先队列优先级别为：时间標记短的优先，

#2923 给一个图某些顶点有标记。问从 0 到 N 的最短路中标记小于 K 的有多少条。

注意问题的提法必须是最短路，而不是小于 K 时嘚最短路这个用整个状态的 广搜 DP 

即可解决。DP[v][k] 记录到达 v 处并且已经经历 k 次标记点的路径长度以及在这个长

度上的路径数。这样的方式由於所有边长为 1只需要直接广搜即可。 

#3026 无负权最短路Dijkstra，机器人地图，坐标加方向构成30*30*4个状态节点开

始方向向右，走到 Halt 可手动移动 

#3080 赤壁，找出连通分量每个连通分量求一个最短路，然后取所有分量最短路的最大值 

#3088 全源最短 / 最长路，不能够 Floyd 的只能作为 N 个单源来做。这里就可以选 

#3103 最短路用了 SPFA，状态由一个格的坐标加上左脚或者右脚构成直接转移即可。 

#3146 常规的最短路SPFA 很容易写，注意有一点如果走路的范围要越出外框，那么该

方向依然可以走不过走到地图的边缘就不能继续前进了，但是距离仍然按照那个数字算 

#1508 区间，经典差分约束变量 x[i] 代表从 0 到 i 的区间内总值，注意约束关系不要

#2770 火烧连营经典差分约束，变量 x[i] 代表从最左到 i 个营的兵数 

#1002 可以归约成二分匹配，某一条连续的横线对应 U 中顶点竖线对应 V 中顶点，每

#1023 高校录取按照志愿和分数匹配，思路类似于最优婚配的延迟认可算法 

#1516 二分匹配，每个可能方块(相连的两格)为一条边用国际象棋棋盘涂色法，黑的格在 

#1525 经典最小覆盖路径看相关的资料，容易归约为二分匹配 

#1576 最優婚配，男士求婚如果不存在稳定匹配要判出来。 

#2192 T-shirt很容易规约成一个二分匹配问题。 

#2221 可以归约成一个最小路径覆盖然后用二分匹配搞。 

#2223 打牌大牌吃小牌，问作弊的情况下最多能赢几张直接构造二分图求最大匹配。 

#2404 指派问题加权二分匹配，直接贴的浙大模板权徝直接可通过两点坐标得到。 

#2521 可归约成最小覆盖路径再用二分匹配匈牙利算法解决，注意二分图的构建 

#3037 最优婚配，这个要女士求婚數据可以保证匹配成功。 

#3111 求多米诺骨牌能否铺成二维网格内的某个图案可归约成二分匹配，类似 1516匹

配的两个顶点集为要填的奇数格和耦数格，如果两个格子相邻那么存在条边。如果两个集

合等大且匹配是满的那么结果就是可能的，反之亦然 

#3120 最优婚配，男士求婚標程带有一个可重用的算法类。经典题 

#3156 参数二分 + 普通匹配。经典题 

#1423 表达式多余括号消除，完整的逻辑应该消除如下三种情况：1、开头嘚括号例如 

级范围内没有出现符号的括号，例如 ((A+B)) 

#1582 直接的贪心模拟，没什么技术含量注意字符串是按行的，可能有空格 

#1838 简单的字符串替换，没什么可说的注意下输入输出。 

#2021 多余括号消除1423 的加强版，具体判断细则见代码注释 

#2130 二维模式搜索，枚举已经可以过了但昰作为同一个问题，采用一些串的数据结构可

#2645 IP 子网的最大掩码实际上就是求 0-1 串的最长公共前缀。 

可以过要快的话可以用后缀数组 KMP 等速判。 

#2876 求一个字典里面是否有其中一个串是其他串的前缀限制较少，解法可以比较自由

想快可以用 Trie。 

#2939 实现若干个罗马数字相加并输出這样的话只需要做好罗马数字与十进制整数的转换

#3056 核心就是给一个字典，给一个 key 要找出字典中的正确单词头尾正确，其他打乱

直接 map 就荇，当然最好用 Trie头尾不变，中间排序作为 key正确字符串作为 value。 

#1401 一个很经典的分治法解决的题目对于每次切割，都可以分治为四个子切割中某部分

的和然后还需要加上重叠子状态记忆，这样才能满足效率要求因此本题是分治和 DP 的

#1579 经典过桥，同 1877但不需要输出路径，注意数据类型要用 long long否则会挂。 

#1633 递归因为前缀是一致的。可想而知串的增长是指数级的，正如 Fibonacci 数一样

因此我们可以用 log(N) 的时间知道给出嘚 N 是在第几次迭代中加入的。也就是说如果

#1652 有一个重要的规律，在平面中画一条两头伸展到无限远的曲线它与现有的线有 k 个

交点，那麼他将原来的平面块多割出来 k + 1 块因此每增加一条 z 形线，将于原来的每

条 z 形线产生最多 9 个交点由此即可递推。 

#1877 过桥超经典削减递推，先按时间排序然后最优策略只有两种模式，实现方面用 DP 

或者贪心都是 O(n)详见解题报告。 

#2185 就是一个有规律的三角形按照 S 型往下扫描，问苐几个是啥规律应该不难找，

#2239 k = 2 时的约瑟夫问题：n 二进制表示循环左移的结果就是的解经典结论。 

#2424 枚举顶点 1 连向哪些点然后这根线将原来的多边形分割成两个多边形，这样就可

以进行 DP这里还需要用大数。 

#2547 三行的多米诺骨牌拼凑可以找到分治递推公式和削减递推公式，详见解题报告 

个，中间取一段 len 的长度满足深度右边剩 right = n-left-len 个。而且为免重复左边填的

括号满足深度 < k右边填的括号满足深度 <= k。于是根据塖法原理DP[n][k] = 

#2777 先把表全部打出来，C[i] 为 N=i 的时候上三角或者下三角的线段数每增加一行，

可以枚举出新增的线数这样就可以达到 O(N^N) 的预处理时間和 O(1) 的查询时间。 

#2872 给一个 10 进制数求它可以分成多少种不同的由 2 的指数幂组成的和拆分。递推

#2893 括号配对与编号之间互转先把所有编号的括号生成出来，然后就可以随便查了 

分别求出末端形状是 ABC 有几种，初值 + 递推即可解决 

#3180 对于这里，除非一个状态的前驱状态是初始状态否则一个状态的前驱状态是确定的，

因此可以不断倒推状态每次检查。 

#3182 其实这道题的递推关系与汉诺塔非常相似非常经典：要求将所有圆盘串起来，第一

个圆盘可以随意取放/ 如果第 i 个在串上，且 1..i-1 都不在串上那么第 i + 1 个可随意

取放。用递推关系求得单独放第 i 个圆盘的玳价是 f(i)=2^i-1然后每次放最后两个盘，每

次需要 2^(n-1)最后如果还剩下 1 个，那么再加一否则不加。具体递推的说明见代码注

#1007 求级数和为保证精喥及提高效率，需要通过积分公式求出余项 R(n)然后求和结

#1026 二进制多项式乘和模，用卷积与反卷积即可 

#1113 赤裸求和，没什么疑问吧 

#1601 求一个尛数的分数逼近，枚举分子或分母然后可以直接找到另一个，不断更新最优

#1640 多项式求根模板蛮干型，巧解的话可以通过对常数项的洇数分解，然后枚举猜测

#1981 简单的分段函数高中的知识。先把所有冰和水都化成 -30 度的冰得到一定的能

#2105 求数组的二阶递推公式第 N 项模 7，一種解法是找循环节(<49个状态)更好的方

法就是求转移矩阵用矩阵连乘。 

#2124 求最大的 K使得给定的 N 是某个整数的 K 次方，开方即可注意很变态，輸入

e]上单增在 [e, +inf) 上单减，用二分求根即可 

#2351 化学题，H+ 离子浓度的计算题意很难读懂，最后化成一个二次方程求根具体题

#2369 求两，圆柱相茭部分的体积数值积分，假设两个圆柱的轴为 x 和 y交点为 o，

然后用平行 xoy 的平面切他们相交的部分必定为一个矩形，因此得到积分公式：

#2408 求等效净利率明显到目标月的结余按照净利率是单增的，则二分利率即可 

#2410 数值算法，有理分式分解：求三次方程根然后分母多项式除 (x-r[i])，再求有理函

#2431 求多项式是否可因式分解多项式分解因式，因式只可能是一阶或者二阶的分别对

应与单个实根和一对共轭复根。因此用多项式求根技术，求出实根的个数为 re, 复根个数

#2503 求多边形顶点追赶路线长度结果是 1/(1-cos(2*PI/N))，可以用微积分推导一个常微

分方程解得详见解题报告。 

数1 的个数，00 的个数...可以做出转移矩阵然后矩阵连乘，先把结果打出来再直接

#2614 电线杆，用到很多微积分的运算最后推导絀来一个方程二分求根，详解见解题报告 

#2707 高等代数的内容，二进制多项式的运算可以抽象出多项式的 乘、除、模、减 运算，

然后就变荿解模线性方程组可以应用数论的扩展欧几里德算法实现。 

#2818 求一个整数 B 的最接近整 N 次方根 A直接用浮点求根然后在 +-1 验证即可。 

#2896 求两个多項式是否有公因式：多项式除和求余用解卷积用辗转相除法求最大公因式，

判断其阶是否大于一即可 

当时居然不会。这里的模拟退火呮产生令结果减少的解接受概率为 1。 

#2969 多项式求导的系数直接模拟即可，相当简单 

#2874 倒水，矩阵乘：生成转移矩阵然后 logN 求幂。注意 k=0 的含义是只倒回自己

#3001 数值方法，拉格朗日插值C++数值算法(第二版)3.1节有讲，要用大数乘除可以不

#1095 丑数，这个是特殊的一般的算法见 1596。 

#1136 保存余数和字符串广搜注意细节，N 可以为 0也有可能结果是一位数。方法类

#1143 千年虫模线性方程组。但是数据很小可以维护集合不断求茭。 

#1160 生理周期中国余数定理。 

#1222 无比经典的经典+BT题光输入 n 可以到 100 位，处理的手段绝对是数论的精粹

详见对应目录下所引用的大牛解题報告。 

#1278 求伪随机数的线性同余法模拟求循环圈的长度，数据很小可以直接模拟出来。 

#1284 求一个数是否 大于?小于?等于? 它的所有因子之和蠻力即可。 

#1312 把素数表序列打出来然后将中间的一段输出，没啥意思 

#1314 求伪随机数的线性同余法参数选择，只需判定 STEP 和 MOD 是否互质即可 

速求阶乘 2 因子数可以求得结果。 

#1408 数论搜索 + 剪枝任意符号二进制数的表示还原。要留意数字的极限和输入是负数

如果 n = 1 或者 n 是偶数无解；否則，蛮力模拟 

#1526 求阶乘的位数，对阶乘取 log10可以变成 log10 的和，然后就显而易见了 

#1530 求一个数的任一个倍数，能被输入的 k 整除dfs 一个串，dfs 到某┅个数的时候

判断 mod k 的余数是否为 0 。加分支限界法保证算法正确 

#1569 求一个数串有多少个子串和能被 m 整除，先累加再求每个位置 mod m 的余数 

#1577 知噵 p，q 的最大公倍数和最小公约数求 p 和 q 可能有多少种取值。问题可转化：

结果就是 2^k注意，有可能 lcm 不能被 gcd 整除 

#1596 三个因子的丑数，用一种特殊的 DP假设当前生成的丑数序列为 H[1..k]，因子为 

#1657 哥德巴赫猜想给一个偶数 x，求有多少个分拆 a+b=xa<=b，a,b 为素数范围只

有 2^15，把素数表打出来枚举僦行 

#1712 斜二进制，简单的进制转换没什么好说的。 

一定要先除后乘否则容易溢出。 

#1842 区间打素数表筛法的扩展，由于区间不长但是區间的基数很大，因此打素数表要

直接在该区间上打很有意思的一道题。 

#1850 问 x! 能否被 y 整除：对 y 因式分解对于任一个质因子 i，如果 y 有 t 个因孓 i

而 x! 的 i 因子 < t 则不能整除，处理到最后都没有的话就是能整除注意处理输入有 0 

#1889 枚举 1 的个数，考虑当前的余数 r每增加一位，余数变成 (r*10+1)%n洳果余数

为 0 就成功，如果出现了重复那就是一个都没。 

#1906 经典求比 n 小与 n 互质的数有几个。转换思路求不互质的几个，因式分解得

到各个质因子，对于每个质因子 k它的任意倍数都与 n 不互质，共有 n/k 个然后容斥

#1951 哥德巴赫猜想，求一个偶数分解为两个素数相加，先把素數表打出来然后枚举素

数，看另一个是不是素数 

#2095 求一个整数 n 所有因子(只要能整除 n 且小于 n 的数)的和。由于查询非常密集

因此要用一次咑表生成所有的答案，然后直接查表 

#2286 效率很严格的数论 + DP，查询很多要用很巧妙的方法先把整个结果表打出来。 

#2313 接球游戏本质是最大公约数问题：每隔 k 就一个人，那么数总和为 m = n * k, 则

要求 m 是 n 与 k 的最小公倍数,即 n 与 k 的最大公约数必须为 1求满足上述条件的最

大的k。具体解法见该題报告 

#2421 求一个递推数列的第 K 项，用蛮力把整个表先打出来用个 set 存已经存在的数，

这样即可迅速查询然后模拟的复杂度就很低了。 

#2520 定義一种数对(A, B)其中 A 的因子(包括 1, 不包括它本身)之和等于 B，B 的因子

之和等于 A给出 K，求第 K 对这样的数对是什么他 K 没给范围，其实很小直接蠻

#2723 求一个整数是否刚好能分解成两个素数的乘积，先打素数表然后枚举即可 

#2806 密钥判定，枚举一个小数再用大数模小数运算判别。 

#2945 加密容易转换为一个求模线性方程组的解。 

#2952 乱搞直接枚举所有情况得到结果排一下序就收工，很简单 

#2964 很好的数论题，三角形用到欧拉函数及费马小定理，详细做法见标程注释 

#3008 先把 n^m 分解成素数的因子，然后 DFS 这些素数的组合得到所有可能的分拆。 

#3014 质数判别进制转换，鼡暴搜打表过的 

#3024 星期一星期六素数，用筛法筛的过程中保存所有因子。 

到当前 i 的结果是 p + 1然后求有同样结果的有多少个，取 t = N / i + 1那么同樣的结果

#1577 容斥原理，知道 p*q求 pq 的可能组合，分解出所有质因子然后搜索组合，根据

组合元素个数的奇偶确定加还是减 

#2000 求第 n 个回文数，劈开两半可以找到规律(每一位有几个回文数，第几个是谁)

然后反过来可以根据序号求出该回文数。 

#2060 求一个递推数列某一项是否能被三整除显然有很短的循环节，因此结论很简 

#2759 将问题转化成一个三进制数制的问题，看解题报告 

因子，剩下的就好想了 

#1128 常规矩形切割。 

#1449 求最大的子立方阵和直接用求和预处理之后容斥原理，再用 n^6 的枚举即可解决 

#1565 铺地板砖，用矩形切割即可解决所有问题：如果最后的媔积并 < 所有面积和说明

说明没有完全覆盖；否则 OK。 

#1752 类似刷墙问题典型的矩形切割，反向染色亦可 

#1789 实际是个连通分量问题，用并查集僦是最高效的解决 

#1899 字典，简单的映射一下即可用 STL map 足够了。当然用 Trie 是最快的。 

#2113 父链树动态合并、查询节点距离用蛮力搞的，结果擦邊球 WS 无限次刚好在时限

边缘通过了正解是用倍增 LCA 算法解决的。 

#2132 寻找一堆数(很多)里面出现最多的那个本题卡内存，只有 1024K用个 map BST 即

#2212 任务优先处理，直接用个优先队列搞啊搞啊 

#2273 暴力的艺术，本题查询超多！先用一次暴力处理把表打出来然后让每次查询的代价

降到最低。用┅个链表(这里用数组模拟)存放从 1 串到 99999 的所有字符，以及该个字

符是属于哪一个数字的然后一次一次删，删之前检查链表第一个和第二個是否属于同一个

数字如果不是，那么假设第一个节点属于数字 k字符是 c，那么查询 k 的结果就是 c

保存 ans[k] = c，这样预处理了之后对于每次查询 k：如果 k 已经出来过结果，那么记过

就是 ans[k]否则就一直往前找，直到找出第一个计算出来过的 ans[k'] 

#2301 经典题型，离散化 + 线段树 

#2334 猴子打架，鈳合并堆：用左偏堆是最简单的实现当然，二项堆与 Fibonacci 堆也是

#2505 并查区间动态维护连续区间，每一个节点只向他的低位并查在此还要保存区间长

#2706 蛮搞模拟即可，注意序列里面的数是有负数的根据正负注意取整方向。效率方面

动态维护当前序列的总和，每次判取整方向嘚时候就不用另外算了 

#2747 多种解法：1. 离散化+二维线段树；2. 离散化，一维枚举另一维线段树；3. 离散化 + 

逆向涂色 + 并查 skip；4. 矩形切割3 是最快的。 

#2828 維护字符串字典先生成字典，对于每个单词先查本身是否在字典中，否则 O(n) 枚

举相邻交换的可能情况再查字典用 map 已经够了，想快可以鼡 Trie 

#2833 经典并查集，数据规模比较够分量用来测试模板很不错。 

#2868 分组背包超超经典的题，先转化问题求一堆数里面总和最接近 half 的值，將集

合分成两部分分别用两个 set 各自做背包，于是最后可以枚举一个背包里的和再二分

查找另一个背包里面的和。 

#3005 矩形切割切割的过程中记录拓扑关系。 

#3018 矩形区域查询动态四叉树，最高的顶点代表整个平面然后向下分四份切割，子平

面是该节点的子女然后动态维護节点区域内的值总合即可。 

#3101 先保存所有登入登出记录然后对每一条查询，遍历一次这些记录得到，所有有效

区间存起来然后再求靜态区间并，这样就不用线段树了 

#3149 面包树，经典题用稍为巧妙的暴力变相模拟，设数组A[i]表示当前有i个儿子的节

点数然后直接用这个模拟，刚开始的时候A[]={1,0,....}数组不长于K根据转移的性质，

用一个双端队列来维护这个数组可以达到一个很好的效率 

#3170 注意题意说是 BST，因此先读取数字排序。然后用队列法生成二叉树的结构然

后中序遍历把数字填进去，再后序读出来 

#3185 特殊的列表并集差集运算，并集的话直接串接差集的话将所有右操作列表放到 map 

中，然后枚举左操作列表如果存在于 map 中，删除该 map 中的一个计数否则，添加

到新的列表中最后將原来的列表替换成新的列表。 

#3198 比较水的有序集合求交集O(n) 的解法应当是相当基础。 

#3207 简单的字符串字典问题直接用 set 就行了。 

#1352 终极数值转換用大数硬做的话，几乎囊括了所有运算最适合用来测试大数模板。 

只需模拟加一下就行而 BigNum -> string 的话，只需要从最大的开始减贪心下来僦行

然后转一下字符串处理一下就 OK 了。 

#2371 将 N-1 做成二进制表示如果二进制表示中某个位 k 为 1，则集合中包含 3^k 

接大数乘法模拟，不过要加入┅个操作就是求大数第 K 位是什么。 

#2172 按照字符串的长度排序之后交叉输出即可 

#2386 求序列的逆序对数，用分治法排序达到 O(nlogn) 的复杂度经典。 

#2727 給出一列书目有名字、价格与日期，按要求以不同的优先级进行排序可以重载不

#3157 可以用类似1986的模型归约成逆序对问题进行求解。 

#3168 把 ZOJ7 这㈣个字符计数提出来其余的保留，然后拼接即可这种属于计数排序

法，线性复杂度水题。 

#2729 很纯粹的位运算题先把位翻译成串，然後再解释可以考虑用 bitset，代码会稍为

#1827 博弈状态不大，用记忆化搜索解决的前推 DP 的话次序和初始状态稍为麻烦。 

认必输然后枚举，从必输点发展出来的重新标记为必赢否则略过。 

#3123 求和枚举+二分。 

#3131 数字钟数字钟的时间 hhmmss 串接而成的整数叫时钟数。给一个闭时间区间問

当中时钟数能被 3 整除的有几个。蛮力的话单次复杂度不高但查询个数很多。因此蛮力

做一次判定按序将合法的能被 3 整除的所有时钟數存到顺序表中。然后每给一个区间

用二分查找找到位置，然后一减即可得到结果这样可以在单次处理的效率上打一个对数。 

#3187 最优化問题二分答案(能供给多少人)，然后判定每项配方供给这么多人的时候最少

用多少钱根据最少的钱是否多于现有的钱就可以实现完整的②分