从2024.8.25号开始，就要离开老赛码了，呜呜呜呜呜呜呜呜呜呜

冲刺777道（要走了冲刺不了了呜呜呜呜呜呜呜呜呜）

ybhome.iok.la:8888 集训域

主页的乱七八糟都删了，已老实，求放过

/*
       ┏┓　　　┏┓
     ┏┛┻━━━┛┻┓
     ┃　　　　　　　┃
     ┃　　　━　　　┃
     ┃　┳┛　┗┳　┃
     ┃　　　　　　　┃
     ┃　　　┻　　　┃
     ┃　　　　　　　┃
     ┗━┓　　　┏━┛Codes are far away from bugs with the animal protecting
         ┃　　　┃    神兽保佑,代码无bug
         ┃　　　┃
         ┃　　　┗━━━┓
         ┃　　　　　 ┣┓
         ┃　　　　 ┏┛
         ┗┓┓┏━┳┓┏┛            orz orz orz orz orz
           ┃┫┫　┃┫┫			   orz orz orz orz orz
           ┗┻┛　┗┻┛     ○|￣|_  orz orz orz orz orz
*/

图（关系结构）

由点和边构成的集合

• 无向图
• 有向图

带权图

度

出度：从一个点出去的边的数量

入度：进入一个点的边的数量

连通图

概念：一个图中所有点之间至少存在一条路径（路径：一个点有一条路到达另一个点）的图

无向图：连通图

有向图

• 弱连通图：将此图转换为无向图后，是连通状态，即为若连通

• 强连通图：有向图中任意一点都存在一条到达其余所有点的路径

完全图

一张图中，任意两点之间均有着一条直接连接的边

树

概念：只有n-1(n:点的数量)条边的连通图

点和点之间的关系

• 父子
• 兄弟
• 祖孙

度：一个点的儿子数量

节点类型

• 根结点
• 分支节点
• 叶子节点

完全二叉树

概念：按照每一层节点依次填充的顺序的二叉树，是完全二叉树

特性：

• n层的二叉树，最多共有** 2n−12​n​−1个节点**
• 二叉树第n层，最多有个2n−12n**−1节点**

满二叉树

概念：n层的二叉树中所有分支节点的度数都为2

最小生成树

kruskal算法

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
//kruskal算法 
const int N=2e5+7;
int n,m,p[N];
struct edge{
	int u,v,w;
	bool operator < (const edge t){
		return w<t.w;
	}
}edges[N];
int find(int x){
	if(p[x]!=x)p[x]=find(p[x]);
	return p[x];
}
bool merge(int a,int b){
	int fa=find(p[a]),fb=find(b);
	if(fa==fb)return false;
	p[fa]=fb;
	return true;
}
void kruskal(){
	sort(edges+1,edges+1+m);
	for(int i=1;i<=n;i++)p[i]=i;
	int sum=0;
	for(int i=1;i<=m;i++){
		int u=edges[i].u,v=edges[i].v,w=edges[i].w;
		if(merge(u,v)){
			sum+=w;
		}
	}
	cout<<sum<<endl;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		edges[i]={u,v,w};
	}
	kruskal();
	return 0;
}

拓扑排序

//方法一
bool toposort() {
  vector<int> L;
  queue<int> S;
  for (int i = 1; i <= n; i++)
    if (in[i] == 0) S.push(i);
  while (!S.empty()) {
    int u = S.front();
    S.pop();
    L.push_back(u);
    for (auto v : G[u]) {
      if (--in[v] == 0) {
        S.push(v);
      }
    }
  }
  if (L.size() == n) {
    for (auto i : L) cout << i << ' ';
    return true;
  } else {
    return false;
  }
}
//方法二
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;

int n,m;
int in[100005];
vector<int> vt[100005];
//int out[1000005];

int main(){
	cin>>n>>m;
	while(m--){
		int a,b;
		cin>>a>>b;
		vt[a].push_back(b);
		in[b]++;
		//out[b]++;
	}
    stack<int> stk;
    for(int i=1;i<=n;i++){
        if(in[i]==0) stk.push(i);
    }
    while(!stk.empty()){
        int p=stk.top();
        stk.pop();
        cout<<p<<" ";
        for(int i=0;i<vt[p].size();i++){
            int t=vt[p][i];//获取这条边的终点
            in[t]--;
            if(in[t]==0){
            	stk.push(t);
			}
        }
    }
	return 0;
}

迪杰斯特拉

struct edge {
  int v, w;
};

