JU's Blog

计算几何

计算几何注意一定要好好注意两向量的旋转方向的判断!! 比如判断点与向量,向量与向量的位置/旋转关系要特别注意叉积是大于还是小于 $0$ . 向量数量积也叫点积/内积. 几何意义为一个向量在另一个向量上的投影再乘上第二个向量的模长. (通过几何意义可以比较方便地求一些东西,比如最小矩形覆盖的左右边界啥的) $\vec{a}\cdot\vec{b}=|\vec{a}||...

Posted by JU on May 21, 2019

APIO2019酱油记

Day -3 & -2 看完了进击的巨人(三季)… Day -1 到了 $BJ$ . 惊喜地发现忘带充电器,于是决定合理分配使用电脑的时间(一天 $20\%$). 可能是水土不服,不太舒服.. Day 1&2 几乎都在酒店放松(打游戏-用老王的机器),听了一次讲课, $Paging \& Caching$ ,不怎么听得懂. Day 3 考得十分菜,暴...

Posted by JU on May 21, 2019

GDSOI酱油记

Day 1 先看完全部题,惊喜地发现——一题都不会. $T1$ :送分大水题.成功送了我 $10$ 分. $T2$ :大概是花时间最久的,获得高达 $0$ 分. $T3/T4$ :暴力. 期望: $10+(0\sim40)+10+10=30\sim70$ 实际: $10+0+10+10=30$ %Ghastlcon $100$ %sc $340$ 进队稳了. Day 2 ...

Posted by JU on May 6, 2019

多项式部分总结

感觉并无何用

