首页
算法相关
软件分享
技术教程
网站源码
自学干货
值得一看
联系我
02
牛客小白月赛75
陈小白
2023.07.02
算法相关
抢沙发
204人打酱油
比赛地址:https://ac.nowcoder.com/acm/contest/60063 先说好消息,搞出模拟了。 再说坏消息,就A了三个.......DE真的很巧妙,尤其D D:大意是给出给出n*m的矩阵,从11走到nm。求最小花费时间。 两类操作,向上下左右四个反向走,...
Continue
Tags:
算法竞赛
动态规划
图论
24
洛谷3个简单黄dp总结
陈小白
2023.03.24
算法相关
抢沙发
269人打酱油
感觉脑子确实钝了。。。 dp一直是知识框架的弱项。 https://www.luogu.com.cn/problem/P1806 跑步,大意是跑n圈,要求每次比上一次跑的多,问多少种跑法。 很明显这个问题可以当作背包计数来考虑。每次直接用j-i来转移就可以。 ...
Continue
Tags:
动态规划
08
洛谷绿蓝题选做总结(数论、线代)
陈小白
2023.03.08
算法相关
抢沙发
363人打酱油
TalentShowG蓝 题目链接:https://www.luogu.com.cn/problem/P4377 类型:二分法与01分数规划 大意是根据n头奶牛的体重和才艺值选择出战的一组奶牛,才艺和体重比值最大的获胜,有体重下限限制(需要凑够这些重量)。 solu...
Continue
Tags:
二分
动态规划
28
AtCoder Beginner Contest 291 (D、E)
陈小白
2023.02.28
算法相关
抢沙发
302人打酱油
比赛链接:https://atcoder.jp/contests/abc291/tasks D题:大意是给出n张卡片的正面和反面的数值,卡片正反面为不同数字,求翻某些卡片的一面使得向正的一面的数值全都不一样的集合的数量。 解决方法:考虑使用01动态规划解决。f[i][0/1],...
Continue
Tags:
思维
动态规划
图论
28
蓝桥杯 11道黄橙dp题总结
陈小白
2022.12.28
算法相关
抢沙发
259人打酱油
题目链接:https://www.luogu.com.cn/problem/list?tag=363,361%7C3&page=1&orderBy=difficulty&order=asc 先说3个橙题。现在感觉都是比较简单的dp题,都是通过递推的形式转换过来...
Continue
Tags:
动态规划
26
状压dp 解决 哈密顿回路问题
陈小白
2022.12.26
算法相关
抢沙发
207人打酱油
步骤: 确定采用状压dp范围20左右。 状态转移f[i][j]表示对于第i个节点,它走到的第j个状态。对于任意状态,遍历任意节点,找到此节点并确定另一节点与其重合。 路径确定i>>j&1路径重合i-(1<<j)>>k&1 ...
Continue
Tags:
动态规划
图论
23
砝码称重 线性dp+备份表/滚动数组
陈小白
2022.12.23
算法相关
抢沙发
206人打酱油
题目链接:https://www.luogu.com.cn/problem/P8742 大意是给出砝码,求称出的重量的数量。 经过观察,发现新给出的第i个砝码,只是在第i-1个砝码的基础上产生印象。因此只需要两张映射表做一个滚动数组即可 code: constintn...
Continue
Tags:
动态规划
09
P1026 [NOIP2001 提高组] 统计单词个数
陈小白
2022.11.09
算法相关
抢沙发
250人打酱油
题目链接:https://www.luogu.com.cn/problem/P1026 感觉可以贪心,但是贪心只过了两个点╮(╯▽╰)╭ 我的思路是这样的:我们从后往前去记录出现单词,数据量小完全可以暴力,然后将单词标记一下,首字母额外标记一下。 最后我们统计出有多少个单词,下面开始...
Continue
Tags:
动态规划
04
有依赖的背包问题——有线电视网
陈小白
2022.11.04
算法相关
抢沙发
244人打酱油
题目链接:https://www.luogu.com.cn/problem/P1273 树形dp。但这个本质上是个背包问题,一时间没有想起来有依赖的背包问题。 读题的时候没有发现客户端一定是接在转发器上的,想成了一颗比较自由的树。 做的时候要当作一个有依赖的背包问题来做,分好组...
Continue
Tags:
动态规划
03
加分二叉树
陈小白
2022.11.03
算法相关
抢沙发
267人打酱油
题目链接:https://www.luogu.com.cn/problem/P1040 大意是给出一个树的中序遍历,这个树每个子树都有一个加分,得分=左子树分数*右子树分数+根的分数。 在每个节点都有一个分数,第i个节点分数为di。其实就是给出的中序。求最大加分并输出先序遍历 ...
Continue
Tags:
动态规划
28
树形dp问题
陈小白
2022.10.28
算法相关
抢沙发
322人打酱油
感觉codeforces也是来到了能做D题的水平。 在解决完子区间的查询问题之后,感觉C题能做的就多了。 codeforces的D题多是一些C题的加强版,这里往往涉及到某些规律,例如二进制位。 同样D题往往也容易出现一些简单的树和图的问题,尽管我目前的水平仍然做不出来,但是可以...
Continue
Tags:
动态规划
05
Educational Codeforces Round 136 (Rated for Div. 2)
陈小白
2022.10.05
算法相关
抢沙发
274人打酱油
比赛链接:https://codeforces.ml/contest/1739 这样有点难,B使劲WA,C题直接解不出来,思维上要求很高。C题更是赛出了组合数学 A题:水题,棋盘固定走法,求哪个格子没有可走的步子。 code: #include<bits/stdc...
Continue
Tags:
算法竞赛
思维
动态规划
13
蓝桥杯积木画
陈小白
2022.09.13
算法相关
抢沙发
279人打酱油
题目链接:https://www.lanqiao.cn/problems/2110/learning/ 动态规划一直是我的弱项,这个题其实是一个很简单的动态规划的题非板子题。 这个题的精髓在于递推上面。 下面来仔细分析一下。 首先当n=1,2,3时s=1,2,5这是...
Continue
Tags:
动态规划
31
01背包的数量问题
陈小白
2022.08.31
算法相关
抢沙发
294人打酱油
题目链接:http://noi.openjudge.cn/ch0206/2985/ 描述 有n个正整数,找出其中和为t(t也是正整数)的可能的组合方式。如: n=5,5个数分别为1,2,3,4,5,t=5; 那么可能的组合有5=1+4和5=2+3和5=5三种组合方式...
Continue
Tags:
动态规划
12
多重背包的二进制优化
陈小白
2022.08.12
算法相关
抢沙发
235人打酱油
题目链接:https://www.acwing.com/problem/content/5/ 最近没有比赛可打,好好看看基础。 多重背包的朴素写法很简单,基本上都能写,复杂度nmk级别的,在数据量几千的情况下就处理不了了。 因此我们考虑用空间换时间,对物品进行二进制优化,...
Continue
Tags:
动态规划
11
最长公共上升子序列 加强理解版
陈小白
2022.08.11
算法相关
抢沙发
277人打酱油
题目链接:https://www.acwing.com/problem/content/description/274/ 两个序列a,b求最长公共上升子序列 我们定义f[i][j]为a序列的前i个和b序列的前j个元素的最长公共上升子序列 那么当前的f[i][j]可以继承f[i-...
Continue
Tags:
动态规划
11
AcWing 187. 导弹防御系统(LIS,贪心,dfs,迭代加深)
陈小白
2022.08.11
算法相关
抢沙发
361人打酱油
题目链接:https://www.acwing.com/problem/content/description/189/ 为了对抗附近恶意国家的威胁,R国更新了他们的导弹防御系统。 一套防御系统的导弹拦截高度要么一直严格单调上升要么一直严格单调下降。 例如,一套系统先后拦...
Continue
Tags:
贪心
搜索
动态规划
09
oi普及组 防御法阵(背包预处理+区间dp)
陈小白
2022.08.09
算法相关
抢沙发
299人打酱油
题目链接:https://ac.nowcoder.com/acm/contest/21865/D 大意是给出n个城墙,每个城墙有一定数量的法阵,破坏他们可以获得经验值,同时消耗时间。每个城墙有一个固定的最大停留时间。且最多可以破坏m个城墙。当破坏掉一个城墙后,它邻近的城墙的经验值将增...
Continue
Tags:
动态规划
06
Educational Codeforces Round 133 (Rated for Div. 2)
陈小白
2022.08.06
算法相关
抢沙发
325人打酱油
比赛链接:https://codeforc.es/contest/1716 A了两道题A和B,速度还可以,但是CD态度太大一个也没做出来。 A题:给出一个数n,从0点开始到n点,每次只能走2步或3步,也可以回退。求最少多少次可以走到n点。 很简单,我们优先考虑3,如果是3的倍数可以直接/3过...
Continue
Tags:
算法竞赛
动态规划
14
P1280 尼克的任务
陈小白
2022.07.14
算法相关
抢沙发
284人打酱油
题目链接:https://www.luogu.com.cn/problem/P1280 大意,给出一个时间n和任务数k 每个任务给出开始时间和持续时间。求最大的休闲时间。 很明显这个题是一个线性动态规划的题,但是却不好推导状态转移公式,尤其是有任务的时候,状态转移公式很难...
Continue
Tags:
动态规划
14
P1020 [NOIP1999 普及组] 导弹拦截
陈小白
2022.07.14
算法相关
抢沙发
317人打酱油
深夜更一波啊。明天任务,分别A一道二分,线性dp和搜索题 题目链接:https://www.luogu.com.cn/problem/P1020 大意:给出一组数据,求出这种数据的最长不升子序列以及至少多少个这样的不升子序列个数。 思路:前半个题最长不升子序列正常线性dp...
Continue
Tags:
动态规划
12
P2196 [NOIP1996 提高组] 挖地雷
陈小白
2022.07.12
算法相关
抢沙发
304人打酱油
题目链接:https://www.luogu.com.cn/problem/P2196 大意:有n个地窖,每个地窖里有一些地雷,给出第i个地窖到i+1-n的连通性。求出最优解及路径,要求拆除地雷最多。 这个题可以爆搜(因为n的值很小),也可以dp(类似于最长子序列那种,这里不同...
Continue
Tags:
动态规划
04
蓝桥杯 质数行者
陈小白
2022.07.04
算法相关
抢沙发
329人打酱油
题目链接:https://www.lanqiao.cn/problems/1027/learning/ 一道dp题,但是用普通三维dp最多只能的30%的测试点,记忆化搜索同理。 快筛一遍质数,然后用三维dp再然后剪枝可以过40%测试点的样子。 给出大佬的代码:https://b...
Continue
Tags:
动态规划
25
洛谷 P1802 5 倍经验日
陈小白
2022.06.25
算法相关
抢沙发
293人打酱油
题目链接:https://www.luogu.com.cn/problem/P1802 题目背景 现在乐斗有活动了!每打一个人可以获得5倍经验!absi2011却无奈的看着那一些比他等级高的好友,想着能否把他们干掉。干掉能拿不少经验的。 题目描述 ...
Continue
Tags:
动态规划
05
最大子段和 三种解法 :分治、贪心、dp
陈小白
2022.04.05
算法相关
抢沙发
357人打酱油
题目链接:https://www.luogu.com.cn/problem/P1115 如题,先分析复杂度。n的范围是2*10^5,对应之前总结的复杂度问题,nlogn可以解决10^5,这个题能解决一半 从而这个题只能考虑n线性计算的复杂度,这里贪心算法和一维dp可以解决,两个...
Continue
Tags:
贪心
二分
动态规划
03
蓝桥杯 字符串转换
陈小白
2022.04.03
算法相关
抢沙发
339人打酱油
题目链接:https://www.lanqiao.cn/problems/1507/learning/ 一道小小思维的dp题 要弄明白3个操作对应的数据的位置 先说说为什么要从i+1j+1开始计算呢,因为我们初始化默认第一个元素相等更容易操作 其实如果从ij开始计算...
Continue
Tags:
动态规划
30
闫氏dp分析法博客
陈小白
2022.03.30
算法相关
抢沙发
334人打酱油
先转发 https://blog.csdn.net/yc_cy1999/article/details/106106912?spm=1001.2101.3001.6650.5&utm_medium=distribute.pc_relevant.none-task-blog-2...
Continue
Tags:
动态规划
29
蓝桥杯 最长公共子序列
陈小白
2022.03.29
算法相关
抢沙发
317人打酱油
题目链接:https://www.lanqiao.cn/problems/1189/learning/ 关于序列、子串这类问题挺多的,往往这些思想可以移植到别的地方,如一些dp或者贪心的题 这个题应该不是第一次做了,但还是没能做出来 dp的公式真是神奇而又巧妙==orz了...
Continue
Tags:
动态规划
24
蓝桥杯 最少砝码
陈小白
2022.03.24
算法相关
抢沙发
471人打酱油
题目链接:https://www.lanqiao.cn/problems/1461/learning/ 怎么说呢,这个需要递推公式,奈何本人愚钝,没看出来w(゚Д゚)w 1个砝码1个值 2个砝码4个值 3个砝码13个值 n=n*3+1 上代码 ...
Continue
Tags:
动态规划
21
洛谷提高组 邮票面值设计
陈小白
2022.03.21
算法相关
抢沙发
460人打酱油
题目链接https://www.luogu.com.cn/problem/P1021 又是被oi支配的一天 两种解法,一种是双重暴力,一种是dfs+dp 啊啊啊,太难了。一个都理解不了,有时间再看 暴力 #include<iostream> #...
Continue
Tags:
搜索
动态规划
18
蓝桥杯印章问题
陈小白
2022.03.18
算法相关
抢沙发
458人打酱油
有买的印章数和印章种数两个变量,就自然而然地想成二维数组dp[i][j] 关键是状态转移方程 这里参考https://blog.csdn.net/okok__TXF/article/details/121099645?ops_request_misc=%257B%2522req...
Continue
Tags:
动态规划
站点统计
建站日期: 2021-9-3 11:02
运行时间: 928 天
日志总数: 421 篇
页面数量: 0 个
最后发表: 2024-2-29 20:06
搜索
标签
双指针
博弈论
构造
数论
简单题
树状数组
贪心
前缀和
二叉树
搜索
数据结构
线段树
算法竞赛
二分
数学
最小生成树
记忆化搜索
思维
动态规划
图论
树
概率
高精度
计算几何
哈希
字符串
杂题
暴力
模拟
启发式合并
存档
2024年2月
2023年11月
2023年10月
2023年7月
2023年6月
2023年5月
2023年4月
2023年3月
2023年2月
2023年1月
2022年12月
2022年11月
2022年10月
2022年9月
2022年8月
2022年7月
2022年6月
2022年5月
2022年4月
2022年3月
2021年12月
2021年11月
2021年10月
2021年9月