锐客网

  1. 首页 > it技术 > >

acm算法学习|4/5 逆元+深搜+bfs

算法acm算法学习图论

P1082 [NOIP2012 提高组] 同余方程
同余求最小正整数逆元。用扩展欧几里得定理，a*x+b*y=1
求出a的逆元x.

#include #define int long long using namespace std; const int maxn=1005; int a,b,x,y; void exgcd(int a,int b) { if(b==0) { x=1,y=0; return ; } exgcd(b,a%b); int tmp=x; x=y; y=tmp-a/b*y; } signed main() { cin>>a>>b; exgcd(a,b); cout<<(x%b+b)%b<

蹦蹦炸弹 1.结构体中存放相邻炸弹会爆炸的时间
2.s1集合记录炸弹的位置，自动排序去重，这个是符合逻辑上的顺序
3.s2集合记录每个炸弹的编号。
4.如果一对炸弹爆炸，自动查找两边的炸弹是否会产生爆炸，会则加入到队列中。
一道非常综合的stl容器题。
#include using namespace std; const int inf=0x3f3f3f3f; const int N=1e5+5; int n,x[N],v[N]; sets1,s2; mapmp; struct node { int x,y; double tt; bool operator <(const node &a) const{ return a.ttq; signed main() { double tmp=inf; cin>>n; for(int i=1; i<=n; i++){ cin>>x[i]; s1.insert(x[i]); s2.insert(i); mp[x[i]]=i; } for(int i=1; i<=n; i++) cin>>v[i]; for(int i=2; i<=n; i++){ double k=(x[i]-x[i-1])*1.0/(v[i-1]-v[i]); if(k>=0) q.push(node{x[i-1],x[i],k}); else q.push(node{x[i-1],x[i],tmp}); } while(!q.empty()) { node cur=q.top(); int x=cur.x,y=cur.y,t=cur.tt; q.pop(); //cout<=0) q.push(node{p3,p4,k}); //cout<

二进制补码 之前写的好像错了
void f(int i,int step) { if (step ==8)return; f(i >> 1, step + 1); if (i & 1)cout << "1"; else cout << "0"; }signed main() { f(-20,0); return 0; }

1511: [蓝桥杯2020初赛] 七段码
深搜的方法控制灯的开关；并查集判断是否相连。
#include #define int long long using namespace std; int mp[15][15],ans,f[15]; bool vis[15]; void init() { mp[1][2]=mp[1][6]=mp[2][7]=mp[2][3]=mp[3][7]=mp[3][4]=1; mp[4][5]=mp[5][7]=mp[5][6]=mp[6][7]=1; } int r_find(int r) { if(r==f[r]) return r; f[r]=r_find(f[r]); return f[r]; } void dfs(int x) { if(x>7) { for(int i=1; i<=7; i++) f[i]=i; for(int i=1; i<=7; i++) for(int j=1; j<=7; j++) { if(mp[i][j]&&vis[i]&&vis[j]) { int fx=r_find(i),fy=r_find(j); if(fx!=fy) { f[fx]=fy; } } } int g=0; for(int i=1; i<=7; i++) if(f[i]==i&&vis[i]) g++; if(g==1) ans++; return; } vis[x]=1; dfs(x+1); vis[x]=0; dfs(x+1); } signed main() { init(); dfs(1); cout<

1455: [蓝桥杯2019初赛]迷宫
1.尽量使用结构体，便于随时添加数据元素。
2.每个点都开一个字符串，记录到这里的路径。
3.注意上下左右的顺序。行列的变化，千万不要再这种小细节上出错。
#include using namespace std; int n,m; bool vis[55][55]; int dx[4]={1,0,0,-1}; int dy[4]={0,-1,1,0}; char ch[4]={'D','L','R','U'}; char mp[55][55]; struct node { int x,y; string s; }; queueq; signed main() { n=30,m=50; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>mp[i][j]; q.push(node{1,1,""}); vis[1][1]=1; while(!q.empty()) { node cur=q.front(); q.pop(); int x=cur.x,y=cur.y; if(x==30&&y==50) { cout<n||ny<=0||ny>m) continue; if(!vis[nx][ny]&&mp[nx][ny]=='0') { vis[nx][ny]=1; q.push(node{nx,ny,cur.s+ch[i]}); } } } //cout<<"DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR"<

【acm算法学习|4/5 逆元+深搜+bfs】1326: [蓝桥杯2017初赛]等差素数列
素数筛+暴力枚举
#include using namespace std; const int inf=0x3f3f3f3f; const int N=1e6+5; int p[N],k; bool vis[N],used[N]; void init() { for(int i=2; i*i<=N; i++) if(!vis[i]) for(int j=i*2; j<=N; j+=i) vis[j]=1; } signed main() { vis[1]=1; init(); for(int d=2; ; d++) //枚举公差 { for(int i=2; i<10000; i++) //枚举首项 { int ans=1; for(int j=1; j<10; j++) { if(vis[i+j*d]==1) break; else ans++; if(ans==10) { cout<

    推荐阅读


    上一篇：麦克算法|第12节课 图

    下一篇：C语言程序练习|交换最小值和最大值