220127总结

2023-10-06 18:22:10

220127总结

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

题解

~~不知道什么题目~~（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);
	}
}
```

奇怪的电梯（lift）

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

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

搜就完了

当当前步数多于等于最小步数就直接剪枝否则TLE
当当前楼层是曾经来过的楼层就直接剪枝否则MLE（
记得搜完一个要回溯一下否则洛谷上会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

产生数（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';
			}
		}
	}
}
```
家庭问题

~~打完三道题的题面之后才发现今天发的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;
}
```

码农公寓

220127总结

题解

相关文章