多项式部分总结 $FFT$ struct cp { db real,imag; cp (db x=0,db y=0) { real=x,imag=y; } }; cp operator + (cp A,cp B) { return cp(A.real+B.real,A.imag+B.imag); } cp operator - (cp A,cp B) { return c...

Posted by JU on April 15, 2019

SAM

SAM $\text{SAM}$ 是一个十分 $\text{bdd}$ 的数据结构,然鹅我并不能对它下一个清晰(且我能看懂)的定义…… 状态每个点记录了一个原串的子串集合: $\text{1.}$ 子串出现的末尾位置集合相同. $\text{2.}$ 子串是某些前缀的连续后缀,即长度为一个连续的区间. $\text{3.}$ 集合中所有串都是(集合中)最长串的后缀. ...

Posted by JU on April 8, 2019

(ex)BSGS

BSGS $\text{BSGS}$ 用于解决形如 \[a^k\equiv b\pmod p,\gcd(a,p)=1\] 的求指数(最小)的问题. 方法十分简单: 设 \[m=\lceil\sqrt{p}\rceil\] 则 \[k=xm-y\] 移项 \[a^{xm}\equiv b\cdot a^y \pmod p\] 首先枚举 $y$ ,将 $s=b\cdot a...

Posted by JU on April 4, 2019

201904

smoj520 P1 $\text{yy}$ 一下可以发现,最优策略肯定是: $\text{1.}$ 在一个区间反复横跳 $\text{2.}$ 向右换一个区间 $\text{3.}$ 重复 $\text{1,2}$ 因为切换区间时经过的权值和肯定是负的,所以如果不按上述策略,则会导致重复经过这些负的区间. 于是 $\text{dp}$ : $sum$ :区间权值和 $s...

Posted by JU on April 2, 2019

杜教筛

YEs

一些函数 \[\epsilon(n)=[n=1],I(n)=1,id(n)=n\] \[\mu * I = \epsilon\] \[\varphi*I=id\] \[\mu*id=\varphi\] \[\sum_{d|n}\mu(d)=[n==1]\] \[\sum_{d|n}\varphi(d)=n\] \[\varphi(n^2)=n\varphi(n)\] 杜教筛 ...

Posted by JU on November 21, 2018

NOIp2018游记

凉凉

NOIp2018 第一次考tg。。 Day0 lgj给了套模拟信心赛，然后凉凉（150）。感觉有点方。。和苏畅（大佬）分在同一间房，我们没人带手机。。（两台电脑） lgj查房后，纠结了一下闹钟问题，决定不管了，睡。 Day1 早餐诡异三明治，感觉不太对劲。 7:50到二中门口，苏畅：“对了，你准考证带了没有” 转头就跑。遇到lpq&ozq，lpq：“肯定是忘带准考证，我去年就是...

Posted by JU on November 13, 2018

对拍

duipai.bat 由于较简短，需加文件读写以pair举例 @echo off :loop rand.exe pairforce.exe pair.exe fc pair.out pairforce.out if not errorlevel 1 goto loop pause goto loop

Posted by JU on September 3, 2018

FFT

装13神器

LuoguP3803 #pragma GCC optimize("Ofast,no-stack-protector") #include <bits/stdc++.h> #define pr(p) printf("%d ",p) const int oo=2139063143; const int N=3010000; const int mod=1000000007; usi...

Posted by JU on August 19, 2018

概率与期望

再%lzh

概率在oi当中一般只需要用到离散变量的概率。条件概率定义：设$E$为一试验，$A$和$B$为$E$中两事件，且$P(A)>0$ 则称$P(AB)/P(A)$为事件$A$发生的条件下事件$B$发生的条件概率记作$P(B|A)$，即$P(B|A)= P(AB)/P(A)$ 独立事件对于两个事件A和B，如果他们发生的情况相对独立即$P(AB)=P(A)P(B)$,则为相互独立事...

Posted by JU on August 16, 2018

ExGCD

%%lzh

概念对于不完全为0的非负整数$a,b$，必然存在整数对$x,y$，使得$gcd(a,b)=ax+by$。代码 typedef long long LL; LL ans; LL exgcd (LL a,LL b,LL &x,LL &y) { if (!b) { x=1,y=0; return a; } LL t=exgcd (b,a%b,y,x); ...

Posted by JU on August 16, 2018

整体二分&CDQ分治

我永远喜欢LZZ

整体二分概念对于一个问题，若单个询问能用二分快速解决，那么对于离线的多个询问，可以考虑使用整体二分。整体二分二分的是答案。 HDU5412 #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath>...

Posted by JU on August 13, 2018

树分治

抽象

LuoguP3806 #include <bits/stdc++.h> #define pr(p) printf("%d\n",p) const int oo=2139063143; const int N=100010; const int mod=1000000007; using namespace std; typedef long long LL; inline vo...

Posted by JU on August 7, 2018

LCT

花里胡哨的操作

Luogu3203 #include <bits/stdc++.h> #define pr(p) printf("%d\n",p) const int oo=2139063143; const int N=1010000; const int mod=1000000007; using namespace std; typedef long long LL; typedef d...

Posted by JU on August 7, 2018

可持久化

变简单了？！

可持久化线段树话说线段树大家应该都听说过，然而加上了“可持久化”四个大字后有什么区别呢？？概念我们知道，每次单点修改，都需要更新约logn个线段树上的节点。而可持久化线段树与普通线段树最大的区别在于，每次要修改一个数据时，不在原线段树上修改，而是在受到影响的节点“旁边”新建一个节点，上面记录新的数据。而这些新建的节点与不受影响的节点，构成了一个历史版本。同时，不再使用普通线段...

Posted by JU on August 6, 2018

树链剖分

码力不足

bzoj1036 #include <bits/stdc++.h> #define sc(p) scanf("%d",&p) #define sc2(p1,p2) sc(p1),sc(p2) #define pr(p) printf("%d\n",p) const int oo=2147483640; const int N=1010000; using namespac...

Posted by JU on July 24, 2018

二分图匹配

先求个最大匹配再说

Luogu3386 #include <bits/stdc++.h> #define pr(p) printf("%d\n",p) const int oo=2139063143; const int N=500100; const int mod=1000000007; using namespace std; typedef long long LL; typedef do...

Posted by JU on July 24, 2018

莫比乌斯反演

一脸懵13

LouguP1829 #include <bits/stdc++.h> #define sc(p) scanf("%lld",&p) #define pr(p) printf("%lld\n",p) const int N=10100000; const int mod=20101009; using namespace std; long long miu[N],pr...

Posted by JU on July 24, 2018

Dinic

悲剧的POJ

当前弧优化 Luogu2774 #include <bits/stdc++.h> #define pr(p) printf("%d\n",p) const int oo=2139063143; const int N=1010000; const int mod=1000000007; using namespace std; typedef long long LL; typ...

Posted by JU on July 23, 2018

线性筛和欧拉函数

伟大的欧拉

程序 #include <bits/stdc++.h> #define sc(p) scanf("%d",&p) const int N=10000100; using namespace std; int phi[N],prime[N]; bool vis[N]; void init (int gd) { phi[1]=1; for (int i=2;...

Posted by JU on July 21, 2018

斜率优化

只凸不凹

注意在将分母乘到另一边去的时候，注意正负性，尽量保证分母为正。 Luogu4072 \[a=\frac {\sum_{i=1}^{m}v_i}{m}\] \[s^{2}=\frac {\sum_{i=1}^{m}(a-v_i)^2}{m}\] \[=\frac {\sum_{i=1}^{m}(a^2-2av_i+v_i^2)}{m}\] \[=\frac{m·a^2-2a·\su...

Posted by JU on July 20, 2018

后缀数组

莫名其妙

POJ2774 #include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <cstring> #define pr(p) printf("%d\n",p) const int oo=2147483640; const int...

Posted by JU on July 19, 2018

高斯消元

这是什么“玩意”

Luogu2455（普通方程） #include <bits/stdc++.h> #define pr(p) printf("%d\n",p) const int oo=2139063143; const int N=210; const int mod=1000000007; using namespace std; typedef long long LL; typedef...

Posted by JU on July 17, 2018

树状数组

区间问题

树状数组区间修改&查询 #include <bits/stdc++.h> using namespace std; #define sc(p) scanf("%d",&p) #define pr(p) printf("%d",p) const int N=100100; const int oo=0x7FFFFFFF; int bit1[N],bit2[N]; ...

Posted by JU on May 27, 2018

Splay

在作为储存数据集合的数据结构时,插入后要splay一下,否则会TLE void ins (int x)//!!!!!!!!!!!! { int p=rt; if (!p) { rt=add (x,0); return ; } while (son(p)[x> w(p)]) p=son(p)[x> w(p)]; son(p)[x> w(p)]=add (x,p); ...

Posted by JU on May 22, 2018

Trie&AC自动机应用

字符串处理

luoguP3808 #include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include...

Posted by JU on May 15, 2018

Welcome to my Blog

"Hello World, Hello Blog"

I have nothing to say…

Posted by JU on May 13, 2018

Manacher

Manacher Step 1 为了使对称轴不会形成在两个字符之间，在每两个字符之间插入一个#。 Step 2 记目前右端距离开头最远的回文串。该串：dic（其实没啥用）该串的对称轴：pos。串的最右端：right。第i个字符为对称轴的最长回文子串长度：p[i]。 Step 3 枚举到对称轴i，有两种情况： 1.i>=right，不能从之前的信息中得到有用东西，p[i]=1。 ...

Posted by JU on May 13, 2018

莫队

区间问题

莫队，乃离线处理区间询问(修改)，(可能是)万能的算法。仅查询例题：洛谷P2709 很明显，若已经求出了[L,R]区间中，每个数出现的次数(c[])，那么就可以用O(1)的时间转移到｛[L-1,R]/[L+1,R]/[L,R-1]/[L,R+1]｝这些区间，并求出这些区间的答案与c[]。然后，也可以用这种近乎暴力的方式转移到下一个区间，并一个一个地求出所有答案。然而，这与暴力实际上没...

Posted by JU on May 13, 2018

Miller Rabin

大质数判定

要判定一个数是不是质数，最妇孺皆知的方法莫过于O（sqrt(n)）的方法了（相信大家看见时间复杂度已经知道方法了……）。然而还有基于随机的算法：费马小定理首先要知道的是费马小定理：当p是质数时，a^(p-1)≡1(mod p)　(gcd(a,p)=1) 运用实际上呢，这条东东可以写成：a^(p-1)%p=1 不幸的是，当上面成立时，p并不一定是质数…… 然而，令人欣慰的是，如果上面不...

Posted by JU on May 13, 2018

KMP

字符串匹配

Luogu3375 #include <bits/stdc++.h> #define pr(p) printf("%d\n",p) const int oo=2139063143; const int N=1010000; const int mod=1000000007; using namespace std; typedef long long LL; inline vo...

Posted by JU on May 13, 2018

计算几何

APIO2019酱油记

GDSOI酱油记

多项式部分总结

感觉并无何用

SAM

(ex)BSGS

201904

杜教筛

YEs

NOIp2018游记

凉凉

对拍

FFT

装13神器

概率与期望

再%lzh

ExGCD

%%lzh

整体二分&CDQ分治

我永远喜欢LZZ

树分治

抽象

LCT

花里胡哨的操作

可持久化

变简单了？！

树链剖分

码力不足

二分图匹配

先求个最大匹配再说

莫比乌斯反演

一脸懵13

Dinic

悲剧的POJ

线性筛和欧拉函数

伟大的欧拉

斜率优化

只凸不凹

后缀数组

莫名其妙

高斯消元

这是什么“玩意”

树状数组

区间问题

Splay

Trie&AC自动机应用

字符串处理

Welcome to my Blog

"Hello World, Hello Blog"

Manacher

莫队

区间问题

Miller Rabin

大质数判定

KMP

字符串匹配

ABOUT ME

FRIENDS