牛客小白月赛17

墨蓝 2022-12-23 07:27 137阅读 0赞

### 牛客小白月赛 17 ###

#### A 小 sun 的假期 ####

##### 题目描述 #####

小 sun 非常喜欢放假，尤其是那种连在一起的长假，在放假的时候小 sun 会感到快乐，快乐值等于连着放假的天数，现在小 sun 把他的安排表告诉你，希望你告诉他在他的安排表中， 他的最大快乐值。

当某天没有安排的时候就是放假。

###### 输入描述 ######

> 第一行两个数 n,m，代表总共有 n 天，m 个安排。
> 
> 接下来有 m 行，每行是一个安排 l,r，代表从第 l 天到第 r 天，小 sun 有安排了。
> 
> 安排可能会重复。

###### 输出描述 ######

> 输出一行，在这个安排表中，小 sun 最大的快乐值。

###### 示例 1 ######

输入

> 5 1  
> 2 3

输出

> 2

###### 备注 ######

> 数据范围：  
> n ≤ 1e9, m ≤ 1e5  
> n1 ≤ l, r ≤ n

##### 思路 #####

把所有区间按左端点从小到大排序，然后遍历所有区间  
用一个变量储存当前遍历过的区间的最大右端点，一个变量储存假期的最大值  
如果遍历当前的区间时  
当前区间的左端点比之前遍历过的区间的最大右端点还大  
说明当前的区间和之间的区间之间是有假期的，每次遇到这种有假期的情况就计算一下这段的假期的天数并且维护一下假期的最大值，然后维护一下最大右端点的值  
如果当前区间左端点没有之前遍历过的最大右端点大  
就直接维护一下最大右端点的值  
然后再算上第一段区间和第一天间的假期和最后一段区间和最后一天的假期就可以了

##### 代码 #####

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    struct arrange
    { 
    	int l;
    	int r;
    };
    
    bool cmp(arrange a, arrange b)
    { 
    	if (a.l == b.l)
    	{ 
    		return a.r < b.r;
    	}
    	return a.l < b.l;
    }
    
    int main()
    { 
    	int n, m;
    	scanf("%d%d", &n, &m);
    	arrange arr[m];
    	for (int i = 0; i < m; i++)
    	{ 
    		scanf("%d%d", &arr[i].l, &arr[i].r);
    	}
    	sort(arr, arr + m, cmp);
    
    	// 计算第一段区间和第一天之间的假期
    	int max = arr[0].l - 1;
    
    	// 初始化最大右端点
    	int right = arr[0].r;
    	for (int i = 1; i < m; i++)
    	{ 
    		if (arr[i].l > right)
    		{ 
    			max = max > arr[i].l - right - 1 ? max : arr[i].l - right - 1;
    			right = arr[i].r;
    		}
    		else
    		{ 
    			right = right > arr[i].r ? right : arr[i].r;
    		}
    	}
    
    	// 计算最后一段区间和最后一天之间的假期
    	max = max > n - right ? max : n - right;
    	printf("%d\n", max);
    }

#### B 扫雷 ####

##### 题目描述 #####

小 sun 上课的时候非常喜欢玩扫雷。他现小 sun 有一个初始的雷矩阵，他希望你帮他生成一个扫雷矩阵。

扫雷矩阵的每一行每一列都是一个数字，每个数字的含义是与当前位置相邻的 8 个方向中，有多少个雷（在下图中，雷用*表示）；如果当前位置就是雷的话，仍输出一个*。

比如初始的雷矩阵如下：  
…  
…\*\*  
\*.\*.  
.\*.\*  
对应的数字矩阵为：  
0122  
13\*\*  
\*4\*4  
2\*3\*

###### 输入描述 ######

> 第一行两个整数 n,m，代表矩阵有 n 行 m 列
> 
> 接下来共 n 行，每行 m 个字符

###### 输出描述 ######

> 输出共 n 行 m 列，为扫雷矩阵。

###### 示例 1 ######

输入

> 4 4  
> …  
> …\*\*  
> \*.\*.  
> .\*.\*

输出

> 0122  
> 13\*\*  
> \*4\*4  
> 2\*3\*

###### 示例 2 ######

输入

> 3 4  
> …  
> \*…\*  
> .\*.\*

输出

> 1111  
> \*23\*  
> 2\*3\*

##### 思路 #####

水题，遍历一遍统计一下即可，本人这题代码写的比较烂，不喜勿喷

##### 代码 #####

