头像

幼稚园小明同学




在线 



#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int tfind(int l, int r, int x);

int n;
int len;
int a[N];
int f[N];

signed main()
{
    cin>>n;
    for(int i=0;i<n;i++) scanf("%d", &a[i]);

    for(int i=0;i<n;i++)
    {
        int r=tfind(0, len, a[i]);
        len=(len, r+1);
        f[r+1]=a[i];
    }

    cout<<len<<endl;
}

int tfind(int l, int r, int x)
{
    while(l<r)
    {
        int mid=(l+r+1)/2;
        if(f[mid]<x) l=mid;
        else r=mid-1;
    }

    return l;
}


活动打卡代码 AcWing 175. 电路维修

#include<iostream>
#include<cstdio>
#include<cstring>
#include<deque>
#define f first
#define s second
using namespace std;
typedef pair<int, int> PII;
const int N=550, INF=0x3f3f3f3f;
int bfs();

int T;
int n, m;
char g[N][N];
int dist[N][N];
bool st[N][N];
int dx[4]={-1, -1, 1, 1}, dy[4]={-1, 1, 1, -1};
int ix[4]={-1, -1, 0, 0}, iy[4]={-1, 0, 0, -1};
char op[]={"\\/\\/"};

signed main()
{
    cin>>T;

    while(T--)
    {
        scanf("%d%d", &n, &m);
        for(int i=0;i<n;i++) scanf("%s", g[i]);

        if((n+m)&1)
        {
            puts("NO SOLUTION");
            continue;
        }

        printf("%d\n", bfs());
    }
}

int bfs()
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);

    deque<PII> q;
    q.push_back({0, 0}), dist[0][0]=0;

    while(q.size())
    {
        auto t=q.front();
        q.pop_front();

        if(st[t.f][t.s]) continue;
        st[t.f][t.s]=true;

        for(int i=0;i<4;i++)
        {
            int a=t.f+dx[i], b=t.s+dy[i];
            if(a<0||a>n||b<0||b>m) continue;

            int ca=t.f+ix[i], cb=t.s+iy[i];
            int d=dist[t.f][t.s]+(g[ca][cb]!=op[i]);

            if(d<dist[a][b])
            {
                dist[a][b]=d;
                g[ca][cb]!=op[i]?q.push_back({a, b}):q.push_front({a, b});
            }
        }
    }

    return dist[n][m];
}


活动打卡代码 AcWing 1107. 魔板

#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>
#include<unordered_map>
#define f first
#define s second
using namespace std;
typedef pair<char, string> PCS;
const int N=10;
int bfs(string st, string ed);
void make(string str);
string get(char g[N][N]);
string trans0(string str);
string trans1(string str);
string trans2(string str);

queue<string> q;
char g[N][N];
unordered_map<string, int> dist;
unordered_map<string, PCS> pre;

signed main()
{
    string st="12345678", ed;
    for(int i=0;i<8;i++)
    {
        int x;
        scanf("%d", &x);
        ed+=char(x+'0');
    }

    int t=bfs(st, ed);

    string res;
    while(st!=ed)
    {
        res+=pre[ed].f;
        ed=pre[ed].s;
    }

    reverse(res.begin(), res.end());
    cout<<t<<endl;
    if(t) cout<<res<<endl;
}

void make(string str)
{
    for(int i=0;i<4;i++) g[0][i]=str[i];
    for(int i=0, j=7;i<4&&j>=4;i++, j--) g[1][i]=str[j];
}

string get(char g[N][N])
{
    string res;

    for(int i=0;i<4;i++) res+=g[0][i];
    for(int i=3;~i;i--) res+=g[1][i];

    return res;
}

string trans0(string str)
{
    make(str);

    for(int i=0;i<4;i++) swap(g[0][i], g[1][i]);

    return get(g);
}

string trans1(string str)
{
    make(str);

    char v1=g[0][3], v2=g[1][3];
    for(int i=3;i;i--) g[0][i]=g[0][i-1], g[1][i]=g[1][i-1];
    g[0][0]=v1, g[1][0]=v2;

    return get(g);
}

string trans2(string str)
{
    make(str);

    char t=g[0][1];
    g[0][1]=g[1][1], g[1][1]=g[1][2], g[1][2]=g[0][2], g[0][2]=t;

    return get(g);
}

