徐德铸

UID: 3978, 注册于 2023-8-27 9:13:40, 最后登录于 2024-9-19 18:47:34, 最后活动于 2024-9-17 17:51:14.

解决了 1 道题目，RP: 8 (No. 2514)

个人简介

深搜模板

#include iostream>

#include cstdio>

#include cstring>

#include cmath>

#include string>

#include algorithm>

#include queue>

#include stack>

#include map>

#include deque> using namespace std;

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

/ 图（关系结构）由点和边构成的集合无向图有向图带权图度出度：从一个点出去的边的数量入度：进入一个点的边的数量连通图概念：一个图中所有点之间至少存在一条路径（路径：一个点有一条路到达另一个点）的图无向图：连通图有向图弱连通图：将此图转换为无向图后，是连通状态，即为若连通强连通图：有向图中任意一点都存在一条到达其余所有点的路径完全图一张图中，任意两点之间均有着一条直接连接的边树概念：只有n-1(n:点的数量)条边的连通图点和点之间的关系父子兄弟祖孙度：一个点的儿子数量节点类型根结点分支节点叶子节点完全二叉树概念：按照每一层节点依次填充的顺序的二叉树，是完全二叉树特性： n层的二叉树，最多共有* 2n−12n−1个节点** 二叉树第n层，最多有个2n−12n**−1节点** 满二叉树概念：n层的二叉树中所有分支节点的度数都为2 最小生成树 kruskal算法 #include #include #include #include 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 L; queue 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 #include #include #include using namespace std;

int n,m; int in[100005]; vector 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 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 e[maxn]; int dis[maxn], vis[maxn]; priority_queue<node, vector, greater > 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);

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二级考点 image

image

GESP三级考点 image

image

GWL要吃郑兴亚，害怕ing...... 主域一言没有任何人有资格剥夺他人的愿望，即便是「神」也不行。

神在白天做梦，太阳在西边升起。

如果我们只看到自己的普通，可能就会错过特别的人生。

今后无论发生什么事也好，这个左手上的⋯⋯都是同伴的记号！ / 图（关系结构）由点和边构成的集合无向图有向图带权图度出度：从一个点出去的边的数量入度：进入一个点的边的数量连通图概念：一个图中所有点之间至少存在一条路径（路径：一个点有一条路到达另一个点）的图无向图：连通图有向图弱连通图：将此图转换为无向图后，是连通状态，即为若连通强连通图：有向图中任意一点都存在一条到达其余所有点的路径完全图一张图中，任意两点之间均有着一条直接连接的边树概念：只有n-1(n:点的数量)条边的连通图点和点之间的关系父子兄弟祖孙度：一个点的儿子数量节点类型根结点分支节点叶子节点完全二叉树概念：按照每一层节点依次填充的顺序的二叉树，是完全二叉树特性： n层的二叉树，最多共有* 2n−12n−1个节点** 二叉树第n层，最多有个2n−12n**−1节点** 满二叉树概念：n层的二叉树中所有分支节点的度数都为2 最小生成树 kruskal算法 #include #include #include #include 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 L; queue 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 #include #include #include using namespace std;

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