#include <iostream>
    #include <cstdio>
    using namespace std;
    int main()
    { 
    	int m, n;
    	scanf("%d%d", &m, &n);
    	char s[m + 2][n + 2];
    	char s2[m + 2][n + 2];
    	getchar();
    	for (int i = 1; i <= m; i++)
    	{ 
    		scanf("%s", &s[i]);
    	}
    	for (int i = 1; i <= m; i++)
    	{ 
    		for (int j = 1; j <= n; j++)
    		{ 
    			if (s[i][j - 1] == '.')
    			{ 
    				s2[i][j] = '0';
    			}
    		}
    	}
    	for (int i = 1; i <= m; i++)
    	{ 
    		for (int j = 1; j <= n; j++)
    		{ 
    			if (s[i][j - 1] == '*')
    			{ 
    				s2[i - 1][j - 1]++;
    				s2[i - 1][j]++;
    				s2[i - 1][j + 1]++;
    				s2[i][j + 1]++;
    				s2[i + 1][j]++;
    				s2[i + 1][j + 1]++;
    				s2[i + 1][j - 1]++;
    				s2[i][j - 1]++;
    			}
    		}
    	}
    	for (int i = 1; i <= m; i++)
    	{ 
    		for (int j = 1; j <= n; j++)
    		{ 
    			if (s[i][j - 1] == '*')
    			{ 
    				printf("*");
    			}
    			else
    			{ 
    				printf("%c", s2[i][j]);
    			}
    		}
    		printf("\n");
    	}
    }

#### C 异或和 ####

##### 题目描述 #####

小 sun 非常的喜欢数字，现在他想到了一个新问题：给你一个数列，想你帮他算算，这个数列中，出现次数为奇数个的数字的异或和。

###### 输入描述 ######

> 第一行是一个整数 n  
> 接下来一行，n 个整数 ai，代表整个数列

###### 输出描述 ######

> 一行，代表出现次数为奇数个的数字的异或和

###### 示例 1 ######

输入

> 5  
> 1 2 3 4 4

输出

> 0

###### 示例 2 ######

输入

> 5  
> 1 1 2 3 3

输出

> 2

###### 备注 ######

> 数据范围：  
> 1≤n≤10000000  
> 1≤ai≤1e9
> 
> 注意数据较大，cin 会 T 掉

##### 思路 #####

水题，只需要把所有输入的数做一下异或即可  
因为出现次数为偶数的数字异或之后会抵消掉，所以最后的结果就是所有出现次数为奇数的数字的异或和

##### 代码 #####

#include <iostream>
    #include <cstdio>
    using namespace std;
    int main()
    { 
    	int n;
    	scanf("%d", &n);
    	int res = 0;
    	int t;
    	for (int i = 0; i < n; i++)
    	{ 
    		scanf("%d", &t);
    		res ^= t;
    	}
    	cout << res << endl;
    }

#### D 解密 ####

##### 题目描述 #####

小 sun 为了考试最近正在复习密码学，他现在遇到了一个问题：有一个由大小写字母组成的密文，要解密成明文。小 sun 知道怎么算，但是小 sun 很懒，他并不想算，所以他想让你帮他算算。

加密算法如下：

若明文为 x，密文 c 为  
C≡k1∗x+k2(mod 26)  
二十六个英文字母依次标号为 0~25，比如 A（a）为 0，Z（z）为 25

###### 输入描述 ######

> 第一行，两个整数 k1,k2  
> 第二行一个字符串，代表密文（长度不超过 1000）  
> 保证 gcd(k1,26)=1

###### 输出描述 ######

> 输出一行字符串，为解密后的字符串

###### 示例 1 ######

输入

> 45 66  
> RmppuQuzpt

输出

> HelloWorld

###### 备注 ######

> k1,k2 均在 int 以内  
> 密文仅包含大小写字母 A(a)~Z(z)  
> 大写字母输出大写字母，小写字母对应输出小写字母

##### 思路 #####

由题意易得明文和密文之间是双射的（一一对应）的，所以我们只要根据 k1,k2 找到 26 个字母明文密文之间的对应关系然后再还原即可，然后还原的时候注意一下大小写就好

##### 代码 #####

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    int main()
    { 
    	int k1, k2;
    	char s[1005];
    	int a[26];
    	scanf("%d%d", &k1, &k2);
    	getchar();
    	scanf("%s", s);
    	int len = strlen(s);
    	int t;
    	for (int i = 0; i < 26; i++)
    	{ 
    		a[(k1 * i + k2) % 26] = i;
    	}
    	for (int i = 0; i < len; i++)
    	{ 
    		if (s[i] >= 'A' && s[i] <= 'Z')
    		{ 
    			s[i] = 'A' + a[t = s[i] - 'A'];
    		}
    		else
    		{ 
    			s[i] = 'a' + a[t = s[i] - 'a'];
    		}
    	}
    	printf("%s\n", s);
    }