int bfs(string st, string ed)
{
    q.push(st), dist[st]=0;

    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(t==ed) return dist[ed];

        string state[3];
        state[0]=trans0(t);
        state[1]=trans1(t);
        state[2]=trans2(t);

        for(int i=0;i<3;i++)
            if(!dist.count(state[i]))
            {
                q.push(state[i]);
                dist[state[i]]=dist[t]+1;
                pre[state[i]]={'A'+i, t};
            }
    }
}


活动打卡代码 AcWing 173. 矩阵距离

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define f first
#define s second
using namespace std;
typedef pair<int, int> PII;
const int N=1010;
void bfs();

int n, m;
char g[N][N];
PII q[N*N];
int dist[N][N];
int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};

signed main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) scanf("%s", g[i]);

    bfs();

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            printf("%d ", dist[i][j]);
        puts("");
    }
}

void bfs()
{
    memset(dist, -1, sizeof dist);

    int hh=0, tt=-1;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j]=='1')
                q[++tt]={i, j}, dist[i][j]=0;

    while(hh<=tt)
    {
        auto t=q[hh++];

        for(int i=0;i<4;i++)
        {
            int a=t.f+dx[i], b=t.s+dy[i];
            if(a<0||a>=n||b<0||b>=m||dist[a][b]!=-1) continue;
            q[++tt]={a, b}, dist[a][b]=dist[t.f][t.s]+1;
        }
    }
}


活动打卡代码 AcWing 1106. 山峰和山谷

#include<iostream>
#include<cstdio>
#include<algorithm>
#define f first
#define s second
using namespace std;
typedef pair<int, int> PII;
const int N=1010;
void bfs(int x, int y, bool &has_higher, bool &has_lower);

int n;
int g[N][N];
bool st[N][N];
PII q[N*N];
int dx[8]={-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8]={0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{
    cin>>n;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d", &g[i][j]);

    int peak=0, valley=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(!st[i][j])
            {
                bool has_higher=false, has_lower=false;
                bfs(i, j, has_higher, has_lower);
                if(!has_higher) peak++;
                if(!has_lower) valley++;
            }

    cout<<peak<<' '<<valley<<endl;
}

void bfs(int x, int y, bool &has_higher, bool &has_lower)
{
    int hh=0, tt=-1;
    q[++tt]={x, y}, st[x][y]=true;

    while(hh<=tt)
    {
        auto t=q[hh++];

        for(int i=0;i<8;i++)
        {
            int a=t.f+dx[i], b=t.s+dy[i];

            if(a<0||a>=n||b<0||b>=n) continue;

            if(g[a][b]!=g[t.f][t.s]) g[a][b]>g[t.f][t.s]?has_higher=true:has_lower=true;
            else if(!st[a][b]) q[++tt]={a, b}, st[a][b]=true;
        }
    }
}


活动打卡代码 AcWing 1113. 红与黑

#include<iostream>
#include<cstdio>
#include<algorithm>
#define f first
#define s second
using namespace std;
typedef pair<int, int> PII;
const int N=25;
void dfs(int x, int y);

int res;
int n, m;
char g[N][N];
int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};

signed main()
{
    while(scanf("%d%d", &m, &n), n||m)
    {
        for(int i=0;i<n;i++) scanf("%s", g[i]);

        PII st;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(g[i][j]=='@')
                    st={i, j};

        res=0;        
        dfs(st.f, st.s);

        printf("%d\n", res);
    }
}

void dfs(int x, int y)
{
    res++;
    g[x][y]='#';

    for(int i=0;i<4;i++)
    {
        int a=x+dx[i], b=y+dy[i];
        if(a<0||a>=n||b<0||b>=m||g[a][b]=='#') continue;
        dfs(a, b);
    }
}


活动打卡代码 AcWing 1112. 迷宫

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define f first
#define s second
using namespace std;
typedef pair<int, int> PII;
const int N=110;
void dfs(int x, int y);

int T;
int n;
PII sta, ed;
char g[N][N];
bool st[N][N];
int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};

