[kuangbin带你飞]专题一 简单搜索 解题报告

发布于 2019-08-27  122 次阅读



专题链接
A题
这个没什么可说的,直接dfs搜一遍就行

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
//using namespace __gnu_pbds;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
ll ans;
int n,k;
int x[10],y[10];
char s[10][10];
inline void data_init()
{
    mem(x,0),mem(y,0);ans=0;
    mem(s,0);
}
void dfs(int step,int nx,int ny){
    if(step==k+1){ans++;return;}
    if(nx>n||ny>n)return;
    if(s[nx][ny]=='.'){
        if(nx==n&&ny==n)return;
        if(ny==n)dfs(step,nx+1,1);
        else dfs(step,nx,ny+1);
    }
    else{
        int tmp;
        if(!x[nx]&&!y[ny]){
            x[nx]=1;y[ny]=1;
            if(ny==n)dfs(step+1,nx+1,1);
            else dfs(step+1,nx,ny+1);
            x[nx]=0;y[ny]=0;
        }
        if(nx==n&&ny==n)return;
        else if(ny==n)dfs(step,nx+1,1);
        else dfs(step,nx,ny+1);
    }
}
int main(){
    while(scanf(
        if(n==-1&&k==-1)break;
        data_init();
        for(int i=1;i<=n;++i){
            scanf(
        }
        dfs(1,1,1);
        printf(
    }
    return 0;
}

B题
这个就是裸的走迷宫啊......也没什么可说的

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
char s[35][35][35];
int L,R,C;
struct state{
    int x,y,z;
    int step;
    inline void init_(){
        step=inf;
    }
};
inline int id(state x){
    return x.x*10000+x.y*100+x.z;
}
inline state operator + (const state &A,const state &B){
    state ret;
    ret.x=A.x+B.x;ret.y=A.y+B.y;ret.z=A.z+B.z;
    return ret;
}
state beg,en;
int ans;
bool vis[400000];
int dis[400000];
state dir[6];
inline void direction_init(){
    dir[0].x=0;dir[0].y=0;dir[0].z=1;
    dir[1].x=0;dir[1].y=0;dir[1].z=-1;
    dir[2].x=1;dir[2].y=0;dir[2].z=0;
    dir[3].x=-1;dir[3].y=0;dir[3].z=0;
    dir[4].x=0;dir[4].y=1;dir[4].z=0;
    dir[5].x=0;dir[5].y=-1;dir[5].z=0;
}
inline void bfs(){
    queue <state> q;q.push(beg);
    mem(vis,0);mem(dis,inf);
    dis[id(beg)]=0;
    while(!q.empty()){
        state u=q.front();q.pop();vis[id(u)]=0;
        for(int k=0;k<6;++k){
            state nxt=dir[k]+u;
            if(nxt.z<1||nxt.z>L||nxt.x<1||nxt.x>R||nxt.y<1||nxt.y>C)continue;
            if(s[nxt.z][nxt.x][nxt.y]=='#')continue;
            if(dis[id(nxt)]>dis[id(u)]+1){
                dis[id(nxt)]=dis[id(u)]+1;
                if(!vis[id(nxt)]){
                    vis[id(nxt)]=1;
                    q.push(nxt);
                }
            }
        }
    }
}
int main(){
    direction_init();
    while(scanf(
        if(!L&&!R&&!C)break;
        beg.init_();en.init_();
        for(int k=1;k<=L;++k){
            for(int i=1;i<=R;++i){
                scanf(
                for(int j=1;j<=C;++j){
                    if(s[k][i][j]=='S'){
                        beg.step=0;
                        beg.x=i;beg.y=j;beg.z=k;
                        break;
                    }
                    if(s[k][i][j]=='E'){
                        en.x=i;en.y=j;en.z=k;
                        break;
                    }
                }
            }
        }
        bfs();
        ans=dis[id(en)];
        if(ans>10000000LL)printf("Trapped!\n");
        else printf("Escaped in
    }
    return 0;
}

C题
照样没啥可说的,注意从牛的位置开始搜要好做一些

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
int dfs(int n,int k){
    if(n>=k)return n-k;
    if(k&1){
        return min(dfs(n,k+1),dfs(n,k-1))+1;
    }
    else{
        return min(dfs(n,k/2)+1,k-n);
    }
}
int n,k,d;
int ans;
int main(){
    read(n),read(k);
    if(n==0){n=ans=1;}
    ans=ans+dfs(n,k);
    printf(
    return 0;
}

D题
参照这道题就行,不过该题更毒瘤了一些(那个方案输出......呵呵)
后来懒得写了就抄了份代码

#include <iostream>
#include <cstring>
using namespace std;
int a[20][20],b[20][20];
int f[20][20],ans[20][20],fNum,aNum,n,m;
void tranc(int x,int y){
    fNum ++;
    f[x][y] = 1;
    b[x][y] = 1-b[x][y];
    b[x-1][y] = 1-b[x-1][y];
    b[x+1][y] = 1-b[x+1][y];
    b[x][y-1] = 1-b[x][y-1];
    b[x][y+1] = 1-b[x][y+1];
}
void record(){
    aNum = fNum;
    for(int i = 1; i <= m; i ++){
        for(int j = 1; j <= n; j ++){
            ans[i][j] = f[i][j];
        }
    }
}
int main(){
    cin >> m >> n;
    for(int i = 1; i <= m; i ++){
        for(int j = 1; j <= n; j ++){
            cin >> a[i][j];
        }
    }
    int t = 1 << n;
    aNum = 10000;
    for(int loop = 0; loop < t;  loop ++){
        for(int i = 1; i <= m; i ++){
            for(int j = 1; j <= n; j ++){
                b[i][j] = a[i][j];
            }
        }
        fNum = 0;
        int moveN = loop;
        memset(f,0,sizeof(f));
        for(int j = 1; j <= n; j ++){
            if(moveN & 1) tranc(1,j);
            moveN = moveN >> 1;
        }
        for(int i = 2; i <= m; i ++){
            for(int j = 1; j <= n; j ++){
                if(b[i-1][j]) tranc(i,j);
            }
        }
        //判断这种翻转方式是否合法
        int j;
        for(j = 1; j <= n; j ++){
            if(b[m][j]) break;
        }
        if(j == n + 1 && fNum < aNum) record();
    }
    if(aNum == 10000){
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }
    for(int i = 1; i <= m; i ++){
        cout << ans[i][1];
        for(int j = 2; j <= n; j ++){
            cout << " " << ans[i][j];
        }
        cout << endl;
    }
    return 0;
}

E题
不用担心会爆,开个unsigned int 就行

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
typedef unsigned __int64 u_int64;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
int n;
bool flag;
void dfs(u_int64 num,int step){
    if(flag)return;
    if(nu
        printf(
        flag=true;
        return;
    }
    if(step==20)return;
    dfs(num*10,step+1);
    if(flag)return;
    dfs(num*10+1,step+1);
}
int main(){
    while(scanf(
        flag=false;
        dfs(0,0);
    }
    return 0;
}

F题
题干一大堆废话......
总的来说就是每次操作可以更改其中某一位的数字,更改后的数字不能有前导0,还必须是质数,而且只给你两个4位数
先筛再搜

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
const int N=10050;
bool vis[N],isprime[N];int pri[N],tot;
void shaipri(){
    for(int i=2;i<=10000;++i){
        if(!vis[i]){pri[++tot]=i;isprime[i]=1;}
        for(int j=1;j<=tot&&i*pri[j]<=10000;++j){
            vis[i*pri[j]]=1;
            if(
        }
    }
}
int S,T;
int ans;
void bfs(){
    queue <pair<int,int> > q;int v;
    q.push(make_pair(S,0));mem(vis,0);
    while(!q.empty()){
        pair <int,int> u=q.front();
        q.pop();vis[u.first]=0;
        if(u.second>=ans)continue;
        for(int i=0;i<10;++i){
            v=u.first;
            if(i==(
            v-=(
            v+=i;
            if(isprime[v]){
                if(!vis[v])q.push(make_pair(v,u.second+1));
                vis[v]=1;
                if(v==T)ans=min(ans,u.second+1);
            }
        }
        for(int i=0;i<10;++i){
            v=u.first;
            if(i*10==(
            v-=(
            v+=i*10;
            if(isprime[v]){
                if(!vis[v])q.push(make_pair(v,u.second+1));
                vis[v]=1;
                if(v==T)ans=min(ans,u.second+1);
            }
        }
        for(int i=0;i<10;++i){
            v=u.first;
            if(i*100==(
            v-=(
            v+=i*100;
            if(isprime[v]){
                if(!vis[v])q.push(make_pair(v,u.second+1));
                vis[v]=1;
                if(v==T)ans=min(ans,u.second+1);
            }
        }
        for(int i=1;i<10;++i){
            v=u.first;
            if(i*1000==(
            v-=(
            v+=i*1000;
            if(isprime[v]){
                if(!vis[v])q.push(make_pair(v,u.second+1));
                vis[v]=1;
                if(v==T)ans=min(ans,u.second+1);
            }
        }
    }
}
int main(){
    shaipri();
    int Test;read(Test);
    while(Test--){
        read(S),read(T);
        if(S==T){puts("0");continue;}
        ans=inf;
        bfs();
        if(ans==inf)puts("Impossible");
        else printf(
    }
    return 0;
}

G题
不多解释,题意读懂就行

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
map <string,bool> vis;
int n;
int ans;
string s,s1,s2,s3;
inline bool check(){
    for(int i=0;i<2*n;++i){
        if(s[i]!=s3[i])return false;
    }
    return true;
}
inline int solve(){
    int ret=0;
    s.clear();s.resize(205);
    while(true){
        for(int i=0;i<n;++i){
            s[i*2]=s2[i];
            s[i*2+1]=s1[i];
        }
        ret++;
//        cout<<s1<<endl;
//        cout<<s2<<endl;
//        cout<<s<<endl;
        if(check())break;
        if(vis[s]&&check()==false)return -1;
        vis[s]=1;
        for(int i=0;i<n;++i){
            s1[i]=s[i];
        }
        for(int i=n;i<2*n;++i){
            s2[i-n]=s[i];
        }
    }
    return ret;
}
int main(){
    int Test;read(Test);
    for(int T=1;T<=Test;++T){
        read(n);vis.clear();
        cin>>s1>>s2>>s3;
        ans=solve();
        printf(
        printf(
    }
    return 0;
}

H题
经典的倒水问题,不过这个题要输出方案,也只能老老实实搜了
(我的代码长度是最长的?)

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#include <vector>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
int a,b,c;
int ans=inf;
bool vis[305][305];
int dis[305][305];
int pre[300050];
struct Answer{
    int A,B;
    Answer(){}
    Answer(int _,int __):A(_),B(__){}
}beg;
inline int cal(Answer x){
    return x.A*1000+x.B;
}
struct Print{
    int op,id;
    Print(){}
    Print(int _,int __):op(_),id(__){}
};
vector <Print> v;
void bfs(){
    queue <Answer> q;
    q.push(beg);
    Answer nxt;
    vis[0][0]=1;
    mem(dis,inf);
    dis[0][0]=0;
    while(!q.empty()){
        Answer u=q.front();q.pop();vis[u.A][u.B]=0;
        nxt=u;
        if(u.A!=a){
            if(dis[a][u.B]>dis[u.A][u.B]+1){
                dis[a][u.B]=dis[u.A][u.B]+1;
                nxt.A=a;
                pre[cal(nxt)]=cal(u);
                if(!vis[a][u.B]){
                    vis[a][u.B]=1;
                    q.push(nxt);
                }
            }
        }
        nxt=u;
        if(u.B!=b){
            if(dis[u.A][b]>dis[u.A][u.B]+1){
                dis[u.A][b]=dis[u.A][u.B]+1;
                nxt.B=b;
                pre[cal(nxt)]=cal(u);
                if(!vis[nxt.A][nxt.B]){
                    vis[nxt.A][nxt.B]=1;
                    q.push(nxt);
                }
            }
        }
        nxt=u;
        if(u.A>0){
            if(dis[0][u.B]>dis[u.A][u.B]+1){
                dis[0][u.B]=dis[u.A][u.B]+1;
                nxt.A=0;
                pre[cal(nxt)]=cal(u);
                if(!vis[nxt.A][nxt.B]){
                    vis[nxt.A][nxt.B]=1;
                    q.push(nxt);
                }
            }
        }
        nxt=u;
        if(u.B>0){
            if(dis[u.A][0]>dis[u.A][u.B]+1){
                dis[u.A][0]=dis[u.A][u.B]+1;
                nxt.B=0;
                pre[cal(nxt)]=cal(u);
                if(!vis[nxt.A][nxt.B]){
                    vis[nxt.A][nxt.B]=1;
                    q.push(nxt);
                }
            }
        }
        nxt=u;
        if(u.A>0&&u.B<b){
            int tmp=min(u.A,b-u.B);
            nxt.A-=tmp;nxt.B+=tmp;
            if(dis[nxt.A][nxt.B]>dis[u.A][u.B]+1){
                dis[nxt.A][nxt.B]=dis[u.A][u.B]+1;
                pre[cal(nxt)]=cal(u);
                if(!vis[nxt.A][nxt.B]){
                    vis[nxt.A][nxt.B]=1;
                    q.push(nxt);
                }
            }
        }
        nxt=u;
        if(u.B>0&&u.A<a){
            int tmp=min(u.B,a-u.A);
            nxt.A+=tmp;nxt.B-=tmp;
            if(dis[nxt.A][nxt.B]>dis[u.A][u.B]+1){
                dis[nxt.A][nxt.B]=dis[u.A][u.B]+1;
                pre[cal(nxt)]=cal(u);
                if(!vis[nxt.A][nxt.B]){
                    vis[nxt.A][nxt.B]=1;
                    q.push(nxt);
                }
            }
        }
    }
}
int main(){
    read(a),read(b),read(c);
    beg.A=0,beg.B=0;
    bfs();
    int startpre;
    for(int i=0;i<=a;++i){
        if(dis[i][c]<ans){
            ans=dis[i][c];
            startpre=cal(Answer(i,c));
        }
    }
    for(int i=0;i<=b;++i){
        if(dis[c][i]<ans){
            ans=dis[c][i];
            startpre=cal(Answer(c,i));
        }
    }
    if(ans==inf)return puts("impossible"),0;
    else printf(
    while(startpre){
        int las=startpre;
        startpre=pre[startpre];
        int A1=las/1000,B1=la
        int A2=startpre/1000,B2=startpr
        if(A1==A2&&B1<B2){
            v.push_back(Print(2,2));
        }
        else if(A1<A2&&B1==B2){
            v.push_back(Print(2,1));
        }
        else if(A1==A2&&B1>B2){
            v.push_back(Print(1,2));
        }
        else if(A1>A2&&B1==B2){
            v.push_back(Print(1,1));
        }
        else if(A1>A2&&B1<B2){
            v.push_back(Print(3,2));
        }
        else if(A1<A2&&B1>B2){
            v.push_back(Print(3,1));
        }
    }
    for(int i=v.size()-1;i>=0;--i){
        if(v[i].op==1){
            printf("FILL
        }
        else if(v[i].op==2){
            printf("DROP
        }
        else{
            if(v[i].id==1)printf("POUR(1,2)\n");
            else printf("POUR(2,1)\n");
        }
    }
    return 0;
}

I题
哎呀这个题没法评测(fzu已炸)我也不知道过不过得了啊......先搁在这吧

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#include <vector>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
int n,m;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
char s[15][15];
bool vis[2000];
int dis[2000];
int tot;
inline int id(int x,int y){return x*100+y;}
inline void data_init(){
    mem(vis,0);mem(dis,inf);
    tot=0;
}
void bfs(int x,int y){
    queue <int> q;
    q.push(id(x,y));mem(vis,0);
    dis[id(x,y)]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        int ux=u/100;int uy=
        vis[u]=0;
        for(int k=0;k<4;++k){
            int nx=dx[k]+ux;
            int ny=dy[k]+uy;
            if(s[nx][ny]!='#')continue;
            if(dis[id(nx,ny)]>dis[id(ux,uy)]+1){
                dis[id(nx,ny)]=dis[id(ux,uy)]+1;
                if(!vis[id(nx,ny)]){
                    vis[id(nx,ny)]=1;
                    q.push(id(nx,ny));
                }
            }
        }
    }
}
int main(){
    int Test;read(Test);
    for(int T=1;T<=Test;++T){
        data_init();
        read(n),read(m);
        for(int i=1;i<=n;++i){
            scanf(
        }
        printf("Case
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                if(s[i][j]=='#'&&dis[id(i,j)]==inf){
                    tot++;
                    bfs(i,j);
                }
            }
        }
        if(tot>2){printf("-1\n");continue;}
        else{
            int ans=-1;
            for(int i=1;i<=n;++i){
                for(int j=1;j<=m;++j){
                    if(s[i][j]!='#')continue;
                    if(dis[id(i,j)]==inf)continue;
                    ans=max(ans,dis[id(i,j)]);
                }
            }
            printf(
        }
    }
    return 0;
}

 
J题
两遍bfs,第一次以每个火源为起点,搜出每个格子被火占据的最短时间(打时间戳),之后再以人为起点bfs,就可以了
我的代码的第二遍bfs写了个dfs,也不知道能不能过......没过的话再改(现在uva炸了)

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#include <vector>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
int n,m;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int sx,sy;
char s[1005][1005];
int d[1005][1005];
bitset <200000000> vis;
int ans;
inline int id(int x,int y){
    return x*10000+y;
}
queue <int> q;
inline void data_init(){
    while(!q.empty())q.pop();
    ans=inf;vis.reset();
    mem(d,inf);
}
inline void bfs(){
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        int ux=u/10000;int uy=
        for(int k=0;k<4;++k){
            int nx=dx[k]+ux;
            int ny=dy[k]+uy;
            if(s[nx][ny]=='#')continue;
            if(d[nx][ny]>d[ux][uy]+1){
                d[nx][ny]=d[ux][uy]+1;
                if(!vis[id(nx,ny)]){
                    vis[id(nx,ny)]=1;
                    q.push(id(nx,ny));
                }
            }
        }
    }
}
void dfs(int x,int y,int tim){
    if(tim>=ans)return;
    if(x==n+1||y==m+1||x==0||y==0){
        ans=min(ans,tim);
        return;
    }
    for(int k=0;k<4;++k){
        int nx=dx[k]+x;
        int ny=dy[k]+y;
        if(s[nx][ny]=='#'||s[nx][ny]=='F')continue;
        if(d[nx][ny]<=tim+1)continue;
        dfs(nx,ny,tim+1);
    }
}
int main(){
    int Test;read(Test);
    while(Test--){
        data_init();
        read(n),read(m);
        for(int i=1;i<=n;++i){
            scanf(
            for(int j=1;j<=m;++j){
                if(s[i][j]=='F')q.push(id(i,j)),vis[id(i,j)]=1,d[i][j]=0;
                if(s[i][j]=='J')sx=i,sy=j;
            }
        }
        bfs();
        dfs(sx,sy,0);
        if(ans==inf)puts("IMPOSSIBLE");
        else printf(
    }
    return 0;
}

K题
没什么可说的

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#include <vector>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
inline int id(int x,int y){return x*100+y;}
char a[10][10];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int d[2000];
bool vis[2000];
int pre[2000];
void bfs(){
    queue <int> q;
    q.push(id(1,1));
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        int ux=u/100;int uy=
        for(int k=0;k<4;++k){
            int nx=dx[k]+ux;
            int ny=dy[k]+uy;
            if(a[nx][ny]!='0')continue;
            if(d[id(nx,ny)]>d[id(ux,uy)]+1){
                d[id(nx,ny)]=d[id(ux,uy)]+1;
                pre[id(nx,ny)]=id(ux,uy);
                if(!vis[id(nx,ny)]){
                    vis[id(nx,ny)]=1;
                    q.push(id(nx,ny));
                }
            }
        }
    }
}
vector <pair<int,int> > v;
int main(){
    for(int i=1;i<=5;++i){
        for(int j=1;j<=5;++j){
            cin>>a[i][j];
        }
    }
    mem(d,inf);
    d[id(1,1)]=0;
    bfs();
    int p=id(5,5);
    while(p){
        v.push_back(make_pair(p/100,
        p=pre[p];
    }
    for(int i=v.size()-1;~i;--i){
        printf("
    }
    return 0;
}

L题
纯粹的判连通块......注意是八方向联通

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#include <vector>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
int n,m;
char s[105][105];
int dx[]={1,1,0,0,1,-1,-1,-1};
int dy[]={1,-1,1,-1,0,0,-1,1};
void dfs(int x,int y){
    s[x][y]='*';
    for(int k=0;k<8;++k){
        int nx=x+dx[k];
        int ny=y+dy[k];
        if(s[nx][ny]!='@')continue;
        dfs(nx,ny);
    }
}
int main(){
    while(scanf(
        int tot=0;
        for(int i=1;i<=n;++i){
            scanf(
        }
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                if(s[i][j]=='@'){
                    tot++;dfs(i,j);
                }
            }
        }
        printf(
    }
    return 0;
}

M题
懒得搜了,直接上数论(高一班上某同学推过这个)

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#include <vector>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
int s,n,m;
int gcd(int x,int y){return y==0?x:gcd(y,
int main(){
    while(scanf(
        s/=gcd(n,m);
        if(s&1){puts("NO");continue;}
        printf(
    }
    return 0;
}

N题
可以建图跑最短路,但不要以KFC跑,这样会跑多次最短路,应该以两个人为起点分别跑一次

//#include <bits/extc++.h>
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <bitset>
#include <vector>
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+ch-'0';ch=getchar();}
    if(ck==1)e=-e;
}
int n,m;
inline int id(int x,int y){
    return (x-1)*m+y;
}
int sx1,sy1,sx2,sy2;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
char s[205][205];
bool vis[40500];
int d1[40500],d2[40500];
struct edge{
    int v,nxt;
}e[100500<<1];
int head[40500],ecnt;
inline void data_init(){
    ecnt=0;mem(head,0);
}
inline void ad(int u,int v){
    e[++ecnt].v=v;e[ecnt].nxt=head[u];head[u]=ecnt;
}
inline void sp1(int node){
    queue <int> q;
    mem(d1,inf);mem(vis,0);
    q.push(node);
    d1[node]=0;
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(d1[v]>d1[u]+1){
                d1[v]=d1[u]+1;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
inline void sp2(int node){
    queue <int> q;
    mem(d2,inf);mem(vis,0);
    q.push(node);
    d2[node]=0;
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(d2[v]>d2[u]+1){
                d2[v]=d2[u]+1;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    while(scanf(
        data_init();
        for(int i=1;i<=n;++i){
            scanf(
        }
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                if(s[i][j]=='#')continue;
                for(int k=0;k<4;++k){
                    int nx=dx[k]+i;
                    int ny=dy[k]+j;
                    if(s[nx][ny]=='.'||s[nx][ny]=='@'){
                        ad(id(i,j),id(nx,ny));
                    }
                }
            }
        }
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                if(s[i][j]=='Y'){
                    sx1=i;sy1=j;
                }
                else if(s[i][j]=='M'){
                    sx2=i;sy2=j;
                }
            }
        }
        int ans=inf;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                if(s[i][j]=='Y'){
                    sp1(id(i,j));
                }
                else if(s[i][j]=='M'){
                    sp2(id(i,j));
                }
            }
        }
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                if(s[i][j]=='@'){
                    ans=min(ans,d1[id(i,j)]+d2[id(i,j)]);
                }
            }
        }
        printf(
    }
    return 0;
}