避风港

数据类型	范围
tinyint	1个字节的整数
smallint	2个字节的整数
mediumuint	3个字节的整数
int	4个字节的整数
bigint	8个字节的整数
float	4个字节的浮点数
double	8个字节的浮点数
decimal	字符串浮点数(金融计算)

数据类型	范围
char	固定长度字符串(0 ~ 255)
varchar	可变长字符串(0 ~ 65535)
tinytext	微型文本 (0 ~ 2^8 - 1)
text	大文本(0 ~ 2^16 - 1)

数据类型	范围
date	YYYY - MM - DD 日期
time	hh : mm : ss 时间
datetime	YYYY - MM - DD hh : mm : ss 日期+时间
timestamp	时间戳 1970.1.1到现在的毫秒数
year	年份

SQL操作数据库

发表于 2021-09-14 分类于 MySQL

1、创建数据库

1	CREATE DATABASE [IF NOT EXISTS] XXX

2、删除数据库

1	DROP DATABASE [IF EXISTS] XXX

3、切换数据库

1 2	USE XXX --如果字段名是特殊字符，需要用`XXX`

4、查看所有数据库

1	SHOW DATABASE

一、创建数据库

CREATE DATABASE xxx CHARACTER SET utf8 COLLATE utf8_general_ci;

二、创建表

三、命令行操作

mysql -u root -p  --连接数据库
show databases; --查看所有数据库
use xxx --切换数据库
show tables； --查看所有表
describe xxx; --显示表中所有信息
create database xxx; --创建数据库
exit; --连接退出
--单行注释
/* 多行注释 */

四、语言概念

DDL 数据库定义语言

DML 数据库操作语言

DQL 数据库查询语言

DCL 数据库控制语言

DAG图上的灭绝树

例题P2597

难点：DAG图上求LCA

其思路是：给每个数多维护一个值dad,用来表示如果此时它要被连入灭绝树中，它应该是哪个点的儿子。一开始将dad清为-1，将开始入度为0的点 pi的dad设为0（太阳）。在拓扑排序取出一个点i的时候连接边 dad[i]->i(此时i的父亲（根节点的父亲前面已经确定）都已经被处理过了，所以dad[i]已经确定（怎么确定的马上会说））。然后更新点i相对应的深度和倍增数组（因为i的祖先们已经在i之前被确定，所以此时的深度和其倍增数组可以唯一确定），接着遍历i的儿子们，如果它的儿子p的父亲dad[p]为0，说明它的父亲还没有被更新过，此时把dad[p]更新为i。否则就将dad[p]更新为LCA（dad[p],i）。这样，在遍历到p的时候它的父节点就被确定下来了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int in[100010];
vector<int>v1[100010];
vector<int>v2[100010];
int f[100010][30], d[100010];
int sz[100010];
queue<int>q;
int t;
int lca(int x, int y) {
	if (d[x] > d[y])swap(x, y);
	for (int i = t; i >= 0; i--) {
		if (f[y][i] == -1)continue;
		if (d[f[y][i]] >= d[x])y = f[y][i];
	}
	if (x == y)return x;
	for (int i = t; i >= 0; i--) {
		if (f[x][i] == -1 || f[y][i] == -1)continue;
		if (f[x][i] != f[y][i])x = f[x][i], y = f[y][i];
	}
	return f[x][0];
}
void bfs() {
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = 0; i < v1[x].size(); i++) {
			int k = v1[x][i];
			in[k]--;
			if (f[k][0] == -1)f[k][0] = x;
			else f[k][0] = lca(f[k][0], x);
			d[k] = d[f[k][0]] + 1;
			for (int j = 1; j <= t; j++)f[k][j] = f[f[k][j - 1]][j - 1];
			if (!in[k]) {
				q.push(k);
				v2[f[k][0]].push_back(k);
			}
		}
	}
}
void dfs(int x) {
	sz[x] = 1;
	for (int i = 0; i < v2[x].size(); i++) {
		dfs(v2[x][i]);
		sz[x] += sz[v2[x][i]];
	}
}
signed main() {
	ios::sync_with_stdio(false);
	memset(f, -1, sizeof(f));
	cin >> n;
	t = log(n + 1) / log(2) + 1;
	for (int i = 1; i <= n; i++) {
		while (1) {
			int k;
			cin >> k;
			if (!k)break;
			v1[k].push_back(i);
			in[i]++;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!in[i]) {
			d[i] = 1;
			f[i][0] = 0;
			q.push(i);
			v2[0].push_back(i);
		}
	}
	bfs();
	dfs(0);
	for (int i = 1; i <= n; i++) {
		cout << sz[i] - 1 << endl;
	}
	return 0;
}

