发表于

之前写的太丑了

可并堆插入的值和num是一直对应的
如果按顺序new_node
那么不管怎么修改，t[i].val=a[i]
主体：

1
2
3
4
5
6
7
8
9
struct node{
	int val,fa,ls,rs;
	inline node(int _val=0,int _fa=0,int _ls=0,int _rs=0)
	{
		val=_val;fa=_fa;ls=_ls;rs=_rs;
	}
};
node t[N];
int num;

初始化清空：

1
2
3
4
inline void clear()
{
	num=0;
}

加新点：

1
2
3
4
5
6
inline int new_node(int x)
{
	++num;
	t[num]=node(x);
	return num;
}

合并两个堆：

1
2
3
4
5
6
7
8
9
inline int merge(int x,int y)
{
	if(!x||!y)	return x+y;
	if((t[x].val>t[y].val)||((t[x].val==t[y].val)&&(x>y)))	swap(x,y);
	t[x].rs=merge(t[x].rs,y);
	t[t[x].rs].fa=x;
	swap(t[x].ls,t[x].rs);
	return x;
}

找所在的堆：

1
2
3
4
5
inline int get_fa(int x)
{
	while(t[x].fa)	x=t[x].fa;
	return x;
}

删除堆顶：

1
2
3
4
5
6
inline void pop(int x)//改成int，把merge的结果return就可以知道新的根
{
	t[x].val=0;
	t[t[x].ls].fa=t[t[x].rs].fa=0;
	merge(t[x].ls,t[x].rs);
}

发表于

设a,m是正整数
阶：
如果(a,m)=1，对于$a^n \equiv 1 (mod~{p})$的最小的n，叫做a模p的阶。（阶|ϕ(m)）
原根：
若a模m的阶等于ϕ(m)，则称a为模m的一个原根。

求阶：bsgs
求原根：（原根都不大，一般不超过50）
检查$a^{(m/pi)}=1(mod~p)$，pi是m的质因子（因为假如存在更小的阶，一定有模不为1的值）
复杂度$O(原根大小lognlogn+sqrt(n)（质因数分解）)$

发表于

杨氏矩阵是这样一个矩阵，满足条件：
(1)如果格子(i,j)没有元素，则它右边和上边的相邻格子也一定没有元素。
(2)如果格子(i,j)有元素a[i][j]，则它右边和上边的相邻格子要么没有元素，要么有元素且比a[i][j]大。
$F[1]=1,F[2]=2,F[n]=F[n-1]+(n-1)*F[n-2] (n>2)$

钩子公式：
对于给定形状，不同的杨氏矩阵的个数为：n!除以每个格子的钩子长度加1的积。其中钩子长度定义为该格子右边的格子数和它上边的格子数之和。

发表于

update:
dev编辑器选项中添加缩进到{}和:
老是不灵，干脆关掉。。

先安装最新版本dev
编译时加入以下命令：
-Wall -Wl,–stack=1000000000 -std=c++11（最后改成03编译！！）
-O2用于打表找规律

字体：Consolas
预设：Obsidian

取消代码补全、符号匹配

开始写模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
int main()
{
	return 0;
}

写完加入到缺省源

然后建文件夹

然后写生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
timeb tim;
mt19937 mt;
inline int ra()
{
	return mt()>>1;//mt()是unsigned int 
}
inline LL rall()
{
	return (1ll*ra()<<30)+ra();
}
int main()
{
	freopen("1.in","w",stdout);
   	ftime(&tim);
   	mt.seed(tim.time*1000+tim.millitm);
   	
	return 0;
}

然后写duipai.bat（和bf拍）和pai.bat（测极限数据的时间）

duipai.bat

1
2
3
4
5
6
7
8
9
10
@echo off 
:loop
sc.exe 
A.exe <1.in >my.out
bf.exe <1.in >1.out
fc 1.out my.out 
if errorlevel 1 pause
goto loop
pause 
end

pai.bat

1
2
3
4
5
6
7
@echo off 
:loop
sc.exe 
A.exe <1.in >my.out
goto loop
pause 
end

最后把东西复制到各个文件夹就行了
多余的时间打打ksm，add_ans,add_edge,(fx treap)

发表于

主席树的时间复杂度：O(nlogn)
主席树的空间复杂度：O(nlogn)（开2logn比较好）
主席树的插入要用引用！

主席树的主体：

1
2
3
4
5
6
int rt[N],tot;
struct president_tree{
	int ls,rs,sz;
	LL sum;
	/* more */
}tr[N*150];//能开多大开多大

