zhizhesoft

  • 首页
ZHIZHESOFT
zhizhesoft
页面

CF1276F Asterisk Substrings [后缀自动机]

抄一下 \(\color{\black}{n}\color{\red}{antf}\) 的题解 我 nantf 怎么这么强啊…这题我不到半个小时就写掉了…为什么div1的时候只有一个人做掉这个 F 啊…这个不是我 nantf 随随便便就写掉的么… 这个 CF 评分 3300 的题为什么这么水啊,直接1A了( 我们先考虑不带 star 的,人人会做,\(\sum len_i - len_{fa_i}\)。 考虑 star 在最前面和最后面,最后一个字符插入到 SAM 之前统计一下 \(\sum len_i - len…

2019年7月2日 0条评论 16点热度 0人点赞 risingsun 阅读全文
页面

P4173 残缺的字符串 [FFT]

构造 \(f(x,y) = xy(x-y)^2\) // powered by c++11 // by Isaunoya #include <bits/stdc++.h> #define rep(i, x, y) for (register int i = (x); i <= (y); ++i) #define Rep(i, x, y) for (register int i = (x); i >= (y); --i) using namespace std; using db = doub…

2019年7月2日 0条评论 1点热度 0人点赞 risingsun 阅读全文
页面

CF528D Fuzzy Search [FFT]

没啥好说的… #include <bits/stdc++.h> using namespace std; #define int long long struct cpx { double x, y; cpx(double _x = 0, double _y = 0) { x = _x; y = _y; } }; cpx operator * (cpx x , cpx y) { return cpx(x.x * y.x - x.y * y.y, x.x * y.y + x.y * y.x); } cpx…

2019年7月2日 0条评论 0点热度 0人点赞 risingsun 阅读全文
页面

#4589. Hard Nim [FWT]

考虑到如果 \(n=2\) 那么显然这个答案是 \(\sum_i [prime_i \leq m]\) 然后我们发现 \(ans(x) = a^n(x)\) \(ans_0\) 就是答案。 // powered by c++11 // by Isaunoya #include <bits/stdc++.h> #define rep(i, x, y) for (register int i = (x); i <= (y); ++i) #define Rep(i, x, y) for (registe…

2019年7月2日 0条评论 16点热度 0人点赞 risingsun 阅读全文
页面

CF868F Yet Another Minimization Problem [决策单调性]

\(calc(i,j)\) 同样满足四边形不等式,于是没了。 // powered by c++11 // by Isaunoya #include<bits/stdc++.h> #define rep(i , x , y) for(register int i = (x) ; i <= (y) ; ++ i) #define Rep(i , x , y) for(register int i = (x) ; i >= (y) ; -- i) using namespace std ; us…

2019年7月2日 0条评论 0点热度 0人点赞 risingsun 阅读全文
页面

P3515 [POI2011]Lightning Conductor [决策单调性]

求 \(p\) 使得所有 \(a_j \leq a_i + p - \sqrt |i-j|\) 发现绝对值不好搞,然后就正反做两遍 // powered by c++11 // by Isaunoya #include<bits/stdc++.h> #define rep(i , x , y) for(register int i = (x) ; i <= (y) ; ++ i) #define Rep(i , x , y) for(register int i = (x) ; i >= (…

2019年7月2日 0条评论 16点热度 0人点赞 risingsun 阅读全文
页面

CF763E Timofey and our friends animals [回滚莫队,可撤销并查集]

题意: 给你 \(n\) 个点,已知 \(m\) 对关系 \([u,v] (|u - v| \leq k)\),\(k\) 给出,询问 \(q\) 次,每次问你 \([l,r]\) 有多少个连通块。 sol: 显然的回滚莫队,我们按块来分,对于每个块 \(i\),我们可以把所有 \(l\in block_i\) 丢到 \(i\) 里面,然后我们对 \(r\) 排序,右指针向右移动,然后左指针那边撤销就好了,复杂度 \(n \sqrt n \log n\),如果在同一块的话直接暴力撤销就好了。 // powered …

2019年7月2日 0条评论 16点热度 0人点赞 risingsun 阅读全文
页面

P3710 方方方的数据结构 [KD-Tree]

这题似乎就 KD-Tree 板子。 矩形加法,矩形乘法,QAQ。 都是离线下来按顺序添加的,所以没有什么关系。 // powered by c++11 // by Isaunoya #include <bits/stdc++.h> #define rep(i, x, y) for (register int i = (x); i <= (y); ++i) #define Rep(i, x, y) for (register int i = (x); i >= (y); --i) using …

2019年7月2日 0条评论 20点热度 0人点赞 risingsun 阅读全文
页面

CF1101D GCD Counting [点分治]

复习一下点分治(?) 我们发现 \(a_i \leq 2\times 10^5\) calc 一手,发现质数不会太多,直接暴力就好了。 // powered by c++11 // by Isaunoya #include <bits/stdc++.h> #define rep(i, x, y) for (register int i = (x); i <= (y); ++i) #define Rep(i, x, y) for (register int i = (x); i >= (y);…

2019年7月2日 0条评论 0点热度 0人点赞 risingsun 阅读全文
页面

#4919. [Lydsy1706月赛]大根堆 [启发式合并,dp]

这个其实是一个树形的 LIS。 我们考虑到 multiset 怎么维护一个序列,然后扩展到树上,这样就可以了。 怎么维护一个序列呢? 我们考虑 \(s.size()\) 是当前的 LIS 长度,然后我们插入一个数,要么比最大的要大,比最大的要大直接丢进去,这样长度显然也是+1。 如果比最大的要小?那么我们直接替换掉那个数,这样长度还是不变,微调就可以了,不能相同就直接删掉一个 \(\leq x\) 的数。 在树上的话直接丢到上面启发式合并就好了。 // powered by c++11 // by Isaunoya…

2019年7月2日 0条评论 17点热度 0人点赞 risingsun 阅读全文
1…196259196260196261196262196263…196265
Search

COPYRIGHT © 2022 zhizhesoft. ALL RIGHTS RESERVED.