signed main()
{
    cin>>T;

    while(T--)
    {
        scanf("%d", &n);
        for(int i=0;i<n;i++) scanf("%s", g[i]);
        scanf("%d%d%d%d", &sta.f, &sta.s, &ed.f, &ed.s);

        if(g[sta.f][sta.s]=='#'||g[ed.f][ed.s]=='#')
        {
            puts("NO");
            continue;
        }

        memset(st, false, sizeof st);
        dfs(sta.f, sta.s);

        if(!st[ed.f][ed.s]) puts("NO");
        else puts("YES");
    }
}

void dfs(int x, int y)
{
    st[x][y]=true;
    if(x==ed.f&&y==ed.s) return;

    for(int i=0;i<4;i++)
    {
        int a=x+dx[i], b=y+dy[i];
        if(a<0||a>=n||b<0||b>=n||g[a][b]=='#'||st[a][b]) continue;
        dfs(a, b);
    }
}


活动打卡代码 AcWing 1100. 抓住那头牛

#include<iostream>
#include<cstdio>
using namespace std;
int bfs(int n);
const int N=1e5+10;

int n, k;
int q[N];
int dist[N];

signed main()
{
    cin>>n>>k;

    if(n>=k) cout<<n-k<<endl;
    else cout<<bfs(n)<<endl;
}

int bfs(int n)
{
    int hh=0, tt=-1;
    q[++tt]=n, dist[n]=0;

    while(hh<=tt)
    {
        auto t=q[hh++];
        if(t==k) return dist[t];

        if(t-1>=0&&!dist[t-1]) q[++tt]=t-1, dist[t-1]=dist[t]+1;
        if(t+1<=N&&!dist[t+1]&&t+1<=k) q[++tt]=t+1, dist[t+1]=dist[t]+1;
        if(2*t<=N&&!dist[2*t]) q[++tt]=2*t, dist[2*t]=dist[t]+1;
    }
}


活动打卡代码 AcWing 188. 武士风度的牛

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define f first
#define s second
using namespace std;
typedef pair<int, int> PII;
const int N=160;
void bfs(int x, int y);

int n, m;
PII q[N*N];
char g[N][N];
int dist[N][N];
int dx[8]={-2, -2, 2, 2, -1, -1, 1, 1}, dy[8]={-1, 1, -1, 1, -2, 2, -2, 2};

signed main()
{
    cin>>m>>n;
    for(int i=0;i<n;i++) scanf("%s", g[i]);

    PII st, ed;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j]=='K') st={i, j};
            else if(g[i][j]=='H') ed={i, j};

    bfs(st.f, st.s);

    cout<<dist[ed.f][ed.s]<<endl;
}

void bfs(int x, int y)
{
    memset(dist, -1, sizeof dist);
    int hh=0, tt=-1;
    q[++tt]={x, y}, dist[x][y]=0;

    while(hh<=tt)
    {
        auto t=q[hh++];
        if(g[t.f][t.s]=='H') return;

        for(int i=0;i<8;i++)
        {
            int a=t.f+dx[i], b=t.s+dy[i];
            if(a<0||a>=n||b<0||b>=m||dist[a][b]!=-1||g[a][b]=='*') continue;
            q[++tt]={a, b}, dist[a][b]=dist[t.f][t.s]+1;
        }
    }
}


活动打卡代码 AcWing 1076. 迷宫问题

#include<iostream>
#include<cstdio>
#include<algorithm>
#define f first
#define s second
using namespace std;
typedef pair<int, int> PII;
const int N=1010;
void bfs(int x, int y);

int n;
PII q[N*N];
int g[N][N];
PII pre[N][N];
int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};

signed main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d", &g[i][j]);

    bfs(0, 0);
}

void bfs(int x, int y)
{
    int hh=0, tt=-1;
    q[++tt]={x, y}, g[x][y]=1;

    while(hh<=tt)
    {
        auto t=q[hh++];

        for(int i=0;i<4;i++)
        {
            int a=t.f+dx[i], b=t.s+dy[i];
            if(a<0||a>=n||b<0||b>=n||g[a][b]==1) continue;
            q[++tt]={a, b}, g[a][b]=1, pre[a][b]=t;
        }
    }

    PII res[N*N];
    int c=n-1, d=n-1, cnt=0;
    while(c||d)
    {
        res[cnt++]={c, d};
        auto t=pre[c][d];
        c=t.f, d=t.s;
    }
    res[cnt++]={0, 0};

    for(int i=cnt-1;~i;i--) printf("%d %d\n", res[i].f, res[i].s);
}