220127总结

• 又是上来就打模拟赛的一天

题解

1. 不知道什么题目（Area）

   【题目描述】编程计算由”*“号围成的下列图形的面积。面积计算方法是统计*号所围成的闭合曲线中水平线和垂直线交点的数目。如下图所示，在10*10的二位数组中，有“*”围住了15个点，因此面积为15

   【样例输入】

   0 0 0 0 0 0 0 0 0 0
   0 0 0 0 1 1 1 0 0 0
   0 0 0 0 1 0 0 1 0 0
   0 0 0 0 0 1 0 0 1 0
   0 0 1 0 0 0 1 0 1 0
   0 1 0 1 0 1 0 0 1 0
   0 1 0 0 1 1 0 1 1 0
   0 0 1 0 0 0 0 1 0 0
   0 0 0 1 1 1 1 1 0 0
   0 0 0 0 0 0 0 0 0 0

   【样例输出】

   15

   一看题目就想到了泛洪算法

   再一看这题，诶这不是信竞第一次试讲时候的题目吗（

   • 泛洪算法（FloodFill）

     属于一种填充算法，就是在一个点向周围四个/八个点递归地寻找没有被填充的点。

     在这道题的应用是，从左上角开始填充，遇上“墙”就停止。

     最后检查填充的点的个数，用总数减去被填充的点就是面积

   不过还有一些需要注意的地方

   1. 数组需要开得更大，上下左右都扩充到14*14，因为第一圈全围上“墙”防止漏出去，第二圈为可填充区防止左上角被围上（真正的原题输入数据在2~12）
   2. 不能遇到墙就停，因为这个墙可能有厚度，还需要把连续的墙给填充上
   3. 找墙的时候需要检查周围八个点，因为可能会有角落的墙没被填充
   4. 找面积的时候找周围四个点是不是墙就可以

   //四邻域方向
   int F[4][2] = {{1,0},{0,1},{0,-1},{-1,0}};
   //八邻域扩充的方向
   int f[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}};
   //t用来标注现在在找墙还是找路 
   void Search(int x,int y,int t){
   	//这个点找过了就返回 
   	if(B[x][y] == 1) return;
   	//如果在找墙但是这个点是路就返回 
   	if(t == 1 && A[x][y] == 0) return;
   	//标记这个点找过 
   	B[x][y] = 1;
   	//八邻域泛洪找连续的墙 
   	if(A[x][y] == -1){
   		for(int i = 0;i<4;i++){
   			if(A[x+F[i][0]][y+F[i][1]] == -1){
                   Search(x+F[i][0],y+F[i][1],-1);
               }
   		}
   		for(int i = 0;i<4;i++){
   			if(A[x+f[i][0]][y+f[i][1]] == -1){
                   Search(x+f[i][0],y+f[i][1],-1);
               } 
   		}
   		return;
   	}
   	//四邻域泛洪找路 
   	for(int i = 0;i<4;i++){
   		Search(x+F[i][0],y+F[i][1],0);
   	}
   }

2. 奇怪的电梯（lift）

   我996上的AC码交到洛谷上WA两个点…?我不理解.jpg事实证明996做出来的数据不行（bushi

   我似乎用的深搜做的…宽搜板子题…?

   搜就完了

   1. 当当前步数多于等于最小步数就直接剪枝否则TLE

   2. 当当前楼层是曾经来过的楼层就直接剪枝否则MLE（

   3. 记得搜完一个要回溯一下否则洛谷上会WA（然而996不会

   void Search(int k,int sum){
   	if(B[k]) return;//来过就剪
   	if(sum >= minM) return;//步数大于最小步数就剪
   	if(k<1 || k>n) return;//楼层不对就剪
   	if(k == b){//楼层对了就记录
   		minM = min(sum,minM);
   		return;
   	}
   	if(A[k] == 0) return;//这层楼动不了就回去
   	B[k] = 1;//标记
   	int step_ = A[k];
   	Search(k+step_,sum+1);
   	Search(k-step_,sum+1);
   	B[k] = 0;//回溯
   }
   //一个数据，非常好（bushi
   //输入
   //150 1 150
   //1 1 26 7 9 21 10 5 12 13 3 15 3 26 2 9 28 12 24 10 21 26 22 10 5 10 14 8 25 9 15 5 27 9 24 30 15 27 25 1 5 5 16 1 18 1 24 20 24 22 17 7 21 18 29 20 30 8 21 9 3 24 15 27 16 18 29 21 11 1 22 30 24 23 6 5 28 24 18 26 21 9 3 19 9 27 5 9 17 29 6 5 9 6 18 15 9 5 19 23 23 3 3 2 4 24 25 12 19 14 23 15 11 25 25 5 3 3 2 6 21 7 18 8 11 26 10 10 20 21 28 10 15 9 24 23 17 22 13 17 18 27 21 4 15 13 4 2 1 0
   
   //输出
   //14