一般图最大匹配(带花树)模板

发表于 2021-09-09 分类于图论

一般图最大匹配(带花树)模板

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int T,n,m,e,cnt,tot,ans,hd[N],p[N],match[N],pre[N],vst[N],dfn[N];
queue<int>q;
struct edge{int t,nxt;}es[N*N];
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
inline void read(register int&x){
    x=0;int s=gc();
    while(!isdigit(s))s=gc();
    while(isdigit(s))x=(x<<3)+(x<<1)+s-'0',s=gc();
}
void print(register int x){
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
inline void Add(register int u,register int v){es[++tot]=(edge){v,hd[u]};hd[u]=tot;}
inline void add(register int u,register int v){Add(u,v),Add(v,u);}
int find(register int x){return x==p[x]?x:p[x]=find(p[x]);}
inline int lca(register int u,register int v){
	for(++cnt,u=find(u),v=find(v);dfn[u]!=cnt;){
		dfn[u]=cnt;
		u=find(pre[match[u]]);
		if(v)swap(u,v);
	}
	return u;
}
inline void blossom(register int x,register int y,register int w){
	while(find(x)!=w){
		pre[x]=y,y=match[x];
		if(vst[y]==2)vst[y]=1,q.push(y);
		if(find(x)==x)p[x]=w;
		if(find(y)==y)p[y]=w;
		x=pre[y];
	} 
} 
inline int aug(register int s){
	if((ans+1)*2>n)return 0;
	for(register int i=1;i<=n;++i)p[i]=i,vst[i]=pre[i]=0;
	while(!q.empty())q.pop();
	for(q.push(s),vst[s]=1;!q.empty();q.pop()) 
		for(register int u(q.front()),i(hd[u]),v,w;i;i=es[i].nxt){
			if(find(u)==find(v=es[i].t)||vst[v]==2)continue;
			if(!vst[v]){
				vst[v]=2;pre[v]=u;
				if(!match[v]){
					for(register int x=v,lst;x;x=lst)lst=match[pre[x]],match[x]=pre[x],match[pre[x]]=x;
					return 1;
				}
				vst[match[v]]=1,q.push(match[v]);
			}else blossom(u,v,w=lca(u,v)),blossom(v,u,w);
		}
	return 0;
}
int main(){
	read(n),read(m);
	for(register int i=1,u,v;i<=m;i++)read(u),read(v),add(u,v),add(v,u);
	for(register int i=n;i;--i)if(!match[i])ans+=aug(i);
	print(ans),putchar('\n');
	for(register int i=1;i<=n;i++)print(match[i]),putchar(' ');
	return 0;
}

复杂度同匈牙利算法，常数略大。

虚树

发表于 2021-09-09 分类于图论

虚树

什么是虚树

虚树常常被使用在树形dp中，就比如这题。当一次询问仅仅涉及到整颗树中少量结点时，为每次询问都对整棵树进行dp在时间上是不可接受的。此时，我们建立一颗仅仅包含部分关键结点的虚树，将非关键点构成的链简化成边或是剪去，在虚树上进行dp。

虚树包含所有的询问点及它们之间的LCA。显然虚树的叶子节点必然是询问点，因此对于某次含有k个点的询问，虚树最多有K个叶子结点，从而整颗虚树最多只有2k-1个结点（这会在虚树变成二叉树形态时达到）。

建立虚树之前

我们需要：

预处理出原树的dfs序以及dp可能用到的一些其他东西。

高效的在线LCA算法，单次询问O(logn)的倍增和树剖，O(1)的RMQ−ST皆可。

将询问点按dfs序排序。

如何建立虚树

最右链是虚树构建的一条分界线，表明其左侧部分的虚树已经完成构建。我们使用栈stak来维护所谓的最右链，top为栈顶位置。值得注意的是，最右链上的边并没有被加入虚树，这是因为在接下来的过程中随时会有某个lca插到最右链中。

初始无条件将第一个询问点加入栈stak中。

将接下来的所有询问点顺次加入，假设该询问点为now，lc为该点和栈顶点的最近公共祖先即lc=lca(stak[top],now)。

由于lc是stak[top]的祖先，lc必然在我们维护的最右链上。

考虑lc和stak[top]及栈中第二个元素stak[top-1]的关系。

情况一

lc = stak[top]，也就是说，now在stak[top]的子树中

这时候，我们只需把now入栈，即把它加到最右链的末端即可。

情况二

lc在stak[top]和stak[top-1]之间。

显然，此时最右链的末端从stak[top-1]->stak[top]变成了stak[top-1]->lc->stak[top]，我们需要做的，首先是把边lc-stak[top]加入虚树，然后，把stak[top]出栈，把lc和now入栈。

情况三

lc=stak[top−1]。

这种情况和第二种情况大同小异，唯一的区别就是lc不用入栈了。

情况四

此时有dep[lc]<dep[stak[top-1]]。lc已经不在stak[top-1]的子树中了，甚至也未必在stak[top-2],stak[top-3]……的子树中。

以图中为例，最右链从stak[top-3]->stak[top-2]->stak[top-1]->stak[top]变成了stak[top-3]->lc->now。我们需要循环依次将最右链的末端剪下，将被剪下的边加入虚树，直到不再是情况四。

就上图而言，循环会持续两轮，将stak[top],stak[top-1]依次出栈，并且把边stak[top-1]-stak[top],stak[top-2]-stak[top-1]加入虚树中。随后通过情况二完成构建。

当最后一个询问点加入之后，再将最右链加入虚树，即可完成构建。

另一种虚树构建方法：欧拉序

什么是欧拉序

正常的dfs序仅在入栈的时候计算一次，而欧拉序，不仅在入栈的时候计算一次，还在出栈的时候计算一次，也就是说一个点有两次出现机会压栈为+，弹栈为-，欧拉序记录了dfs的全部信息，只要有了这个树的欧拉序，就算没有树，给我们一个栈，照样可以在树上跑dfs。

我们发现，抽出来的那只树，它的欧拉序大小关系和原来的树的欧拉序是一样的，所以只需要把所有点的复制一个弹出点，然后把压栈点和弹栈点按原来树上的欧拉序排一波序，就是新树中的点按欧拉序排序的结果，然后欧拉序我们有了，直接不建树跑dfs即可

2020CCPC威海站

发表于 2021-09-09 分类于补题

2020CCPC威海站

A	B	C	D	E	F
⚫	▲	⚫	⚫
思维	BFS	图上计数	数学	概率DP	？

G	H	I	J	K	L
▲	⚫		△		⚫
哈希+线段树	差分（线段树）	？	博弈论+计数	？	数学+背包

B Labyrinth

题目大意：

一个n*m的矩阵，其中有一些不能走的黑洞。询问q次，每次给起点终点，问最短距离。

做法：

1.如果起点终点之间没有黑洞，那么最短距离就是两点的曼哈顿距离。

2.如果起点终点之间有黑洞，那么最短距离一定经过某个黑洞四周的一个点。

因为黑洞最多只有42个，所以首先预处理出每个黑洞四周的每个点到任一点的最短距离。

处理询问时，只需要枚举这些点，答案就是这个点到起点距离+这个点到终点距离。

代码：

#include<bits/stdc++.h>
using namespace std;
int dis[210][200010];
int dis_pos[210];
int bk[45];
int c[200010];
int xp[4] = { 0, 0, -1, 1 }, yp[4] = { -1, 1, 0 , 0 };
int n, m, k, q;
int tot = 0;
int pos(int x, int y) {
	return (x - 1) * m + y;
}
pair<int, int> apos(int p) {
	return make_pair((p - 1) / m + 1, (p - 1) % m + 1);
}
int check(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= m)return 1;
	return 0;
}
int mp[200010];
void bfs(int num, int x, int y) {
	c[pos(x, y)] = 1;
	queue<int>q;
	dis[num][pos(x, y)] = 0;
	q.push(pos(x, y));
	while (!q.empty()) {
		int top1 = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			auto p = apos(top1);
			p.first += xp[i], p.second += yp[i];
			if (!check(p.first, p.second))continue;
			if (c[pos(p.first, p.second)])continue;
			if (mp[pos(p.first, p.second)])continue;
			c[pos(p.first, p.second)] = 1;
			dis[num][pos(p.first, p.second)] = dis[num][top1] + 1;
			q.push(pos(p.first, p.second));
		}
	}
}
signed main() {
	memset(dis, -1, sizeof(dis));
	scanf("%d%d%d%d", &n, &m, &k, &q);
	for (int i = 1; i <= k; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		bk[i] = pos(x, y);
		mp[pos(x, y)] = 1;
	}
	for (int i = 1; i <= k; i++) {
		int x = apos(bk[i]).first, y = apos(bk[i]).second;
		for (int j = 0; j < 4; j++) {
			int xn = x + xp[j], yn = y + yp[j];
			if (!check(xn, yn))continue;
			if (mp[pos(xn, yn)])continue;
			dis_pos[++tot] = pos(xn, yn);
			memset(c, 0, sizeof(c));
			bfs(tot, xn, yn);
		}
	}
	while (q--) {
		int xl, yl, xr, yr;
		scanf("%d%d%d%d", &xl, &yl, &xr, &yr);
		if (mp[pos(xl, yl)] || mp[pos(xr, yr)]) {
			printf("-1\n");
			continue;
		}
		int ff = 0;
		for (int i = 1; i <= k; i++) {
			auto p = apos(bk[i]);
			if (p.first >= min(xl, xr) && p.first <= max(xl, xr) && p.second >= min(yl, yr) && p.second <= max(yl, yr)) {
				ff = 1;
				break;
			}
		}
		if (!ff) {
			printf("%d\n", abs(xl - xr) + abs(yl - yr));
			continue;
		}
		int mmin = 1e9;
		for (int i = 1; i <= tot; i++) {
			if (dis[i][pos(xl, yl)] == -1 || dis[i][pos(xr, yr)] == -1)continue;
			mmin = min(mmin, dis[i][pos(xl, yl)] + dis[i][pos(xr, yr)]);
		}
		if (mmin == 1e9)printf("-1\n");
		else printf("%d\n", mmin);
	}
	return 0;
}

