盘点最近遇到最坑的AC题

# 互动｜晒出你的期末真实状态

互动｜晒出你的期末真实状态 AC狗友们！ 发下现在大家期末进度完全不一样，状态五花八门：有人早就考完，快乐躺平自由玩耍；有人还没开考，每天疯狂冲刺；还有人卡在中间，一边焦虑一边摸鱼摆烂…… 本次话题也随之调整，不局限复习干货，欢迎自由分享！ ✍️ 随便聊聊你的期末日常 不用硬讲复习干货，想说什么都可以： 你现在处在哪个期末阶段？考完 / 备考中 / 刚开考 期末专属解压、摸鱼小方式 近期最真实的期末碎碎念、吐槽趣事 评论区自由发言，一句话吐槽、搞笑碎碎念、干货经验全都收！ 🎁 罐头福利放送 活动结束统一结算奖励： 1. 评论点赞TOP5：每人50罐头 2. 随机抽取5位幸运友友：每人20罐头 ⏰ 活动时间 即刻起 — 2026年7月5日 快来评论区晒出你的期末真实日常，角逐最强期末生存大师！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 往期互动

互动｜真没招了！那些让你当场放弃的瞬间

真没招了！那些让你当场放弃的瞬间👇 Hi，AC狗友们 。有没有那么一刻 ，你对着屏幕 / 书本 / 生活 ，默默说了一句：“算了，真没招了”。 不是摆烂，是真的尽力了 。但结果还是……emmm 🎁交出你的“没招了”瞬间🧾 👉 你最近一次觉得 “真没招了” 是什么时候？ 👉 因为什么事？后来怎么解决的（还是没解决）？ 评论区直接写👇 例子：“调代码调了俩小时，结果是中文分号，真没招了。” 格式不限，一句话 or 小故事都行～ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 福利时间 活动截止后： * 评论点赞前 5 名 → 罐头 × 50： @💩💩百大游戏解说官💩💩，@꧁慕温ᨐ꧂(不加团 新人)LHY，@科技起源，@萧瑶自在，@‮‏‏ * 随机抽 5 人 → 罐头 × 20 ：@小金 回关，@AC乔，@人机猫，@永盼，@含双（破谜者暮汐.研梦） ⏰ 即日起 至 2026 年 6月 16 日 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💬 评论区交出你的 “没招了” 瞬间 往期互动

Code date creation发布

