cf_710_E
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog
cf_710_E
此文更新于2019.6.22
你最开始有一个0，要构造出n
你有两种操作，
1 加上或减去一 代价为x
2 乘以2 代价为y
数据范围
n<1e18
x<1e9
y<1e9
dp[i] -> 构造 ...
牛客18多校第一场H
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog
牛客18多校第一场H
此文更新于2019.7.12
给一颗边带权点不带权点树
定义两点间的距离为：
若路径上的边权构成数列a[0...n]
则距离d= 对所有i>=1求和 (a[i-1]-a[i])*(a[i-1]-a[i])
现在要求距离每个点最远的那个点的距离为多少
树dp求down很简单
关于up , 仔细分析，抽象出来为此：
给你w[]和d[]
对每一个i，要求出 ...
about_sqrt_and_acos
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog
关于sqrt对负数开根号acos对大于1的数计算反三角函数值的问题
空间里面有一个实心球，两个点，问两点不经过实心球的路径的最小值.
题目意思很简单，我们可能会用到余弦定理，但是，余弦定理有误差，我们可能会得到一些奇怪的数字，浮点数的误差导致
余弦定理计算出来了小于-1或者大于1的其他数字，当我们对这样的数字进行反三角函数运算时，会得到nan，当然sqrt
有时候也 ...
ACM-ICPC 2018 徐州赛区网络预赛 G Trace
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace
题目大意 :
有n波海浪，每个海浪是一个以(0,0)为左下角(x,y)为右上角的长方形，每一波海浪会留下自己
的长方形边界为海浪残留，同时会冲刷掉长方形内部的其他海浪残留，问n波之后，留下来的海浪边界总长度为多少n
用线段树维护即可
#include<bits/stdc ...
bzoj2124
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog
bzoj2124
题目大意 :
在一个很长(1e5)的串里面找一个长度为三的等比子序列
考虑枚举中间值，想办法在lg的复杂度下解决单次枚举，初次考虑为依次比较中间值+d和中间值-d是否 ...
hdu5726
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog
hdu5726
题目难点 :
给你一个不变的序列，输入很多k，输出区间gcd等于k的区间的数量。
对所有区间计数，枚举左端点，二分右端点即可。
理论依据: 以任意左端点为起点的所有区间的gcd的种类不会超过这个点的值的因子的个数。
细节: 区间询问使用ST表.
...
hdu6183
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog
hdu6183 Color
it
题目大意 :
D喜欢画画，为了防止他画太乱的画，D要你帮他维护一些操作，
0:清除所有的颜色
1 x y c:在点(x,y)添加颜色c
...
hdu5745
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog
hdu5726
题目大意 :
在母串里面找子串，字串可以变化，询问所有匹配位置
其实是一个dp，设状态dp[i][j][0]表示母串匹配到i子串匹配到
j，且子串最后一个字符与前面的字符交换， dp[i][j][1]不交换，dp[i][j][2]交换，
于是就有了转移式子：
dp ...
hdu6161
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog
hdu6161
题目大意 :
给你一颗很大的完全二叉树，节点编号从1到n，对于除了1号节点以外的其他节点x，他的父亲是x>>1,1号节点为根，节点x的初始权值为x
给出两种操作：
1.update u x 意味着更新节点u的权值为x
2.query u 询问经过节点u的路径中，权值最大的条路径的权，（定义路径的权为路径上节点的权的和）
操作一共有m次
...
hdu6170
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog
hdu6170
题目大意 :
类似正则匹配
这个题开始的时候没有写出来，想到了状态的设法，如果设dp[i][j]代表第一个串的前i项能否匹配第二个串的前j项，状态个数很明显是n2的，然而一直苦于*符号的匹配，找不到好的转移方程，不管怎么想都是n3的转移复杂度，当s2[j]是*的时候，dp[i][j]