字节流中文乱码处理(转换流)

发表于 2020-06-17 更新于 2021-09-12 分类于 Java ， I/O

转换流

public void LuanMa(){
    FileOutputStream fos = new FileOutputStream("X:\\xxx.xxx");
    //BufferedOutputStream bos = new BufferedOutputStream(fos);//缓冲流自动处理乱码
    OutputStreamWriter osw = new OutputStreamWriter(fos,"UTF-8");//UTF-8,GBK等
    //fos.write("hello 中国".getBytes());//产生乱码
    osw.write("hello 中国");
    //bos.close();
    osw.close();
    fos.close();
}

字符流

发表于 2020-06-17 更新于 2021-09-12 分类于 Java ， I/O

与字节流

什么时候用字节流：用来读取图片、视频、音频等等。(字节流可以处理任何文件)

什么时候用字符流：便于读取纯文本。(但字符流底层仍是字节流)

字符输入流

public void readFile() throws Exception{
    //建立字符输入流
    FileReader fr = new FileReader("X:\\xxx.xxx");//类似FileInputStream
    char[] car = new char[1024];
    int len = 0;//返回字符数组中字符数
    while((len=fr.read(car))!=-1){
        System.out.println(new String(car,0,len));
    }
    //关闭流
    fr.close();
}

