Mxiaocao Blog

codefoces mind (T1-10)1. The 67th XOR Problem（1200）（binary search）（bitmasks）（brute force） Ques门钥匙 题意 You are given an array , initially containing non-negative integers. You perform the following operation exactly times: Select an index of (, where denotes the current length of ). Let . Set for all , where denotes the bitwise XOR operation. Remove from the array. It can be shown that after operations, exactly one element remains in the array. Your task is to determine the maximu...

欧拉筛欧拉筛（Euler Sieve），也被称为线性筛，是算法竞赛中极其重要且优雅的基础算法。它可以在 的严格线性时间内，找出 范围内的所有质数。它比我们初学时接触的“埃氏筛（埃拉托斯特尼筛法，）”更快。 接下来介绍它的核心（不重复劳动）： 在普通的埃氏筛中，我们会用质数去筛掉它的倍数，比如用质数2筛掉4，6，8，10，12，用质数3筛掉6，9，12，15。不难发现，像6，12，被2筛了一次，被3也筛了一次。当N很大时，就会有很多个数会被重复标记，这样就浪费了大量的时间。 而欧拉筛则避免了这个问题，它保证每一个合数，必定且只能被它的最小质因数筛掉一次 步骤： 我们先假设所有数初始都是质数，并且再创建一个数组记录已经找到的质数 123vector<char> is_prime(n+1,1);vector<int> primes;is_prime[0] = is_prime[1] = 0; //0和1不是质数 然后开始循环，遍历2到N的每一个数字 123for(int i = 2;i <= n;++i){ } 如果一个数i，它没被前面的数筛...

乘法逆元在计算组合数 时，我们一般不会直接除以6，而是乘以6的乘法逆元（INV6)。 那么为什么要引入乘法逆元呢？根本原因在于，在取模运算的世界里，加减乘都满足分配律，唯独除法不行。 进一步地讲三个核心原因： 模运算中不能直接做除法 假设我们要计算，如果我们对A B分别取模，拿结果一般是错误的 比方说，正确的是，但是分别取模后却有，这逻辑上就崩溃了 防止中间过程的数值溢出 对于这道题的，当然是可以的(因为 在 64 位整数 long long 的极限 之内)，但是在大多数算法题中，N通常会达到甚至更大，此时分子乘积会达到，连64位整数都会严重溢出。 因此，我们需要每乘一次就取一次模： 12ans = E * (E - 1) % MOD;ans = ans * (E - 2) % MOD; 但是，这又会有个问题：取了模之后，这个ans还能保证被6整除吗？并不行。 用“乘法逆元”代替“除法” 既然不能除，数学家就想了一个办法：把除法变成乘法 在普通的数学里，除以6等于乘以 在模的世界里，我们也想找一个整数X，使得”乘以X取模“的效果，等同于”除以6取模“。这个神奇的X，就...

01Trie 最大异或对思路： 异或运算 二进制位 N个整数均转化为二进制数表示 构造 Tire树 在树上进行异或运算 说明： Trie存单词，由26个小写字母构造，是一棵26叉树，深度为最长单词的长度 Trie存整数，由整数的十进制位构造，是一棵10叉树，深度为10层 Trie存整数，由整数的二进制位构造，是一棵二叉树，深度为31层 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100// 01 Trie (max xor), supports: // 1) insert(x) // 2) max_xor(x): max value of (x ^ y) among inserted y // 3) erase(x): optiona...