hi，acgo朋友们，我带来最新一款数据生成器Code date creation。 榜2了加油！ 预告 下一次，exceed！ 为每个人造福！ CDCFUTURE发布了！ 增加小工具，各种功能集全。 相比较PRO1.0.0兼容好点了图片。 电脑系统不同，有些小工具不能用。 图片可以保存。 手动选择g++会自动保存。 界面美化。 懒人化彻底。 下载FUTURE http://b-bu.cn/b01d70zgla 密码：CDC未来 展示 常规 图片与颜色 图片因为导入不同，一直刷新，所以卡。 提示 只有正式版源码会公开！ 开发日志 2026年6月12日 5.0.0发布 2026年6月19日 6.0.0发布 2026年6月20日 pro1.0.0发布 2026年6月21日 future发布 介绍 Code-date-creation 是一款由 CDCluogu 团队研发的新一代 C++ 图形化数据生成器。该工具可以帮助用户在洛谷网站、acgo网站等平台上生成测试数据。 该工具包含一个安装包，用户可以将其安装在计算机上。安装完成后，用户可以通过运行主体exe文件来使用它。 Code-date-creation 的主要功能是为 C++ 编程者提供一个方便的工具，用于生成各种类型的测试数据。这些数据可以用于测试和验证 C++ 程序的功能和性能。 该工具的使用非常简单。首先，用户需要将 Code-date-creation 安装到计算机上。然后，通过运行主程序，用户可以选择要生成的数据类型，如数组、字符串、函数等。接下来，用户可以根据需要进行配置，例如设置数据的范围、长度等。最后，用户点击“生成”按钮，即可生成所需的测试数据。 总之，Code-date-creation 是一个功能强大且易于使用的 C++ 静态数据生成器，可以帮助用户轻松生成各种类型的测试数据。又CDCluogu研发出的，新一代C++静态数据生成器，包含安装包，已经主体exe，帮助你在洛谷网站或acgo网站等生成测试数据，cpp已公开。 此介绍摘自此网站 功能介绍 可帮助你快速编译数据，支持随机数据和自编译模式，界面图形化。 只要你有AC代码就能造！ 快速帮助新手上手。 6.0.0新功能 在此次生产数据中，可自动打包zip 由于自编译不同，只会加入一组测试数据，剩下需要自行加入。 我们会在6.1.0修复。 5.0.0新功能 我们支持颜色更改，换一下主题也不错，如果想换回来，可以点默认颜色呢，此软件保留之前颜色。 版权问题 以下是本次工作人员。 starryfast 主策划（编写者兼宣传） 也就是我。 StellarCode bug测试 pjz1061065454 360安全测试 skysunrise_c颜色测试 chfqwq全科测试 我们开发团队仅有这些人，请注意辨别。 市面盗版不要下载，可能中病毒。 本次使用 VSCode 编译，主要为**C++**代码编译。 软件要求 本次软件有安装包，需要您的电脑有 g++。 没有安装包有自带 g++，不过自带 g++ 仅仅支持 C++11。 请确保您的电脑空间充足。 下载 5.0.0下载网站：http://b-bu.cn/b01d70edvg ，密码CDC500 6.0.0下载网站：http://b-bu.cn/b01d70wg6h，密码CDC600 PRO下载网站 ，密码：CDCPRO 代码仓 github：https://github.com/starryfast/Code-date-creation gitcode https://gitcode.com/starryfast/Codedatecreation 招募 现在招一位bug检测和宣传。 有意者联系作者。 QQ：272215275 邮箱：272215275@qq.com 联系同意后加入。 https://www.luogu.com.cn/team/129680 https://gitcode.com/starryfast 详细解说 https://www.bilibili.com/video/BV1jzJp6CEG8/?spm_id_from=888.80997.embed_other.whitelist&bvid=BV1jzJp6CEG8 提醒日志 2026年6月18日19:18:29 目前不适合特别麻烦数据，如果数据过于麻烦，使用自编译模式 2026年6月20日10:08:32 不支持小熊猫 C++ 编译器的 g++ 感谢 感谢支持者 @AC君 亮出你安装的生成器吧

我的马蜂真的很AI吗？？？

我的马蜂真的很AI吗？？？ 难道你们不加空格吗？？？ 放代码 告诉我

MMOI R1 T1-3 题解

