- 博客(62)
- 收藏
- 关注
RSS订阅原创 BFS
广度优先搜索（BFS）BFS介绍树和图的广度优先遍历都需要使用一个队列来实现。在过程中，我们不断从队头取出一个节点x，对于x面对的多条分支，把沿着每条分支到达的下一个尚未访问过的节点插入队尾。BFS有两个重要性质：在访问完所有的第 iii 层节点后，才会开始访问第 i+1i+1i+1 层节点。任意时刻，队列中至多有两个层次的节点。若其中一部分节点属于第 iii 层，那么另一部分节点就属于第 i+1i+1i+1 层，并且所有第 iii 层节点排在第 i+1i+1i+1 层节点之前。也就是说，广度
2021-03-26 16:49:22
249
原创 DFS
深度优先搜索（DFS）DFS介绍深搜，就是在每个点 x 上面对多条分支时，任意选择一条边走下去，执行递归，直至回溯到点 x 后，再考虑走其他的边。树的DFS序、深度和重心这个很简单，不写了深搜剪枝优化搜索顺序大部分情况下，我们应该优先搜索分支较少的节点。排除等效冗余在搜索的时候，尽量不搜索重复的状态，即在不考虑顺序的时候，尽量用组合的方式来搜索。可行性剪枝搜索的一半的时候，发现不合法就可以退出。最优性剪枝搜索到某一个程度的时候，如果发现当前的状态无论如何都比之前搜索
2021-03-26 16:45:19
192
1
原创 双栈排序（栈+二分图）
牛客题面：双栈排序题面大意：给定一个整数 nnn 和一个初始序列 aaa，其中序列 aaa 的值为[1,n]不重复的正整数。现在有以下四个操作，希望能够凭借这四个操作使得序列 aaa 成为一个升序的序列。操作a：如果输入序列不为空，将第一个元素压入栈S1操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列操作c：如果输入序列不为空，将第一个元素压入栈S2操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列让我们判断，初始序列 aaa 是否能够通过以上四个操作得到升序序列，如果不能输出
2020-12-04 12:29:30
708
原创 【POJ 2442】Sequence（二叉堆+多路归并）
POJ题面：Sequence题面大意：给定 mmm 个序列，每个序列包含 nnn 个非负整数。现在我们可以从每个序列中选取一个整数来新成一个包含有 nnn 个整数的新序列。显然，我们可以得到 nmn^mnm 个新序列，nmn^mnm 个新序列的整数之和。求出在这些新序列中，整数之和最小的一个新序列。（输出这个新序列）思路：我们可以先考虑 m=2m = 2m=2 的情况。此时，我们有两个序列 {a1,a2,...,an}\{ a_1,a_2,...,a_n \}{a1,a2,...,an}
2020-11-17 17:18:53
155
原创 【POJ 3764】The xor-longest Path（按位Trie树）
POJ题面：The xor-longest Path题目大意：给定一个具有边权的树。树中一条路径 ppp 的异或长度被定义为该路径上所有边的权值的异或和：xorlength(p)=⊕e∈pw(e)_{xor}length(p)=\oplus_{e\in p}w(e)xorlength(p)=⊕e∈pw(e)其中，⊕\oplus⊕ 表示异或运算。给定上述具有 nnn 个节点的树，求一条异或长度最大的路径。（也就是求所有路径中最大的异或长度）思路：每条边都有相应的权值，我们可以拿一个数组 di
2020-11-17 00:15:27
98
原创 The XOR Largest Pair（按位Trie树维护）
题面地址：牛客 The XOR Largest Pair题目大意：给定 NNN 个整数 A1,A2,A3,...,ANA_1,A_2,A_3,...,A_NA1,A2,A3,...,AN，并从中选出两个数进行 XORXORXOR（异或）运算，求得到的最大结果。数据范围：N≤105,0≤Ai≤231N\leq 10^5, 0\leq A_i\leq 2^{31}N≤105,0≤Ai≤231。思路：我们可以考虑将所有数都转化成一个32位的二进制01串，并且将这些01串，按高位到低位插入到同一
2020-11-14 10:53:30
97
原创 前缀统计（Trie板子题，复习）
题目地址：前缀统计思路：先把 nnn 个字符串插入同一棵Trie树中，对于Trie树上的每个节点可以拿一个cntcntcnt数组来维护以当前节点为末尾的字符串的个数。对于每次询问，在Trie树中检索字符串 TTT 时，累加每次经过的节点的 cntcntcnt 值即可得到最终答案。代码：#include <bits/stdc++.h>#define sc scanf#define pf printfusing namespace std;typedef long long LL;
2020-11-13 22:16:40
91
原创 swust oj 249 求凸包面积板子
分治求出凸点，累加每个三角形的面积得到最终答案。三角形面积等于叉积的一半。代码如下：#include <iostream>#include <iomanip>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <cmath>#include <vector>#include <q
2020-11-13 21:32:30
262
原创 火车进出栈序列问题（Catalan数+高精度压位）
题面：Acwing 130思路先假设每一个入栈的操作为 111，出栈的操作为 000。这样就抽象出一个 nnn 个 111 和 nnn 个 000 的排列问题。因为每次出栈操作都必须保证栈里有火车，所以入栈的次数一定都不少于出栈的次数（出栈次数包括当前出栈）。于是有一个很强的性质：序列任意前缀中的 111 的个数都不少于 000 的个数于是该问题就转化成了 求第 nnn 项的卡特兰数，即 :C2nnn+1=(2n)!n!n!(n+1)\cfrac{C_{2n}^n}{n+1}=\cfrac{(2
2020-09-06 18:20:51
222
原创 【POJ 3714】Raid（分治、平面最近点对）
题面：Raid题目大意有 N 个核电站能源供应点需要被摧毁。将军派出了 N 位特工去摧毁这些供应点。由于受到了帝国空军的袭击，特工分散到了几个位置，每个位置有坐标给出。将军想哪个特工离任意一个核电站的距离最小。请你求出这个最小距离。思路分治。将所有点按 xxx 坐标从小到大先排好序，之后可以分成左右两部分进行分别的计算最短距离，再进行计算中间部分可能的最短距离。但是这题是由两个不同的阵营组成，我们可以先将阵营标记出来，同阵营之间的距离就给赋值成 “无穷大”。左右两边我们只要运用归并的思想
2020-09-03 18:35:53
504
原创 【POJ 1723】SOLDIERS（排序、中位数）
题面：SOLDIERS题目大意有 nnn 个士兵，并且知道每个士兵在二维坐标图上的位置。士兵可以进行移动，但是每个士兵每次只能向上、向下、向左或向右移动一个单位，因此，他的 xxx 或 yyy 坐标也将相应的加 1 或减 1。现在希望通过移动士兵，使得所有士兵彼此相邻的处于同一条水平线内，即所有士兵的y坐标相同并且x坐标相邻。请你计算满足要求的情况下，所有士兵的总移动次数最少是多少。注意：两个或多个士兵不能占据同一个位置。思路分析题目，可以发现，每个士兵的横纵坐标对于他们的移动是彼此独立的，
2020-09-03 16:32:39
416
原创 【HDOJ 4864】Tack（贪心）
题面：Tack题目大意今天某公司有 mmm 个任务需要完成。每个任务都有自己相应的难度级别和完成任务所需的时间，记作 (y,x)(y,x)(y,x)。公司若完成第 iii 个任务，可以获得 (500∗xi+2∗yi)(500*x_i+2*y_i)(500∗xi+2∗yi) 美元的报酬。现在，公司有 nnn 台机器，每台机器都有相应的最长工作时间和级别。如果任务所需时间超过机器的最长工作时间，则机器无法完成此任务。如果任务难度级别超过机器的级别，则机器无法完成次任务。每台机器一天内只能完成
2020-09-03 11:39:40
204
原创 【POJ 1050】To the Max（降维，贪心，最大子区间和）
题面：To the Max题目大意给定一个整数 nnn ，代表的是方形区间的边长，之后再输入所有格子内的数。求该区间内的最大子区间的和。思路暴力要搞到 O(n4)O(n^4)O(n4)。考虑一下降维和动归。正常动归，要用到二维动态规划，可能会超时。这里可以将每一列的前缀和算出来，即把每一列当作一个数，在确定好上下界之后，就可以用一维动归来解决这个问题了。算法的时间复杂度就降到了 O(n3)O(n^3)O(n3)贪心思想在做一维动归的时候，需要一些贪心思想。遍历到第 kkk 个数时，如果
2020-09-03 10:33:59
343
原创 【POJ 3045】Cow Acrobats（贪心）
题面：Cow Acrobats题目大意相当于有 nnn 头奶牛在叠罗汉。每头牛都有两个特质，一个是重量 www，一个是强壮度 sss。每头牛都有一个崩溃风险，该风险等于在她上面的所有奶牛的总重量减去她本身的强壮度。所以每头牛都要找到合适自己的位置。求：确定所有奶牛的位置，从而使任何奶牛中的最大风险最小。思路芜湖~~先贪心试一下。将每头牛按照 w+sw+sw+s 从小到大排序，这样就得到正确的答案啦哈哈哈哈哈哈。贪心证明：设最优解为 real_ansreal\_ansreal_ans，自己方
2020-09-02 23:36:44
378
原创 NUMBER BASE CONVERSION（高精度模拟短除法+思维）
题面：POJ 1220题目大意给定两个整数 a,ba,ba,b，且 0<a,b<620<a,b<620<a,b<62，并给出一个 aaa 进制的数。要我们将该数转化成 bbb 进制的数。思路高精度模拟短除法。第一反应会想到高精度先将 aaa 进制转化成 101010 进制数，最后转化成 bbb 进制数，其中过程要不断求余。这里其实只要转变一下思路，让被除数上的每一位先加上之前的余数乘以 aaa 进制数，再去除以除数 bbb ，最后得出的数就是 aaa 进制
2020-09-02 16:16:21
319
原创 糖果传递（环形均分/中位数）
题面：糖果传递【Acwing】思路我们可以假定糖果是单向传递的，即都是逆时针（顺时针）传给某个孩子。#mermaid-svg-waRziq1ZTt8vNIUH .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-waRziq1ZTt8vNIUH .label text{fill:#333}#mermaid-sv
2020-09-02 14:53:32
289
原创 【POJ2083】Fractal（分形、递归）
题面：Fractal题目大意分形，具有以非整数维形式充填空间的形态特征。通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，即具有自相似的性质。现在，定义“盒子分形”如下：一级盒子分形： X\\XX二级盒子分形：X X XX X\\X\ X\\\ \ X\\X\ XX X XX X如果用B(n - 1)代表第n-1级盒子分形，那么第n级盒子分形即为：B(n
2020-09-02 10:12:07
707
原创 占卜DIY（模拟）
题面：占卜DIY思路：没什么好说的，就纯粹的模拟。注意：000 代表的是 101010代码：#include <bits/stdc++.h>#define sc scanf#define pf printfusing namespace std;deque<string> q[20];map<string, int> vis;int check(string x){ if(x == "A") return 1; if(x ==
2020-09-02 09:55:11
290
原创 The Pilots Brothers‘ refrigerator（思维）
题面：The Pilots Brothers’refrigerator代码#include <bits/stdc++.h>#define sc scanf#define pf printfusing namespace std;typedef pair<int, int> PII;string str[5];bool mark[5][5];vector<PII> ans;int main(){ memset(mark, false, size
2020-09-01 23:56:21
131
原创 Corral the Cows（二分、前缀和、离散化）
题面：Corral the Cows【牛客】题目大意有 nnn 个单位的三叶草，每单位三叶草占据一个 1×11×11×1 的土地，每块土地的位置由其左下角的下标确定，并且下标 xxx 和 yyy 都是整数，且 1≤x,y≤100001\leq x,y\leq100001≤x,y≤10000。农夫约翰希望为他的奶牛们建立一个畜栏。其中畜栏必须是正方形，且至少要包含 CCC 单位的三叶草。要求出至少包含 CCC 单位的三叶草情况下，畜栏的最小边长。注意：每个区域可能会有多个单位的三叶草，所以输入的时候
2020-09-01 22:52:08
367
原创 Running Median（动态维护中位数问题，对顶堆）
题面：Running Median题目大意顺序输入 nnn 个数，当下标为奇数时，就输出一次当前序列的中位数。例如，当遍历或输入到第 iii 个数时，iii 恰好为奇数，则就要在序列 a[1]a[1]a[1] 到 a[i]a[i]a[i] 之间找到一个中位数，并输出出来。思路这题是对顶堆的板子题。用两个小根堆和大根堆来动态维护序列。其中，大根堆维护较小的一半元素，小根堆维护较大的一半元素。即：序列中从小到大次序为 [1,len/2][1,len/2][1,len/2] 的整数存储在大根堆中
2020-09-01 21:43:25
1118
1
原创 防线（二分）
原题链接：防线题意给定 NNN 组防具，并给出每组防具放置的起始点 startstartstart 、终点 endendend 和防具与防具之间的距离 ddd。每个位置的防具数量可以由不同组的防具叠加。求防具数量为奇数的位置和该位置的防具数量。（题目给定防具数量为奇数的位置唯一）思路题目给出起始点、终点和防具之间的距离，可以很直观的看出，每组防具的位置分布是一个等差数列 an=a1+(n−1)∗da_n=a_1+(n-1)*dan=a1+(n−1)∗d。所以，在一维坐标上，我们可以很快的算出每
2020-09-01 09:53:03
144
原创 HDOJ 6867 Tree
原题链接：Tree题面：思路：只能添加一条有向边由题意可知，所建出来的树，父节点到子结点之间都是一条由父节点指向子结点的有向边。要想得到最大对数的 (x,y)(x,y)(x,y)，只能从叶子节点添加一条有向边到根节点。所以，可以先暴搜求出每个节点可以到达的节点数，并求和得到 tottottot，然后更新最大值。其中每个叶子节点连接到根节点后得到的可行对数为 n+tot−cnt[i]n+tot-cnt[i]n+tot−cnt[i]。代码：#include <bits/stdc++.h>
2020-08-19 23:10:29
94
原创 CH0503 奇数码问题（逆序对）
题面：奇数码问题思路：找了好久，没有找到奇数码问题和 n∗mn*mn∗m 数码问题的详细证明。先记个结论。奇数码游戏两个局面可达，当且仅当两个局面下网络中的数依次写成不含零的 111 到 n∗n−1n*n-1n∗n−1 的序列后，逆序对个数的奇偶性相同。结论必要性证明：空格（即 000 )左右移动的时候，我们列出出来的序列是不变的；空格上（下）移动时，相当于某个数与它后（前）边 n−1n-1n−1 个数交换了位置，因为 n−1n-1n−1 是偶数，所以逆序对数的变化也是一个偶数。拓展到 nnn 为
2020-08-08 11:00:02
283
原创 HDU 6835 Divisibility
原题链接：Divisibility题目大意：对于任意 bbb 进制的正整数 y=c1c2...cn‾y=\overline{c_1c_2...c_n}y=c1c2...cn，如果有 c1+c2+...+cn≡0(modx)c_1+c_2+...+c_n\equiv 0\pmod xc1+c2+...+cn≡0(modx)，那么有 y≡0(modx)y\equiv 0\pmod xy≡0(modx)，否则 y≢0(modx)y\not\equiv 0\pmod xy≡0(modx)。
2020-08-07 16:13:12
106
原创 HDU 6827 Road To The 3rd Building（前缀和+乘法逆元+数学推导）
原题链接：Road To The 3rd Building题面：题目大意：有 nnn 棵银杏树，每棵树都有可爱价值，当从第 iii 棵树走到第 jjj 棵树，则他们的平均可爱价值为 1j−i+1∑k=ijs[i]\cfrac{1}{j-i+1}\sum_{k=i}^{j}s[i]j−i+11∑k=ijs[i]。最后求这些可爱价值的数学期望。即 ∑i=1nE[i]\sum_{i=1}^{n}E[i]∑i=1nE[i]。数学推导：我们可以先考虑每一个数对于期望值的贡献。以 n=4n=4n=
2020-08-07 11:33:17
164
原创 HDU 6825 Set1（组合数学+数学推导）
原题链接：Set1题面：题目大意：给定一个集合 S={1∼n}S=\{1\sim n\}S={1∼n}，对集合进行如下操作直到 ∣S∣=1|S|=1∣S∣=1。首先会先删除集合中最小的数，之后以相同的概率删除其他的数。求集合中每一个数被保留下来的概率。数学推导：令操作111为删除最小的元素，操作222为随机删除一个元素。假设元素 iii 会被保留下来，则它的前面有 i−1i-1i−1 个元素，后面有 n−in-in−i 个元素。我们需要考虑保留下元素 iii 的所有方案数。显然，保留下
2020-08-06 23:28:39
169
原创 HDU 6822 Paperfolding（数学推导）
原题链接：Paperfolding题面：题目大意：给你一张纸，可以进行四种操作，向上向下向左向右对折，实际上向上向下为一种，即竖直对折；向左向右一种，即水平对折。对折完后可以进行横竖一刀切的操作，将纸张分成 sss 张。现在给定一个 nnn，问经过 nnn 次四种操作后，期望 E(s)E(s)E(s) ，即最终切割后得到的纸张数 sss 的期望是多少。数学推导：用纸张模拟 （我脑子不太好使，撕了几张纸）。可以发现，水平和竖直的对折，对于结果的影响都是独立的，即水平对折只影响水平的切痕，竖直的
2020-08-06 22:47:48
179
原创 2020杭电多校第五场A题\HUD 6814 Tetrahedron（数学推导）
原题链接：Tetrahedron题面：直角四面体的性质：题目要我们求的，就是 E(1/OH2)E(1/OH^2)E(1/OH2) 是多少。根据性质：E(1/h2)=E(1/a2+1/b2+1/c2)=3E(1/a2)E(1/h^2)=E(1/a^2+1/b^2+1/c^2)=3E(1/a^2)E(1/h2)=E(1/a2+1/b2+1/c2)=3E(1/a2)数学推导：全部都是正经题解给的哈。方法一：利用海伦公式和面积体积的关系推导。方法二：运用向量叉积。这里有一个问题，平面向量叉
2020-08-06 22:16:31
167
原创 2020杭电多校C题\HDU 6816 Boring Game（模拟）
原题链接：Boring Game题面：输入输出：思路：这是一个模拟 nnn 张纸展开的情况，每次只截取上半部分展开到左侧，一共模拟 kkk 次得到答案。该题，也可以直接看作模拟 111 张纸，对折 kkk 次，每次对折一半并截取上半部分到左侧的情况。下面是正经题解给的展开（模拟）图：所以，该题就是一个模拟题，这里采用 vectorvectorvector 进行模拟。下面是核心代码的模拟样板：代码：#include <bits/stdc++.h>#define sc s
2020-08-06 21:55:23
186
原创 2020牛客多校第四场B题 Basic Gcd Problem（唯一分解定理）
原题：Basic Gcd Problem题面：题面大意：给一对 nnn 和 ccc ，结合所给的公式，问 f[n]f[n]f[n] 等于多少。思路：分析式子，会发现，所有质数的 fff 值都是 c∗f[1]c*f[1]c∗f[1]，也就是 ccc。由唯一分解定理可知，max gcd(i,n)[1≤i<n]max\ gcd(i,n) [1\leq i< n]max gcd(i,n)[1≤i<n]所能取到的最大公约数，是 nnn 除以一个自己最小的质因数而构
2020-08-04 11:24:59
157
原创 2020牛客多校第八场G题 Game SET（？？？）
原题：Game SET题面：题目大意：给你 nnn 个字符串，每个字符串包含以下四种牌（每种牌三个属性）：number of shapes(one, two ,three)number\ of\ shapes(one,\ two\ ,three)number of shapes(one, two ,three)shapes(diamond,squiggle,oroval)shapes (diamond, squig
2020-08-04 10:34:20
230
原创 2020牛客多校第八场I题 Interesting Computer Game（并查集+离散化）
原题：Interesing Computer Game题面：题面大意：给我们 nnn 对数字 aaa 和 bbb ，我们可以进行下面三个操作：啥都不选如果数字 aia_iai 在前面没有被选过，我们可以选择它如果数字 bib_ibi 在前面没有被选过，我们可以选择它求我们总共能选择至多多少数字。（求最大数量）思路：一开始，没观察到数字的相关性，是疯狂乱贪心啊。每个数字都是有可能重复的，并且数字的数据范围在 [1,1e9][1,1e9][1,1e9]，非常大，我们可以离散化这些数
2020-08-03 22:42:02
148
原创 2020牛客多校第八场K题 Kabaleo Lite（前缀和+小贪心）
原题：Kabaleo Lite题面：思路：本题需要注意的是数据范围，可能会达到 ±1e19\pm1e^{19}±1e19。用ULL可以处理正数，LL处理负数？不知道，我不会，我太菜了。普遍用 int128int128int128 处理数据。我们可以先预处理出 profitprofitprofit 的前缀和，以及每一道菜会被用的次数。第 iii 道菜的选择次数是由它的前继菜品的最小数量和它的数量构成的，也就是： cnt[ i ]=min(cnt[ i−1 ],
2020-08-03 20:43:26
344
原创 64位整数乘法（龟速乘板子）
题面：64位整数乘法方法一：类似于快速幂的思想，把整数 bbb 用二进制表示，有：b=ck−12k−1+ck−22k−2+...+c020b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+...+c_{0}2^{0}b=ck−12k−1+ck−22k−2+...+c020于是，a∗ba*ba∗b 就有：a∗b=ck−1∗a∗2k−1+ck−2∗a∗2k−2+...+c0∗a∗20a*b=c_{k-1}*a*2^{k-1}+c_{k-2}*a*2^{k-2}+...+c_{0}*a*
2020-08-03 00:34:21
259
原创 a^b （快速幂板子）
题面：a^b快速幂思想：每个正整数都可以唯一表示为若干指数不重复的 222 的次幂的和。如果 bbb 在二进制表示下有 kkk 位，其中第 i(0≤i<k)i(0\leq i<k)i(0≤i<k) 位的数字是 cic_ici，那么有：b=ck−12k−1+ck−22k−2+...+c020b=c_{k-1}2^{k-1} + c_{k-2}2^{k-2} +...+c_02^0b=ck−12k−1+ck−22k−2+...+c020所以：ab=ack−12k−1∗ack−
2020-08-03 00:21:01
182
原创 Fractal Streets（经典分形递归+坐标旋转）
原题链接：Fractal Streets题面：思路：本题关键要解决：求编号为MMM的房屋在NNN级城市中的位置。把该问题记为 calc(N,M)calc(N, M)calc(N,M) ，本题就是求 calc(N,A)calc(N, A)calc(N,A) 和 calc(N,B)calc(N, B)calc(N,B) 之间的距离。该题每一级的图像都是由上一级的图像变换得来的。具体的变换如下：假设当前为 NNN 级城市，将其对称的分成房屋数量完全相等的四个小块，即左上、右上、右下、左下。而这四个方
2020-08-02 23:59:59
783
原创 Tallest Cow（基础差分思想）
原题题面：Tallest Cow题目大意：有 NNN 头牛站成一排。两头牛能看见彼此，当且仅当它们中间的所有牛都比它们矮。现已知最高的牛是第PPP头，且它的身高为HHH，不知其他剩下 N−1N-1N−1 头牛的身高。题目还给出了 MMM 对关系，每队关系都有两头牛AAA和BBB能互相看见。求每头牛的身高最大可能是多少。思路：如果两头牛之间看得见，那么 Ai+1Ai+1Ai+1 到 Bi−1Bi-1Bi−1之间的牛比 AiAiAi 和 BiBiBi 都小1，也就是让这个区间内的牛身高都减1，可以简单想
2020-08-02 15:48:33
482
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人