#### F 小黄鸭 ####

##### 题目描述 #####

小 sun 的寝室有一只小黄鸭，小黄鸭浮在水面上的样子特别可爱，现在小 sun 有一个问题：

为了简单，我们把小黄鸭视为一个均匀的球体，它浮在水面上的样子大概为：

![小黄鸭][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeDYwcnp2dmJq_size_16_color_FFFFFF_t_70_pic_center]

图中黑色的线即为水平线，灰色的部分为没在水中的部分，现在你要求的是，这个球体浮在水面上的部分的高度（即为图中的 h）。

高度定义为：一端在圆上，一端在水平线上且过圆心切垂直于水平线的线段长。

浮力定律：物体在液体中所获得的浮力，等于物体所排出液体的重量。（水的密度为 1）

###### 输入描述 ######

> 第一行两个整数：R，m
> 
> 代表球体的半径与质量

###### 输出描述 ######

> 一行实数，代表浮在水面上的高度值，请保留两位小数。

###### 示例 1 ######

输入

> 33 37

输出

> 65.40

###### 备注 ######

> 1≤R,m≤100

##### 思路 #####

题目大意就是找到水中的体积和小黄鸭质量相同的时候水面上的高度  
我们需要做一个浮点二分去找到体积和质量相同时的高度  
我们需要用高度计算出体积，求水面下的体积的方法是一个经典的定积分求旋转体体积的问题  
积分过程大概如下：  
首先我们二分水面下的高度，计为 h，将水面下方的物体垂直的分为一片一片的小圆柱体，然后积分区间就为\[0,h\],设积分变量为 x，可以通过 x 计算出小圆柱体的半径，然后再对 x 积分，积分之后的结果为 π \* (R \* h^2 - h^3/3) (R 为球体的半径)

##### 代码 #####

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    using namespace std;
    int main()
    { 
    	double PI = 3.14159265358979;
    	double R, m;
    	cin >> R >> m;
    	double l = 0, r = 2 * R;
    	while (r - l > 1e-4)
    	{ 
    		double mid = (l + r) / 2;
    		if (PI * (R * mid * mid - mid * mid * mid / 3) > m)
    			r = mid;
    		else
    			l = mid;
    	}
    	printf("%.2lf\n", 2 * R - l);
    }

#### I 坐电梯 ####

##### 题目描述 #####

小 sun 非常懒，所以他非常喜欢坐电梯，但是他发现了一个问题：当他在 k 楼想要坐电梯去 1 楼时，如果比他高的楼层有人想坐电梯去 1 楼，他就必须等待，直到电梯把他楼上的人接完了，才能到他的楼层来接他，于是他非常的苦恼。现在他想问问你，如果他知道某个时刻所有想坐电梯的人所在的楼层，他要等多久电梯才能到他的楼层。

关于电梯：  
电梯最开始在 1 楼，每一秒可以上升，或者下降一个楼层。  
在同一时刻有多个请求时，电梯会优先处理最高楼层的请求。

###### 输入描述 ######

> 第一行，两个整数：n，k，代表在当前时刻总共有 n 个去 1 楼的请求，小 sun 在第 k 楼，数据保证 k 不为 1  
> 第二行，共 n 个整数 ai，每个整数代表一个请求所在的层数。

###### 输出描述 ######

> 输出一行，他要等待的时间（秒）

###### 示例 1 ######

输入

> 5 3  
> 1 2 3 5 5

输出

> 6

###### 备注 ######

> 数据范围：  
> 1 ≤ n ≤ 1e6  
> 2 ≤ k ≤ 1e8  
> 1 ≤ ai ≤ 1e8

##### 思路 #####

水题，统计出最高的楼层，然后结果就是从 1 楼到最高楼层再加上从最高层到第 k 层的时间

##### 代码 #####

#include <iostream>
    #include <cstdio>
    using namespace std;
    int main()
    { 
    	int n, k;
    	scanf("%d%d", &n, &k);
    	int max = 0;
    	int t;
    	for (int i = 0; i < n; i++)
    	{ 
    		scanf("%d", &t);
    		max = max > t ? max : t;
    	}
    	cout << (2 * max - k - 1) << endl;
    }

##### 以上 #####

ヾ(≧∪≦\*)ノ〃

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeDYwcnp2dmJq_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/1d56bb662f234bc28b9f16cbd94fd113.png