难度大概是橙黄黄绿吧。感谢金钩大佬在百忙之中出思维好题给我们。 T1 Difficulty：3- / Easy Tag：- 假设存在一个 xxx 使得满足 pi>n−xp_i\gt n-xpi >n−x 的数量大于 xxx。 注意到是排列，所以不可能。 所以修改显然不优。 所以最优解是不把任何平台修改接收平台，答案就是 pi≤ip_i\le ipi ≤i 的数量。 时间复杂度：O(n+q)O(n+q)O(n+q)。 T2 Difficulty：3.4 / Easy Tag：- 脑电波题。 注意到如果 nnn 是奇数，出现的数只有奇数和 000 可以这么构造： [n,n−2,...,9,7,5,3,1,0,1,3,5,7,9,...,n−2,n][n,n-2,...,9,7,5,3,1,0,1,3,5,7,9,...,n-2,n][n,n−2,...,9,7,5,3,1,0,1,3,5,7,9,...,n−2,n] 偶数同理。 然后注意到把这两块拼出来，中间有三个 000，而最左边和最右边的空的距离恰好是 n+1n+1n+1，刚好能放进 nnn。所以构造如下（这里展示 n=11n=11n=11 的）： [9,7,5,3,1,11,1,3,5,7,9,10,8,6,4,2,0,11,2,4,6,8,10][\red{9,7,5,3,1}\green{,11,}\red{1,3,5,7,9}\blue{,10,8,6,4,2},0\green{,11,}\blue{2,4,6,8,10}][9,7,5,3,1,11,1,3,5,7,9,10,8,6,4,2,0,11,2,4,6,8,10] 时间复杂度：O(∑n)O(\sum n)O(∑n)。 T3 Difficulty：3.5 / Easy Tag：隔板法 首先计算长度为 nnn 的方程数。 其实就是求 n+A1+A2+...+An+1=Sn+A_1+A_2+...+A_{n+1}=Sn+A1 +A2 +...+An+1 =S，Ai≥0,An>0A_i\ge 0,A_n\gt 0Ai ≥0,An >0 的整数解数量。容斥一下，分别计算 n+...=Sn+...=Sn+...=S 与 n+...=S−1n+...=S-1n+...=S−1 的非负整数解数量。这里讨论前者。 移一下项，A1+A2+...+An+1=S−nA_1+A_2+...+A_{n+1}=S-nA1 +A2 +...+An+1 =S−n。根据隔板法，答案为 (Sn)S\choose n(nS )。 所以总数为 ∑n=1S(Sn)−∑n=1S(S−1n)=2S−2S−1=2S−1\sum_{n=1}^S {S\choose n}-\sum_{n=1}^S {S-1\choose n}=2^S-2^{S-1}=2^{S-1}∑n=1S (nS )−∑n=1S (nS−1 )=2S−2S−1=2S−1。第二问就是在问满足 ∑n=1m(Sn)−∑n=1m(S−1n)>k\sum_{n=1}^m {S\choose n}-\sum_{n=1}^m {S-1\choose n}\gt k∑n=1m (nS )−∑n=1m (nS−1 )>k 的最小的 mmm。 注意到 (Sn)S\choose n(nS ) 增长极快，当 SSS 较大时，m=2m=2m=2 时原式就已经超过 10910^9109 了。所以组合数怎么实现都行。 我使用了一种十分拟人的 O(mS)O(m\sqrt S)O(mS ) 实现求组合数。能过就是好算法 时间复杂度：O({∅,∅,∅,{∅},{∅,∅,{∅}}}×S)O(\{\varnothing, \varnothing, \varnothing, \{\varnothing\}, \{\varnothing, \varnothing, \{\varnothing\}\}\}\times\sqrt S)O({∅,∅,∅,{∅},{∅,∅,{∅}}}×S )。 T4 不会。

分组背包

怎么上榜三的 万能开头@78鼠鼠 @156****6690@仰天长啸你爹驾到@AC酱 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 溢位

关于小码王2026暑期集训营...(预)

今年小码王不出意外的又又又又要办暑期集训营了（应该是为了CSP竞赛搞的封闭集训。？） 然后大概就是家父家母又给我报名了吧嗯对 去年是7.11-7.21+7.21-7.31两期20天连续报的 XP0102的课 但我的听课质量毫不意外的在初赛就落榜了；；； 去年的住宿我那个房间前几天阳台门没关严 导致屋内变成了“盘丝洞” 但视野很好 前十天的房间可以直接从阳台那里看到2022冬奥的那个冰雪大跳台（顺带说一句去年的住宿是河北的一个什么睿景什么酒店来着 挨着大跳台的；甚至集训营的合照都是去大跳台那一片的草地拍的） 今年报的两期是分开的：7.21-7.31XP03，8.11-8.21XP04【不敢想知识点对我的恐怖程度】 这期集训营我的坐标：河北or北京（应该是北京但我不确定 确定了在此帖PLQ通告） so如果有和我IP坐标或入营时间一样的在PLQ报个到口贝 也欢迎其他IP&入营时间的狗友来此帖冒泡 bye bye我们下个帖子见

官方题解 | 欢乐赛#75题解

