south_king

分类

bzoj(7) dp(7) hdu(1) kmp算法(1) NEW(1) python(1) spfa(12) tarjan(5) vijos(2) 二分(1) 二分图(1) 二叉树(1) 回忆(1) 搜索(2) 数论(7) 最小生成树(2) 期望dp(1) 未归档(8) 树形dp(3) 树状数组(1) 模拟(2) 模拟退火(2) 模板(14) 水题(14) 洛谷(17) 状压d(2) 考试(13) 贪心(2)

/ 注册

全部文章（共131篇）

prufer编码与Cayley公式学习（洛谷P4430 小猴打架）

purfer 编码 purfer编码是一种无根树的表示方式，对于一棵无根树，有着为一的prufer编码。如何把一棵树转化成为purfer编码呢？我们用删点乱搞的方式。在第i步时，移去所有叶子节点中标号最小的顶点和相连的边，并把与它相邻的点的编号加入Prufer序列中，重复以上步骤直到原图仅剩2个...

2021-05-28

0 614

P2573 [SCOI2012]滑雪

题目描述 a180285 非常喜欢滑雪。他来到一座雪山，这里分布着 mm 条供滑行的轨道和 nn 个轨道之间的交点（同时也是景点），而且每个景点都有一编号 i\space (1 \le i \le n)i (1≤i≤n) 和一高度 h_ia180285 能从景点 i 滑到景点 j 当且仅当存在一条 ...

2021-05-28

0 433

洛谷 P4180 [BJWC2010]严格次小生成树

题目描述小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时，小P又来泼小C冷水了。小P说，让小C求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是EM，严格次小生成树选择的边集是ES，那么需要满足...

2021-05-28

0 375

洛谷 P4071 [SDOI2016]排列计数

简化版题意： 1~n n个数字，问满足m个ai=i的排列个数答案对1e9+7取模这题就是道裸题，不知道为啥还能是蓝的前置技能一：快速幂（太简单了不讲了这周和矩阵的知识点一起写）前置技能二：错排公式（顾名思义错排就是ai!=i的排列个数，高中应该都学过）下面是推理过程：我们设f[n]代表...

2021-05-28

0 400

洛谷 P3243 [HNOI2015]菜肴制作

题目描述知名美食家小 A被邀请至ATM 大酒店，为其品评菜肴。 ATM 酒店为小 A 准备了 N 道菜肴，酒店按照为菜肴预估的质量从高到低给予1到N的顺序编号，预估质量最高的菜肴编号为1。由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 M 条形如”i 号菜肴’必须...

2021-05-28

0 507

洛谷P3878 [TJOI2010]分金币

题目描述现在有n枚金币，它们可能会有不同的价值，现在要把它们分成两部分，要求这两部分金币数目之差不超过1，问这样分成的两部分金币的价值之差最小是多少？输入格式每个输入文件中包含多组测试数据，输入文件的第一行是一个正整数T，用来说明文件中有多少组测试数据。接下来将依次给出所有测试数据的描述，每...

2021-05-28

0 405

洛谷SP34 RUNAWAY - Run Away

题意翻译在给定范围内找一个点，使得距离所有点的最小值最大。模拟退火 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include &l...

2021-05-28

0 456

北航忘了第几次上机的题解（3.27）

都是模拟，自行食用 A /* Author: 张皓南 Result: AC Submission_id: 2384206 Created at: Fri Mar 27 2020 20:47:33 GMT+0800 (CST) Problem_id: 3143 Time: 16 Memory: 16...

2021-05-28

0 425

洛谷P2797 Facer的魔法

题目背景 Facer 误闯入禁地，学会了魔法。题目描述 Facer 闯入禁地之后，遇到了对手。具体来说，Facer 魔法是一串数字。但是 Facer 能力有限，这串数字只能从给定的 n 个数中选择，能产生的魔法值为选择出的这些数字的平均数。他的对手不会像 Facer 这样的强大的魔法...

2021-05-28

0 337

洛谷P2034 选择数字

题目描述给定一行n个非负整数a[1]…a[n]。现在你可以选择其中若干个数，但不能有超过k个连续的数字被选择。你的任务是使得选出的数字的和最大。输入格式第一行两个整数n，k 以下n行，每行一个整数表示a[i]。输出格式输出一个值表示答案。一个小dp 我们设f[i]为不选i时候的最...

2021-05-28

0 350