专题链接
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("%d%d",&n,&k)==2){
if(n==-1&&k==-1)break;
data_init();
for(int i=1;i<=n;++i){
scanf("%s",s[i]+1);
}
dfs(1,1,1);
printf("%lld\n",ans);
}
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("%d%d%d",&L,&R,&C)==3){
if(!L&&!R&&!C)break;
beg.init_();en.init_();
for(int k=1;k<=L;++k){
for(int i=1;i<=R;++i){
scanf("%s",s[k][i]+1);
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 %d minute(s).\n",ans);
}
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("%d\n",ans);
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(num%n==0&&num){
printf("%lld\n",num);
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("%d",&n)==1&&n){
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(i%pri[j]==0)break;
}
}
}
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%10))continue;
v-=(v%10);
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%100)-(v%10))continue;
v-=(v%100)-(v%10);
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%1000)-(v%100))continue;
v-=(v%1000)-(v%100);
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%10000)-(v%1000))continue;
v-=(v%10000)-(v%1000);
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("%d\n",ans);
}
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("%d ",T);
printf("%d\n",ans);
}
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("%d\n",ans);
while(startpre){
int las=startpre;
startpre=pre[startpre];
int A1=las/1000,B1=las%1000;
int A2=startpre/1000,B2=startpre%1000;
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(%d)\n",v[i].id);
}
else if(v[i].op==2){
printf("DROP(%d)\n",v[i].id);
}
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=u%100;
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("%s",s[i]+1);
}
printf("Case %d: ",T);
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("%d\n",ans/2);
}
}
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=u%10000;
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("%s",s[i]+1);
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("%d\n",ans);
}
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=u%100;
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%100));
p=pre[p];
}
for(int i=v.size()-1;~i;--i){
printf("(%d, %d)\n",v[i].first-1,v[i].second-1);
}
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("%d%d",&n,&m)==2&&n+m){
int tot=0;
for(int i=1;i<=n;++i){
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(s[i][j]=='@'){
tot++;dfs(i,j);
}
}
}
printf("%d\n",tot);
}
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,x%y);}
int main(){
while(scanf("%d%d%d",&s,&n,&m)==3&&s+n+m){
s/=gcd(n,m);
if(s&1){puts("NO");continue;}
printf("%d\n",s-1);
}
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("%d%d",&n,&m)==2){
data_init();
for(int i=1;i<=n;++i){
scanf("%s",s[i]+1);
}
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("%d\n",11*ans);
}
return 0;
}
Comments NOTHING