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