[数据结构与算法]4/5 逆元+深搜+bfs

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

#include <bits/stdc++.h>
#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<<endl;
    return 0;
}

蹦蹦炸弹

1.结构体中存放相邻炸弹会爆炸的时间
2.s1集合记录炸弹的位置，自动排序去重，这个是符合逻辑上的顺序
3.s2集合记录每个炸弹的编号。
4.如果一对炸弹爆炸，自动查找两边的炸弹是否会产生爆炸，会则加入到队列中。
一道非常综合的stl容器题。

#include <bits/stdc++.h>

using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+5;
int n,x[N],v[N];
set<int>s1,s2;
map<int,int>mp;
struct node
{
    int x,y;double tt;
    bool operator <(const node &a) const{
        return a.tt<tt;
    }
};
priority_queue<node>q;
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<<x<<" "<<y<<" "<<t<<endl;
        if(t==tmp)
            break;
        if(!s1.count(x)||!s1.count(y))
            continue;
        auto p1=s1.find(x),p2=s1.find(y);
        p1--,p2++;
        int p3=*p1,p4=*p2;
        double k=(p4-p3)*1.0/(v[mp[p3]]-v[mp[p4]]);
        if(k>=0)
            q.push(node{p3,p4,k});
         //cout<<x<<" "<<y<<" "<<t<<endl;
        s1.erase(x),s1.erase(y);
        s2.erase(mp[x]),s2.erase(mp[y]);
    }
    cout<<s2.size()<<endl;
    for(auto x:s2)
        cout<<x<<endl;
    return 0;
}

二进制补码

之前写的好像错了

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 <bits/stdc++.h>
#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<<ans<<endl;
    return 0;
}

1455: [蓝桥杯2019初赛]迷宫
1.尽量使用结构体，便于随时添加数据元素。
2.每个点都开一个字符串，记录到这里的路径。
3.注意上下左右的顺序。行列的变化，千万不要再这种小细节上出错。

#include <bits/stdc++.h>

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;
};
queue<node>q;

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<<cur.s<<endl;break;
        }
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<=0||nx>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"<<endl;
    return 0;
}

1326: [蓝桥杯2017初赛]等差素数列
素数筛+暴力枚举

#include <bits/stdc++.h>
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<<d<<endl;return 0;
                }
            }
        }
    }
    return 0;
}