4 KalznAsawind

尚未进行身份认证

我要认证

qdu-打不到名额的菜鸡一枚

等级
TA的排名 7w+

我是一个功利主义ACMer

如果你是一个真正热爱算法竞赛,热爱ACM的人,请关闭这篇博客,我害怕这篇博客的丧气会影响到你。坚持你的热爱!加油叭!如题,从大一开始参加ACM训练起,我就是功利的。或者说,真正驱动我的是大厂实习和竞保的机会,和期末专业课考试时那点卑微的自信。教练已经多次强调,打ACM最重要的是热爱和兴趣,如果只是想往简历上添点东西,那蓝桥的性价比更高,的确如此。我曾经用教练所说的标准检验我自己是不是真的热爱ACM,然而得到的答案是否定的:我不会因为一道题的AC而激动,更不会因为一道难题而钻研到深夜,我甚至不确定我心血来潮

2020-06-20 00:13:23

上下限网络流模板

下面是模板代码:/*特别注意:::以下建边tot从2开始记录!1.建图对于每一个(a, b, low, up)首先建立(a, b, up - low)并记录: div[a]-=low, div[b]+=low待全部边都建好之后, 对于每个点:if (div[i] < 0) add(i, TT, -du[i]);if (div[i] > 0) add(SS, i, du[i]), flow += du[i];2.可行流如果有源汇点,加边(t, s, inf)if (Din

2020-05-15 16:11:01

生成树相关模板(续)

发现一个写太多编辑器比较卡。继续,这也就是一些小点了。完全图生成树计数Cayley公式:f(n)=n∗(n−2)f(n) = n*(n-2)f(n)=n∗(n−2)有向图树形图计数树形图计数仍适用Matrix-Tree定理,其Kirchhoff矩阵: 外向树:所计算的矩阵中的对角线元素代表的是点的出度,而且除对角线元素外,代表的是又向的路是否存在(存在就设为-1);内向图树:对角线元素代表的是点的出度。生成树先这样,,如果有其他的我会继续更新...

2020-05-15 16:10:41

生成树相关模板

基本的最小生成树的Kruskal, Prime算法不再阐述.有向图最小树形图以某一根节点出发,可以到达所有节点,且边权总和最小的子图.这里模板使用的时朱刘算法;下面时模板代码:/*朱刘算法:1.找所有节点的最小入边,标记2.累加这些边的权值,如果这时没有环,则得到了最优解. 有环则进行下一3.将环缩点,所有连接此环的入边权值减少当前这个终节点的最小入度边权值(可能减成负的)4.返回1复杂度:O(nm)*/const int N = 2e5+5;const int inf =

2020-05-15 16:10:25

图的匹配问题相关模板

基本二分图匹配匈牙利算法和一些基本的定理不再阐述必经\可行点,必经\可行点必经可行边在这里可以看到。可行点:同可行边,所有可行边连接的点,都是可行点,否则不是可行点。必经点:除暴力枚举外,我们在跑完网络流的残留图上枚举所有的未匹配点,进行dfs,记录所有历经点,所有没有被历经的点,都是必经点。(因为每个点每条边最多经历一边,所以dfs复杂度是O(n+m) )...

2020-05-15 16:10:04

QDU-思政答题平台

1.挑战题目本平台可以实现学生线上答题,并在答题结束后给出分数。2. 题目解析当学生回答完一套题后,学生可选择查看题目解析。3. 编辑题目集本平台的一大特色功能。用户自主编辑题集的功能不能不说是一大亮点。老师使用这套平台,可以用它来出题,对于学生和其他使用者,也可以编辑自己的题目库,整理知识点。4. 线上挑战与线上排名本平台上的线上题目集是由管理者或者用户上传的题目组成的。选择回答线上题目集时,用户需注册本平台账号,凭借个人账号参与线上挑战。5. 上传题目集本小组的答题平台与本班其他同类项

2020-05-13 23:55:02

杜教BM (线性齐次递推式推演,无define)

下面是模板代码:#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#include <string>#include <map>#include <set>#include <iostream>#include <cassert>using

2020-05-10 22:35:15

青岛大学软件梦工厂蓝桥讲课_素数题解

A.zx学长与失落城使用筛法将小于1e6的素数输出,注意格式输出即可.下面是标程代码#include<cstdio>#include<iostream>#include<cstring>#include <map>#include <queue>#include <set>#include <cstdl...

2020-03-02 13:43:18

FFT前置知识及FFT\FFT分治