3. 产生数（Produce）

   【问题描述】

   给出一个整数$\text{n}(n\leqslant 2000)$和$k$个变换规则$(k\leqslant 15)$。规则：

   ①1个数字可以变换为另一个数字；

   ②规则中，右边的数字不能为零。

   例如：$n=234,k=2$

   ​ 规则为：$2\rightarrow5,3\rightarrow 6$

   上面的整数234经过变换后可能输出的整数为（包括原数）：234，534，264，564共4种

   求经过任意次的变换（0次或多次），能产生多少个不同的整数。仅要求输出不同整数个数。

   【样例输入】

   234

   2

   2 5

   3 6

   【样例输出】

   4

   根据题中描述，“一个数字变成另一个数字”且“$k\leqslant 15$“，那么就可能出现一个数对应多种规则的情况

   因此可以开一个二维数组，第一维表示原数，第二维的第一个数表示原数对应的法则数量n，第二维的第2~n位就是对应的法则

   因为$n\leqslant 2000$是个四位数，所以可以开一个长为10000的数组记录四位以内的数字是否用过（洛谷上那个体太大了还不能通用

   还要检查最右边的数字是否为0

   char S[35];
   int B[10005];
   int poi[10];
   int guize[10][11];
   int cnt = 0;
   
   int TOINT(char s[]){
   	int r = 0;
   	for(int i = 0;i<strlen(s);i++){
   		r = r + (s[i]-'0') * pow(10,strlen(s)-i-1);
   	}
   	return r;
   }
   void Search(char s[]){
       //标记这个数已用
   	B[TOINT(s)] = 1;cnt++;
   	for(int i = 0;i<strlen(s);i++){
           //读第i位数
   		int t = s[i] - '0';
           //如果有规则就替换之后继续搜
   		if(guize[t][0] > 0){
   			for(int j = 1;j<=guize[t][0];j++){
                   //判断最后一位是不是0
   				if(i == strlen(s)-1 && guize[t][j] == '0') continue;
                   //替换
   				s[i] = guize[t][j] + '0';	
                   //如果生成过就回溯
   				if(B[TOINT(s)] == 1){
   					s[i] = t + '0';
   					continue;
   				}
   				Search(s);
                   //回溯
   				s[i] = t + '0';
   			}
   		}
   	}
   }

4. 家庭问题

   打完三道题的题面之后才发现今天发的PDF可以复制（

   【问题描述】
   有 n 个人，编号为 $1,2,\cdots ,n$，另外还知道存在 K 个关系。一个关系的表达为二元组$(\alpha,\beta)$形式，表示$\alpha,\beta$为同一家庭的成员。
   当 $n，k$ 和$k$ 个关系给出之后，求出其中共有多少个家庭、最大的家庭中有多少人？
   例如：$n＝6,k＝3$，三个关系为$(1,2),(1,3),(4,5)$
   此时，6 个人组成三个家庭，即：${1,2,3}$为一个家庭，${4,5}$为一个家庭，${6}$单独为
   一个家庭，第一个家庭的人数为最多。

   【输入格式】
   文件的第一行为$n,k$二个整数$(1 \leqslant n \leqslant 100)$（用空格分隔）
   接下来的 k 行，每行二个整数（用空格分隔）表示关系
   【输出格式】
   二个整数（分别表示家庭个数和最大家庭人数）
   【输入样例】
   6 3
   1 2
   1 3
   4 5
   【输出样例】
   3 3

   因为有n个人，但是这n个人不一定每个人都有家庭（？

   所以组完家庭之后剩下的人各自是一家

   然后每组关系，都有如下情况：

   1. 两个人都没有家：家庭数+1，这个家庭的人数为2，将两个人的编号放入这个家庭
   2. 一个人有家：没有家的人加入
   3. 两个人都有家：合并两个家庭然而我没写也过了（996上居然没做这类的数据

   int PEOPLE[105];
   //FAMILY第一维表示第i个家庭 第二维[0]表示家庭人数 
   int FAMILY[105][105];
   int familyNum = 0;
   
   int main(){
   	int n,k;
   	scanf("%d%d",&n,&k);
   	for(int i = 1;i<=n;i++) PEOPLE[i] = 1;
   	for(int i = 0;i<k;i++){
   		int u,v;
   		scanf("%d%d",&u,&v);
   		bool notInFam = true;
   		for(int j = 0;j<familyNum;j++){
   			int inNum = 0;
   			for(int k = 1;k<=FAMILY[j][0];k++){
   				if(FAMILY[j][k] == u){
   					inNum++;
   					notInFam = false; 
   				}else if(FAMILY[j][k] == v){
   					inNum++;
   					notInFam = false;
   				}
   			}
   			if(inNum == 1){
   				bool testU = false;
   				for(int k = 1;k<=FAMILY[j][0];k++){
   					if(FAMILY[j][k] == u) testU = true;
   				}
   				if(testU){
   					FAMILY[j][++FAMILY[j][0]] = v;
   				}else{
   					FAMILY[j][++FAMILY[j][0]] = u;
   				}
   			}
   			
   		}
   		if(notInFam){
   			FAMILY[familyNum][0] = 2;
   			FAMILY[familyNum][1] = u;
   			FAMILY[familyNum][2] = v;
   			familyNum++;
   		}
   	}
   	int maxFamilyMM = 1;
   	int maxFamilyID = 0;
   	for(int i = 0;i<familyNum;i++){
   		if(FAMILY[i][0] > maxFamilyMM){
   			maxFamilyMM = FAMILY[i][0];
   			maxFamilyID = i;
   		}
   		for(int j = 1;j<=FAMILY[i][0];j++){
   			PEOPLE[FAMILY[i][j]] = 0;
   		}
   	}
   	for(int i = 0;i<=n;i++){
   		familyNum += PEOPLE[i];
   	}
   	printf("%d %d",familyNum,maxFamilyMM);
   	return 0;
   }