官方题解 | 欢乐赛#75题解 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 皓仔卖蜂蜜 入门 T2 皓仔加油 入门 T3 皓仔找不同 入门 T4 皓仔的十六进制矩阵 入门 T5 皓仔的回响数 普及- T6 皓仔的字符串修剪 普及- T1 皓仔卖蜂蜜 题目大意 已知每个礼盒需要放入 aaa 瓶蜂蜜。现在皓仔一共有 nnn 瓶蜂蜜，他会尽可能多地把蜂蜜装成完整的礼盒。 请你帮皓仔计算：装完所有能装成礼盒的蜂蜜后，还会剩下几瓶蜂蜜。 题解思路 nnn 瓶蜂蜜， 每个礼盒需要装 aaa 瓶， 问最后剩下几瓶， 这个问题也就是问数字 nnn 除以 aaa 之后的余数是多少， 因此答案直接输出 n%an \% an%a 即可。 参考代码 T2 皓仔加油 题目大意 已知皓仔身上一共有 xxx 元钱，当前油价为每升 ppp 元，汽车油箱最多可以装 vvv 升油。 皓仔想尽可能多地加油，但是加油量不能超过油箱容积。 请你计算皓仔最多可以加多少升油。 题解思路 假如将身上所有的钱都拿去买汽油， 则可以买到 x/px / px/p 升汽油， 但是需要注意油箱最多只能装 vvv 升油，因此最多可以加的油量需要在二者中取一个较小值。 也就是当 x/p≤vx / p \le vx/p≤v 时候， 输出 x/px / px/p，否则输出 vvv。 参考代码 T3 皓仔找不同 题目大意 给定一个长度为 nnn 的数组。 这个数组中，有且只有一个数字和其他所有数字不同，其余 n−1n-1n−1 个数字都是相同的。 现在请你找出这个特殊数字所在的位置，输出它的下标。 数组下标从 111 开始。 题解思路 给定的数字在数组中固定只出现一次， 因此可以从前往后遍历数组， 对于每一个长度为 333 的相邻数字段， 看是否存在一个数字与另外两个数字不同。 变量 iii 循环遍历从 111 开始到 n−2n - 2n−2 结束，每次遍历相邻的 333 个数字 a[i],a[i+1],a[i+2]a[i], a[i + 1], a[i + 2]a[i],a[i+1],a[i+2]， 只要其中某个数字和另外两个数都不相同，就是我们要找的答案， 输出对应下标即可。 参考代码 T4 皓仔的十六进制矩阵 题目大意 给定 nnn 行 nnn 列的表格，每个位置上都是一个十六进制字符。 十六进制字符包括： * 0 到 9 * A 到 F 其中，字符 0 到 9 分别表示数值 000 到 999，字符 A 到 F 分别表示数值 101010 到 151515。 现在请你计算两个十进制结果： * 所有行的总和中，最大的那一个行和； * 所有列的总和中，最大的那一个列和。 题解思路 本题中可以不用专门开二维数组记录完整的表格， 只需要开两个数组 row[]， col[] 用以记录每一行每一列的总和。 例如 row[i] 表示第 iii 行的总和， col[j] 表示第 jjj 列的总和。 两重循环遍历表格的每一个位置 (i,j)(i, j)(i,j) ，输入对应的十六进制字符 xxx 并且转化成对应的数值: * 当 xxx 为数字字符时， 对应的数值 ccc 为 x - '0'; * 当 xxx 为大写字母时候， 对应的数值位 x - 'A' + 10； 然后将该数值累加到所在行和所在列的数组中，也就是 row[i] += c, col[j] += c； 最后完整遍历所有行和所有列， 求出最大的行总和，以及最大的列总和即可。 参考代码 T5 皓仔的回响数 题目大意 如果一个正整数的十进制表示可以写成 ababab... 的形式，也就是由同一个两位数字片段不断重复组成，且两个数字不同，那么皓仔就称它为“回响数”。 例如： * 1212 是回响数，因为它可以看成 12 重复了 222 次； * 343434 是回响数，因为它可以看成 34 重复了 333 次； * 9090 是回响数，因为它可以看成 90 重复了 222 次； * 1234 不是回响数。 特别地，回响数的位数必须是偶数，并且至少有 444 位。也就是说，像 12 这样的两位数不算回响数。 现在给定两个整数 l,rl,rl,r，请你统计区间 [l,r][l,r][l,r] 中一共有多少个回响数。 题解思路 注意到数据范围中 r−l≤106r - l \le 10^6r−l≤106， 也就是说虽然值域非常大ai≤1018a_i \le 10^{18}ai ≤1018， 但是所有需要我们判断的数字数量只有 10610^6106 个。 因此可以枚举 lll 到 rrr 范围内的所有数字， 进行数位分解， 判定是否是回响数， 是的话答案加一。 最后输出回响数个数就好。 本题的另一种解法是枚举所有的 ab的可能，并且进行重复拼接得到所有的回响数，可以得到总的回响数个数是较少的。枚举所有的回响数看是否在 [l,r][l, r][l,r] 区间内即可。 参考代码 T6 皓仔的字符串修剪 题目大意 皓仔拿到了两个字符串 sss 和 ttt。 他可以对每个字符串进行若干次删除操作，每次只能删除当前字符串最左端或最右端的一个字符。 也就是说，经过若干次操作后，字符串中剩下的部分一定是原字符串中的一个连续子串。 皓仔希望通过删除操作，使得两个字符串最后剩下的内容完全相同。请你求出最少需要删除多少个字符。 如果两个字符串没有任何公共字符，也可以把两个字符串都删空，此时剩下的内容都为空串，也是剩下内容完全相同的情况。 题解思路 本题问最少删除多少个字符可以使得剩余的子串相等， 因此问题可以转化成两个字符串 s,ts, ts,t 的最长公共子串有多长。 因此可以枚举 sss 的所有子串， 并且在 ttt 中寻找该子串是否出现过， 出现过的话则该子串可以认为是两者的公共子串。 获取 sss 的子串这一操作可以直接使用成员函数 substr 获取， 在 ttt 中查找子串是否出现过可以直接使用成员函数 find来获取。 参考代码

