第二次双周赛
7-1 输出全排列
-
知识点：应该不是要用函数但是函数真好用
next_permutation() 产生全排列
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
char ch[1000];
cin>>n;
for(int i=0;i<n;i++)
ch[i]=i+1+'0';
ch[n]='\0';
do
{
cout<<ch<<endl;
} while(next_permutation(ch,ch+n));
return 0;
}
7-2 山
- 知识点：dfs
#include<bits/stdc++.h>
using namespace std;
int m,n,ans=0;
int mp[10005][10005];
int xx[5]={0,1,0,-1};
int yy[5]={1,0,-1,0};
void dfs(int i,int j)
{
mp[i][j]=0;
for(int k=0;k<4;k++)
{
int nx=i+xx[k];
int ny=j+yy[k];
if(nx>=0&&nx<m&&ny>=0&&ny<n)
{
if(mp[nx][ny]==1)
dfs(nx,ny);
}
}
}
int main()
{
cin>>m>>n;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cin>>mp[i][j];
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(mp[i][j]==1)
{
dfs(i,j);
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
7-3 跳跃
- 知识点：dfs
#include<bits/stdc++.h>
using namespace std;
int n;
int vis[50005]={0};
bool flag=false;
void jump(int start,int m[])
{
if(m[start]==0&&start<n&&start>=0)
flag=true;
if(vis[start]==0&&start>=0&&start<n)
{
vis[start]=1;
jump(start+m[start],m);
jump(start-m[start],m);
}
}
int main()
{
int start;
int m[50005];
cin>>n;
for(int i=0;i<n;i++)
cin>>m[i];
cin>>start;
jump(start,m);
if(flag)
cout<<"True"<<endl;
else
cout<<"False"<<endl;
return 0;
}
7-4 最长光路
- 知识点：dfs
- 思路：如果两次经过同一个格子，且光照向同一个方向，就说明是环路。
#include <iostream>
using namespace std;
int toward[4][2] = {
{-1, 0},
{0, 1},
{1, 0},
{0, -1}
};
string map[500];
int main() {
int N, M, start_x, start_y, max_sum = 0, max_light = 0;
cin >> N >> M;
for (int i = 0; i < N; i++)
cin >> map[i];
cin >> start_x >> start_y;
for (int i = 0; i < 4; i++) {
int light = i, cur_x = start_x - 1, cur_y = start_y - 1, sum = 1;
while (true) {
cur_x += toward[light][0];
cur_y += toward[light][1];
sum++;
if (cur_x == start_x - 1 && cur_y == start_y - 1 && light == i) {
switch (i)
{
case 0:
putchar('U');
break;
case 1:
putchar('R');
break;
case 2:
putchar('D');
break;
case 3:
putchar('L');
break;
default:
break;
}
putchar('\n');
cout << "COOL";
return 0;
}
if (cur_x < 0 || cur_x >= N || cur_y < 0 || cur_y >= M) {
sum--;
break;
}
else if (map[cur_x][cur_y] == '.')
continue;
else if (map[cur_x][cur_y] == 'C') {
sum--;
break;
}
else if (map[cur_x][cur_y] == '\\') {
switch (light)
{
case 0:
light = 3;
break;
case 1:
light = 2;
break;
case 2:
light = 1;
break;
case 3:
light = 0;
break;
default:
break;
}
}
else if (map[cur_x][cur_y] == '/') {
switch (light)
{
case 0:
light = 1;
break;
case 1:
light = 0;
break;
case 2:
light = 3;
break;
case 3:
light = 2;
break;
default:
break;
}
}
}
if (max_sum < sum) {
max_sum = sum;
max_light = i;
}
}
switch (max_light)
{
case 0:
putchar('U');
break;
case 1:
putchar('R');
break;
case 2:
putchar('D');
break;
case 3:
putchar('L');
break;
default:
break;
}
putchar('\n');
cout << max_sum;
return 0;
}
7-5 回文数文回
- 知识点：应该不是要暴力但是暴力大法好！
- 思路：因为是回文，且固定9位数，所以只用枚举前5位即可
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e9+5;
const int st=1e8;
int main(){
int n;
int sum=0;
cin>>n;
string s;
s=to_string(n);//把int转化成string
int a=s[0]-'0';
for (int a1=1; a1<=a; a1++)
for (int b1=0; b1<=9; b1++)
for (int c1=0; c1<=9; c1++)
for (int d1=0; d1<=9; d1++)
for (int e1=0; e1<=9; e1++){
int k=a1*100000000+b1*10000000+c1*1000000+d1*100000+e1*10000+d1*1000+c1*100+b1*10+a1;
if (k<=n){
sum++;
}
}
cout<<sum<<endl;
return 0;
}