lzr010506

未归档

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

/ 注册

全部文章 / 未归档（共51篇）

牛牛的字符串游戏

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

2020-06-15

0 584

牛妹的数论题

令,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 521

牛牛的序列

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

2020-06-09

0 580

中位因数和

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

2020-06-02

0 430

牛牛切木棒

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

2020-06-01

0 464

牛牛摆玩偶

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

2020-05-31

0 541

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

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

2016-07-27

0 440

后缀平衡树 bzoj3682 Phorni

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

2016-05-18

0 506

bzoj3524 [Poi2014]Couriers

Description 给一个长度为n的序列a。1≤a[i]≤n。 m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。 Input 第一行两个数n，m。第二行n个数，a[i]。接下来m行，每行两个数l...

2016-05-18

0 434

bzoj 1571~1755 简单题解（持续更新）

如果有值得粘的代码我会留链接。 bzoj 1571 水动态规划定义f[i][j]代表在i时间，能力值为j的最多滑雪次数。对应最后三种选择： ①美美地喝上一杯可可汁 f[i][j]=f[i-1][j], ②上课 f[i][j]=f[上课前一个时刻][任意], ③滑雪 ...

2016-05-17

0 447