经典并查集(DSU)可以将并查集想象成一个帮派合并的过程。 假设现在有n个人，一开始大家都不认识，每个人都可以是自己的老大。当然，有了ai，以后每个人都可以有自己的个体公司。当然，随着剧情的发展，会产生两种操作：合并、查询。 合并：两个帮派结盟了，此时就需要一个帮派的老大带着全体小弟去归顺另一个老大。 查询：随便抓两个人，问问他们的帮派的老大是不是一个人（即是不是一个帮派的）。 为了处理这两种操作，聪明的人类发明了并查集。 而如何实现并查集呢？我们可以使用数组，数组名可以使用par，而关于par数组里面存的是什么，后面我们将探讨当然不少题解会写far（farther的缩写） 一、初始化一开始，每个人自成一派，也就是par[i] = i，这里的par数组存的是每个人的“直系上级”。当一个人的直系上级是他自己时，他就是这个帮派的首领（即树的根节点）。 123456789vector<int> par;void Init(int n){ par.resize(n); for(int i = 0;i < n;++i){ ...

拓扑排序一、介绍适用于有向无环图(DAG)，节点 => 任务，边 => 依赖关系，箭头从前置任务指向后置任务，目标是将任务按依赖关系排序 结果不唯一 二、实现方式（1）Kahn 算法 (BFS)流程 先让入度为0的节点入队，一开始队列里是A和B，把A取出放入排序结果，将其指向的C的入度减1，再取出B，放入排序结果，并将其指向的C和D的入度减一。此时C和D的入度为0，继续将其加入队列。最终可以得出ABCDEF。 代码1234567891011121314151617181920212223242526272829303132void solve(){ int n; cin >> n; vector<vector<int> > g(n+1); vector<int> deg(n+1,0); queue<int> q; for(int i = 1;i <= n;++i){ int v; while(cin >> v && v)&...

5.2.3 Dijkstra 最短路适用条件：单源、边权非负。 负边权 -> Bellman-Ford 1. 邻接矩阵：O(V^2) dijkstra算法是每次都是找距离源点最近的点，所以我们可以维护一个dist数组，来存储v到每个点的最短距离 (1) 初始化首先创建数组dist，存源点v到每个点的最短距离，然后我们自然是要进行初始化的 12345int dist[MAXV]; //存源点v到每个点的最短距离for(int i = 0;i < n;++i){ dist[i] = g[v][i]; //对于下标i的点，dist就是g[v][i]的值}dist[v] = 0; //源点自己到自己的距离为0 而后续就是每次寻找距离源点v距离最短的点，所以我们是要枚举dist数组看看哪个最小的。但是，如果我们已经确定了一个点，后续还要再考虑进去吗？自然是不用的，所以我们可以创建一个bool类型的ok数组，已确定标1，未确定标0。比如此时只有源点0确定了，那就给ok数组下标为0的位置标记为1，其余的点为0。 12345678int dist[MAXV];bool ok[...

线性 DP大多数教材没有定义什么是线性dp，而是把它归为dp的入门篇目。 那什么是线性DP呢？下面引用gpt的话： “线性 DP 是指把状态按一个线性顺序（通常是下标、时间、位置）依次计算，且每个状态只依赖这个顺序中更早的少量状态的动态规划。 可写成抽象形式：dp[i] = transfer(dp[i-1], dp[i-2], …, input[i]) 核心特征就两点： 1. 有明确的一维推进顺序（前缀化处理）。 2. 依赖只向前看，不成环，且局部。” 说白话就是该问题的模型是线性的，基本从左到右扫一遍前缀，且每步只看前面的有限信息，即无后效性，就是当前的状态只由前面的问题转移而来 做这类题有个四步走的策略： dp[][]：表达的意思 题目问什么，dp表示什么意思 初始值： dp[1][1] = a[1][1]; ==确定状态转移：==（核心） 当前状态由哪些状态转移而来 dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + a[i][j]; 结束 一、基于数字三角形例1. 数字三角形 Number Triangles门钥匙 题意 观察下...

这里是小草(mxiaocao)的秘密基地，一个用代码和热爱搭建的数字花园。作为一名算法竞赛爱好者，我将在这里专注分享数据结构与ACM/ICPC的实战心得。从基础算法到进阶技巧，从比赛复盘到解题思路，我都会用清晰的代码和通俗的讲解，陪你一起攻克那些让人头疼的难题。这里不仅是刷题与沉淀的自留地，更是记录成长、交流思路的小天地。无论是入门萌新还是进阶选手，都能在此收获干货、理清逻辑、少走弯路。往后会持续更新刷题题解、知识点总结、赛题复盘、调试经验与避坑指南，用扎实的积累对抗迷茫，用持续的输出沉淀成长。愿每一次敲码都有回响，每一次刷题都有收获，与所有热爱算法的同路人，一同奔赴更辽阔的编程山海。

2.1.8 dequedeque(双端队列)支持两端 O(1)插入/删除，比vector更适合做队头操作，比queue/stack更灵活。 deque常见用途 普通队列（push_back + pop_front) 双端操作（回文、窗口） 单调队列（滑动窗口最值） 0-1 BFS 一、结构二、初始化头文件：<bits/stdc++.h> or <deque> 12345deque<int> d1; //空deque<int> d2(5); //5个0deque<int> d3(5,7); //5个7deque<int> d4 = {1,2,3,4}; //列表初始化deque<int> d5(d4.begin(),d4.end()); //迭代器 三、基本操作1. 两端插入/删除1234d.push_back(x);d.push_front(x);d.pop_back();d.pop_front(); 2. 访问元素1234d.front();d.back();d...