struct node {
  int dis, u;

  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;

void dijkstra(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}

位运算符

左移运算：<<

用法：** **x<<y

作用：将表示** x 的二进制数的每一位左移 **y 位，移出去的数就丢掉，空余地方用 0 补位。

例如：一个二进制数 10101011 将其左移 3 位，得到 01011000。

右移运算：>>

用法：x>>y

作用：将表示** x 的二进制数的每一位右移 **y 位，移出去的数就丢掉，空余地方用 0 补位。

例如：一个二进制数 10101011 将其右移 3 位，得到 00010101。

按位与运算：&

用法：x&y

作用：按位进行与运算。

例如：1101 和 0011 进行与运算就为：0001。

按位或运算: |

用法：x|y

作用：按位进行或运算。

例如：1101 和 0011 进行或运算就为：1111。

按位异或运算：^

用法：x^y

作用：按位进行异或运算。

例如：1101 和 0011 进行异或运算就为：0001。

按位非运算：~

用法：~x

作用：按位进行非运算。

例如：1101进行非运算就为：0010。

状态压缩常用位运算符技巧

1.取出x的第k位:

y = x&(1<<(k-1));//i<<(k-1)能够做成一个第k为1，其余位为0，如:10000 的二进制数，再结合位与运算就能提取到变量x的二进制中第k位数为1还是0了，常用于判断

2.将x第k位取反:

x ^= (1<<(k-1));//通过左移制作一个10000般的二进制数，然后结合异或运算的特点，将变量x的二进制中第k位数取反

3.将x第k位变为1：

x |= (1<<(k-1));//通过左移制作一个10000般的二进制数，然后结合异或运算的特点，将变量x的二进制中第k位数修改为1

4.将x第k位变为0：

x &= (~(1<<(k-1))); //通过左移制作一个0001 0000般的二进制数，然后位非运算将其修改为1110 0000般的二进制数，最后结合位与运算的特点，将变量x的二进制中第k位数修改为0

5.将x最靠右的1去掉：

x = x&(x-1); //减去1会将数字二进制中末尾的1去掉，然后需要借位的地方全变为1，如原1010 0000，减去1后变成1001 1111，再进位与运算得1000 0000，相当于去掉末尾1

6.取出x最靠右的1:

y = x&(-x); //结合负数的二进制的特点，如数字20的二进制为0001 0100，-20的二进制为1110 1100，再进行位与运算能够获取到二进制数100也就是4，及提前数字x中包含的最大2的指数值

7.判断是否有两个连续的一：

if(x&(x<<1)) cout<<"YES"; //左移后的数字会进行偏移，如13的二进制0000 1101，左移后未0001 1010，再进行位与运算，连续的1会在偏移后有至少一个1重叠，让结果不为0，如果结果为0，说明不存在连续的1

8.枚举子集：

for( int x = sta ; x ;  x = ( ( x - 1 )&sta) )  
	cout<<x;//通过技巧6的方式，如二进制:1011 0101,此循环能够枚举1011 0101、1011 0100、1011 0000、1010 0000、1000 0000这几个数据，即十进制：181、180、176、160、128这几个数字。

freopen("A.in","r",stdin); freopen("A.out","w",stdout);

深搜模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<deque>
using namespace std;

int n,m;
char mat[505][505];
int vis[505][505];
int dx[4]={1,0,-1,0};//下右上左 
int dy[4]={0,1,0,-1} ;
int flag=0;
void dfs(int x,int y){
	vis[x][y]=1;
	if(mat[x][y]=='g'){
		flag=1;
		return;
	}
	for(int i=0;i<4;i++){
		int tx=dx[i]+x;
		int ty=dy[i]+y;
		if(mat[tx][ty]=='#') continue;
		if(vis[tx][ty]==1) continue;
		if(tx<1||tx>n||ty<1||ty>m) continue;
		dfs(tx,ty);
	} 
}

int main(){
	cin>>n>>m;
	int a,b;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mat[i][j];
			if(mat[i][j]=='s'){
				a=i,b=j;
			}
		}
	}
	dfs(a,b);
	if(flag) cout<<"Yes";
	else cout<<"No";
	return 0;
}

GESP二级考点

GESP三级考点

让我看看是哪个小可爱这么无聊没写完代码在看别人主页看到底的鸭~~，赶紧去写代码！！！啊哈哈哈哈哈哈哈哈哈哈哈哈哈哈啊哈哈哈哈哈哈哈哈哈哈哈啊哈哈哈哈哈哈哈哈