MMOI Round 1 题解

T1 刷怪塔 现在我们证明取 x=0x=0x=0 总是最优的。令最高层刷怪平台为 t=n−xt=n-xt=n−x，考虑通过接收平台满足目标的平台个数，即满足 i≤ti\le ti≤t 且 pi>tp_i>tpi >t 的 iii 的个数，由于 ppp 是一个排列，这个数量一定等于 pi≤t<ip_i\le t<ipi ≤t<i 的 iii 的个数，因此将 xxx 改为 000 后仍然满足 pi≤ip_i\le ipi ≤i，原来合法的仍然合法，不会变得更劣。 因此问题等价于求有多少 iii 满足 pi≤ip_i\le ipi ≤i，直接维护即可，时间复杂度 O(n+q)O(n+q)O(n+q)。 T2 染色 先将 1∼n−11\sim n-11∼n−1 的所有奇数颜色排成 …,5,3,1,?,1,3,5,…\dots,5,3,1,\text{?},1,3,5,\dots…,5,3,1,?,1,3,5,… 的形式，再将 1∼n−11\sim n-11∼n−1 的所有偶数颜色排成 …,6,4,2,?,?,2,4,6,…\dots,6,4,2,\text{?},\text{?},2,4,6,\dots…,6,4,2,?,?,2,4,6,… 的形式，将两者并排放置可以得到： …,5,3,1,X,1,3,5,…,6,4,2,Y,Z,2,4,6,…\dots,5,3,1,X,1,3,5,\dots,6,4,2,Y,Z,2,4,6,\dots …,5,3,1,X,1,3,5,…,6,4,2,Y,Z,2,4,6,… 此时还剩下 0,n,n0,n,n0,n,n 三个颜色要放在 X,Y,ZX,Y,ZX,Y,Z 的位置，而不难发现 XXX 与 ZZZ 下标差恰好是 n+1n+1n+1，因此令 X=Z=n,Y=0X=Z=n,Y=0X=Z=n,Y=0 即可构造出一个符合条件的序列，时间复杂度 O(n)O(n)O(n)。 T3 数学题 当整式 PPP 的次数 nnn 固定时，所求即为 a0+a1+⋯+an=n+Sa_0+a_1+\cdots+a_n=n+Sa0 +a1 +⋯+an =n+S 的方案数，其中 a0,a1,…,an−1a_0,a_1,\dots,a_{n-1}a0 ,a1 ,…,an−1 为自然数，ana_nan 为正整数。这可以转化为 (a0+1)+(a1+1)+⋯+(an−1+1)+an=S(a_0+1)+(a_1+1)+\cdots+(a_{n-1}+1)+a_n=S(a0 +1)+(a1 +1)+⋯+(an−1 +1)+an =S，其中 a0+1,a1+1,…,an−1+1,ana_0+1,a_1+1,\dots,a_{n-1}+1,a_na0 +1,a1 +1,…,an−1 +1,an 均为正整数。由插板法可得方案数为 (S−1n)S-1\choose n(nS−1 )。 对于第一问，好的整式 PPP 的个数即为 (S−10)+(S−11)+⋯+(S−1S−1){S-1\choose 0}+{S-1\choose 1}+\cdots+{S-1\choose S-1}(0S−1 )+(1S−1 )+⋯+(S−1S−1 )，这等价于从 S−1S-1S−1 个物品中选出来任意多个物品的方案数，所以第一问的答案为 2S−12^{S-1}2S−1。 对于第二问，由于次数为 nnn 的好的多项式的个数为 (S−1n)S-1\choose n(nS−1 )，我们可以从小往大枚举 nnn，统计次数小于等于 nnn 的好的多项式个数之和，直到数量大于等于 kkk 时输出答案。由于当 (S−1n)S-1\choose n(nS−1 ) 随着 nnn 增大是指数级别增长的，复杂度可以接受。 实现时可能需要使用 __int128。 T4 探索 显然移动后 x+yx+yx+y 的奇偶性不会改变，所以每个方格都只会有一条对角线可能被经过。考虑对于所有 x+yx+yx+y 为偶数的点建图，在每一个方格能经过的对角线两点间连边。问题转化为在这个图上至少要删除几条边才存在一条从 (0,0)(0,0)(0,0) 到 (x,y)(x,y)(x,y) 的欧拉路径。 这张图上两个点间的最短路长度很容易计算：d(P,Q)=max⁡(∣xP−xQ∣,∣yP−yQ∣)d(P,Q)=\max(|x_P-x_Q|,|y_P-y_Q|)d(P,Q)=max(∣xP −xQ ∣,∣yP −yQ ∣)。 而一张图存在欧拉路径的充要条件是起点和终点的度数为奇数，其余点度数均为偶数。不难发现这张图上度数可能为奇数的点只有四个：A(0,0),B(n,0),C(0,m),D(n,m)A(0,0),B(n,0),C(0,m),D(n,m)A(0,0),B(n,0),C(0,m),D(n,m)。具体地，按照 n,mn,mn,m 的奇偶性可以得到： * n,mn,mn,m 都是奇数：奇度点是 A,DA,DA,D。 * nnn 是偶数，mmm 是奇数：奇度点是 A,BA,BA,B。 * nnn 是奇数，mmm 是偶数：奇度点是 A,CA,CA,C。 * n,mn,mn,m 都是偶数：奇度点是 A,B,C,DA,B,C,DA,B,C,D。 先考虑 n,mn,mn,m 中至少有一个是奇数时的做法。此时图中只有两个奇度点 AAA 和某一个角 ZZZ。若终点是 TTT，我们的目标就是删除一些边使得只有 A,TA,TA,T 的度数为奇数。不难发现这本质上相当于找到一条从 TTT 到 ZZZ 的最短路并删除，之后跑欧拉路径即可。 现在考虑 n,mn,mn,m 均是偶数的做法。类似地，我们要将 T,B,C,DT,B,C,DT,B,C,D 四个点分成两对，删去这两条最短路。可以证明，存在一种选这两条最短路的方案使得这两条最短路不重合。枚举配对方案，找到答案最小的一组即可。 注意上述讨论中没有考虑 T=A,B,C,DT=A,B,C,DT=A,B,C,D 的情况，实现时需要精细讨论。 时间复杂度 O(nm)O(nm)O(nm)。

