P2014 [CTSC1997]选课  题意为选一门课前要看它是否有前提条件：即选了一门主课才能选 “副科”，所以可以树形背包来做。 注意是不能用分组背包来做，因为这道题附件有很多个，光是两个附件的分组背包就需要四个转移方程，在这里根本没法做。 链式前向星建树。 本身这道题的数据是一组森林，但是森林很难一起dfs所以就把所有的树根都以0为根节点建一颗大树，直接链式前向星前序遍历即可。 本题最多能选M节课 转移方程      f   [   p   ]   [   j   ]    f[p][j]   f[p][j]是指     f   [   以   p   为   根   节   点   ]...

P1156 垃圾陷阱  每个垃圾只能用一次，典型的01背包。 关键是时间的处理 ll f[N];题目要中求的是生存的最长时间，所以这里的f[i]是指高度i时生存的最长时间 对于每一块垃圾，我们都有两种选择，吃，或者不吃。这里时间的处理类似迷宫DP，对于i，求所有能到达这一高度的时间中取最大值，不用记录时间段，每次加上高度试探一下，如果可以直接逃出去就输出这一块垃圾到来的时间即可。因为数据中没说是否按照T升序，所以最好先自己排个序。 然后转移方程： 不吃： f[j+e[i].H]=max(f[j],f[j+e[i].H]);//不吃，直接摞上去，比较所有能到达这里的时间（有点像那个迷宫DP）  ...

题意翻译 Polycarp正在开发一个名为“Polychat”的新项目。按照IT的现代倾向，他决定，这个项目也应该包含聊天。为了实现这一目标，Polycarp在笔记本电脑前花费了几个小时，实现了一个可以处理三种命令的聊天服务器： 将一个人加入聊天（“添加”命令）。 从聊天中删除一个人（“删除”命令）。 向所有正在聊天的人发送消息，包括发送消息的人（“发送”命令）。 现在，Polycarp希望了解处理特定命令集时服务器将产生的传出流量。 Polycarp知道聊天服务器不会为“添加”和“删除”命令发送流量。当处理“发送”命令时，服务器向聊天的每个参与者(当前在线的人)发送l个字节，其中l是消息的长...

CF12E Start of the season 题目描述 在伯兰的足球节开幕式中有一个奇怪的魔术秀。最有经验的魔术师会找一个     n   ×   n    n×n   n×n的矩阵（n为偶数）。足球节没有这个魔术秀绝对不会开始。这个矩阵应该包含0~n-1的正整数，且包含以下三条规则： 1、主对角线上的数应该都是0 2、且整个矩阵应该都是对称的 3、每行每列上的数都是不同的。 魔术师很不喜欢一遍又一遍的接矩阵（魔术师真懒），于是就请你写一个程序来帮助他们解决矩阵问题。 输入输出格式 输入格式 只有一行，包含一个偶整数     （   2   <   =   n   <   =...

题意翻译 题目大意 给出一张图，请输出其中任意一条可行的从点 11 1 到点 nn n 的最短路径。 输入输出格式 输入格式 第一行：两个整数n，m，分别表示点数和边数 接下来m行：每行三个整数u，v，w，表示u和v之间连一条边权为w的双向边。 输出格式 一行：一个可行的路径，如果不存在这种路径输出-1      2   <   =   n   <   =   1    0   5    ，   0   <   =   m   <   =   1    0   5     2<=n<=10^5，0<=m<=10^5   2<=n<=1...

蓝桥杯的题还是有难题的。这道题的可行性证明比较麻烦，但是代码比较简单。 学到了新的序列操作。前缀和的应用，前缀和还是学的不够扎实，晚上再复习一遍。 #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #define ls (p<<1) #define rs (p<<1|1) #define mid (l+r)/2 #define over(i,s,t) for(int i=s;i&...

