---恢复内容开始---
题目连接：https://cn.vjudge.net/contest/171139#overview
A题：
题目要求：求一个环，满足相邻的节点的和为素数，都是一开始
思路：深搜dfs，只到位数等于要求的位数，然后输出，接着回溯，只到所以情况都出来
代码：
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#define ll __int64
using namespace std;
int prime[40]={0,1,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0};//素数打表
int num[25];
int v[25];
int n;
void dfs(int d)
{
if(d==n&&prime[num[d]+num[1]])
{
for(int i=1;i<n;i++) cout<<num[i]<<" ";
cout<<num[n]<<endl;
return ;
}
for(int i=2;i<=n;i++)
{
if(!v[i]&&prime[num[d]+i])//v数组表示有没有访问过，再判断当前这个i加上num【d】d是表示第d位值的数
{
v[i]=1;
num[++d]=i;
dfs(d);
v[i]=0;//回溯
d--;
}
}
}
int main()
{
for(int i=0;i<=20;i++) num[i]=i;
int cnt=1;
while(~scanf("%d",&n))
{
memset(v,0,sizeof(v));
printf("Case %d:
",cnt++);
num[1]=1;
dfs(1);
cout<<endl;
}
return 0;
}
B题目：
直接看代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <string> #include <queue> #include <map> #include <vector> #define ll __int64 const int maxn=1005; using namespace std; int n,m,k; int da[]={0,0,1,-1}; int db[]={1,-1,0,0}; int x,y,enx,eny; int cnt=0; int flag; int v[maxn][maxn]; int mp[maxn][maxn]; bool judge(int pa,int pb,int nowa,int nowb,int nxta,int nxtb)//判断是不是要转弯 { if(pa==nowa&&pb==nowb) return true; if(pa==nowa&&nowa==nxta) return true; if(pb==nowb&&nowb==nxtb) return true; return false; } void dfs(int prex,int prey,int nowa,int nowb,int ctime)//上一个点，当前的点，上一个点 { if(flag) return; if(ctime==2) //能不能ac的关键，剪枝，如果到这里的转弯次数为二了，判断他的横坐标和纵坐标是不是都不等于终点，就return； { if(nowa!=enx&&nowb!=eny) return ; } if(ctime>2) return ; if(ctime<=2&&nowa==enx&&nowb==eny) { flag=1; return; } for(int i=0;i<4;i++) { int na=nowa+da[i]; int nb=nowb+db[i]; if(na>=1&&na<=n&&nb>=1&&nb<=m&&!v[na][nb]) { if((na==enx&&nb==eny)||(!mp[na][nb])) { //cout<<na<<" "<<nb<<endl; if(na==enx&&nb==eny)//判断当前的点是不是终点 { if(judge(prex,prey,nowa,nowb,na,nb))//判断从上一点点到终点要不要再转一次湾 { if(ctime<=2) { flag=1; return ; } } else if(ctime<=1) { flag=1; return ; } continue; } v[na][nb]=1; if(judge(prex,prey,nowa,nowb,na,nb)) { dfs(nowa,nowb,na,nb,ctime); } else { dfs(nowa,nowb,na,nb,ctime+1); } v[na][nb]=0; } } } } int main() { while(~scanf("%d %d",&n,&m)) { if(n==0&&m==0) break; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&mp[i][j]); } } scanf("%d",&k); for(int i=0;i<k;i++) { memset(v,0,sizeof(v)); flag=0; cnt=0; scanf("%d %d %d %d",&x,&y,&enx,&eny); if(mp[x][y]!=mp[enx][eny]||mp[x][y]==0||mp[enx][eny]==0) { printf("NO "); continue; } dfs(x,y,x,y,0); if(flag) printf("YES "); else printf("NO "); } } return 0; } /* 另一个思路： 我的同学说可以拿一个数组记录，起点到任意点的最短转弯次数，也是dfs，多加了一个数组记录转弯次数，每次都 更新成最短的转弯次数 */
C题目：
题目要求：求有多少个连通块（8连通）
思路：bfs
代码：
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#define ll __int64
using namespace std;
int n,m;
char a[105][105];
int dx[]={0,0,1,-1,1,-1,-1,1};
int dy[]={1,-1,0,0,1,-1,1,-1};
void bfs(int x,int y)
{
a[x][y]='*';
for(int i=0;i<8;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0&&nx<n&&ny>=0&&ny<m)
{
if(a[nx][ny]=='@')
{
bfs(nx,ny);
}
}
}
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
if(n==0&&m==0) break;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]=='@')
{
//cout<<i<<" "<<j<<endl;
bfs(i,j);
/*for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cout<<a[i][j];
}
cout<<endl;
}*/
ans++;
}
}
}
cout<<ans<<endl;
}
return 0;
}
D题：
E题：暴力枚举到最大的数，然后存到数组里，打表
代码：
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#define ll __int64
using namespace std;
int jc(int a)
{
if(a==0) return 1;
int ans=1;
for(int i=a;i>=1;i--) ans*=i;
return ans;
}
int main()
{
cout<<1<<endl;
cout<<2<<endl;
cout<<145<<endl;
cout<<40585<<endl;
return 0;
}
F题：
直接看代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <string> #include <queue> #include <map> #include <vector> #define ll __int64 const int maxn=10000+10; using namespace std; int n; int cnt; char ans[25]; /* 个人觉得这题的难点，就是点这个符号，碰到点这个符号的话，判断到点的话，sum-num就是没有点时候的，然后在连接点之间的数变成nxt，sum-num在加或者减去这个数 （nxt） 取决于除了第点之外的第一个符号。 */ void dfs(int num,int sum,int d)//num代表前面一个数，sum表示前面数的和，d表示深度 ,或者表示当前的数字 { /*for(int i=2;i<=d;i++) cout<<ans[i]<<" "; cout<<endl;*/ //cout<<num<<" "<<sum<<" "<<d<<endl; if(d==n+1) { if(sum==0) { cnt++; if(cnt<=20) { cout<<"1 "; for(int i=2;i<=n;i++) { cout<<ans[i]<<" "<<i<<" "; } cout<<endl; } } return; } ans[d]='+'; dfs(d,sum+d,d+1); ans[d]='-'; dfs(d,sum-d,d+1); int nxt; ans[d]='.'; if(d>9) { nxt=num*100+d; } else nxt=num*10+d; int k=d-1; while(ans[k]=='.'&&k>=1) k--;//找到第一个不为.的符号 if(k==0)//如果前面没有找到不为.的符号，那就是代表前面的都是连在一起的 { dfs(nxt,nxt,d+1); } else if(ans[k]=='-') { dfs(nxt,sum+num-nxt,d+1); } else { dfs(nxt,sum-num+nxt,d+1); } } int main() { while(~scanf("%d",&n)) { cnt=0; dfs(1,1,2); cout<<cnt<<endl; } return 0; }
G题：
H题：
题目要求：#的位置可以放棋子，要让棋子不同行不同列，我们就枚举每一个行，深搜
代码：
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#define ll __int64
using namespace std;
char a[105][105];
int vr[105];
int vl[105];
int v[105][105];
int cnt=0;
int n,m;
void dfs(int x,int d) //遍历到第x行
{
if(d==m)
{
cnt++;
return;
}
if(x>=n) return;
for(int j=0;j<n;j++)
{
if(vl[j]==0&&a[x][j]=='#')//vl表示j列上有没有放东西
{
vl[j]=1;
dfs(x+1,d+1);
vl[j]=0;
}
}
dfs(x+1,d);//x行算完之后，你接着算x+1行的！！！！！很重要，本题最难的地方
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
cnt=0;
if(n==-1&&m==-1) break;
memset(vr,0,sizeof(vr));
memset(vl,0,sizeof(vl));
int flag=1;
int x=105,y=105;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>a[i][j];
if(a[i][j]=='#'&&flag)
{
x=i;
flag=0;
}
}
}
if(flag)
{
cout<<"0"<<endl;
continue;
}
dfs(0,0);
cout<<cnt<<endl;
}
return 0;
}
I题：
题目要求：
思路：找规律
代码:
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#define ll __int64
using namespace std;
ll f[36];
int main()
{
f[1]=2;
for(int i=2;i<=35;i++)
{
f[i]=3*f[i-1]+2;
}
int n;
while(~scanf("%d",&n))
{
cout<<f[n]<<endl;
}
return 0;
}
J题：
题目要求：S点经过T秒能不能到D
思路：dfs计算所有路线的情况，看看是否有等于T的路，但是如果没有剪枝的话，就会一直TML，
一个矩形
S。。。。
。。。。D
。。。。。
。。。。。
。。。。。
把他们坐标的和为偶数的标为0，奇数的标为1，每个0到1都要奇数步，1到1或者0到0都是偶数步数，就是两个坐标的奇偶性不同，就是奇数步，相同的话就是偶数步，所以如果题目要求的t和SD点的步数奇偶不一样的话就直接NO，还有如果两点的距离大于T的话，也直接NO
代码
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#define ll __int64
using namespace std;
int n,m,t;
int flag=0;
char a[105][105];
int v[105][105];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int x,int y,int d)
{
if(d==t&&a[x][y]=='D')
{
flag=1;
return;
}
if(d>=t) return;
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0&&nx<n&&ny>=0&&ny<m)
{
if(!v[nx][ny]&&a[nx][ny]!='X')
{
v[nx][ny]=1;
dfs(nx,ny,d+1);
v[nx][ny]=0;
if(flag) return;
}
}
}
}
int main()
{
while(~scanf("%d %d %d",&n,&m,&t))
{
flag=0;
if(n==0&&m==0&&t==0) break;
int x,y;
int enx,eny;
memset(v,0,sizeof(v));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
if(a[i][j]=='S')
{
x=i;y=j;
}
if(a[i][j]=='D')
{
enx=i;eny=j;
}
}
}
if(abs(x-enx)+abs(y-eny)>t||(x+y+enx+eny+t)%2==1)
{
cout<<"NO"<<endl;
continue;
}
v[x][y]=1;
dfs(x,y,0);
if(flag)
{
cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
}
return 0;
}
K题：
题目要求：就是【key】 value
思路：hash（不会），暴力，map的话会报内存，又学了下stl，string s，
s.find（r） 找s中r的位置，否则返回s.end
s.erase（r，n） 从r这个位置开始，删除n个；
s.substr（l，n） 从l开始长度为n的字符分离出来
代码：
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#define ll __int64
using namespace std;
struct ans
{
string k,v;
}ans[100010];
int main()
{
int m,l,r;
string s,a,b;
int cnt=1;
while(getline(cin,s)&&s!="@END@")
{
int len=s.size();
int l,r;
for(int i=0;i<len;i++)
{
if(s[i]=='[')
{
l=i;break;
}
}
for(int i=0;i<len;i++)
{
if(s[i]==']')
{
r=i;break;
}
}
for(int i=l+1;i<r;i++) a+=s[i];
for(int i=r+2;i<len;i++) b+=s[i];
//cout<<a<<" "<<b<<endl;
ans[cnt].k=a;
ans[cnt++].v=b;
a="";b="";
}
cin>>m;
getline(cin,s);
for(int i=0;i<m;i++)
{
int flag=0;
getline(cin,s);
int tt=0;
if(s[0]=='[')
{
tt=1;
s.erase(0,1);
s.erase(s.size()-1,1);
for(int i=1;i<cnt;i++)
{
if(ans[i].k==s)
{
cout<<ans[i].v<<endl;
flag=1;
break;
}
}
}
if(tt==0)
{
for(int i=1;i<cnt;i++)
{
if(ans[i].v==s)
{
cout<<ans[i].k<<endl;
flag=1;
break;
}
}
}
if(!flag) cout<<"what?"<<endl;
}
return 0;
}
L题目：
题目要求：n*n的棋盘，放n个棋子，任意两个不能同一行，同一列，同一对角线
其实和H题差不多，就是加上一个对角线的判断，还有一点不用就是他不用枚举每行，因为它的数量是n说明每行都要放棋子的
代码：
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#define ll __int64
using namespace std;
int vl[11];
int a[11][11];
int n;
int cnt=0;
bool judge(int r,int l)
{
for(int i=1;;i++)
{
if(r-i<0||l-i<0) break;
if(a[r-i][l-i]) return false;
}
for(int i=1;;i++)
{
if(l+i>=n||r+i>=n) break;
if(a[r+i][l+i]) return false;
}
for(int i=1;;i++)
{
if(l-i<0||r+i>=n) break;
if(a[r+i][l-i]) return false;
}
for(int i=1;;i++)
{
if(l+i>=n||r-i<0) break;
if(a[r-i][l+i]) return false;
}
return true;
}
void dfs(int x,int d)
{
if(d==n)
{
cnt++;
//cout<<cnt<<endl;
return ;
}
if(x>=n) return;
for(int j=0;j<n;j++)
{
if(!vl[j]&&judge(x,j))
{
// cout<<x<<" "<<j<<endl;
vl[j]=1;
a[x][j]=1;
dfs(x+1,d+1);
vl[j]=0;
a[x][j]=0;
}
}
}
int main()
{
int num[11]={1,1,0 ,0 ,2 ,10 ,4 ,40 ,92 ,352 ,724};
while(~scanf("%d",&n))
{
if(n==0) break;
/*dfs(0,0);
cout<<cnt<<endl;*/
cout<<num[n]<<endl;
}
return 0;
}
M题目：
题目要求：输入火车进站的数列，和出站的数列，问是否满足合理的情况
stack题目
代码：
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define ll __int64
using namespace std;
vector<string> ans;
int main()
{
stack<char> s;
int n;
int v[10];
while(~scanf("%d",&n))
{
char a[105];
char b[105];
cin>>a>>b;
s.push(a[0]);
ans.push_back("in");
int i=1;
int len=strlen(a);
int j=0;
int flag=1;
while(!s.empty())
{
if(s.size()&&b[j]==s.top())
{
s.pop();
ans.push_back("out");
if(j==n-1)
{
flag=1;
break;
}
j++;
if(!s.size())
{
if(i==n)
{
flag=0;
break;
}
s.push(a[i]);
i++;
ans.push_back("in");
}
}
else
{
if(i==n)
{
flag=0;
break;
}
//cout<<a[i]<<endl;
s.push(a[i]);
i++;
ans.push_back("in");
}
}
if(flag)
{
printf("Yes.
");
for(int i=0;i<ans.size();i++) cout<<ans[i]<<endl;
}else
{
printf("No.
");
}
printf("FINISH
");
ans.clear();
while(s.size()) s.pop();
}
return 0;
}
---恢复内容结束---