首页 > 代码库 > 暑期集训7/16
暑期集训7/16
---恢复内容开始---
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:\n",cnt++);
num[1]=1;
dfs(1);
cout<<endl;
}
return 0;
}
B题目：
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题：
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.\n");
for(int i=0;i<ans.size();i++) cout<<ans[i]<<endl;
}else
{
printf("No.\n");
}
printf("FINISH\n");
ans.clear();
while(s.size()) s.pop();
}
return 0;
}
---恢复内容结束---
暑期集训7/16
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。