N0Ne-Zer0's Blog

近期遇到的好题，值得反复回味。 持续更新，最新的在前面。 本文由AI分析题解后经个人修改而成 超节点——把 O(N²) 降为 O(N) 来源：ABC463-E — AtCoder Beginner Contest 463 技巧：超节点，堆优化 Dijkstra，代价拆分 思路：传送门花费为 Xu+Xv+YX_u + X_v + YXu​+Xv​+Y，如果暴力为每对 (u, v) 建边，是 O(N²) 的稠密图，Dijkstra 不可接受。关键洞察：传送代价可拆分——引入两个超节点 S、T，建 u→Su \to Su→S（权 XuX_uXu​），S→TS \to TS→T（权 Y），T→vT \to vT→v（权 XvX_vXv​），则 u→vu \to vu→v 传送等价于 u→S→T→vu \to S \to T \to vu→S→T→v。从 N² 条边降为 2N+1 条，配合堆优化 Dijkstra 即可。 核心：超节点拆分这类"与两端相关的代价"是图上最短路的经典模式。见到 f(u)+f(v)+Cf(u) + f(v) + Cf(u)+f(v)+C...

这里记录我需要完成的文章 题解篇 Codeforces AtCoder 算法篇 图论系列 最短路（Dijkstra 堆优化 / SPFA 判负环 / Floyd）（已完成） 最小生成树（Kruskal / Prim） 拓扑排序 Tarjan（SCC 缩点 / EDCC 缩点） 二分图最大匹配（匈牙利算法） 差分约束 网络流（Dinic 最大流 / EK 费用流） 2-SAT 数据结构系列 树状数组（BIT）（已完成） ST 表（静态 RMQ）（已完成） 前缀和 / 差分（一维 / 二维）（已完成） 线段树合并（配合树上操作） 可持久化 01 Trie（配合异或 / 数位） 点分治（统计树上路径） DSU on tree（树上启发式合并） 莫队 + 分块 CDQ 分治 DP 系列 背包 DP（01 / 完全 / 多重 / 分组） 区间 DP 状压 DP 树形 DP 数位 DP 单调队列优化 DP 斜率优化 DP 数论系列 EXGCD（扩展欧几里得） 高斯消元（实数 / 异或方程） 线性基（异或最值） 容斥原理 矩阵快速幂（加速递推） 欧...

引言 最短路分为一些情况，主要有分类：非负or含负、边权or点权、单源点or全源点。 含有负权时还需要判断有无负环，而如果是点权则可以通过将一个点分裂成入点和出点，从而将点权转化为边权。 至于全源最短路好像考察的很少，Floyd也非常简单粗暴，而Johnson算法的势能思想是将负权图转化为非负权图从而可以跑Dijkstra。 在这篇文章中会设计到以下算法： 朴素Dijkstra和堆优化Dijkstra，处理非负权图最优 Bellman-Ford，常用于判断负环和限制经过边数 SPFA，Bellman-Ford的队列优化形式，容易被特殊构造图卡死导致TLE Floyd，基于DP的全源最短路，简单粗暴 Johnson，通过一次SPFA将图转化为非负权图后，进行V次Dijkstra 说明 distidist_idisti​数组是记录目前i点距离源点的最距离 disti,jdist_{i,j}disti,j​是记录目前点i到点j的最短距离 初始的distdistdist值为极大值inf⁡\infinf (i,j)(i,j)(i,j)表示从i到j这条边的边权 松弛，指i点当前的dist...

赛时ABCD，也是在最后时刻惊险通关D题，还不错 A A题，由于每个位置可以操作一次，最终结果就是一个单调不增的序列，从头开始模拟即可。 B Ja the Ghost is playing with rubber ducks. He has nnn piles of rubber ducks arranged in a row, where the iii-th pile contains aia_iai​ ducks. Quack the Duck gives Ja a strictly increasing sequence b1,b2,…,bnb_1,b_2,\ldots,b_nb1​,b2​,…,bn​ and commands him to make the piles a1,a2,…,ana_1,a_2,\ldots,a_na1​,a2​,…,an​ become exactly this sequence. Ja performs the process in the following two stages: Ja may add any number of...