缓冲输入字符流

public void readFile() throws Exception{
    //建立字符输入流
    FileReader fr = new FileReader("X:\\xxx.xxx");//类似FileInputStream
    BufferedReader br = new BufferedReader(fr);//逐行读取
    String line = null;
    while((line=br.readLine())!=null){
        System.out.println(line);
    }
    //关闭流
    br.close();
    fr.close();
}

字符输出流

public void writeToFile() throws Exception{
    //建立字符输出流
    FileWriter fw = new FileWriter("X:\\xxx.xxx");
    //fw.write("kkkooo");//默认从开头覆盖
    fw.write("oookkk",true);//true从文件末尾，false从文件开头
    fw.close();
}

缓冲输出字符流

piblic void writeToFileFast() throws Exception{
    FileWriter fw = new FileWriter("X:\\xxx.xxx");
    BufferedWriter bw = new BufferedWriter(fw);
    bw.write("kkkooo");
    bw.newLine();//各操作系统通用换行方法
    bw.close();
    fw.close();
}

对象流改造集合

发表于 2020-06-17 更新于 2021-09-12 分类于 Java ， I/O

HashMap与对象流组合应用(主函数部分实现)

public static void main(String[] args) throws Exception{
    //用File可判断文件是否为空，否则出现异常
    File file = new File("X:\\xxx.xxx");
    long len = file.length();
    Map<String, Person> map = null;
    if(len>0){//有数据
       FileInputStream fis = new FileInputStream(file);
       ObjectInputStream ois = new ObjectInputStream(fis);
       Map<String, Person> map = (Map<String, Person>)ois.readObject();
    }else{
        map = new HashMap<String, Person>();
    }
    
    do{
        System.out.println("************请输入如下选项************");
        System.out.println("\t\t\t1.信息录入");
        System.out.println("\t\t\t2.信息查询");
        System.out.println("\t\t\t3.信息修改");
        System.out.println("\t\t\t4.信息删除");
        System.out.println("\t\t\t5.退出");
        Scanner input = new Scanner(System.in);
        int flag = input.nextInt();
        switch(flag){
            case 1:
                Operation.addPerson(input,map);
                break;
            case 2:
                Operation.getAllPerson(map);
                break;
            case 3:
                break;
            case 4:
                break;
            case 5:
                System.out.println("退出成功");
                FileOutputStream fos = new FileOutputStream("X:\\xxx.xxx");
                ObjectOutputStream oos = new ObjectOutputStream(fos);
                oos.writeObject(map);
                oos.close();
                fos.close();
                System.exit(0);
                break;
        }
    }while(true);
}

1、数值类型

2、字符串类型

3、时间日期类型

4、null类型

1、创建数据库

2、删除数据库

3、切换数据库

4、查看所有数据库

一、创建数据库

二、创建表

三、命令行操作

四、语言概念

DAG图上的灭绝树

难点：DAG图上求LCA

代码：

一般图最大匹配(带花树)模板

虚树

什么是虚树

建立虚树之前

如何建立虚树

情况一

情况二

情况三

情况四

另一种虚树构建方法：欧拉序

什么是欧拉序

2020CCPC威海站

B Labyrinth

题目大意：

做法：

转换流

与字节流

字符输入流

缓冲输入字符流

字符输出流

缓冲输出字符流

HashMap与对象流组合应用(主函数部分实现)