主席树是动态开点权值线段树，注意上下界的设置（注意inf的设置和0/1的设置）
因为主席树是不支持修改的，所以一般都是一开始就把树建好
插入：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline void update(int &t,int l,int r,int val)
{
	tr[++tot]=tr[t];
	++tr[tot].sz;
	tr[tot].sum+=val;//先产生一个新点
	t=tot;//再赋值
	if(l==r)	return;
	int mid=l+(r-l)/2;//可能会爆int
	if(val<=mid)	update(tr[t].ls,l,mid,val);
	else	update(tr[t].rs,mid+1,r,val);
}
for(int i=1;i<=n;++i){
	rt[i]=rt[i-1];
	update(rt[i],1,inf,a[i]);
}

询问函数可以有返回值，也可以没有，而使用一个全局变量记录答案
注意：查询的时候要用ls或者rs的差！！
询问：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LL tmp;
inline void query(int t1,int t2,int l,int r,int num)
{
	if(!num)	return;
	if(tr[t2].sz-tr[t1].sz<=num){
		tmp+=tr[t2].sum-tr[t1].sum;
		return;
	}
	if(l==r){
		tmp+=1ll*num*l;
		return;
	}
	int mid=l+(r-l)/2,t=tr[tr[t2].rs].sz-tr[tr[t1].rs].sz;
	if(num<=t)	query(tr[t1].rs,tr[t2].rs,mid+1,r,num);
	else{
		tmp+=tr[tr[t2].rs].sum-tr[tr[t1].rs].sum;
		query(tr[t1].ls,tr[t2].ls,l,mid,num-t);
	}
}

清空主席树：

1
2
tot=0;
//rt[]和tr[]里的东西都会重新加

发表于

treap有点难写啊
fx treap好！（没有引用！）
那么常数大也没什么办法。。

fx treap的主体：

1
2
3
4
int rt,tot;
struct node{
	int ls,rs,val,pri,sz;
}fx[N];

（假如要写多颗平衡树，把这个东西封装一下就好了）
rt：这颗树的根的编号
tot：总点数（删除的点不会消失，只是它的编号不再被使用了）
ls：左孩子
rs：右孩子
val：关键码（平衡树存的值）
pri：随机的优先级比较值
sz：点数（相同的值并没有合并到一起）

加入一个新的点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int seed=233;
inline int ra()//可以不重复的生成1~INT_MAX-1的每一个数
{
	seed=48271ll*seed%INT_MAX;
	return seed;
}
inline int new_node(int x)
{
	++tot;
	fx[tot].sz=1;
	fx[tot].val=x;
	fx[tot].pri=ra();
	fx[tot].ls=fx[tot].rs=0;
	return tot;
}

更新节点的信息：（更改了树的结构的时候需要更新，fx treap需要在merge和split的时候更新）

1
2
3
4
5
inline void pushup(int x)
{
	fx[x].sz=fx[fx[x].ls].sz+fx[fx[x].rs].sz+1;
	/* more */
}

合并(merge)两颗fx，要求左边的fx的每个点的关键码小于右边的fx的每个点的关键码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline int merge(int x,int y)
{
	if(!x||!y)	return x+y;
	if(fx[x].pri<fx[y].pri){
		fx[x].rs=merge(fx[x].rs,y);
		pushup(x);
		return x;
	}
	else{
		fx[y].ls=merge(x,fx[y].ls);
		pushup(y);
		return y;
	}
}

分裂(split)一颗fx，可以按值分裂，也可以按排名分裂，这里将键值<=x的分成左树，其余分成右树
split操作会得到两个值，rt_l表示左树的根的编号，rt_r表示右树的根的编号（这样写没有返回值，注意这两个值的变化，要即时的把值存下来，每次split之后他们的值就变了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int rt_l,rt_r;
inline void split(int rt,int x)
{
	if(!rt){
		rt_l=rt_r=0;
		return;
	}
	if(fx[rt].val>x){
		split(fx[rt].ls,x);
		fx[rt].ls=rt_r;
		rt_r=rt;
	}
	else{
		split(fx[rt].rs,x);
		fx[rt].rs=rt_l;
		rt_l=rt;
	}
	pushup(rt);
}

拥有了merge和split的fx treap，仍然拥有treap的一切性质，仍然可以使用treap的一切函数
fx treap独特之处在于，它抛弃了旋转操作，那么treap的insert和delete就不适用于fx treap了（只有这两个操作是需要zag和zig的）
插入：

1
2
3
4
5
inline void inser(int x)
{
	split(rt,x);
	rt=merge(merge(rt_l,new_node(x)),rt_r);
}

删除：

1
2
3
4
5
6
7
inline void delet(int x)
{
	split(rt,x);
	int tmp=rt_r;
	split(rt_l,x-1);
	rt=merge(merge(rt_l,merge(fx[rt_r].ls,fx[rt_r].rs)),tmp);
}

短小精悍，那么其他操作也可以考虑用fx特有的merge和split来完成（常数大）
求键值为x的最小排名（相同的不算）：

1
2
3
4
5
6
7
inline int rank(int x)//rank在c++11中是关键字
{
	split(rt,x-1);
	int ans=fx[rt_l].sz+1;
	rt=merge(rt_l,rt_r);
	return ans;	
}

