【算法介绍】动态规划
算法简介： DP 与算法之歌所谓 DP 也就是 $\tt Dynamic\ Programming$ 的缩写，即动态规划算法。我们常说的动态规划，它是一种基于把一个问题分为多个子问题，通过权衡他们之间的最优，得到最后的最优。而这种做法和我们一开始学过的暴力枚举的区别就在于 —— $\tt DP$ 数组。$\tt DP$ 的核心就是把子问题分解为不相互独立的子问题后，使用数组记录最优解，从而减少计算次数的一种算法。穷举法也可以称为静态规划。对于和 DP 特别像的另外两个算法，也就是贪心和分治。贪心，是一种对于每一步都取最优解，最后使得总答案最优的算法。他和 DP 的区别是，DP 为了求全局最优，可以适当舍弃一部分的最优解，而贪心不行。分治算法，是把问题分为相互独立的子问题计算，这一点与 DP 是不同的。而对于 DP 算法，我们完全不需要有那么多的顾忌，不要以为他是英文的名称就很高大上，我们只需要知道，它不过是存下了每一步的答案去权衡最优解罢了。DP 其实并没有特别的拘泥于一些模板，所以没有太多需要记的东西，我们只需要一个灵活的大脑。
算法演示：递推递归千题间对于 DP 的几种常见形式， ...
2024-517集训总总结
2024-517集训总总结还好。
关于题目的那些事算法方面十天集训，只有两道 $\tt DP$ 还压在最后一天。。。。。。真的是短板了现在。。。
其他的算法都还好，正解都能想出来，AK两次其他基本都是榜前3
码力方面代码打完还能有一至半小时空闲划水，这个问题真的不大。
难度方面个人认为偏简单，难题都压在二期了。还有就是。。。这出题人尼玛包完原神的，题题原，纯若至
关于平时的饭菜很难评。。。中午饭吃的有点山寨。。。晚饭还好。
关于我们住的宿舍还好，没想象中的那么差，没想象中的那么好。
关于一些玄学设备空调很凉快，插线板也没有以前那种不够用的情况。桌子有点小，其他还好。
关于大佬我周围的都是大佬，就我最菜，菜飞了，天天他们AK了我才AK，，，，，rzrzrzrz
周泽共
【2024 - 517集训四期】Day8 集训总结
比赛总结发挥基本正常，T3 超级无敌尼玛比大失误
T1 总结赛时总结简单题，纯模拟即可
题目思路模拟
题目代码无
T2 总结赛时总结一眼题。小学生题目，模拟
题目思路模拟
题目代码无
T3 总结赛时总结赛时思路基本正确，结果为了计算正确的转弯次数多此一举，WA + TLE 0 分。
题目思路记忆化搜索
题目代码无
T4 总结赛时总结知道是前缀和，但是摆烂
题目思路从 $k = 2$ 的情况扩展出来，变成了简单的小学题
题目代码无
CSP - S 2022 题解T3 星战（Galaxy）题意给出一张有 $n$ 个点，$m$ 条边的无向图。有如下几种操作。
摧毁一条边
修复一条边
摧毁一个点以及其所有的边
修复一个点以及它所有的边
思路和哈希或异或哈希。处理每一个点的入度，与满图状态比较。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787 ...
【2024 - 517集训四期】Day7 集训总结
比赛总结正常发挥 + 题目过水，AK虐全场。
由于题目过水，赛时题目总结略。
CSP-S 2022 SolutionT1 - 假期计划（Holiday）形式化题意给出一个有 $n$ 个节点的无向图。求从 $1$ 号点出发，在路上选择经过的四个不同的景点，最后回到 $1$ 号点后，选择的四个节点权值之和。选择的点之间距离最多的长度不可以超过 $k$ 。
思路直接 BFS 得到两个点是否可达，和距离前 3 的节点。最后合并答案即可。（这个蓝题评的名不副实，一下子就想出来了）
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212 ...
【2024 - 517集训四期】Day6 集训总结
比赛总结发挥基本正常，T3 超级无敌尼玛比大失误
T1 总结赛时总结简单题，纯模拟即可
题目思路模拟
题目代码无
T2 总结赛时总结一眼题。小学生题目，贪心
题目思路贪心
题目代码无
T3 总结赛时总结赛时一眼顶针，结果某一行代码莫名奇妙不见了，导致 RE 还差了半天没查出来
400 -> 325 ，R1 -> R5
题目思路思路打开，模拟即可
题目代码无
T4 总结赛时总结一眼顶针二分，场切
题目思路二分，带点小学奥数（鸡兔同笼）。
题目代码无
CSP - S 2023 题解T4 种树按照前天的思路成功AC。附上这个首A的代码：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111 ...
【2024 - 517集训四期】Day5 集训总结
比赛总结发挥基本正常，T3 小失误。
T1 总结赛时总结简单题，纯模拟即可
题目思路模拟
题目代码无
T2 总结赛时总结一眼题。线段树模板
题目思路线段树模板
题目代码无
T3 总结赛时总结找规律都不需要的找规律题。一眼就看出 1e18 内的数的数量特别少，打表 & 递归即可（517测评机吃了我的正解导致 T3 “未提交” 直接掉大分 ）
题目思路打表 & 递归
题目代码无
T4 总结赛时总结无思路。骗分 15pts
题目思路由于题目保证有解，所以直接贪心匹配，贪心涂色。（赛时竟然没有人想到如此简单的题目）
题目代码无
【2024 - 517集训四期】Day4 集训总结
比赛总结发挥基本正常，T3 小失误。
T1 总结赛时总结简单题，基本上是模拟即可
题目思路数学，模拟，推公式
题目代码无
T2 总结赛时总结一眼题。典中典。
题目思路记录起始元素，用处理环的方式处理
题目代码无
T3 总结赛时总结一开始思路正确，因为旁边的 wangletao dalao 过了压力极大，发现写出来的代码样例没过直接删了打暴力，并且因为紧张过度理解错题意暴力也挂了
题目思路分类讨论。有意义的区间分为：$[1,l], [l, r], [r,n]$ 。
处理最小和最大值即可
题目代码无
T4 总结赛时总结极限乱贪AC
题目思路正贪一遍处理酒店 i 和市场 i 的最大值，在反贪一遍处理答案
题目代码无
2023 CSP - S 题解T1 密码锁场切没话说
T2 字符串思路不难发现，O(n ^ 2) 做法就是枚举起点 i 模拟，栈每空一次统计一次。由这个不难想到，记录每一个栈的状态，没重复一次记录，对于出现 $n$ 次的情况会有 $\cfrac{n(n-1)}{2}$ 的贡献。
代码无
T3 结构体思路纯模拟。没有任何技术含量
代码纪念一下最长的模拟代码
1237 行
T4 种 ...
【2024 - 517集训四期】Day2 集训总结
T1 总结赛时总结若至题。一眼顶针
题目思路数学，模拟，推公式
题目代码无
T2 总结赛时总结一眼题。典中典。
题目思路打表发现，第一项和第二项的系数是斐波那契数列。预处理出后计算即可
题目代码无
T3 总结赛时总结没有难度
题目思路贪，最小是优先未感染，最大是优先感染
题目代码无
T4 总结赛时总结思路正确，实现失误 ：100 -> 55最后一刻，重新提交： 55 -> 5
R2 -> R5 nerd
题目思路把出生死亡和查询看作事件，按照时间排序。出生优先级大于查询大于死亡。余下模拟。
题目代码无
【2024 - 517集训四期】Day1 集训总结
T1 总结赛时总结若至题。一眼顶针
题目思路上数据结构 map
题目代码无
T2 总结赛时总结贪心策略错误，难度排序排成了满意度排序
题目思路贪，按照难度排序
题目代码1234567891011sort(con + 1, con + c + 1);sort(pro + 1, pro + p + 1);ll ans = 0;ll mx = 0, j = 0;for(int i = 1; i <= p; i++) { while(con[j + 1].first <= pro[i].first && j <= c) { mx = max(mx, con[++j].second); } ans += max(0LL, mx - pro[i].second);}printf("%lld", ans);
T3 总结赛时总结水题，典中典。
题目思路不难发现横竖无关，单独处理后合并答案
题目代码无
T4 总结赛时总结完全没有思路，部分分拿满
题目思路对于绝对值考虑分解，情况分 ...
CF1637D - Yet Another Minimization Problem
题面原题链接大秦 为你打开 题目传送门
题目翻译定义某数组 $x$ 的权值为
\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n(x_i+x_j)^2现在，给定两个长度为 $n$ 的数组 $a,b$。你可以执行若干次操作，每次操作选择一个下标 $i$，并交换 $a_i,b_i$。求在进行操作之后两个数组的权值之和最小能够达到多少。
数据范围：
$t$ 组数据，$1\leqslant t\leqslant 40$。
$1\leqslant n,\sum n\leqslant 100$。
$1\leqslant a_i,b_i\leqslant 100$。
Translated by Eason_AC
输入格式Each test case consists of several test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 40 $ ) — the number of test cases. The following is a descriptio ...