首先依次介绍FFT(快速傅里叶变换)前置知识:复数及单位根 复变函数欧拉定理单位根三大引理多项式的系数与点值表示法多项式的求值与插值(顺介绍拉格朗日插值法)向量卷积复数及单位根我们知道复数可以写成z=a+biz=a+biz=a+bi,其中aaa为实部,bibibi为虚部.而且一个复数可以在一个复平面上表示出来,而我们可以将其写成极坐标的形式z=r(cosθ+isinθ)z=r(co...

2020-02-26 22:35:08

青岛大学软件梦工厂蓝桥讲课_前缀和与差分题解

A.zx学长的施工队1解题思路在视频中已给出,标程代码:#include <iostream>#include <cstring>#include <string>#include <algorithm>#include <cmath>#include <queue>#include <map>...

2020-01-31 21:02:47

线段树合并(四道例题)

顾名思义,就是合并两个同构(就是维护的区间长度一样)线段树,其实也没啥比较nb的算法,就是一个一个节点的合并,但是如果在n个要合并的线段树里,如果一共有m个元素,则配合动态开点,复杂度会均摊成一个惊人的O(mlogn)O(mlogn)O(mlogn)所以,在多次合并的均摊复杂度是非常优秀的.另外线段树合并还可以和线段树分裂一起构成维护一组线段树森林的方法我们每次合并一个点,就是综合两个线段树表示...

2020-02-14 14:34:48

线段树分裂/合并模板

模板链接最早从zx神仙口中得知这个玩意,但是一直没学,现在学一下再说,发现不是什么神仙东西,说实话有点小失落.按照区间分裂可以在O(logn)O(logn)O(logn)内完成,不过,合并操作需要枚举线段树的每个点进行合并,效率不是太高,数据量1e3差不多就是极限了.且应用面不是很广.洛谷所给的模板是多个权值线段树的维护操作.下面是模板代码:#include <iostream&g...

2020-02-12 21:39:26

可持久化数组及并查集(概念及模板)

可持久化数组模板链接顾名思义,就是可以查询历史版本的数组,我们使用主席树维护这个数组就ok了.从此延伸出了可持久化并查集等很多可持久化结构,比较简单,下面是模板代码:#include <iostream>#include <cstring>#include <string>#include <vector>#include <q...

2020-02-12 15:05:27

网络流/费用流(洛谷 P3980 [NOI2008]志愿者招募)

题目链接想了许久,一看题解是一种比较sao的办法.1.源点连第一天汇点连最后一天容量为INF费用为02.然后每一天向后一天连一条容量为INF-a[i]费用为0的边3.然后将每一类志愿者s[i]与t[i]+1连一条容量为INF花费为c[i]的边这样为了保证最大流是inf,图会从3类边中花费补流,最后最小费即为所求.下面是ac代码:#include <iostream&gt...

2020-02-11 17:57:25

网络流\费用流\监控某批边满流的处理办法(P1251 餐巾计划问题)

题目链接这个题想了半天.最后构建这样一个模型:对于N天1.对每一天iii,拆点,拆成两个(i,i+N)(i,i+N)(i,i+N).中间连一条容量为当天需要餐巾数量,费油为0的边<i,i+N,a[i],0><i,i+N,a[i],0><i,i+N,a[i],0>.2.对于每天的后点,都往下一天连一条容量为inf,费用为0的边<i+N,i+N+1,i...

2020-02-08 17:50:24

莫比乌斯函数及其反演定理

定义,求法,打表及反演定理在这篇博客进行了介绍给出两个反演公式f(n)=∑d∣ng(d)⟺g(n)=∑d∣nμ(d)f(nd)(1)f(n)=\sum_{d|n}g(d)\Longleftrightarrow g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})\tag1f(n)=d∣n∑​g(d)⟺g(n)=d∣n∑​μ(d)f(dn​)(1)f(n)=∑d∣ng(d)⟺...

2020-02-05 20:59:10

杜教筛(概念及模板)

功能杜教筛可以在非线性的时间内求出极性函数的前缀和。洛谷给出的模板:对于n(n<231n<2^{31}n<231)求出:ans1=∑i=1nφans_1=\sum^{n}_{i=1}\varphians1​=∑i=1n​φ...

2020-02-05 16:06:37

二分图的必经边与可行边(HDU - 3026 Chinese Chess)

题目链接对于一个二分图,我们对于满足最大匹配的多组匹配方案中,ruo对于某些边:如果对于每个方案,这个边都被选择了,我们称这条边为必经边如果一条边,它在至少一个方案中被选择了,我们称这条边为可行边求必经边第一种方案,我们易知可以枚举每个边,去掉该边后,跑一边最大匹配,看看最大匹配数是否减小,若减小,该边为必经边。显然我们就算用Dinic跑最大匹配,时间复杂度也会到达O(E2∗V)O(...

2019-11-08 23:36:05

树上莫队算法学习

题目链接学习树上莫队算法,首先了解一下欧拉序。欧拉序对于一颗树,我们遍历的时候,我们第一次经过时,把该点加入序列,回溯时再加一遍,形成欧拉序。例如:这棵树的欧拉序就是:1,2,3,6,6,4,4,5,5,3,7,7,2,1我们就在这个序列上进行莫队对于一个区间:如果该点出现且仅出现一次。那我们计算时就要计算这个点。否则不计算。对于每次查询(x,y),我们先有以下操作:scanf...

2019-11-08 14:50:12

AC自动机学习/模板

题目连接(只提供模板及简单思路。)憨批的第一个字符串算法。前置知识:Tire树、KMP匹配思想第一步:首先把所有的匹配串建一个Tire树。第二步:从Tire树根节点开始,一个一个字符的匹配模式串。到某一个节点失配后,寻找一个fail指针,该指针从这个节点,到它的最大后缀的节点第三步:反向fail指针建树。第四步:fail树上树形dp。#include <iostream&g...

2019-11-06 19:56:38

查看更多

勋章 我的勋章
  • 技术圈认证
    技术圈认证
    用户完成年度认证,即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。