stony_oi-CSDN博客

原创最长公共子串模板

#include<iostream>#include<algorithm>#include<cstdio>#include<cstdlib>#include<cstring>using namespace std;typedef long long LL;inline int read(){ int x=0;bool ...

2018-12-14 12:04:49 221

原创 bzoj4589 FWT

#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0;

2017-05-28 14:25:08 438

原创 bzoj 4880: [Lydsy2017年5月月赛]排名的战争

zz题，随便搞搞就行了然而代码写得又丑又慢，有时间再改改吧#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()

2017-05-05 23:10:30 695

原创 uoj191 Unknown

点分治还能这么用，感觉好妙啊然而我不到200行的程序居然错了10多个地方，调了一晚上，简直zz#include#include#include#include#include#define R registerusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char

2017-05-05 08:50:28 412

原创 codeforces 623 E FFT

#include#include#include#include#include#includeusing namespace std;typedef long long LL;#define R registerconst int N=66005,P=1000000007,bt=16,mas=65535;const long double _2Pi=2*acos(-1.0);

2017-05-04 15:13:37 349

原创 bzoj2219 【原根】【CRT】

先把代码放在这，感觉还是有问题的，只是数据比较弱#include#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar

2017-05-02 10:07:58 349

原创 bzoj4144 splay模板题

#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0; for (;c>='0'&&c<

2017-04-22 10:32:51 269

原创 51nod 1123 X^A Mod B 问题

先放在这好了。。。模2的次幂那一块还有问题，待改正#include#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getcha

2017-04-20 17:10:55 735

原创 NOI2014 购票

#include#include#include#include#include#includeusing namespace std;typedef long long LL;inline LL read(){ LL x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0;

2017-04-15 09:24:45 491

原创 51nod 1258 FFT 多项式求逆伯努利数

#include#include#include#include#include#include#define rd roundusing namespace std;typedef long long LL;inline LL read(){ LL x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-

2017-03-03 08:50:20 456

原创 bzoj3566

#include#include#include#include#includeusing namespace std;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0; for (;c>='0'&&c<='9';c=getchar()) x=x*

2017-02-13 16:46:13 316

原创 bzoj1406【数论】

#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0; for (;c>='0'&&c<

2017-02-12 15:17:15 201

原创 bzoj3994【莫比乌斯函数】

最关键的是这个恒等式然后推式子就行了#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c==

2016-12-17 11:19:32 273

原创 bzoj2693

#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0; for (;c

2016-12-17 10:25:58 494

原创 bzoj2989&4170【二进制分组】【主席树】

其实没有要求强制在线，可以直接上CDQ分治二进制分组嘛可以看看2013年xhr的《浅谈数据结构题的几个非经典解法》或者看看%%CA的博客http://m.blog.csdn.net/article/details?id=47909599本题概括：给定平面上一些点和一些操作，操作分两种，一种是加点，一种是查询某个菱形区域内的点数搞个坐标变换就能变成正方形了首先，二进制分组和CDQ

2016-12-16 15:29:42 1764

原创 bzoj4310【后缀数组+二分】

二分原串的所有子串最多O(n^2)个求一个子串的排名和由排名求子串都可以拿height数组乱搞（如果多组询问的话还可以二分）判断的话也是贪心一下就好了#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;

2016-12-15 18:18:18 680

原创 bzoj1565

#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0; for (;c

2016-12-14 18:13:33 271

原创 bzoj2251

乱搞前面求后缀数组是O(n^2+nlog n)的，后面求答案是乱搞，貌似可以卡到O(n^3)，不过数据很水#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar();

2016-12-14 15:35:32 256

原创 bzoj3900【状压】

设f[S]是保证子集S完全满足要求的最小交换次数。对于一个集合S先判断是否可能有解，若有解则先令f[S]=S中的点数-1（相当于整个集合进行置换）。但是也有可能S是分成若干个子集，在这些子集中分别置换，所以最后再dp一下就行了。#include#include#include#include#includeusing namespace std;typedef long long

2016-12-13 15:49:23 420

