- 博客(1074)
- 资源 (1)
- 问答 (1)
- 收藏
- 关注
RSS订阅
原创 国家集训队论文分类整理
国家集训队论文分类整理组合数学 计数与统计 2001 - 符文杰：《Pólya原理及其应用》 2003 - 许智磊：《浅谈补集转化思想在统计问题中的应用》 2007 - 周冬：《生成树的计数及其应用》 2008 - 陈瑜希《Pólya计数法的应用》 数位问题 2009 - 高逸涵《数位计数问题解法研究》 2009 - 刘聪《浅谈数位类统计问题》 动态统...
2019-04-17 12:37:51
675
6
原创 网路流24题
决心去做好每一道网络流24题，去理解最大流、最小费用流、最小割、……好好去体验吧，开题！开始按顺序来写了。太空飞行计划问题【网络流24题】【最小割】 这道题的精髓在于如果割哪个边，那么最后deep[]会停留在它前面的一个点，那么就可以知道被安排的是哪个点了。 还要强调一点，这个时候千万不能使用判断边的流量和容量来看，只能去判断割点的位置，不然一定会出现偏大或者偏小的情...
2019-03-18 17:02:22
409
原创 Dinic算法学至大佬，学以致用【挂上相应的题目】
这个巨佬讲的超级厉害，学起来很快，还有优化的说呢Dinic算法（研究总结，网络流）网络流是信息学竞赛中的常见类型，笔者刚学习了最大流Dinic算法，简单记录一下网络流基本概念什么是网络流在一个有向图上选择一个源点，一个汇点，每一条边上都有一个流量上限（以下称为容量），即经过这条边的流量不能超过这个上界，同时，除源点和汇点外，所有点的入流和出流都相等，而源点只有流出的流，汇点只有...
2019-03-12 19:31:08
587
3
原创 树链剖分学习日记
树链剖分【11月27日星期二晴】先【下认识树链剖分的概念】从大佬处摘录而来，先认识下概念。树链剖分就是对一棵树分成几条链，把树形变为线性，减少处理难度需要处理的问题：将树从X到ý结点最短路径上所有节点的值都加上ž 求树从X到ý结点最短路径上所有节点的值之和 将以X为根节点的子树内所有节点值都加上ž 求以X为根节点的子树内所有节点值之和概念重儿子：对于每一个非...
2018-11-27 09:42:54
433
2
原创 Xcode10闪退（编译、运行时输入数据后或没输入数据直接闪退问题）
频繁的崩溃让我敲代码的心情都受到了影响，然后今天还是10.1更新了，更新完以为会有所好转，但是频繁闪退这个问题还是没有修复，简直时醉了。崩溃向这种频繁崩溃的情况，直接暴力解决。首先右键主项目文件即xcodeproj文件，显示包内容。找到找到project.xcworkspace文件，右键显示包内容。Snip20160702_3.png删除xcuserdata文件夹，解决...
2018-10-31 14:34:31
2469
4
原创 字符串匹配的KMP算法（后期不断学习后更新）【学习日记】
（网上的说法）10月24日·第一天的学习学习任务：这天我们先来了解一下什么是KMP，并且先不看代码自己揣测下应该如何去写这样的代码。举例来说，有一个字符串“BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串“ABCDABD”？1。首先，字符串“BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词“ABCDABD”的第一个字符...
2018-10-24 20:38:31
601
原创 [NOIP2016 提高组] 蚯蚓
但，我们再想一下，同样经过T次“增量q”，如果先分解的两个，是不是后期分得的“增量q”会更多呢（因为分解成了两个，相当于每个都享受到了这样的优惠，但是没分解的，现在是两个共享同一个“增量q”），先分解的在随着时间的推移反而会越来越有优势。那么，又如何维护“增量q”呢，实际上，我们只需要再多统计一个信息就可以了，就是这个值是第几轮生成的，用当前轮次减去生成的轮次，不就得到了它需要被增加多少次了呢。题目很长，题意如下：一开始有n个值，，有m次操作，每次操作选择一个最大的值x，将它分解成两个数，分别为。
2023-09-20 21:05:41
224
原创 神奇编码【牛客小白月赛78F】【队列的巧妙用法】
再者，就是维护合成之后的节点，因为哈夫曼树的性质，我们可以将这些节点逐一的放入到“合成后的节点”的小根堆中去，由于这里是线性递增的，所以这个“小根堆”我们可以使用队列去进行维护。制造哈夫曼树的过程，有一个很容易被我们忽视掉的线性关系，就是哈夫曼树的新生成的根节点，他们的权值是不断的递增的。2、取出一个值最小的节点，它只有一个，那么我们还需要再取一个，然后跟他合并，新取出来的节点的数量如果大于1，那么还需要减掉这个使用掉的，再把自己送回自己的队列中去。那么，又可以发现，数量是不断的减少的，如果我们用三元组。
2023-09-20 10:46:51
170
原创 Mac安装python3
可以在命令行中输入：brew install python3但是出现了error，如下所示：tar: Error opening archive: Failed to open '/Users/my/Library/Caches/Homebrew/downloads/29542f91b1856b9da2f25619c9e7e9d329c362e96ae8661ebb55063e67968be9--gdbm-1.19.mojave.bottle.tar.gz'网上说是清华源的问题，我们就临
2022-04-02 19:51:30
835
原创 基于Liunx与C语言的网络抓包学习（简单抓包之数据包的长度）
用到一个pcap中的数据类型：pcap_pkthdr。struct pcap_pkthdr { struct timeval ts; /* time stamp */ bpf_u_int32 caplen; /* length of portion present */ bpf_u_int32 len; /* length this packet (off wire) */ };ts：时间戳cpalen：当前分组的长度len：数据包的长度cap...
2021-09-23 10:55:30
774
原创 基于Liunx与C语言的网络抓包学习（pcap.h）
首先，利用终端配置好gcc的环境，然后还要配置上libpcap的环境，以上通过相关文章进行学习。<pcap.h> 首先，先能得到数据包的包的长度。这里用到的头文件是pcap.h，其中用到的有pcap_if_t数据类型。 pcap_if_t 保存网卡基本信息的类型。通常用指针来使用，pcap_if_t *alldevs。 当然，很多时候pcap_if_t可以用pcap_if进行替代。struct pcap_if{ struct pcap_if *nex...
2021-09-22 20:23:43
1075
原创 Mac终端-bash No such file or directory以及执行操作时候command not found
我们可以通过搭建临时路径的方式来找到bug。我在调试Java环境的时候，在已经配好Java PATH的时候，错误的将当前的版本删除了，以至于我们找不到当前的版本了。很显然，我们之前用过的vim操作，发生了一些冲突。说明你的.bash_profile文件修改错误。1.在终端输入export PATH=/sbin:/bin:/usr/sbin:/usr/bin:/usr/local/bin，配置临时路径；2.输入命令sudo vim .bash_profile，查看文件内容；3.然后我们
2021-03-04 10:28:31
6221
11
原创 宝石街【尺取法】
题目链接 6e7级别的输入，那么说明复杂度限制在了O(N)级别，所以很明显的就是去用线性的做法来解决这个问题了。 我们可以试着去枚举终点，那么会发现当步数增加的时候，我们只需要不断的弹出起点，起点后推，说明有线性关系，尺取即可（two point）。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>..
2021-01-03 21:42:26
187
原创 Quad Trees【POJ-1610】【模拟】
题目链接 有N*N的矩阵，保证N是2的幂次数，然后利用四叉树编码，来进行对这个矩阵的长度优化。 具体是怎么四叉树编码的呢？如果现在一棵四叉子树内只有1或者只有0，那么此时只需要返回(0,1/0)，就可以了“1/0”指的是为0还是为1，其他情况呢，我们需要继续分治，使得它成为只包含1、0的子树才可以。 然后，这题的内存卡的蛮死的，当N==512时候，构造的四叉树的大小为349525个元素，所以动态开点就可以了。#include <iostream>#include <...
2020-11-18 20:43:27
136
原创 PowerOJ2512: 小红灌溉【染色】
题目链接 划重点！！！每个有菜的点只能浇一次且恰好一次，所以意思就是，譬如某个菜的位置是(x, y)，那么，行x、列y的浇水方案只能使用其中的一个。 以此类推，我们给每个有蔬菜的位置的(x, y)的x点与y点链接一条无向边，代表x和y只能选择其中的一个，那么这个问题不就转化成了0、1染色问题了嘛？然后选择权值最少的0、1块就可以了。#include <iostream>#include <cstdio>#include <cmath>#includ..
2020-10-19 21:50:16
214
原创 PowerOJ2546: fork【C++ STL __gnu_cxx::rope】
题目链接我们可以这样定义一个可持久化数组rope<int> rp;push_back(x)：在末尾添加x (x是int)erase(pos, x): 从pos开始删除x个at(x)/[x]：访问第x个元素用以上这些操作可以解决这道题了，但是rope还有其他的操作：如果将rope用来维护char类型，那么：rope<char> rp;push_back(x)：在末尾添加x (x是char)insert(pos,x)：在pos插入x (x是字符串,
2020-10-16 20:47:16
222
原创 PowerOJ 2543: 赛场布置
题目链接 对于每个点，它可以选择男或者女，如果要加上的贡献，那么相邻的一定得是异性才可以。所以，对相邻的，我们可以考虑成： 然后，我们对于点坐标的的奇偶性分别讨论即可。 当然，还需要考虑的贡献。 然后就是全选减去最少割去的即可。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#in...
2020-10-15 09:57:47
518
原创 Monkey King【大根堆】
题目链接 有N只孤独的猴子，然后他们会打M次架，每次打架的两只猴子战斗力减半，并且会成为朋友，朋友的朋友也是朋友，问的是朋友中战力最大的猴子是有多少战力？ 于是，考虑维护这样的一个大根堆，每次将小的大根堆推给大的，相当于是启发式合并的操作，复杂度。 或者，我们可以直接进行维护，我们维护一个二叉树的“深度”，然后尽量保证深度平衡，也就是使得整棵二叉树的深度尽可能小，所以，我们定义一个dist，表示它和它的子树中的dist最小的值+1，但是这样的维护最后可能退化会形成一条链，不妥，不如我们让左...
2020-10-04 16:04:09
204
原创 Art Class【HDU-6888】【吉司机线段树】
题目链接 有一张二维平面，现在全是空白的，我们的操作是给为左下角，为右上角的面涂黑，现在我们想知道所有的黑色块的周长。 可以发现对于上部和下部的周长我们可以利用区间覆盖来进行计算，但是竖着的边我们该如何计算呢？容易想到的是，我们可以通过把“区间点”变成“区间块”这样的做法，使得原本表示的区间点，变成表示的区间块，表示块第到第。然后我们求的就是任意相邻两块之间的高度差之和。 这个东西可以怎样维护呢？我们易发现，只有变大才会改变这个答案，所以其实就是维护最大值的这样一个操作。 那么对于区...
2020-09-23 21:33:58
489
原创 【模板】AC自动机（加强版）【AC自动机fail树上求最多出现次数】
题目链接 P3796 给出N个模式串，然后我们用一个文本串去进行匹配，这样的做法，就是AC自动机了，于是乎，我们可以先将N个模式串丢进去，然后建立fail树，然后先对所有的节点求出最大串在文本串中出现的次数，然后利用dfs跑fail树的办法，我们可以O(N)的求解这个问题。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cst.
2020-09-22 16:43:23
237
原创 【模板】AC自动机
题目链接 有N个模式串，再给出一个文本串，现在我们想知道有多少个模式串在文本串中出现过？ 这就是一个AC自动机的模板题了，我们可以将AC自动机建立出来，在上面建立fail指针，然后建立fail树这样的做法来解决这个问题。 具体的说一下，我们可以先建立Trie树，然后利用bfs建立AC自动机，然后再建立fail树，然后我们利用文本串在AC自动机上进行fail的跳转，我们可以知道它可以表示哪些节点，然后我们就可以利用这样的前缀匹配算法来进行计算贡献了。 注意，这里用的是前缀匹配算法！...
2020-09-22 10:42:34
153
原创 [APIO2014]序列分割【long long与long double的精度差异】
题目链接 这道题的数据是真的大，如果你的得分是88分，有可能就需要对精度做一个优化了！ 首先，考虑一点：上下两式子相等。所以，不需要考虑划分的先后顺序问题，最后的值只跟点的位置有关。所以，dp方程就自己推了，我只是记录一下我错的那个点的问题：考虑到值可能很大，所以很容易想到的是开一个long double来进行维护，但是可能想象不到的是，我们对于原本是整数的，可能用long long先存下来会更好一些。 然后，在求斜率的过程中，我们将整数部分用long long 记...
2020-09-16 10:29:22
295
原创 Three Occurrences【CF-1418G】【线段树】
题目链接 题意：有一个长度为N的数组，现在我们要查询合法区间的数量，合法区间定义为“在区间中出现的数值都是刚好只出现3次的区间”。譬如“1 1 2 2 1 2”是一个合法区间，每个数值都恰好出现三次。 那么，我们可以知道一点，我们定义为值为i的数在此之前第j次出现的位置（倒叙的），我们只需要知道前面三个的位置，就可以确定我们想知道的东西了，因为合法区间就在之间，此时保证了价值为i的这个数取了刚好三次。 所以我们不妨做一个“滑动”一样的操作，现在我们知道，那么我们来做这样的一个东西：给定...
2020-09-16 10:17:44
472
原创 乔乔和牛牛逛超市【CCF202006-5】
简单的说，就是我们想知道取其中的一些点，使得他们之间满足题目中给出的要求，然后问这样的集合的权值的最大值。 将问题这样展开之后，实际上就是一个最大权闭合子图问题了，什么是最大权闭合子图？就是求一个集合，集合的所有的点的出边所指向的点也在集合内，求这样的集合的点的权值和的最大。 于是，这个问题就是一个网络流求最大权闭合子图问题了。 分两种状态考虑。情况1：1 x y 那么，我们让，意思是我们要取x的话，就必须取y。情况2：2 x y 我们让，指的是要取y的端点，就...
2020-09-11 15:31:55
715
原创 Subsequences of Length Two【DP】
题目链接 有一个长度为N的串S，有一个长度为2的串T，现在可以对S串做K次改变，最后使得T串在S串中的子序列出现次数最多。 于是，涉及计数问题，就可以推一个DP来进行操作了，表示处理到第i个位置，有j个t[0]时候，改变次数为k时候的最大值，然后分类讨论t[0]和t[1]的情况（相等、不想等）就可以推完这个dp方程了。#include <iostream>#include <cstdio>#include <cmath>#include <s..
2020-09-05 16:08:50
340
原创 Bracket Sequences on Tree【哈希+随机数+树DP】
题目链接 HDU-6647 有一棵N个点构成的无根树，我们可以任选一点开始进行dfs跑，得到一个括号序，现在我们想知道跑完整个dfs，有多少种括号序？ 于是，可以比较容易的想到，我们可以推一个dp方程来解出从一个点出发，得到的方案数，假设表示以u为子树的根节点时候的跑完下面子树的种类数，那么可以看到，其中，表示u的不同形态的子树的个数。 于是，我们可以根据这个式子来进行DP得到目前假设的根节点的值，然后再根据该式子可以进行换根DP得到剩下以每个点为根时候的答案值，当然，当以它为根时候的树跟...
2020-09-04 20:24:10
199
原创 Boboniu Walks on Graph【CF-1395E】【哈希】
题目链接 有N个点的，M条有向边组成的图，每个点的出度都小于等于K，现在要求我们求这样的K元组意思是出度为i的点，选择边权第小的边走，最后要求满足所有的点一定是能走回该点。 那么，题意其实也就是每个点最后只有一条出边，并且因为要求形成环，所以每个点最多被进一次（不然就一定是无解的）。 所以，这道题就是去枚举，然后如何记录状态呢？最开始的时候我想了个bitset<maxN>的解法，但是发现其实这样会很多元素会被多次处理，所以这样的做法就浪费了，所以我们不如直接使用哈希，复杂度O(...
2020-09-01 16:46:50
173
原创 牛牛的粉丝【循环矩阵】
题目链接【牛客练习赛68】比赛的时候用了一个的做法来解决这个问题，显然是TLE的，显然的，我们没有发现矩阵中隐含的条件。当我们把这个矩阵列写下来的时候，会发现以第一行为初始的，后面一行相当于前一行右移一位，每一行都具有这样的信息，所以可以将第i行，第j列第值看作是，当然，这里的是要取模N的。 所以，我们不妨只用维护一行的信息，就可以完整的表述所有的信息了，时间复杂度就可以降了一个N。#include <iostream>#include <cstdio>#in.
2020-08-29 10:20:45
137
原创 [JSOI2009]球队收益 / 球队预算【费用流】
题目链接 先说一下我一开始错了有一段时间的做法为什么是错的：错误做法： 我们可以看到每个点i基础有胜利次，有失败次，可以发现一点，无论是胜利次数增多还是失败次数增多，总的花费一定是增多的，若初始为，则胜利一次会变成，而失败一次呢，则会变成，所以他们一定是增加的。于是，我们可以说费用流的根据贪心选最短路的策略，那么一定是会先去选择最小的边。 所以，将每个点拆成胜点、负点，一次u、v打比赛，则一定有一方胜，有一方败，所以不妨胜连败，败连胜，然后又只有一场比赛，所以对其限流就可以了。 ...
2020-08-28 14:56:51
155
原创 [POI2013]LUK-Triumphal arch【树形DP+二分答案】
题目链接给一颗树，1号节点已经被染黑，其余是白的，两个人轮流操作，一开始B在1号节点，A选择k个点染黑，然后B走一步，如果B能走到A没染的节点则B胜，否则当A染完全部的点时，A胜。求能让A获胜的最小的k。 好像洛谷给的N数据范围是1e5级别的。 于是，如果直接查的话，好想不大好查，但是如果我们现在假设一个答案k，然后呢，我们判断这个k是否可以满足这个条件，这样的做法会更好一些。 当我们假设一个k的时候，就可以判断它的可行性了，如果现在B要往树的某个方向走，那么它肯定选择的是最优的策...
2020-08-26 21:48:06
164
原创 Yuno loves sqrt technology III[Ynoi2019模拟赛]【数组分块】
题目链接 我们想知道一个区间内的众数的个数，那么，我们可以把区间看成两种形式：「完整区间」、「不完整区间」，我们把一个区间分成这样的两种，然后可以预处理出来一个「完整区间」内的众数的个数，那么如果我们现在假设知道了这个答案，岂不是就可以对不完整区间进行查询了，如果一个不完整区间的数，能改变当前答案，那么也就是说明它的后面的第ans个它自己是在区间内的，那么我们可以预处理这个信息即可。 当然，本题有个很坑的地方，切记l和r的大小关系一定要判断。#include <iostream>..
2020-08-22 15:17:23
128
原创 [Violet]蒲公英【数组分块】
题目链接 查询时，考虑两种情况：区间包含多个完整的块； 区间不包含完整的块。 对于情况1：如果我们可以处理出来所有的完整的块，那么时间复杂度就是枚举两端的不完整块的复杂度了，也就是说，如果我们可以O(1)的知道中间完整块的最大值的话，那么只需要查两边就可以了，答案一定是中间完整块的答案和两端的不完整块的数中的一个。 对于情况2：既然长度只有根号级别了，直接暴力也未尝不可。 所以，现在的问题转变成处理完整块中的出现最多次的数的个数，以及需要做一个差分的形式，来知道在完整块中出现的值...
2020-08-21 10:15:57
124
原创 Game【HDU-6873】【Splay】
2020 Multi-University Training Contest 9 G题 题意：有N个有各自高度的位置，按1～N从左到右排列。现在我们有两种操作：x y将第x列，第y行的方块，包括它上面的方块从右往左的移动过去，同时推动前面的方块前进，当然，最前面的那个方块，会根据重力掉下去。非法状态（或者不能移动状态）不移动。 x，查询第x列的方块高度是多少。 于是，很明显的，我们可以考虑大于等于y的最长向前的连续，我们找到第一个小于y的高度的列的位置，那么，从到x的这个连续段内肯定是都要往..
2020-08-19 20:46:20
225
原创 教主的魔法【模拟】
题目链接 可以说是一些块状数据结构，用分块数组来进行一个维护，然后对于每个被完整覆盖的块用一个永久化标记来进行存储一下，一道模板题。【分块数组模版】#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <algorithm>#include <limits>#.
2020-08-19 20:36:41
101
原创 Controversial Rounds【CF-1398 F】【线段树】
题目链接 题意：有由字符集{0，1，?}构成的长度为N的字符串，知道"?"可以变成0、1中的任意一个数，现在问长度为1到N的最多0、1连续段的个数。 很显然一点，如果我们直接跑N次，假设查询可以O(1)的完成，那么时间复杂度是一个调和级数，也就是级别的，但是很显然我们需要查询这样的一个东西。 现在需要有这样的一个操作：查询区间内第一个出现的连续长度大于等于i的连续段的首地址，那么，我们不妨维护这样的一个线段树，记录每个位置的最远连续长度，那么实际上就是找到区间范围内第一次出现的长度大于等于...
2020-08-17 21:41:45
195
原创 Omkar and Bed Wars【Codeforces Global Round 10 D】【DP】
题目链接 CF-1392D 有N个人围坐成一个环，每个人会打左边或者右边的那个人，如果只有某一边的人打他，那么他就会只打这一边（打回去），否则，他打哪一边都是可以的（但是一定要打），现在，为了是给出的长度为N的「L、R」串符合规则，问最小需要修改的次数。 于是，开始的时候想法是状压DP，我想，某个点i，它收到的影响只会跟前后两个点有关，但是因为我们的正向DP是不能考虑后继的影响，所以如果将状态压进来还是不好处理。 于是，我们不妨把状态拆出来，那么（作为一个伪环形DP），我们可以存档其中“第...
2020-08-17 20:30:49
176
原创 Two Types of Spells【模拟】
题目链接 有两种魔法，一种是单纯的伤害为d(0 d)，另一种是伤害为d，但是下一次伤害暴击（*2）为(1 d)，现在，我们要用已有的魔法来进行组合，使得伤害总值最大。 那么，很显然的，我们尽可能让值大的去进行“暴击化”处理，于是有如果这个值更大，我们就把这个值放进去暴击堆内去，这样的做法。 然后，很多细节吧，调了蛮久的。111 11 -11 20 30 -31 41 -41 50 61 -21 -5360 1361774120 -1361774120...
2020-08-17 11:19:53
290
1
原创 Colored Rectangles【CF1398 D】【DP】
题目链接CF-1398D Educational Codeforces Round 93 有三种颜色，R、G、B，我们要用他们来构成矩形的长和宽，要求是矩阵的长和宽不能是同一种颜色，也就是一个矩阵必须是两个不同颜色来构成的。并且每个颜色对应的值只能用一次。 于是，就有贪心策略，肯定是要让权值大的尽量和权值大的进行一个匹配，这样能保证权值大的被利用的效果最好。 于是，我们可以对每种颜色降序排序，但是现在就是该确定怎样匹配了，所以可以用一个的这样的一个三维dp来进行维护这个东西。那么很明显...
2020-08-15 15:59:10
164
原创 牛妹的苹果树【牛客练习赛67 F】【倍增+欧拉序+树的直径】
题目链接 求区间内的点对的最大直径。 其实，我们可以发现直径有相对应的传递关系的，如果我们已知一棵树上的直径，，假设又知道另一棵树上的直径，，那么新的直径只能通过这四个点两两组和来实现的。 所以，我们可以用倍增的方法来维护这个连续关系对。9 11 2 11 3 21 4 31 5 51 6 62 7 73 8 44 9 26 7ans:14#include <iostream>#include <cstdio>#include ...
2020-08-15 10:41:22
164
74LS90的功能表.doc
2019-05-10
想了解有关Ubuntu系统使用C语言抓数据包并写文件成为wireshark可执行文件
2021-09-23
TA创建的收藏夹 TA关注的收藏夹
TA关注的人