第六次测训：17省4方格分割，17国1-36进制，17省3-承压计算，17省Ja2-九数算式，17省Ca1-迷宫

男娘i 2022-10-23 11:11 76阅读 0赞

### 17省4-方格分割 ###

[题目链接][Link 1].  
【关键词】dfs 二维数组  
【思路】  
以中心点(3 ,3)为原点,划分得到4个形状相等的象限,这使得很容易通过计算一个象限的情况而得到所有情况  
以中心点为起点使用dfs,每次同时遍历一个点以及与中心点的对称的点,最后将结果/4(总共有4个一样的象限嘛

#include<bits/stdc++.h>
    using namespace std;
    int outcome=0;
    int vis[7][7]={
        0};
    
    void dfs(int x,int y){
        
         if(x==0||x==6||y==0||y==6) {
        outcome++;
         return ;}
         vis[x][y]=1;
         vis[6-x][6-y]=1;
         if(!vis[x+1][y]) dfs(x+1,y);
         if(!vis[x-1][y]) dfs(x-1,y);
         if(!vis[x][y+1]) dfs(x,y+1);
         if(!vis[x][y-1]) dfs(x,y-1);
         vis[x][y]=0;
         vis[6-x][6-y]=0;
    
    
    }
    int main(){
        
        dfs(3,3);
        cout<<outcome/4;
    
    return 0;
    }

#include<iostream>
    
    using namespace std;
    
    int ans=0;//枚举记数
    int vis[7][7] = {
         0 };//标记已走过的点
    int mov[4][2] = {
         {
        1,0},//单位移动方向向量
                       {
        0,1},//从每个点可以往这四个方向走
                       {
        -1,0},
                       {
        0,-1} };
    
    void walk(int x, int y)
    {
        
        if (x == 0 || x == 6 || y == 0 || y == 6) {
        //已到边界，分割完毕
            ans++;
            return;
        }
        vis[x][y] = 1;//先标记
        vis[6 - x][6 - y] = 1;//中心对称的点也标记
        for (int i = 0; i < 4; i++)//走下一个点
        {
        
            //四个方向进行枚举，注意不能改变x和y的值，否则会影响到之后的回溯
            if (!vis[ x + mov[i][0] ][ y + mov[i][1] ]) {
        
                walk(x + mov[i][0], y + mov[i][1]);
            }
        }
        vis[x][y] = 0;//枚举完毕，清除标记
        vis[6 - x][6 - y] = 0;//对称点的标记也清除
    }
    
    int main()::
    {
        
        walk(3, 3);//中心点为（3,3）
        cout << ans / 4 << endl;//因为每种走法有3种重复
                                //所以同一种走法会走4次，数4次
        return 0;
    }

### 17国1-36进制 ###

[题目链接][Link 2].  
【思路】这个题是用草稿纸直接算出来

### 17省3-承压计算 ###

[题目链接][Link 3].  
【思路】我们可以从上到下递推出最后一层电子秤上的重量，求出最小的个最大的数字分别是72665198526.972961

135.349469和3.886331

根据题目的信息，最小值显示2086458231，根据这个数字我们可以计算出最大数字显示是多少。

#include<bits/stdc++.h>
    using namespace std;
    double a[30][30]={
        
                                 {
        7 },
                                {
        5, 8},
                               {
        7, 8, 8 },
                              {
        9, 2, 7, 2},
                             {
        8 ,1, 4, 9 ,1 },
                            {
        8 ,1, 8 ,8 ,4 ,1 },
                           {
        7, 9 ,6, 1, 4, 5, 4 },
                          {
        5, 6, 5, 5 ,6 ,9 ,5 ,6 },
                         {
        5, 5, 4, 7, 9 ,3, 5, 5 ,1 },
                        {
        7, 5 ,7 ,9 ,7, 4, 7, 3, 3, 1},
                       {
        4, 6 ,4 ,5, 5 ,8 ,8, 3 ,2, 4, 3 },
                      {
        1, 1 ,3, 3 ,1 ,6, 6, 5, 5 ,4, 4, 2 },
                     {
        9, 9 ,9, 2, 1, 9 ,1 ,9, 2, 9 ,5, 7, 9},
                    {
        4, 3, 3, 7 ,7 ,9 ,3 ,6 ,1 ,3 ,8 ,8, 3, 7 },
                   {
        3 ,6 ,8 ,1 ,5 ,3, 9, 5, 8 ,3 ,8 ,1, 8 ,3, 3},
                  {
        8 ,3, 2, 3, 3, 5 ,5, 8 ,5, 4 ,2 ,8, 6 ,7, 6, 9 },
                 {
        8, 1, 8, 1, 8, 4 ,6, 2, 2, 1 ,7 ,9 ,4, 2 ,3, 3 ,4 },
                {
        2, 8 ,4 ,2 ,2, 9 ,9, 2 ,8, 3 ,4 ,9 ,6, 3 ,9 ,4, 6, 9 },
               {
        7, 9 ,7, 4, 9, 7, 6, 6 ,2 ,8, 9 ,4, 1 ,8, 1 ,7, 2, 1, 6 },
              {
        9 ,2, 8 ,6 ,4, 2 ,7 ,9 ,5, 4, 1 ,2 ,5, 1 ,7, 3, 9 ,8, 3, 3 },
             {
        5, 2, 1 ,6 ,7 ,9, 3 ,2 ,8 ,9 ,5 ,5, 6, 6, 6 ,2, 1 ,8, 7, 9, 9 },
            {
        6, 7 ,1, 8, 8, 7 ,5, 3, 6 ,5 ,4 ,7, 3, 4 ,6 ,7, 8, 1, 3 ,2 ,7, 4},
          {
         2, 2, 6, 3, 5, 3, 4, 9 ,2, 4 ,5 ,7, 6, 6, 3 ,2 ,7, 2 ,4, 8, 5, 5, 4 },
          {
        7, 4, 4, 5, 8, 3, 3, 8, 1,8, 6, 3, 2, 1, 6, 2 ,6, 4 ,6, 3 ,8, 2, 9, 6},
         {
        1, 2, 4, 1, 3, 3, 5, 3, 4, 9 ,6, 3 ,8, 6 ,5, 9, 1, 5 ,3 ,2 ,6, 8 ,8, 5, 3 },
        {
        2, 2, 7, 9, 3, 3, 2, 8, 6, 9, 8, 4, 4, 9, 5, 8, 2, 6, 3, 4, 8, 4, 9, 3, 8, 8},
       {
        7 ,7 ,7 ,9 ,7 ,5 ,2 ,7 ,9 ,2 ,5 ,1 ,9 ,2 ,6 ,5 ,3 ,9 ,3 ,5 ,7 ,3 ,5 ,4 ,2 ,8 ,9 },
      {
        7 ,7 ,6 ,6 ,8 ,7 ,5 ,5 ,8 ,2 ,4 ,7 ,7 ,4 ,7 ,2 ,6 ,9 ,2 ,1 ,8 ,2 ,9 ,8 ,5 ,7 ,3 ,6 },
     {
        5 ,9 ,4 ,5 ,5 ,7 ,5 ,5 ,6 ,3 ,5 ,3 ,9 ,5 ,8 ,9 ,5 ,4 ,1 ,2 ,6 ,1 ,4 ,3 ,5 ,3 ,2 ,4 ,1}
    };
    int main(){
        
      int i,j;
      double maxx=0,minn=9999999;
      for(i=1; i<=29; i++){
        
    		for(j=0; j<=i; j++){
        
    			//如果为首尾两个数值话，直接自身/2运算
    			if(j==0){
        
    				a[i][j] += a[i-1][0]/2.0;
    			}else{
        
    			//正常两个数值进行向下除法加法运算
    				a[i][j] += a[i-1][j-1]/2.0 + a[i-1][j]/2.0;
    			}
    		}
    	}
    	for(i=0; i<=29; i++){
        
    		if(a[29][i]<minn){
        
    			minn = a[29][i];
    		}
    		if(a[29][i]>maxx){
        
    			maxx = a[29][i];
    		}
    	}
    	printf("%.0lf\n",2086458231/minn*maxx);
    
    
    
    
    return 0;}

答案：72665192664

### 17省Ja2-九数算式 ###

[题目链接][Link 4].  
【思路】考试是做这个题目，觉得比较繁琐，要写很多小函数，但是其实有思路了，就可以动手哇，别觉得烦。

[参考这位大佬的博客吧：][Link 5].

#include <stdio.h>
    #include <algorithm>
    
    using namespace std;
    int num=0;
    
    //判断个位是否为0或与高位重复
    int dup(int z)
    {
        
    	int n=z%10;			//个位
    
    	if (n==0)			//不能为0
    		return 1;
    
    	while (z>10)
    	{
        
    		z/=10;
    		if ( z%10==n )
    			return 1;
    	}
    	return 0;
    }
    
    //判断条件，当z满足从1到9全不重复返回0，否则返回1
    int check(int z)
    {
        
    	while (z>10)
    	{
        
    		if ( dup(z)==1 )
    			return 1;
    
    		z/=10;
    	}
    	return 0;
    }
    
    void p2(int *a,int i)
    {
        
    	int j,x=0,y=0,z;
    
    	for (j=0;j<=i;j++)
    		x=x*10+a[j];
    
    	for (j=i+1;j<=8;j++)
    		y=y*10+a[j];
    
    	z=x*y;
    
    	if ( z>123456789 && !check(z) )
    	{
        
    		num++;
    		//printf("%d*%d=%d\n",x,y,z); 1040254
    
    	}
    }
    
    void process(int *a)
    {
        
    	int i;
    	for (i=0;i<=7;i++)		//i代表乘号分割位置
    	{
        
    		p2(a,i);
    	}
    }
    
    int main()
    {
        
    	int n=9;
    	int a[]={
        1,2,3,4,5,6,7,8,9};
    
    	do
    	{
        
    		process(a);
    	} while (next_permutation(a,a+n));
    
    	printf("%d\n",num/2);
    
    	return 0;
    }

### 17省Ca1-迷宫 ###

[题目链接][Link 6].  
【思路】这个题，我一开始是草稿纸验算，结果是29，正确答案是31，漏了2个。参考了一下别人代码如下 [点我查看][Link 7].

#include<bits/stdc++.h> 
    using namespace std;
    int a[10][10]; 
    int ans = 0;
    string b[10];
    
    //对每个位置测试看是否能走出迷宫
    // x,y代表位置
    bool check(int x,int y)
    {
        
    //	走出迷宫 
    	if(x<0||x>9||y<0||y>9) return 1;
    //	如果此点被访问了,又被访问,说明在兜圈子 
    	if(a[x][y]==1) return 0;
    //	标记此点被访问过 
    	a[x][y]=1;
    	switch(b[x][y])
    		{
        
    			case 'U':return check(x-1,y);
    			case 'D':return check(x+1,y);
    			case 'L':return check(x,y-1);
    			case 'R':return check(x,y+1);
    			default:return 0;
    		}
    } 
    int main(){
        
    //	char b[10][];
    //	string b[10];
    	b[0]="UDDLUULRUL";
    	b[1]="UURLLLRRRU";
    	b[2]="RRUURLDLRD";
    	b[3]="RUDDDDUUUU";
    	b[4]="URUDLLRRUU";
    	b[5]="DURLRLDLRL";
    	b[6]="ULLURLLRDU";
    	b[7]="RDLULLRDDD";
    	b[8]="UUDDUDUDLL";
    	b[9]="ULRDLUURRR";
    	for(int i=0;i<10;i++)
    		{
        
    			for(int j=0;j<10;j++)
    			{
        
    //				每次测试新的位置，都把数组a全部元素重置为0
    //				不然有部分被置为1了 
    				memset(a,0,sizeof(a));
    				if(check(i,j))
    					ans++; 
    			}
    		}
    	cout<<ans<<endl;
    	return 0;
    }

[Link 1]: https://vijos.org/d/gadflycq/contest/60384b1af41362fb2497adac/5a700a22d3d8a103be7e0e6a
[Link 2]: https://vijos.org/d/gadflycq/contest/60384b1af41362fb2497adac/5aabe852d3d8a13712240c21
[Link 3]: https://vijos.org/d/gadflycq/contest/60384b1af41362fb2497adac/5a6f2d83d3d8a103be7e0da3
[Link 4]: https://vijos.org/d/gadflycq/contest/60384b1af41362fb2497adac/5c657c68f41362044c570106
[Link 5]: https://blog.csdn.net/qq_45281807/article/details/108837556
[Link 6]: https://vijos.org/d/gadflycq/contest/60384b1af41362fb2497adac/5c657485f41362044c570104
[Link 7]: https://blog.csdn.net/weixin_46021869/article/details/104183378