P2280 [HNOI2003]激光炸弹  输出 2 1 0 0 1 1 1 1  输入 1  这道题就是最基础的二位前缀和的应用，如果不会的话可以点击下方链接学习哟 前缀和差分详解 #include<iostream> #include<stdio.h> //#include<string.h> #include<algorithm> //#include<queue> //#define ls (p<<1) //#define rs (p<<1|1) //#define mid (l+r)/2 #defin...

P2949 [USACO09OPEN]Work Scheduling G  3 2 10 1 5 1 7  17  后悔法的贪心。 首先思路就是先按截止日期排序，然后如果一个工作有时间去做，就先做了它，然后把它的价值压入一个小根堆。当我们找到一个没法做却价值比当前堆顶高的工作时，我们就放弃那个最小的工作（后悔了），用做它的时间去做这个价值更高的工作。 #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #...

P1005 矩阵取数游戏  输入 2 3 1 2 3 3 4 2  输出 82  说明/提示 NOIP 2007 提高第三题。 数据范围：      60   %    60\%   60% 的数据满足：     1   ≤   n   ,   m   ≤   30    1\le n,m\le 30   1≤n,m≤30，答案不超过      1    0   16     10^{16}   1016      100   %    100\%   100% 的数据满足：     1   ≤   n   ,   m   ≤   80    1\le n,m\le 80   1≤n,m≤80...

区间 DP 什么是区间 DP？ 区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来由很大的关系。令状态      f   (   i   ,   j   )    f(i,j)   f(i,j) 表示将下标位置 到 的所有元素合并能获得的价值的最大值，那么      f   (   i   ,   j   )   =   m   a   x    (   f   (   i   ,   k   )   +   f   (   k   +   1   ,   j   )   )    +   c   o   s   t   )    ...

P1063 能量项链 本题（NOIP2006）和石子合并（NOI1999）几乎一模一样 垃圾NOIP抄袭NOI，手动狗头 但是还是有细微的区别的，首先你得先能看懂题，石子合并是N堆石子，是     i   −   k    i-k   i−k和     k   +   1   −   j    k+1-j   k+1−j之间的合并，但是本题能量项链，是i，j，k三个相邻的珠子起作用，得分是     a   [   i   ]   ∗   a   [   j   ]   ∗   a   [   k   ]    a[i]*a[j]*a[k]   a[i]∗a[j]∗a[k]三个相邻的珠子的值 #...

目录  1、     p   r   u   f   e   r    prufer   prufer编码  1）无根树转化为prufer序列 2）prufer序列转化为无根树。  2、Cayley公式  1）由Cayley公式得到四个推论 例题1、P4981 父子 例二、P4430 小猴打架     部分来自： 大佬的博客，加入了一些自己的理解。 1、     p   r   u   f   e   r    prufer   prufer编码 首先引入     p   r   u   f   e   r    prufer   prufer编码（其实是     P   r  <mov...

P1228 地毯填补问题  离散上讲了这个问题，如下图  初看这个问题，似乎无从下手，于是我们可以先考虑最简单的情况，既n = 2时 0 0 0 1 这时，无论公主在哪个格子，我们都可以用一块毯子填满 继续考虑n = 4的情况 我们已经知道了解决2 * 2的格子中有一个障碍的情况如何解决，因此我们可以尝试构造这种情况 首先，显然可以将4 * 4的盘面划分成4个2 * 2的小盘面，其中一块已经存在一个障碍了 而我们只需在正中间的2 * 2方格中放入一块地毯，就可以使所有小盘面都有一个障碍 于是，n = 4的情况就解决了 我们可以将n = 4时的解法可以推广到一般情况，既当n = 2 k时，我们均...

P3382 【模板】三分法  法1 : 三分法 对于一个二次函数[L,R]内取最值，选取两个点x=(2∗l+r)/3,y=(l+2∗r)/3 若f(x)>f(y)，那么[y,R]这一段可以舍弃(一定不会成为最优解)，否则[l,x]这一段舍弃 #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #include<math.h> #define ls (p<<1) #define...