【历题回顾】CSP-S 2020 初赛后三题详解
最后三题似乎是有点代表性的难题，就挑着讲一讲罢，毕竟我基础的选择题都全对了后面的程序前两题也是一点小失误丢分不大，，，，
第十八题首先我们浅浅的看一看代码：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136// 这道题的编写者手写了几个数据结构，我们要注意一下。// 下面模拟一下顺序查看代码的过程#include <iostream>#include <queue>using namespace std;const in ...
【算法介绍】斜率优化优化动态规划
算法简介：猫爪冻冻这里我们讲的是斜率优化DP。需要用到较多的数学知识，算是 DP 优化中比较难的东西了。这里会尽量的去把它讲详细起来。斜率优化 DP 从字面上来讲就是通过斜率优化这个DP算法。接下来就从一个斜率优化的入门例题讲解下来。
算法演示：猎人射术例题选讲：猫尾隐藏菜单大秦 为你打开 题目传送门
有 $N$ 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 $N$ 个任务分成若干批，每一批包含连续的若干个任务。从时刻 $0$ 开始，任务被分批加工，执行第 $i$ 个任务所需的时间是 $T_i$ 。另外，在每批任务开始前，机器需要 $S$ 的启动时间，故执行一批任务所需的时间是启动时间 $S$ 加上每个任务所需时间之和。
一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。也就是说，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$ 。
请为机器规划一个分组方案，使得总费用最小。
部分分
数值
第一档
$n\le5\times10^3,1\le t_i,c_i\le100$
第二档
$n\le10^ ...
【拾题杂谈】SP9084 Journey to Mars
题面大秦为你打开题目传送门
题目描述给你一个环形跑道，一开始你只能走 $0$ 公里（如果你选择了从第 $i$ 个节点开始的话，那就是 $p_i$ 公里），第 $i$ 个节点可以让你多走 $p_i$ 公里，第 $i$ 个节点距离下一个节点有 $d_i$ 公里。对于每一个节点，如果能从他出发顺时针或逆时针走遍所有空间站，输出 TAK 否则输出 NIE 。
思路那么遇到这种环上的问题，第一步就是破环为链。这样的话可以免去这个跳一圈算来算去的事情。
然后再看看题目，如果起始点一样的话顺时针和逆时针其实就是反过来算的关系，所以说我们就考虑一个方向，然后到时候反过来做一遍就可以了。那么方便起见先考虑顺时针。
那么根据上面我稍微缩减了的题面，从某一个节点加完油出来，到达下一个节点的这个过程，其实就是 $p_i - d_i$ 这样的过程。正的 $p_i$ 是加的油量，负的 $d_i$ 表示走这么一段路我们会花掉那么多的油量。
也就是说，这个点的贡献我们可以认为就是 $p_i - d_i$ 。那么我们一开始的油量是 $0$ 这样一个一个经过节点的过程，其实就是求前缀和的过程，如果某一刻前缀和小于等于 ...
【算法模板】洛谷P1886 滑动窗口
模板：单调队列首先给出自己封装好的模板吧。
12345678910111213141516template<typename T, unsigned int N, bool (*func)(T, T)>class MQueue {private : pair<T , int >q[N]; int hd, tl, len;public : inline void clear(int len) { this->len = len; hd = 0, tl = -1; } inline int size() { return tl - hd + 1; } inline bool empty() { return hd > tl; } inline void push(pair<T, int> ele) { while(!empty() && (*func)(ele.first, q[tl].first) ...
【算法介绍】单调队列优化动态规划
算法简介：寒苦回向首先看名字就知道这是一个基于 单调队列 的动态规划，请先确保对于这个基础知识点理解无误再阅读下面的文章。
单调队列优化 DP 基于一些题目的单调性使用单调队列以达到降低 DP 维度等的优化作用。
算法演示：起死回骸首先，为了保证大家对于单调队列的理解我们首先以一道单调队列的题目来回顾一下。
例题选讲 · 壹：冻冻回魂夜题目描述大秦 为你打开 题目传送门
一个含有 n 项的数列，求出每一项前的 m 个数到它这个区间内的最小值。若前面的数不足 m 项则从第 1 个数开始，若前面没有数则输出 0 。
这道题首先肯定是一眼单调队列了，为了断掉各位数据结构大神的念想 RMQ 是不可能的（似乎卡常也可以哎貌似）。我们就按照这个单调队列的思路走就是了具体是真没什么难度。
代码也不放了。
那么接下来就是单调队列优化DP的内容了。
例题选讲 · 贰：云来古剑法首先我们大可以先了解动态规划优化 DP 的原理。我们想到，单调队列中有这样的一个处理流程：
在窗口内处理的这些决策，有两种情况：
被排除的不合格决策。内层循环j排除的不合格决策，在外层循环i增大时，需要重复排除。
未被排除的 ...
【拾题杂谈】LuoguP1352 没有上司的舞会
题面大秦为你打开题目传送门
题目描述某大学有 $n$ 个职员，编号为 $1\ldots n$。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入格式输入的第一行是一个整数 $n$。
第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i+1)$ 行的整数表示 $i$ 号职员的快乐指数 $r_i$。
第 $(n + 2)$ 到第 $2n$ 行，每行输入一对整数 $l, k$，代表 $k$ 是 $l$ 的直接上司。
输出格式输出一行一个整数代表最大的快乐指数。
样例 #1样例输入 #11234567891011121314711111111 32 36 47 44 53 5
样例输出 #115
提示数据规模与约定对于 $100%$ 的数据，保证 $1\leq n \leq 6 \times 1 ...
【拾题杂谈】LuoguP2014 选课
题面大秦为你打开题目传送门
题目描述在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？
输入格式第一行有两个整数 $N$ , $M$ 用空格隔开。( $1 \leq N \leq 300$ , $1 \leq M \leq 300$ )
接下来的 $N$ 行,第 $I+1$ 行包含两个整数 $k_i $和 $s_i$, $k_i$ 表示第I门课的直接先修课，$s_i$ 表示第I门课的学分。若 $k_i=0$ 表示没有直接先修课（$1 \leq {k_i} \leq N$ , $1 \leq {s_i} \leq 20$）。
输出格式只有一行，选 $M$ 门课程的最大得分。
样例 #1样例输入 #1123456787 42 20 10 42 17 17 ...
【拾题杂谈】LuoguP2015 二叉苹果树
题面大秦为你打开题目传送门
题目描述有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）
这棵树共有 $N$ 个结点（叶子点或者树枝分叉点），编号为 $1 \sim N$，树根编号一定是 $1$。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 $4$ 个树枝的树：
123452 5 \ / 3 4 \ / 1
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
输入格式第一行 $2$ 个整数 $N$ 和 $Q$，分别表示表示树的结点数，和要保留的树枝数量。
接下来 $N-1$ 行，每行 $3$ 个整数，描述一根树枝的信息：前 $2$ 个数是它连接的结点的编号，第 $3$ 个数是这根树枝上苹果的数量。
输出格式一个数，最多能留住的苹果的数量。
样例 #1样例输入 #1123455 21 3 11 4 102 3 203 5 20
样例输出 #1121
提示$1 \leqslant Q < N \leqslant 100$，每根树枝上的苹果 $\leqs ...
【算法介绍】树形动态规划
算法简介：旋风女仆树形 DP 是一种再树形结构上面跑的 DP ，我们经过有限次的递归统计，记录 DP 值再合并，从而解决问题。
介于树的天生递归结构，我们的树形 DP 也就有这个从父到子从子到父的递推方式。
复杂度一般就是遍历树的复杂度，如果多了维度，那就会乘上那么多。
算法演示：干净利落例题选讲：骑士团扫除专家大秦为你打开题目传送门
五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。
已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。
一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。
编程任务：
请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。
例题思路：支援就交给我吧题目就是一棵树，我们就考虑如何去设计状态。这个不 ...
【拾题杂谈】LuoguP1005 矩阵取数游戏
题面大秦为你打开题目传送门
题目描述帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 $n \times m$ 的矩阵，矩阵中的每个元素 $a_{i,j}$ 均为非负整数。游戏规则如下：
每次取数时须从每行各取走一个元素，共 $n$ 个。经过 $m$ 次后取完矩阵内所有元素；
每次取走的各个元素只能是该元素所在行的行首或行尾；
每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 $\times 2^i$，其中 $i$ 表示第 $i$ 次取数（从 $1$ 开始编号）；
游戏结束总得分为 $m$ 次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入格式输入文件包括 $n+1$ 行：
第一行为两个用空格隔开的整数 $n$ 和 $m$。
第 $2\sim n+1$ 行为 $n \times m$ 矩阵，其中每行有 $m$ 个用单个空格隔开的非负整数。
输出格式输出文件仅包含 $1$ 行，为一个整数，即输入矩阵取数后的最大得分。
样例 #1样例输入 #11232 31 2 33 4 2
样例输出 #1182
...