牛客237787563号
牛客237787563号
全部文章
未归档
归档
标签
去牛客网
登录
/
注册
牛客237787563号的博客
全部文章
/ 未归档
(共132篇)
记忆的轮廓 期望 四边形不等式dp|题解
记忆的轮廓 题目描述 通往贤者之塔的路上,有许多的危机。我们可以把这个地形看做是一颗树,根节点编号为1,目标节点编号为n,其中1-n的简单路径上,编号依次递增,在[1,n]中,一共有n个节点。我们把编号在[1,n]的叫做正确节点,[n+1,m]的叫做错误节点。一个叶...
期望
四边形不等式
数学
dp
2019-07-02
0
464
<span>一些树上dp的复杂度证明</span>
树上染色 https://www.lydsy.com/JudgeOnline/problem.php?id=4033 可怜与超市 http://hzoj.com/contest/62/problem/5 可以简单的列出状态转移方程。 它的转移过程类似: ...
dp
复杂度证明
2019-07-15
1
540
赛艇 题解
一颗赛艇 https://www.lydsy.com/JudgeOnline/problem.php?id=4584 虽然名字听起来很暴力(+1s),却是组合计数好题,在考试时都没有看出来是组合计数。 对于子任务1/2 区间的总长度不超过1e6,可以将区间内的每个数离散化到一个区间里。...
数学
组合计数
dp
2019-07-15
0
437
远古杂题 1
基因匹配Match(数据结构优化dp) 题意 1~n 每个数一定出现五次在s1,s2中。求两个字符串的最长公共子序列。 考虑n²的暴力写法,对于每一个i,与他相等的一定只有五个。 所以可以记录相等的位置优化,分别查询该位置之前的最大值+1转移,Ans记录即可。 对于1~n的带修改RMQ,可以...
线段树
dp
状压
字符串
矩阵
2019-07-17
0
465
远古杂题 2
Base基站选址(线段树优化dp) 首先写dp转移式, $dp(i,j)$表示在第i位修建第j个基站。 定义$l(i)$为能覆盖i的最靠左的基站,$r(i)$为能覆盖i的最靠右的基站, l和r数组均可以用二分求出, $dp(i,j)=min( dp(u,j-1)+cost(u,i)...
dp
数学
高斯消元
期望
图论
状压
2019-07-17
0
785
模拟5 题解
星际旅行 题中很特殊的给出,恰好2条边1次经过,m-2条边2次经过,让我有一点想到了欧拉路。 然而考试中还是没有想到拆边这个巧妙的方法,只打了一个dfs。 正解是将每条边拆为两条,问题转化为删去两条不同的边,使图中存在欧拉路。 判断每个点的度即可。 在每个边拆为两条之后,每个点的度一定是偶...
dp
组合计数
图论
欧拉路
数论分块
数学
2019-07-18
0
378
模拟6 题解
A. 那一天我们许下约定 在写出来复杂度为$O(nmd)$的简单dp后,我们考虑优化。 题中D的范围远大与N和M, 我们在dp的过程中,很多一个饼干都不给的天数是无效的一天。 于是我们dp出用i的有效天分完n个饼干的方案数, 然后把这i个有效天分配到d天里即可。 $ans= \sum \...
dp
组合计数
最短路
基环树
2019-07-21
0
331
模拟9 题解
A. 随 (rand) 尽量不要重载乘法,真的很慢。 50分算法因为重载乘法被卡常卡成20分,真的很伤。 $void$函数,传入希望存储答案的指针,使用$memcpy$快速传递。 1 void mult(const matrix &a,const matrix &...
组合计数
dp
数学
期望
矩阵
线性代数
树上差分
原根
2019-07-27
0
338
模拟11 题解
A. string 类似 HEOI2016排序 。 排序这道题因为只询问单点最终答案,二分答案, 将小于和大于等于答案的数分别设为0 1, 用线段树维护0 1的排序即可。 算法一: 本题中的1~n变成了0~25(即a~z),单点询问变成了全体询问。 仿照排序那道题的做法,线段树优...
线段树
dp
trie树
组合计数
2019-08-02
0
442
模拟12 题解
A. 斐波那契(fibonacci) 首先想到a,b<=1e6的暴力:建树,直接向上标记求lca。 建树的过程中发现一个性质。 斐波那契第n代兔子,是n-2代及以前的兔子的儿子。 因为编号连续且与父亲编号大小有关, 设该节点的编号为$x$,在第$k$代, 则$f(x)=x-fib(...
数列
线段树
dp
单调队列
贪心
拓展域
并查集
2019-08-03
0
399
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页