第二次双周赛

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;   
}