原创 bzoj4723

#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0; for (;c>='0'&&c<

2016-12-12 18:12:21 367

原创 spoj GCDEX【线性筛】

设，由于这里f(n)是两个积性函数的卷积，它也是积性的，可以用线性筛预处理出来，而答案即为时间复杂度O(N+T)#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=g

2016-12-12 15:42:47 309

原创 bzoj4237

按x排序，y分治然后单调栈随便搞一搞就行辣#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='

2016-12-12 10:37:03 275

原创 bzoj3295【CDQ分治】

答案在long long 范围内#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-

2016-12-11 19:22:07 556

原创 bzoj2716

mdzz数据范围看错了#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0

2016-12-11 17:43:39 4027

原创 bzoj2301

#include#include#include#include#includeusing namespace std;#define LL long long LL read(){ LL f=1,x=0; char ch=getchar(); for (;ch'9';ch=getchar()) f=ch=='-'?-1:1; for (;ch>

2016-12-10 16:10:41 236

原创 bzoj2440【线性筛】

#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0; for (;c>='0'&&c<

2016-12-10 15:45:45 243

原创 bzoj3529【线性筛】【莫比乌斯函数】【树状数组】

#include#include#include#include#includeusing namespace std;#define pii pair#define fi first#define se secondtypedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for

2016-12-10 10:36:37 269

原创 bzoj2154【莫比乌斯函数】【线性筛】

#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0; for (;c>='0'&&c<

2016-12-09 11:28:34 257

原创 bzoj4140共点圆加强版

#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0; for (;c

2016-12-09 10:37:29 492

原创 bzoj2961【cdq分治】

#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0; for (;c

2016-12-09 10:35:23 355

原创 bzoj2738【整体二分】

#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0; for (;c>='0'&&c<

2016-12-09 10:32:01 266

原创 bzoj2818【莫比乌斯函数】【线性筛】

#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0; for (;c>='0'&&c<

2016-12-08 19:36:55 320

原创 bzoj2190【线性筛】

好久以前做的题答案为#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int f=0,x=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0;

2016-12-08 17:47:42 264

原创 bzoj1951【CRT】【Lucas】

忘了讨论g=P的情况了qaq然后加上以后又忘了写return 0了qaq所以愉快地wa了几发#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for

2016-12-08 17:36:12 272

原创 bzoj3288【线性筛】【结论题】

首先答案就是phi(1)*phi(2)*phi(3)* *** * phi(n)，搜下题解打个表就能看出来然后直接线性筛就行了#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=

2016-12-08 11:53:07 302

原创 bzoj3122【同余方程】【BSGS】

#include#include#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9';c=getchar()) f=c=='-'?1:0;

2016-12-08 11:42:34 254

原创 bzoj1407

直接枚举山洞的数量，对每个值枚举点对解同余方程判断即可好久没写辣结果狂wa不止qaq#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar(); for (;c'9

2016-12-07 18:39:54 228

原创 bzoj3757【树上莫队】

好久之前的代码，现在题已经交不了辣#include#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int f=0,x=0;char c=getchar(); for (;c'9';c=getchar()) f=

2016-12-06 22:26:43 280

原创 bzoj2388【分块+凸包二分】

凸包写挂了调了好久qaq忘了凸包上的点的横坐标并不是等距的qaq首先分块，维护前缀和数组，每块维护一个凸包，那么每一块中的答案都在凸包上可以二分求出对于区间操作，实际上相当于在区间内加一个等差数列，区间以后加一个常数，而这是不改变凸包的，所以打个标记即可时间复杂度O(n*sqrt(n)*log n) 窝写的常数好大qaq#include#include#include#i

2016-12-05 12:05:54 679

原创 bzoj3673【主席树】

好久没写主席树啦虽然是可持久化并查集，但是直接用一个主席树维护一下father数组就好啦居然1A好开心#include#include#include#include#includeusing namespace std;typedef long long LL;inline int read(){ int x=0;bool f=0;char c=getchar();

2016-11-30 20:36:30 245

空空如也

空空如也