lzr010506

分类

bzoj(18) DP优化(1) hdu(1) manacher （马拉车）(1) poj(7) 博客(4) 博弈论(1) 未归档(54) 杂题(1) 树状数组(1) 水题(2) 矩阵快速幂(1) 网络流(2) 计算几何(2)

/ 注册

全部文章（共93篇）

牛牛的字符串游戏

显然我们得按顺序获得目标t的每个字符。对于我们可以在s中找到这么一个子序列。显然如果找到尾巴还是没有需要的。就得从s[0]开始重新开始顺序找。(然后答案递增,因为表示要重新开始加一个子序列了) 所以不能直接找。所以我们可以另外开一个数组表示在i-1位置,如果要找下一个紧接着的j的话,需要到哪个位置找...

2020-06-15

0 482

牛妹的数论题

令,0≤<,gcd(,)=gcd(+,).0≤x<m,gcd(a,m)=gcd(a+x,m).相等的个数等于,gcd(,)=gcd(,).,gcd(a,m)=gcd(x,m).然后欧拉定理一下就行了复杂度O(logm) #define ll long long inline ll phi...

2020-06-15

0 393

牛牛的序列

分析题目性质，因为操作次数无限，所以可以把所有可以交换的位置放到一起处理，对于每一个这样的连通块，肯定要把大的放前面，小的放后面。用并查集处理连通块.然后同一连通块倒序输出，就可以得到字典序最大的解，复杂度O(nlogn). /** * struct Interval { * int st...

2020-06-09

0 476

中位因数和

我们可以枚举因数来更新每个数字的中位因数里面小于等于的那个。因为x最大为，因此只需要枚举到。然后暴力更新当前因数的倍数。这个复杂度是O(nlogn) const int mod = 998244353; long long f[1000010]; class Solution { public:...

2020-06-02

0 343

牛牛切木棒

三角形两边之和大于第三边，因此不构成三角形的条件就是存在两边之和不超过另一边。所以就是贪心的使得尽量多的段能构成的总长度最小，即按照斐波那契数列的方法切割可以使得切割的段数最大，1，1，2，3，5这样可以使得任意三根木棒不能组成三角形，最后无法切割的部分加到最长的一根里面即可。 class Solu...

2020-06-01

0 377

牛牛摆玩偶

从左至右对区间进行排序，因为D满足单调性，即如果D可以，D-1一定可以。所以可以在分隔距离D上进行二分答案。对于固定的D，我们要检查是否可以放置至少N个玩偶。这可以通过贪心的策略来完成。只需将每个玩偶放在最左边的位置即可。一旦奶牛数量达到N，就可以break了，因此可以在O（N + M）时间检查一个...

2020-05-31

0 473

jdfz 培训总结 Day1

今天已经Day4了，写个3天的总结吧。 Day1 先说说考试： T1 这题大新闻了，样例搞错、数据范围没写全。然后我前一个小时都是一脸懵逼的状态，老师在1h30min左右更新的。瞬间秒掉。。。dp+矩阵乘法。 T2 这题显然最长路吗，优化个建图。优化了许久。。算了，写个暴力算了。暴力...

2016-08-04

0 381

好久写博客了，写个总结吧

真的好久没写博客了。最近我都在随着一群进队爷们准备国赛。并参加了网络同步赛。虽然暂时没出成绩，但自我感觉良好啊。最近一段时间，开始刷题，博客将会持续更新。望神犇们留个友链啊

2016-07-27

0 356

bzoj 1751 [Usaco2005 qua]Lake Counting

Description Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N &...

2016-06-05

0 392

后缀平衡树 bzoj3682 Phorni

Description Phorni 是一个音之妖精,喜欢在你的打字机上跳舞。一天,阳光映射到刚刚淋浴过小雨的城市上时,Phorni 用魔法分裂出了许多个幻影,从 1 到 n 编号。她的每一个幻影都站在打出的字符串的一个位置上,多个幻影可以站在同一个位置上。每一个幻影代表的字符串即为从...

2016-05-18

0 416