struct node { int dis, u;

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

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

作用：将表示** 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。

深搜模板

#include #include #include #include #include #include #include #include #include #include using namespace std;

image

GESP三级考点 image

image

“正文开始”

AC很可贵，我曰的

我从未见过如此厚颜无耻之WA

船员：我们一定要把WA全都揪出来
警长：消灭WA，一次只需一颗子弹
工程师：修理WA，哼，我可是专业的
侦探：这是最基本的AC，我的朋友
医生：我觉得AC还可以抢救一下
预言家：AC将指明我们的方向
守卫：别担心AC，我就是你的盾牌
保安：这里有我AC看着，别想闹事
换票师：我觉得AC结果，嗯，应该这样
情报员：我一定要把这份AC传递给大家，不惜一切代价
单面人：哈哈哈，为了正义，请乖乖被我AC
黑客：AC不会出错，会出错的只有WA
管道工：WA有问题，炸一炸就好了
守望者：没人能逃过我的AC
市长：我不会辜负大家的AC的
老兵：保持AC，是战场的第一生存守则
卧底：嘘，对不起啊，我是AC
狱卒：咳，呵呵，没有WA能逃脱我的掌心
诱饵：哈哈，WA上当了吧
时间之主：时间，由我AC来掌控
内鬼：我保证，没有WA能抵达目的地
间谍：记住，你的WA会欺骗你
清洁工：唉，这可比扫整条WA轻松多了
守夜人：没有我去不了的AC
咒术师：尽管逃，你WA是逃不掉的
变色龙：只有聪明人才能看到我AC
双面人：哈哈哈哈，AC，就是一场豪赌
搬运工：垃圾WA，就该去它该去的地方
闪光弹：AC配备检查完毕，准备行动
女巫：嗯，宝贝，帮我做AC
赏金猎人：我的眼里，只有AC和WA
小丑：哈哈哈哈哈哈哈哈，现在，谁才是真正的WA
纵火犯：芜湖，我从小就喜欢AC，我现在就想看
幸存者：AC下去，只要，AC下去
恶魔：我会将AC，分享给你
幻影：来吧，欣赏这场盛大的AC吧
饕餮：血肉苦弱，我会让你们AC的，哈哈哈哈哈
小蜜蜂：去找下一个AC吧
怪盗：怪盗是充满艺术的AC，而追捕他的侦探，最多只能算个WA
墙头草：帮你们太麻烦了，不如AC
孙悟空：嘿嘿，跳出WA之外
丘比特：AC，可真让人琢磨不透
国王：WA，你们的AC回来了

电脑房里生白烟，李白来到电脑前。狂打电脑的键盘，WA映入他眼帘

让我们荡起双桨，把WA拍在沙滩上

正道的光，照在了WA上，让每个绿色的AC都出来蹦跶

爱你一生爱AC，爱你一生恨WA，爱你一看WA，立马就变脸。爱你只爱见AC，爱你只爱原谅色，打开你的界面啊，全都是AC。AC，AC，我最爱的AC。AC，AC，全部都是AC。为啥我的界面就全是WA。啥时候我的界面也是AC

vector&&set
'''
#include<bits/stdc++.h>
using namespace std;
int main(){
//STL容器2
//vector 动态数组、向量
#include<vector>         		//头文件
vector<int> vec;         		//定义一个名叫vec的vector
vector<int> vec1(5);     		//创建一个 vector vec1,初始空间为5,元素默认值为0
vector<int> vec2(5,2);   		//创建一个 vector vec2,初始空间为5,元素默认值为2
vector<int> vec3(vec2);  		//创建一个 vector vec3,其内容拷贝vec2
int arr[5]={1,2,3,4,5};
vector<int> vec4(arr);   		//创建一个 vector vec4,其内容拷贝数组arr
vector<int> vec5(arr+1,arr+5);	//创建一个 vector vec5,其内容拷贝数组区间[1,5] (取头不取尾)

徐德铸

个人简介

“正文开始”

传 送 门

玛 卡 巴 卡

冲刺800道AC

工具箱

位运算符

左移运算：<<

右移运算：>>

按位与运算： &

按位或运算： |

按位异或运算： ^

按位非运算： ~

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

1.取出x的第k位:

2.将x第k位取反:

3.将x第k位变为1：

4.将x第k位变为0：

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

6.取出x最靠右的1:

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

通过的题目

最近活动

题目标签

状态

开发

支持

还没有账户？

登录

传送门

玛卡巴卡

左移运算：`<<`

右移运算：`>>`

按位与运算： `&`

按位或运算： `|`

按位异或运算： `^`

按位非运算： `~`