ZQY Blog

WE HAVE A DREAM

搬家公示

博客搬家

“Yeah It’s on. ” 博客已搬家至： https://blog.csdn.net/qq_49686566?spm=1001.2101.3001.5343 搬家原因： 无法使用LATEX 配置不好Gitalk 我们新博客见！

Posted by 周琪岳 on August 25, 2021

单调队列与单调栈学习与简单应用模型

Monotone queue and monotone stack learning and simple application

单调队列引入 单调队列，就是队列中的元素具有一定单调性的队列，通常用双端队列（STL_deque）来进行实现，跟优先队列有一定相似之处，只不过优先队列只需要提前规定顺序往队列里丢元素就行了，而单调队列需要根据情况判定。然而，好用的东西是有代价的， 「优先队列」的插入和删除操作时间复杂度均为O($\log_2n$) ，而单调队列可以实现近乎O(1)的复杂度。由于空讲概念不能描绘出单调队列的优...

Posted by 周琪岳 on August 18, 2021

P4667 [BalticOI 2011 Day1]Switch the Lamp On题解

Dij最短路

初步分析 读完题，题目要求求最短路，又是电路图，大概率是bfs或者最短路的一堆算法。如果用bfs的话，每扩展一个新节点，所需增加的花费不一致（因为有可能需要转动电路），而本蒟蒻不会双端队列实现广搜，所以只会用dijkstra求解。 思路成形 建图 最短路的前提条件是建图。我们可以将每个交点当做图上顶点，电路通道就是花费为0的边，实际上出了标出的电路通道，还有“隐藏的通道”，就是通过翻...

Posted by 周琪岳 on August 17, 2021

[AHOI2018](非省选)分组(division)

模拟+栈

切入点 此题乍一看很多方法，比如我刚开始以为是二分+贪心，写挂后又以为是DP优化，但是实际上就是一个模拟，只不过需要开栈来维护每个组的实力值。 思路 首先，将实力值排序（很明显）。然后遍历每个人，考虑将这个人放到某一个组中。组内人员的实力值可以开一个栈维护，题目要求实力值连续，我们可以遍历每个栈，分析是否满足题意。如果多个栈都满足实力值连续的要求，我们便选组内人数最小的入栈（因为我们要...

Posted by 周琪岳 on August 12, 2021

酷町堂C3-1线下阶段&升班考游记

COMPLETE AND PROGRESS

7.30号刚刚考完，8.4号又要阶段考啦。这七课主要学图论进阶，为C2第6阶段的拓展运用，课程内容如下： hh，4号下午46中居然要给信息学特长生签协议，妈妈送我去华地酷町堂来不及，只好联系老师在滨湖校区同时考。一到前台，妈呀，只有7分钟了，教务老师不见辣，啊啊啊，妈妈在楼下，让我先找教室坐下。过一会老师来了，让我在教室3和2个补考的xxs一起考，后面有个女老师看着。打开笔记本，插上电...

Posted by 周琪岳 on August 6, 2021

FASTER系列-快速幂

快速幂的推导与实现

引入 快速幂，顾名思义，就是快速算底数的n次幂。其时间复杂度为 O(logn)， 与朴素的O(n)相比效率有了极大的提高，在算法竞赛中有着广泛的运用。 推导前提 明确一下取模运算的性质： (a + b) % c = (a % c + b % c) % c (a - b) % c = (a % c - b % c + c) % c (a * b) % c ...

Posted by 周琪岳 on August 4, 2021

图论-图论基础算法模板汇总

板子参考中心

欧拉路径 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <iostream> using namespace std; int n, m, g[101][101], d[101], cnt, ans[101]; void dfs(int x...

Posted by 周琪岳 on August 3, 2021

图论最短路-Bellman-Ford最短路径算法

图上最短路Bellman-Ford算法课堂笔记

算法简述 Bellman-Ford算法，用于解决不包含负权重环的图上单源最短路径问题。时间复杂度为O(n*m)。时间复杂度比Dijkstra高，但是可以检测负环。 算法流程 松弛迭代n-1轮 每一轮对所有的边进行松弛操作 经过n-1轮 所有点都得到了最短路径 原因：因为最短路最多包含n-1条边，经过n-1轮的迭代，顶点要么已经求出最短路，要么与原点不联通 如果再进行一轮，可以进行松...

Posted by 周琪岳 on August 1, 2021

酷町堂C2-7线上阶段考游记

COMPLETE AND PROGRESS

2021/7/30，下了XES奥数课疯一般地从市区往家赶，路上以1e99km/s的速度开车，晕车差点吐。。。6:24到家，洗把脸奔向电脑前，背了背二进制拆分的板子就开考了 6:30，BEGIN。开卷T1，01背包模板，T2瞧一眼，多重（还是完全？不记得了）背包模板，迅速切掉2题，200到手，RP++。T3一眼看，不是石子合并改编版吗？只不过区间dp答案由dp[1][n]变成了max{dp[...

Posted by 周琪岳 on August 1, 2021

图论MST-基于贪心+并查集的Kruscal算法

图上最小生成树Kruscal算法课堂笔记

算法简述 Kruscal算法，就是基于并查集的贪心算法，时间复杂度为mlogm（m为图的边数），用于解决稀疏图上的MST问题 流程： 首先，我们把所有的边按照权值从小到大排列，并且每个点属于不同的集合 将边从小到大遍历，如果这条边的两个端点不属于同一集合，那么就将它们合并，加入到最小生成树里 直到所有的点都属于同一个集合为止 集合自然可以使用并查集实现 一般来说，将...

Posted by 周琪岳 on July 31, 2021

FEATURED TAGS
生活 C++ 数据结构 图论 题解 动态规划 洛谷 浅谈系列 游记 45CSP-J集训队 线性DP 酷町堂 NOIP普及组 完全背包 并查集 栈 模拟 联通块 01背包 二分法 刷题日记 多重背包 日记 最短路 算法 线性表 队列 阶段考 Meta
ABOUT ME

周琪岳,2019届KDT入坑OI选手,第37届合肥市信息学竞赛一等奖

FRIENDS