求排名第k的键值：//并不能优化这个过程。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline int kth(int rt,int k)
{
	if(k>fx[rt].sz)	return -1;
	while(1){
		if(k==fx[fx[rt].ls].sz+1)	return rt;
		if(k<=fx[fx[rt].ls].sz){
			rt=fx[rt].ls;
		}
		else{
			k-=fx[fx[rt].ls].sz+1;
			rt=fx[rt].rs;
		}
	}
}

求前驱后继：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
inline int get_pre(int x)
{
	int ans;
	split(rt,x-1);
	if(!rt_l){
		ans=-INT_MAX;
	}
	else{
		ans=fx[kth(rt_l,fx[rt_l].sz)].val;
	}
	rt=merge(rt_l,rt_r);
	return ans;
}
inline int get_nxt(int x)
{
	int ans;
	split(rt,x);
	if(!rt_r){
		ans=INT_MAX;
	}
	else{
		ans=fx[kth(rt_r,1)].val;
	}
	rt=merge(rt_l,rt_r);
	return ans;
}

清空：

1
rt=tot=0;

发表于

18-10-23学校模拟赛
orz djq
第一题
101是4位循环的
因为9999是101的倍数
10000=1(mod 101)
满足gcd(x,10)=1的数都有这样的循环
因为10^phi(x)=1(mod x)
最小的循环要枚举phi(x)的因数
求phi(x)是根号的（直接暴力从2到sqrt，每个地方都不停的除即可

本题dp[i][j][p][q]表示区间[i,j]内模101为p位数模4为q的子序列个数
注意初始情况，长度为1和有两个相同的为1
转移要小小的容斥一下
dp[i][j][p][q]+=dp[i+1][j][p][q]+dp[i][j-1][p][q]-dp[i+1][j-1][p][q]
还是有点弱啊（初始情况和转移容斥）

第二题
不考虑是x的多少倍
只考虑它是x的倍数
那就按模x的值来搞
连边变成01bfs

01bfs暑假zr讲了啊（可是我没听啊
连0的边就加到队头
连1的边就加到队尾
队列时刻都不会超过2种值（x和x+1或者只有x）
每个点最多入队两次（先1再0的情况）
且永远是用最小值先来更新
可以不用记录出现最小值的vis数组（类似dijk的vis）

第三题
维护树上并查集
不知道为什么80.。
LL写成int
把变量改成LL以后要查全文！！

发表于

求割边求错了QWQ
写一篇跟tarjan有关的总结

有向图：
求强连通分量：重边、自环都不影响求解，记录fa，要写栈
求割边：未定义割边，要根据题目转化成无向图做（可能吧）
求割点：未定义割点，要根据题目转化成无向图做（可能吧）

无向图：
求割边：自环无影响，重边有影响，要记录是从哪条边来的，而不是记录fa，不要写栈
dfn[x]<low[x]，所以不能用fa更新
求割点：自环、重边无影响，不用记录fa，不要写栈。注意根节点。
dfn[x]<=low[x]，所以可以用fa更新

发表于

在树上找k条点不相交的路径使得权值和最大（一个点算一条退化的路径）
不能只用0/1表示（0表示不能往上，1表示能往上），有坑，合并的时候不知道上面的0有没有算一条路径！！

用0/1/2写，将0/1/2的max存到0中，这是错的，调用0的时候会挂（数据弱拿了50/60）
中途瞎改改对了。。（把t[1][0]赋初值-inf而不是0，选一个单点的情况认为向孩子连了2条边）（但是并没有迅速调对是因为前面把0/1/2全部取max并到0了，题解误导啊！）
$f[x][j][0/1/2]$表示在x及其子树中选了j条路径，x向它的孩子连出0/1/2条边，e[i].f是边权
y是x的一个孩子，$t[j][0/1/2]$表示当前合并的子树
$f[][][]=-inf,f[x][0][0]=f[x][1][1]=f[x][1][2]=0$
$t[][]=-inf,t[0][0]=t[1][1]=t[1][2]=0$
$t[j][0]=max(t[j][0],f[x][j-p][0]+max(f[y][p][0],f[y][p][1],f[y][p][2]))$
$t[j][1]=max(t[j][1],f[x][j-p][1]+max(f[y][p][0],f[y][p][1],f[y][p][2]),f[x][j-p][0]+f[y][p][1]+e[i].f)$
$t[j][2]=max(t[j][2],f[x][j-p][2]+max(f[y][p][0],f[y][p][1],f[y][p][2]),f[x][j-p][1]+f[y][p][1]+e[i].f)$

嘤嘤嘤嘤这题不太一样
不要求路径个数
所以只需要0/1表示跟有没有选
可以通过sum巧妙的转移到1
而确定路径数量的就不好这么做（不能控制sum选了多少，可能还需要一个背包）