赛时ABCD，补题E，D题是典型的最大化最小值的二分答案问题，但是由于看错题耽误了很久，E题是一个建立超节点的单源最短路问题 ABC A题判断x:y是否等于16:9，一个需要注意的地方就是尽量把除法判断转化为乘法以避免精度问题（前提是不越界） B题也是简单的判断题，循环模拟一下就行了。 C题由于时间顺序已经排好了，只需要预处理一个后缀最大值再二分查找时间即可。 D D题出现了经典的最大化最小值描述，首先考虑二分答案，而答案显然具有单调性，越小越有可能，越大越不可能。 至于check函数的写法，先对所有布的右端点进行升序排序，然后贪心地排着取布，满足不重叠，且间距大于需要判断的值就取，如果能取够K个则为True。 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657void sol(){ struct clo { int l,r,i; }; ...

拖延了好久，终于找时间写LCA算法整合了 什么是LCA？ LCA，即Lowest Common Ancestor，最近公共祖先，指在一棵树上两个点的公共祖先中深度最大的那个祖先。 在这里，我会分别介绍朴素法，倍增法，Tarjan离线算法，欧拉序+RMQ，DFN序+RMQ，重链剖分(HLD)。 建议结合代码观看 最常用的是倍增法 RMQ(Range Minimum/Maximum Query)，这里用ST表实现。 *\text{*}*这里重链剖分得到的DFN序在求LCA时并不会用到，实际上重链剖分更重要的作用是可以结合线段树将树上问题转化为区间问题。 如果以后有可能的话，我会去学习动态树求LCA（Link-Cut Tree） 朴素法 维护信息： 节点的父亲FxF_xFx​以及深度HxH_xHx​。 算法步骤： 先通过一遍DFS遍历树，维护节点父亲和节点深度。 对于树上两点u和v，比较两者深度，如果两者深度不同，则不断升高深度更大的点，直至两者深度相同。 此时如果两个节点为同一节点的话，就已经找到了LCA。 否则，让两个节点同步上升，直到两者相等。相等时的节点就是所求的LCA。 显...

本次比赛非常耻辱，只做了AB题，C题贪心失败，D题跳过去做E题，但是一直没调出来。补了CDEF1 AB A题输出MAX+1-MIN即可。 B题顺序处理遇到1则将该位置和往后第k个位置转换，最后判断最后无法改变的k个位置有无1即可。 补题 C An annual programmers fair is taking place on the main square of Omsk. You, as the main programmer of Omsk, decided to take part in this wonderful event and went there. At the entrance, a guard decided to check your skills and gave you a problem: You are given three integers aaa, bbb, xxx. You want to make aaa and bbb equal. In order to do so, you can apply the following o...

赛时ABCE，补D，本次题还是相对简单的，但是做E题过程中因为低级失误罚时很严重，D题没注意不同开始时间也算不同组合 AB A题：输出字符串中的数字，判断即可。 B题：i给给j礼物，往对j的数组中添加i即可。 C Problem Statement There are NNN points numbered 111 through NNN on a two-dimensional plane. Point iii (1≤i≤N)(1\le i\le N)(1≤i≤N) has coordinates (Xi,Yi)(X_i,Y_i)(Xi​,Yi​). Here, it is guaranteed that XXX and YYY are each permutations of (1,2,…,N)(1,2,\ldots,N)(1,2,…,N). Find the number of values of iii such that the interior (not including the boundary) of the rectangle with sides para...

赛时ABC三题，D题畏惧了，没有看，实际上非常简单，F题需要一个特殊处理 A题是简单的排序判断 B题是枚举12剩余类，其中只有余数10不是回文数，因此10没有答案，大于10且余数为10的为22，是回文数，因此直接取1,2,3,4,5,6,7,8,9,22,11作为回文数即可。 如果实在没想到，不妨试试打表，很容易观察出来 PS：我就是打表发现的。。。 D 给你一个整数 kkk 。有一个 nnn \位二进制数 a1,a2,…,a2k+1a_1, a_2, \ldots, a_{2^k + 1}a1​,a2​,…,a2k+1​ 的序列。号码 a1a_1a1​ 和 a2k+1a_{2^k + 1}a2k+1​ 是给你的，其他号码未知。然后通过 kkk 步骤如下填写未知数字： 假设在第 iii 步之前，索引为 p1<p2<…<pmp_1 \lt p_2 \lt \ldots \lt p_mp1​<p2​<…<pm​ 的数字已经被填充。 （在第一步之前，这些是索引为 1,2k+11, 2^{k} + 11,2k+1 的数字）。 然后，对于从 111 ...

本次赛时三题ABC，补了DEF，D出现的问题是对特殊情况没有判断出来，E题是一道有趣的数据结构题，F是正解是DP，但是数据较弱，特殊的爆搜也是可以过的。 由于时间有限，从本次题解开始我就不再去详细写一些过于简单的题了，只是一笔带过。。。 ABC A题是基础的比较题。 B题判断映射关系。 C题排序后贪心地选够M个颜色后，再贪心地任意选择剩下的价值更大的东西。 补题 D 问题陈述 有一个 H×WH \times WH×W 网格，每个单元格包含一个整数 000 或 111 。 每个单元格中写入的整数的信息以长度为 WWW 的 HHH 字符串 S1,S2,…,SHS_1, S_2, \dots, S_HS1​,S2​,…,SH​ 的形式给出。如果 SiS_iSi​ 的第 jjj 个字符为“0”，则将 000 写入网格顶部起第 iii 行、左侧起第 jjj 列的单元格中；如果 SiS_iSi​ 的第 jjj 个字符是“1”，则在该单元格中写入 111 。 求写入的整数之和等于 KKK 的矩形区域的数量。 更正式地说，找到满足以下所有条件的整数四元组 (r1,c1,r2,c2)(r_1, ...

刚打完ABC接着要打div2，看到第一题第一时间没想过来就不打算下场了，后续补题发现，其实前三题都比较简单 补题 A 题面 爱丽丝邀请她的朋友参加一个聚会吃蛋糕。然而，每个朋友可能不在同一个地方，所以大家必须先在同一个地点见面。 Alice 有 nnn 个朋友，其中第 iii 个朋友位于位置 aia_iai​ 。为了让每个人都在同一个地方，Alice 必须进行多次群组通话。不幸的是，信号很弱，Alice 一次只能呼叫 222 其他人。 作为一个好人，爱丽丝不希望她的朋友走太远。因此，对于包含第 iii 个朋友和第 jjj 个朋友的每个群组通话，Alice 会告诉他们两个在 min⁡(ai,aj)\min(a_i, a_j)min(ai​,aj​) 和 max⁡(ai,aj)\max(a_i, a_j)max(ai​,aj​) （含）之间的某个整数位置见面。之后，他们两人都会快速移动到该位置，以至于Alice在移动过程中无法进行任何群组通话。请注意，一旦这些朋友到达该位置，爱丽丝就可以再次呼叫他们。 聚会即将开始，Alice 需要快速进行群组通话。帮助她找到需要拨打的最少群组通话次...

本次赛时只有3题，D题没有写方向数组，八个方向全手搓，导致写了非常久，调试也极其困难，实际上就是个简单的BFS题。而E题作为数论题也是比较简单，是可以尝试解决的。 A 问题陈述 您将获得正整数 NNN 和 MMM 。 如果重复执行以下操作，而 MMM 的值不是 000 ，请找出执行的操作次数。 设 xxx 为 NNN 除以 MMM 的余数。将 MMM 的值替换为 xxx 。 可以证明，经过有限次数的运算后， MMM 变成了 000 。 思路: 按照题意模拟并计数即可。 Code 123456789101112void sol(){ int M,N; cin>>N>>M; int cnt=0; while(M) { M=N%M; cnt++; } cout<<cnt;} B 问题陈述 xyxyxy \平面上有两个圆 C1C_1C1​ 和 C2C_2C2​ 。在这个问题中，圆指的是圆周而非圆面。 圆 C1C_1C1​ 的圆心为 (X...

五月也快结束了，我一共出游5次，到访6家酒吧（5清吧1闹吧）。 包含： 文拾雅·茶酒馆 2046艺术音乐酒吧 爱你 HOMIE BAR 游龙火塘民谣酒馆 Rouman R&B Bar 霍格沃茨 锐评：（只针对鸡尾酒，因为我不喝其他的，我个人很喜欢安静的酒吧） 文拾雅·茶酒馆：超大杯下。 优点：非常独特的中式氛围和环境。很安静，放一些平和的中文歌，里面的特调非常非常有格调，其他鸡尾酒页很有格调，调的酒也是我觉得最好喝的。酒客稀少。 缺点：可能由于位置过于难找。酒客稀少，经常包场，去过三次都没见过歌手。价格偏贵。 2046艺术音乐酒吧：大杯上。 优点：有常驻男歌手，和周末晚的限定女歌手？（我周末晚上去过一次但是没见到）。酒调的不错，氛围第二好，酒客较多，音乐抒情，鸡尾酒很有格调，有台球桌。 缺点：价格偏贵，情侣较多。 爱你 HOMIE BAR：中杯。 优点：有歌手（不知道是不是常），价格便宜，酒客较多，服务员和酒客都很热情。 缺点：是我不大喜欢的闹吧，但我不习惯，鸡尾酒没有什么装饰，以啤酒为主。 游龙火塘民谣酒馆：大杯上 优点：常驻...

引言 给定一个数组AAA，我们需要对他进行各种各样的操作，例如访问/修改单点、修改区间、查询区间性质（如求和、最值…）等操作。 我们列举一些经典操作：区间求和、区间修改、求区间最值。 用这些经典操作，我们引入一系列数据结构，并对其进行复杂度分析。 前缀和 当我们需要进行区间求和的时候，对于普通数组AAA，我们直接将对应区间相加，时间复杂度为O(N)O(N)O(N)。但对于大批量的区间求和，这种做法显然不合适。 我们建立一个数组PrePrePre，PreiPre_iPrei​表示从A1A_1A1​到AiA_iAi​的和，采用递推式Prei=Prei−1+AiPre_i=Pre_{i-1}+A_iPrei​=Prei−1​+Ai​便可构造PrePrePre。 这样的话，AlA_lAl​到ArA_rAr​的和便可以用 Prer−Prel−1Pre_r-Pre_{l-1}Prer​−Prel−1​ 来快速得到。 预处理时间：O(N)O(N)O(N) 区间求和时间：O(1)O(1)O(1) 空间：O(N)O(N)O(N) 二维扩展： 对于二维数组Ai,jA_{i,j}Ai,j​，我...

本次比赛赛时三道题，但是由于D题卡到结束也没想到自己的Yes No输出错了，就算自己过了四道题吧，悲… 刚打完比赛，顺便把题解写了 A 问题陈述 给你一个介于 111 和 101010 （含）之间的整数 XXX 。 输出从字符串 HelloWorld 中只删除 XXX -th 字符得到的字符串。 思路: 输出时跳过SX−1S_{X-1}SX−1​即可。 Code 1234567891011void sol(){ int X; string S="HelloWorld"; cin>>X; for(int i=0;i<10;i++) { if(i+1==X)continue; cout<<S[i]; }} B 问题陈述 给你一个由小写英文字母组成的 NNN 字符串 S1,S2,…,SNS_1, S_2, \ldots, S_NS1​,S2​,…,SN​ 。 定义 NNN 数字 C1,C2,…,CNC_1, C_2, \ldots...

安装工具链 检查一下自己这一步是否已完成，在终端里输入g++ -v，如果正确显示路径则本步骤可跳过，记录一下到\mingw64文件夹的路径即可 下载MinGW-w64，推荐网站 https://winlibs.com/ ，往下翻选择一个心仪的版本下载解压就好了。 打开MinGW文件夹，再打开\bin文件夹，记录\bin文件夹路径后，打开高级系统设置，在高级一栏中点击环境变量，在下方系统中找到Path，双击点开后，电机右侧新建，输入记录的\bin文件夹路径，如..(自己解压的位置)\mingw64\bin，随后一路点击确定即可，再用上面的方法检验是否完成。 安装VSCode插件 （中文插件就不在这里说明了） 下载插件 C/C++ 和 C/C++ Compile Run。 打开插件C/C++的设置，需要修改三个位置。 Cpp Standard ：改为对应C++标准（竞赛一般用c++17） Include Path ：点击添加项，复制文件夹路径。打开\mingw64文件夹，依次打开\include、c++、\xx.x.x(自己对应的文件夹)后，复制路径，粘贴到对应位置，并在后面...