前言 周末(2019/2/23)，Payphone-X学完了唯一的多元最短路，现在，他开始向单元最短路进击啦（给自己一个小小的鼓励）  何为Dijkstra 先看看百度百科对于Dijkstra的解释  迪杰斯特拉算法是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。 ——百度百科  …… 先不看了…… 度娘装高冷的毛病什么时候能改改啊…… 还是看看通俗点的解释吧 在前边，我们已经学习了唯一的多元最短路，现在我们学习的Dijkstra是一种单元最短路算法。 （不知道啥是单元最短路的请自觉滚回Floyd） 时间复杂度为，比...

前言 最近比较颓，把很多原本计划要干的事情咕掉了…… 而今天，我终于找到了一个上午来补各种咕掉的东西。 于是乎，就有了这篇文章……  何为差分约束？ 差分约束系统，即给出一组形如或的不等式，要求出该组不等式的一组解的问题。  差分约束的原理 回忆一下，我们在做图论算法中的单元最短路时，每一次松弛操作都是基于三角不等式的，即 如果用代码表示的话，则是 if(dis[to] > dis[from] + w){ dis[to] = dis[from] + w; //即每时每刻dis[to] <= dis[from] + w } 移一下项，就变成了 dis[to] - dis[from] ...

前言  多学一点数据结构一般是有好处的，至少可以帮你打暴力 ——Wei_taming  因此，作者开始补习DL数据结构  什么是珂朵莉？ 珂朵莉是世界上最幸福的女孩子，没有之一，不接受任何反驳！   什么是珂朵莉树？ 珂朵莉树原名ODT(Ord Driver Tree)，即老司机树。是一种基于set的暴力数据结构，起源于Codeforces-896C 其原理在于使用STL中的set来维护一段连续的相同元素。 它的时间复杂度其实是假的，但在数据随机时可以有很好的表现。 而且珂朵莉树使用的局限性较大，如果没有区间赋值操作，则珂朵莉树就毫无用武之地。 因此，珂朵莉树大部分情况用于骗分。  珂朵莉树的...

题意翻译 给出一个 的矩阵，每个矩阵的权值代表该点的初始高度。 现在需要从点 走到点 ，每一步需要满足以下条件：  只能向右或向下 设当前格子的高度为 ，只能移动到高度为 的格子上去  初始时可以进行操作，使得某个格子的高度减少一个单位。 问最少需要进行多少次操作，可以存在至少一条从点 到点 的路线  输入格式 第一行包含一个整数，表示数据组数 其中，每一组数据的第一行包含两个整数，表示矩阵的行数与列数 之后是一个的矩阵，表示初始状态下矩阵中每个点的高度  输出格式 对于每组数据，输出一行一个整数，表示最少的操作次数  Input & Output 's examples Input ...

题意翻译 你有一个长度为的数组。 你可以进行任意次操作，每一次可以选择一个数，并让变成。 你的目标是使得这个数组每一个元素的乘积最大，请求出这个最大的价值，并输出这个最大价值的序列。  输入格式 第一行包含一个整数，表示数组的长度。 第二行包含个整数，分别为，表示数组中的元素。  输出格式 输出仅有一行，包含个整数，表示这个最大的价值序列。  Input & Output 's examples Input 's eg 1 4 2 2 2 2 Output 's eg 1 -3 -3 -3 -3  Input 's eg 2 1 0 Output 's eg 2 0 Input 's ...

题意翻译 给你一个数组，其中有个元素，每个元素不是就是。 现在可以进行次操作，每次操作可以改变数组中的一个元素（只能改成或）。 请求出操作后最长连续的序列的长度，并输出操作后的序列。  输入格式 第一行输入两个整数和，分别代表元素的个数与可以进行的操作数。 第二行包含个整数。每个整数只存在或两种情况。  输出格式 第一行为一个整数，表示最长连续的序列长度。 第二行包含个整数，表示操作后的序列。 如果有多个答案，请输出其中的任意一种答案。  Input & Output 's examples Input 's eg 1 7 1 1 0 0 1 1 0 1 Output 's eg 1 ...

题意翻译 有个数，个操作。形如：  将改为 将加上 将乘以  其中第个操作的编号为. 现在你可以从中选择最多个操作(不能重复选),并按一定顺序执行，使得最大。 请输出最后的最大值以及你选择的操作。  输入格式 第一行包含个整数， , ,  第二行包含个整数，表示初始序列。 之后行每行三个整数。分别表示操作类型，要修改的数的下标，修改后的数。  输出格式 输出共两行，第一行包含一个整数，表示最大值。 第二行包含个整数，按顺序输出您选择的操作。  Input & Output 's examples Input 's eg 2 4 3 13 20 1 1 14 1 2 30 2 1 6 3...

题意翻译 现在有一个长度为的括号序列，其中，左括号和右括号数量都为。 对于从左到右的第个左括号，与其配对的右括号和这个左括号之间的距离需要在 之间。 请找出一种合法的匹配方案，使其可以满足所有左括号的要求。 若存在多种方案，则只输出其中一种即可。  输入格式 输入文件共有行，第一行给出，表示左括号的数量 之后的行，每行包含两个整数。表示该左括号的距离要求。  输出格式 输出仅有一行，如果满足限制的括号序列存在，则输出任意一个。 否则请输出IMPOSSIBLE。  Input & Output 's examples Input 's eg 1 4 1 1 1 1 1 1 1 1 Out...

题意翻译 给你个点，条带权边的无向图，以及条特殊边，每条边连接和 。 问在保证每个点到的最短距离不变的情况下，最多可以删除这条边中的多少条边，  输入格式 第一行3个数字 下面行，每行3个数字 再下面 行，每行两个数字，代表连接到 的边，权值为  输出格式 输出仅有一行，为一个整数。表示能删除的最大边数。  Input & Output 's examples Input 's eg 1 5 5 3 1 2 1 2 3 2 1 3 3 3 4 4 1 5 5 3 5 4 5 5 5 Output 's eg 1 2 Input 's eg 2 2 2 3 1 2 2 2 1 3 2 1...

题意翻译 超市进行优惠活动，顾客如果在一架购物车中放上一个凳子，他就可以半价买掉这架购物车里最便宜的商品。 每一辆购物车的容量是无限的，但一个购物车里只能有一件商品半价。 现在要用架购物车装要买的件商品，里面有一些是凳子。他希望用最少的钱来买这些东西。  输入格式 第一行两个整数、； 第行至第行，每行两个整数， 。 其中表示商品的价格，表示商品的类型（表示它是凳子，表示它不是凳子）  输出格式 第一行输出一个一位小数，表示折扣之后最少需要付的价格。 接下来的行，每行开头输出一个整数，表示购物车中商品的数量。 后面跟着$$，分别表示商品的编号。 方案可能有很多，输出其中一种即可。购物车和商品的输...

题意翻译 有一个公主一生气就喜欢摔东西。 现在有很多个柜子，每个柜子里面装着很多物品，公主每次摔东西只能随机的选择一个柜子，拿出最左边或者最右边的一个物品摔碎， 给出公主最多生气的次数，求生完气之后，公主摔掉物品的价值的最大总和。  输入格式 第一行输入,,为柜子的层数，为公主最多生气的次数。 接下来行，每行第一个输入该层物品的数量,接下来输入个物品的价值。  输出格式 输出仅有一个整数，表示公主摔掉物品的价值的最大总和。  Input & Output 's examples Input 's eg 1 2 3 3 3 7 2 3 4 1 5 Output 's eg 1 15 In...

题意翻译 给你个点，条边的无向图。但一条无向边的两个方向的边权不同，求图上最小正环的大小。 正环为从一个点出发再回到这个点经过所有边边权之和为正，定义最小正环的含义为这个正环经过的点数最少  输入格式 第一行两个整数，，表示点数和边数 接下来行，一行四个整数，表示到有一条边，到的边权为，到的边权为  输出格式 输出仅有一行，包含一个整数，表示最小正环的大小（即这个正环上点的个数）。 如果没有正环请输出  Input & Output 's examples Input 's eg 4 4 1 2 -10 3 1 3 1 -10 2 4 -10 -1 3 4 0 -3 Output 's...

题意翻译 现在来做雪人，每个雪人由三个不同大小的雪球构成：一个大的，一个中等的，一个小的。 现在有个雪球半径分别为  ​为了做雪人，三个雪球的大小必须两两不同。例如，半径分别为 的雪球可以做成雪人，但或就不行。请帮忙计算最多能做出的雪人数量。  输入格式 第一行是一个整数，代表雪球的数量. 接下来一行有n个整数，分别代表每个雪球的半径。  输出格式 共行 第一行是一个数,表示最大的雪人数.  接下来行是每个雪人的描述，每行三个数，分别代表大雪球的半径，中等雪球的半径，小雪球的半径.  允许按任意顺序输出雪人描述. 如果有多种方案，输出任意一个  Input & Output 's ex...

计算转化成位运算快如闪电，按位与或非异或还有左右移小数点。 ——《我们仍未知道那天所见算法的名字》  前言 SDSC刚刚结束，作者便踏上了前往浙江的旅程。结果……Day1就是状压DP so……作者便开始疯狂补习位运算  何为位运算？ 位运算就是将一个十进制数转换为一个二进制数后，对其中每一位进行运算所得到的结果。 平时爱颓废对计算机原理感兴趣的同学们都知道，计算机中的内容是用二进制数表示的。 而我们平时所用的，，，都是在十进制下进行的运算。 这样的话，在每次运算之前计算机都会把二进制转为十进制。造成时间上的浪费 而位运算则可以直接在二进制上进行操作，因此，位运算的时间效率是比较高的。(卡常神器...