N0Ne-Zer0's Blog

近期遇到的好题，值得反复回味。 持续更新，最新的在前面。 本文由AI分析题解后经个人修改而成 组合博弈 + DAG 上的 N/P 判定 来源：1103d3-D — Codeforces Round 1103 Div.3 技巧：组合博弈，逆向归纳，奇偶性分析，树状数组，DAG 思路：博弈规则是每次选的数必须 ≥ 上一个数且差值 ≤ k。将相同值聚合压缩（出现次数 cnt），排序后从大到小逆向判定每个值 v 的 N/P 状态。判定规则： 若在 v 可达的范围内存在必败态 P，则一步走到 P 交给对手 → v 是必胜态 N。 若范围内全为必胜态 N，则看 cnt(v) 的奇偶性——偶数时可镜像策略保持控制权（N），奇数时被迫交控制权（P）。 区间查询"是否存在 P"用树状数组 O(log N) 完成。全部判定后检查是否存在 N → 有则先手胜。 核心：将相同值聚合成桶、从终点逆向归纳判定 N/P，是组合博弈中"DAG 博弈"的入门典范。 → 我的题解 质因数分解和互质分析 来源：1103d3-F — Codeforces Round ...

这里记录我需要完成的文章 题解篇 Codeforces AtCoder 算法篇 组合博弈系列 巴什博弈、尼姆博弈、反尼姆博弈、威佐夫博弈、斐波那契博弈 SG定理、SG函数、博弈图 二叉树系列 二叉搜索树 替罪羊树 笛卡尔树 Treap FHQ Treap Splay AVL平衡树（不需代码实现） 红黑树（不需代码实现） DP系列 …

拖延了好久，终于找时间写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(自己对应的文件夹)后，复制路径，粘贴到对应位置，并在后面...

本场比赛赛时只做出两道题，A题不必多说，秒了。 对于B题，我最开始复杂度想错了，将每个测试点中的多次遍历当场O(n2)O(n^2)O(n2)复杂度了，因此一直在想是否有O(log⁡n)O(\log n)O(logn)的解法，知道最后一小时才反应过来，但由于最初的写法很复杂又浪费很长时间，随后灵光乍现想到了贪心解。 然后去做C题，把C题的输出当成了最优情况下的数字求出来了，而非答案所要的次数，直到最后五分钟才发现，也是惨败了… Codefoeces的题相比AtCoder差别还是蛮大的，前者有很多思维题 A 问题陈述 给你一个整数 nnn 。你需要构造一个整数数组 a1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​ 以满足以下条件： 从 111 到 nnn 的所有 iii 都是 1≤ai≤2⋅n1 \leq a_i \leq 2 \cdot n1≤ai​≤2⋅n 。 数组的所有元素和相邻元素的和都是成对不同的。换句话说，在数字 {a1,a2,…,an,a1+a2,a2+a3,…,an−1+an}\{a_1, a_2, \ldots, a_n, ...

自用来查表的… 其中有AI辅助 new的使用方法 hexo new "我的文章": 创建一篇新文章。默认布局是 post，文件会生成在 source/_posts 目录下。 hexo new page about: 创建一个新页面，会在 source 目录下新建一个 about 文件夹，并生成 index.md 文件。 hexo new draft "草稿标题": 创建一篇草稿，草稿不会在博客中显示。 hexo publish "草稿标题": 将草稿发布，并移至 source/_posts 目录。(但是我做了文件分类，不能用这个) 利用文件的分类： hexo new -p \第一级\第二级\文章名 "文章名": 会在source/_posts/第一级/第二级目录下生成文章名.md文件。 例如：hexo new -p \比赛\AtCoder\ABC458 "ABC458" 其他常用指令 hexo g: 生成网页的静态文件，运行后会在hexo根目录生成/public文件夹，里面...

[ ] 4.2GPA…？（计科保研可能要4.1+绩点，由于第一学期摆烂均摊下来就这样o(╥﹏╥)o 如果不行就可以摆烂了） [ ] 争取能够AK掉ABC比赛(会赢吗…) [ ] 手写常见的数据结构并封装，用博客的形式呈现（这个简单） [ ] 用掉游泳卡的全部次数（截止目前还有22次.Σ(⊙▽⊙"a） [ ] 把光谷步行街逛得和回家一样（还是这个简单#^.^#） [ ] 找到女朋友 [ ] 和异性能够正常交流（上一个太不切实际，但是感觉这个也好难啊┭┮﹏┭┮）