ZQY Blog

WE HAVE A DREAM

动态规划-C2第七阶段DP质量题刷题日记

THIS IS AC/CE/RE/WA/TLE/MLE/OLE/PE/UKE

2021.7.20 KDT5087买零食 可以用01背包过，但是有一种有趣的做法：把状态设成bool类型，dp[i][j]表示前i个物品选择一些放入容量为j的背包中，能否达到容量j，边界需要考虑一下 2021.7.20 KDT1210西瓜分配 比较有意思，虽然暴力子集好像能飘过，但是标准写法是01背包，只不过体积是总重量的一半，再去跑01背包，需要画图理解理解（最后一句是老师说的）...

Posted by 周琪岳 on July 30, 2021

欧拉路、欧拉回路与哈密尔顿回路课堂笔记

图论

欧拉路径 简述 若图G中存在这样一条路径，使它恰通过G中每条边1次，则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉（Euler）回路 定理1：存在欧拉路的条件：图是联通的，有且仅有2个奇点。 定理2：存在欧拉回路的条件：图是联通的，有0个奇点。 根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点进行深度优先遍历；找欧拉路，则对一个奇点执行DFS，...

Posted by 周琪岳 on July 28, 2021

二叉堆的实现课堂笔记

手写二叉堆

基本定义 堆：完全二叉树，其左右子树仍然是堆，保证堆顶元素是该堆中元素中最大的（最小的） 存储时，按照顺序，用数组存储 基本操作 push：插入 pop：删除 返回堆顶元素 代码实现 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 2...

Posted by 周琪岳 on July 27, 2021

动态规划-O(n^2)算法求最长下降子序列种类数

线性DP拓展

如题，先明确三点： 实现O(n^2)算法 如果两个子序列数值相同，则算作相同序列，只计算一个 子序列必须为单调递减 要求输出的答案为：最长下降子序列的长度以及种类数 第一问无疑非常简单，只要双重循环dp一下就搞定了。但是第二问怎么算呢？ 刚开始我想到可以写一个cnt数组，c...

Posted by 周琪岳 on July 25, 2021

笔记-填满背包的最小物品数

KDT课堂笔记

01背包 f[i][j] 前i个物品选择一些恰填满容量为j的背包，需要的最小物品数 边界： 1 2 memset(f, 0x3f, sizeof(f)); f[0][0] = 0; 状态转移方程： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 for(int i=1; i<=n; i++) { for(int j=0; j<=m; j++) { ...

Posted by 周琪岳 on July 23, 2021

酷町堂-7005买礼物的福利题解

完全背包+01背包练习好题

本篇文章仅有题解，若要查看题目请访问 建模整理 n种物品，手头有m元，每种物品有无数个 每种物品的单价为wi，购买k个即需花费k*wi元 若购买第i种，买X(X>0)个的话会获得ai * X + bi个糖果 计算得到的最多糖果数量 思路 建模之后，可以发现，若不存在bi的话，实际上就是一个多重背包的板子题。但是有了...

Posted by 周琪岳 on July 23, 2021

洛谷-P2258子矩阵题解

动态规划+搜索与回溯

本篇文章仅有题解，若要查看题目请访问 建模整理 给定一个n行m列矩阵，选取r条行、c条列，将行列重合部分组成一个r行c列的子矩阵，并规定： 相邻的元素：矩阵中的某个元素与其上下左右四个元素（如果存在的话）是相邻的。 矩阵的分值：矩阵中每一对相邻元素之差的绝对值之和。 本体任务即为：从这个矩阵中选出一个r行c列的子矩阵，使得这个子矩阵的分值最小，并输出这个分值。 解题思路 ...

Posted by 周琪岳 on July 12, 2021

洛谷P1095-守望者的逃离题解

akDiPy

本篇文章仅有题解，若要查看题目请访问 建模整理 可能的状态： 1）跑步：无代价，速度为17m/s 2）闪烁：消耗魔法值10点，1s移动60m 3）原地休息，恢复魔法值 魔法值恢复速度：4点/s，且只有处在原地休息状态才能恢复 已知魔法初值、总距离、限定时间，求行完总距离的最短时间，若无法行完，求剩下时间内能走完的最远距离 时间单位均为秒，距离单位均为米 解题思路 ...

Posted by 周琪岳 on July 11, 2021

45中集训队第三次比赛游记

COMPLETE AND PROGRESS

继续补游记！！！ 7.5日，早上dxy老师讲图论，什么Floyd、Dijkstra还有Prim之类的，我都在KDT哪儿学过了，所以就在座位上写DP毒瘤题rp降低，下午zcy老师讲动态规划，说有晚上的题，谁知道只讲了一道类似的真题，还没有详细说怎么写，只讲是什么多个01背包在一起，比较懵。晚上跟cjk和王老师去老乡鸡，感觉味道还可以rp++ 开始比赛，第一题，什么玩意儿，签到！第二...

Posted by 周琪岳 on July 10, 2021

45中集训队第二次比赛游记

COMPLETE AND PROGRESS

由于前几天一直在补KDT的CSP冲刺课程，没有时间写集训期间的游记，最近赶快补一发(^_−)☆。 今天是7.4，上午继续完成zcy老师给我布置的一套毒瘤卷子（题目见刷题汇总挑战题），~~真是把人魂都给写出来了~~/qwq。下午讲模拟，没去听，一直刷某谷上的DP题单，看题解的情况下A了2题（我太菜） 6:00 开考。ACM赛制让我这种初出茅庐的OI新手非常不适应，都有人连切2题，结...

Posted by 周琪岳 on July 10, 2021

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

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

FRIENDS