luogu P4099 [HEOI2013]SAO
传送门吐槽题目标题这个依赖关系是个树,可以考虑树型dp,设f_i表示子树i的答案因为这是个序列问题,是要考虑某个数的位置的,所以设\(f_{i,j}\)表示子树i构成的序列,i在第j个位置的方案.转移依次合并儿子\(y\),每次枚举一个位置j,以及枚举儿子\(y\)的序列中有k个数放在插前面,可以得...
Luogu 2886 [USACO07NOV]牛继电器Cow Relays
BZOJ 1706权限题。倍增$floyd$。首先这道题有用的点最多只有$200$个，先离散化。设$f_{p, i, j}$表示经过$2^p$条边从$i$到$j$的最短路，那么有转移$f_{p, i, j} = min(f_{p - 1, i, k} + f_{p - 1, k, j})$。然后做一...
luogu题解 P2886 【牛继电器Cow Relays】-经过K边最短路&矩阵
题目链接：https://www.luogu.org/problemnew/show/P2886Update 6.16最近看了下《算法导论》，惊奇地发现在在介绍\(APSP\) \((All Pairs Shortest Path)\)时的第一个方法就是此法，同时在思考题中看到了不少熟悉的问题，看...
Luogu P4009 汽车加油行驶问题
题目链接 \(Click\) \(Here\)分层图。。好长时间没写差点要忘了\(hhhhh\)，其实思路还是很明了的。注意需要强制消费。#include <bits/stdc++.h>using namespace std;const int N = 110010;const in...
【Luogu1345】周游加拿大（动态规划）
【Luogu1345】周游加拿大（动态规划）题面题目描述你赢得了一场航空公司举办的比赛，奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始，然后一直自西向东旅行，直到你到达最东边的城市，再由东向西返回，直到你回到开始的城市。除了旅行开始的城市之外，每个城市只能访问一次，因为开始的城市...
luogu 1550 [Usaco2008 Oct]打井 最小生成树+小技巧
此题似乎显然最小生成树，小技巧需要注意：在每个点出井水，需要花费，实际上可以把井水视作所有井下统一的一点，需要走路径到达此点，新图上再最小生成树将点化作边处理还有题目写的数据范围一般不可信，开大点总是好的，代码就不贴了吧#include<bits/stdc++.h>#define rep...
luogu P4146 序列终结者
嘟嘟嘟这是一道splay基础题。最坑的一点是，因为有些节点可能没有左儿子或右儿子，所以必须把t[0].Max赋成-INF！因为这个调了半天，看来回头复习复习splay是对的……#include<cstdio>#include<iostream>#include<cmat...
luogu P2511 [HAOI2008]木棍分割
传送门第一问是一道经典的二分,二分答案\(ans\),然后从前往后扫,判断要分成几段救星了第二问设\(f_{i,j}\)表示前\(i\)个数分成\(j\)段,每段之和不超过第一问答案的方案,转移就是从\(f_{k,j-1}(k<i,(a_{k+1}+...+a_i)\leq ans)\)转移过...
luogu P1762 偶数
打表找规律吼题哇首先打出\(1-1000\)内的答案的表0011469916...448363有个**规律啊qwq然后想到用\(\frac{n(n+1)}{2}\)(也就是数字的总数)减去答案,得到另一个表13591115192729...好像有点规律啊,,,发现第\(2^i\)行的数为\(3^i\...
[模板][Luogu3387] 缩点 - Tarjan, 拓扑+DP
Description给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。Input&OutputInput第一行，n,m第二行，n个整数，依次代表点权第三至m+2行，...
[luogu]P1026 统计单词个数[DP][字符串]
[luogu]P1026统计单词个数题目描述给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词...
luogu P1880石子归并
石子归并luogu1880传送门 noi1995在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.数据的第1行试正整数N,1≤N≤10...
luogu P3175 [HAOI2015]按位或
传送门如果每个位置上的数字的意义是这个位置被加进集合的最早时间,那么我们要求的就是集合中最大数的期望,使用Min-Max容斥,\(E(max(S))=\sum_{T\subset S}(-1)^{|T|+1}E(min(T))\),这里的\(E(min(T))\)是集合中加进数字的期望时间,根据题意...
[YNOI2017][bzoj4811][luogu3613] 由乃的OJ/睡觉困难综合症 [压位+树链剖分+线段树]
题面BZOJ题面，比较不清晰Luogu题面，写的比较清楚思路原题目我们先看这道题的原题目NOI2014起床困难综合症的确就是上树的带修改版本那么我们先来解决这个原版的序列上单次询问二进制的这些操作，我们把操作数和符号一起（比如xor 7,and 31）挪动的话，答案是会改变的，不同符号之间不满足交换...
luogu P2657 [SCOI2009]windy数 数位dp 记忆化搜索
题目链接luogu P2657 [SCOI2009]windy数题解我有了一种所有数位dp都能用记忆话搜索水的错觉代码#include<cstdio>#include<algorithm>inline int read() { int x = 0,f = 1; c...
luogu P4008 [NOI2003]文本编辑器 splay 块状链表
LINK：文本编辑器这个东西感觉块状链表写细节挺多 (块状链表本来就难写解释一下块状链表的做法：其实是一个个数组块 然后利用链表给链接起来 每个块的大小为sqrt(n).这样插入删除的时候直接暴力插入删除即可 复杂度都是根号的。插入的时候当前的块过大的时候就要分裂 查询时对于大小为0的块记得及时删除...
【Luogu1272】重建道路（动态规划）
【Luogu1272】重建道路（动态规划）题面题目描述一场可怕的地震后，人们用N个牲口棚(1≤N≤150，编号1..N)重建了农夫John的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此，牧场运输系统可以被构建成一棵树。John想要知道另一次地震会造成多...
Luogu P3165 [CQOI2014]排序机械臂
先讲一下和这题一起四倍经验的题：Luogu P4402 [Cerc2007]robotic sort 机械排序SP2059 CERC07S - Robotic SortUVA1402 Robotic Sort这题作为一道十分经典的平衡树维护序列的问题，自然是值得一做的了。写完翻了下题解发现都是写Sp...
【Luogu】P3856公共子串（DP）
题目链接DP。设last[i][j]是第i个串字符'j'所在的最后的位置,f[i][j][k]是第一个串匹配到i，第二个串匹配到j，第三个串匹配到k，最多的公共子串数。那么我们三重循环i、j、k，每次更新last数组的值。然后在三重循环内部再加一重循环从'a'到'z'，枚举公共子串的最后一个字符是什...
luogu3250 网络 (整体二分+树上差分+树状数组)
首先整体二分，问题变成是否存在经过一个点的满足条件的路径那么我对于每个路径(a,b,lca)，在树状数组的dfn[a]++,dfn[b]++,dfn[lca]--,dfn[fa[lca]--]然后直接查那个点的子树和就行了 #include<bits/stdc++.h> #define ...