深高北-双指针

双指针思想笔记（C++版） 一句话理解 > 双指针：用两个“箭头”在数组或字符串上移动，解决需要比较、查找、反转等问题。 就像两个人同时在一条路上走，有时一起走，有时面对面走，用他们的位置关系来解决问题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、什么是双指针？ 双指针：使用两个指针（下标）来遍历数据结构，通过移动指针来高效解决问题。 核心思想：利用两个指针的位置关系，减少循环的层数，把 O(n²) 变成 O(n)。 常见类型： * 左右指针：一个在左，一个在右，向中间移动 * 快慢指针：一个走得快，一个走得慢 * 同向指针：两个都从左边开始，一前一后 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二、左右指针（对撞指针） 题目1：两数之和（洛谷P1102） 题目描述：给定 n 个从小到大排好序的整数和一个目标数 target，请找出两个数，使它们的和等于 target。输出这两个数的下标（从1开始）。题目保证有唯一解。 输入样例： 输出样例： （因为 a[2]=2, a[4]=6，和是8） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目2：回文判断（洛谷P1015） 题目描述：给定一个字符串，判断它是否是回文串（正着读和倒着读一样）。字符串长度不超过1000。 输入样例： 输出样例： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目3：盛最多水的容器（洛谷P1652） 题目描述：给定 n 个非负整数 a[1], a[2], ..., a[n]，每个数代表坐标中的一个点 (i, a[i])。找出两条线，使得它们与 x 轴构成的容器能容纳最多的水，输出最大面积。 思路：左右指针，每次移动高度较小的那个指针。 输入样例： 输出样例： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三、快慢指针 题目4：删除有序数组中的重复项（洛谷P1116） 题目描述：给定一个有序数组，删除重复出现的元素，使每个元素只出现一次，返回新数组的长度。不要使用额外数组，必须在原数组上操作。 输入样例： 输出样例： （去重后前4个位置：1 2 3 4） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目5：找出数组的中间位置 题目描述：给定一个数组，找出它的中间位置。如果数组长度是奇数，输出正中间的下标；如果是偶数，输出靠左的那个中间下标。 输入样例1： 输出样例1： 输入样例2： 输出样例2： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 四、同向指针 题目6：移除元素（洛谷P1177） 题目描述：给定一个数组和一个值 val，原地移除所有数值等于 val 的元素，返回新数组的长度。元素的顺序可以改变。 输入样例： 输出样例： （剩余元素：1 3 4 5 6 7 8） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目7：把0移到末尾（洛谷P1111） 题目描述：给定一个数组，把所有的0移到数组的末尾，同时保持非零元素的相对顺序。 输入样例： 输出样例： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 五、双指针常见题型总结 类型 指针移动方式 经典题目 左右指针 一左一右，向中间移动 两数之和、回文判断、盛水容器 快慢指针 一快一慢，快慢速度不同 数组去重、找中点 同向指针 一前一后，都向右移动 移除元素、移动零 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 六、时间复杂度对比 方法 时间复杂度 空间复杂度 暴力双重循环 O(n²) O(1) 双指针 O(n) O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 七、易错点 易错点 正确做法 下标从0开始还是从1开始 本笔记统一从1开始 左右指针需要数组有序 两数之和、盛水容器需要有序 循环条件写错 左右指针用 left < right 快慢指针边界 注意 fast + 1 <= n 防止越界 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 八、总结 要点 内容 核心思想 用两个指针减少循环层数 时间复杂度 O(n) 空间复杂度 O(1) 适用场景 数组、字符串相关问题 下标习惯 本笔记统一从1开始 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 记忆口诀 > 双指针，真神奇，两个箭头来回移 > 左右指针向中间，两数和与回文题 > 快慢指针一快慢，去重找中点搞定 > 同向指针一前后，移除元素移零灵 > 暴力循环 n 平方，双指针 n 就搞定 > 下标统一从1起，边界判断要仔细 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------