AtCoder Beginner Contest 255 A—E

A

题目描述

给定一个的$ \ 2 \times 2 \ $矩阵$ \ A \ $，输出其中的值$ \ A_{R,C} \ $。

题目分析

时间复杂度：$O(1)$。

输入就行嘞。

$Code$

int n, m;
int a[10][10];
 
int main()
{
	cin >> n >> m;
	
	for(int i = 1; i <= 2; i ++ )
		for(int j = 1; j <= 2; j ++ )
			cin >> a[i][j];
	
	cout << a[n][m] << endl;
 
	return 0;
}

$ \ $
$ \ $

B

题目描述

有$ \ N \ $个人在位置为$(X_i,Y_i)$的位置上。

其中有$ \ K \ $个人是特殊人~~(被选中的孩子)~~，能够发射光芒。

当一个人位于$ \ (x,y) \ $坐标发射半径为$ \ R \ $的光芒时候，能够照亮以$ \ (x,y) \ $为圆心，半径为$ \ R \ $的一个光圈（包括边界）。

找到最小的半径使得所有特殊人能够将所有人都照耀。

题目分析

时间复杂度：$O(nk)$。

要使得所有人都能够被照耀到，即需要求出每个人到特殊人距离的最小值（因为只用被一个特殊人照射即可，所以取最近的特殊人的位置），然后在这些最小值中取最大值即可。

$Code$

#define x first
#define y second

typedef pair<int, int> PII;
const int N = 1010;

int n, k;
int a[N];  // 特殊人对应的下标
PII b[N];  // 每个人的位置

int main()
{
	cin >> n >> k;
	
	for(int i = 0; i < k; i ++ )
	{
		cin >> a[i];
	}
	
	for(int i = 1; i <= n; i ++ )
	{
		int a, b;
		cin >> a >> b;
		b[i] = {a, b};
	}
	
	double ans = 0;
	
	for(int i = 1; i <= n; i ++ )
	{
		double res = 1e9;  // res求的是每个人到特殊人j的距离的最小值
		for(int j = 0; j < k; j ++ )
		{
			int u = a[j];  // 获取特殊人的下标
			
			res = min(res, sqrt(
			1.0 * (b[i].x - b[u].x) * (b[i].x - b[u].x) + 
			1.0 * (b[i].y - b[u].y) * (b[i].y - b[u].y))); 
		} 
        
		ans = max(ans, res);  // ans求的是所有最小值的最大值
	}
	
	printf("%.10f\n", ans);
	
	return 0;
}

$ \ $
$ \ $

C

题目描述

给定一个整数$ \ X \ $，如下的操作会被记为一次操作。

选择并做一下其中一项操作
- 给$ \ X \ $加$ \ 1 \ $
- 给$ \ X \ $减$ \ 1 \ $

给定一个首项为$ \ A \ $，公差为$ \ D \ $，一共$ \ N \ $项的等差数组$ \ S \ $。

问经过多少次操作才能将$ \ X \ $变为等差数组$ \ S \ $中的一个数。

题目分析

时间复杂度：$O(1)$。

分情况讨论即可。

详见代码注释。

$Code$

const int N = 110;

typedef long long LL;

int main()
{
	LL x, a, d, n;
	
	cin >> x >> a >> d >> n;
	
    // 当公差为0的时候，只需要判断x与首项的位置即可。
	if(d == 0)
	{
		cout << abs(x - a) << endl;
		return 0;	
	} 
	
    // 当公差小于0的时候，可以将这个单调递减的数列变为单调递增的数列，方便统一计算，就不同讨论公差小于0的情况哩
	if(d < 0)
	{
		d = -d;
		a -= (n - 1) * d;
	}
	
    // 当x小于首项a的时候，（由于当前的数列已经是公差大于0的数列，为单增的数列）
    // x----a----a+d-----a+2d-----...
    // 所以只需要计算x到a的距离即可
	if(x <= a) 
	{
		cout << a - x << endl;
		return 0;
	}
	
    // 当x大于数列最后一项的时候
    // ...----a+(n-2)d----a+(n-1)d----x
    // 所以只需要计算x到最后一项a + (n-1)d的距离即可
	if(x >= a + (n - 1) * d)
	{
		cout << x - a - (n - 1) * d << endl;
		return 0;
	}
	
    // 上述情况讨论完毕后，就只剩下x在数列中的情况了
    // ...----a+kd----x----a+(k+1)d-----...
    // 这种情况需要判断x到左边还是到右边的距离，取最小值即可
    // (x - a) % d就是x到左边的距离
    // d - (x - a) % d就是x到右边的距离
	LL pos = (x - a) % d;
	cout << min(pos, d - pos) << endl;
	
	return 0;
}

$ \ $
$ \ $

D

题目描述

给定一个数组$ \ N:A = (A_1,A_2,…,A_N) \ $，如下的操作会被记为一次操作。

首先，选择一个$ \ 1 \ $到$ \ N \ $中的一个位置$ \ A_i \ $。
接下来，选择其中一项进行操作
- 给$ \ A_i \ $加$ \ 1 \ $
- 给$ \ A_i \ $减$ \ 1 \ $

有$ \ Q \ $个询问。

每个询问如下：

找到使得数组$ \ N \ $中的每一个元素都变为$ \ X \ $的最小步骤为多少？

题目分析

时间复杂度：$O(1)$。

对于案例

1 2	N:6 11 2 5 5 X:5

如果暴力计算每个与$ \ X \ $的差的绝对值，那么是恐怖的$O(n^2)$。

因此需要优化。

如果我们对$ \ N \ $进行排序后：

1 2	N:2 5 5 6 11 X:5

我们能够发现对于数字$ \ 5 \ $来说，它之前的数$ \ A_i \ $一定小于$ \ 5 \ $，它之后的数$ \ A_j \ $一定大于$ \ 5 \ $，那么如果我们能够将某个数字$ \ A \ $比它小的所有数和比它大的所有数统计出来，就能优化计算。这就可以用到前缀和的知识了

如何优化计算？

首先不用判断正负号。

然后计算这个数前面的所有数变为X所需要的数字：$cnt(前面所有数的个数) \times X - sum(前面的所有数的和)$ 。

计算这个数后面的所有数变为X所需要的数字：$sum(后面的所有数的和) - cnt(后面所有数的个数) \times X$ 。

这里又要涉及到如何快速找到数$ \ A \ $的下标，可以使用二分

STL库函数

lower_bound/upper_bound二分

lower_bound的第三个参数传入一个元素x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）。

upper_bound的用法和lower_bound大致相同，唯一的区间就是查找的第一个大于x的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。

在有序int数组（元素放在下标1 ~ n）中查找大于等于x的最小整数的下标：

1	int i = lower_bound(a + 1, a + 1 + n, x) - a;

$Code$

const int N = 200010;

typedef long long LL;

int n, m;
int a[N];
LL s[N];

int main()
{
	cin >> n >> m;
	
	for(int i = 1; i <= n; i ++ ) cin >> a[i];
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];	

	while(m -- )
	{
		int x;
		cin >> x;
		int d1 = lower_bound(a + 1, a + n + 1, x) - a;  // 找到第一个大于或者等于x的下标
		int d2 = upper_bound(a + 1, a + n + 1, x) - a;  // 找到第一个大于x的下标
		
		cout << (LL)(d1 - 1) * x - s[d1 - 1] +
		s[n] - s[d2 - 1] - (LL)(n - d2 + 1) * x << endl;
	}
	
	return 0;
}

$ \ $
$ \ $

E

题目描述

给定长度为$ \ N - 1 \ $的数组$S = (S_1,S_2,…,S_{N - 1})$，以及$ \ M \ $个被称为幸运数的数字。

一个长度为$ \ N \ $的数组$A = (A_1, A_2,…,A_N)$的数组，满足如下情况：

$A_i + A_{i + 1} = S_i$，对于$i \in [1,N - 1]$都成立

找到一组数组$ \ A \ $，使得其中包含的幸运数字足够多。

题目分析

思路来自于这位佬

时间复杂度：$O(nmlogn)$。

枚举每一位$\ A_i \ $为幸运数字的情况，那么$ \ A \ $数组的第一位就可以被计算出来（因为只要确定一个数后，所有的数都可以确定出来）。

假设当前位置为$ \ i \ $枚举的幸运数为$ \ x \ $，通过计算可以得到$ \ A_1 \ $，我们假设它为$ \ y \ $，也就是说当$ \ A_1 \ $为$ \ y \ $的时候，在当前位置$ \ i \ $会出现一个幸运数$ \ x \ $。

我们用map<long long, int> cnt来统计$ \ cnt[x] \ $如果第一位数字为$ \ y \ $，那么它就有$ \ cnt[y] \ $个幸运数。在所有情况中取一个最大值即可。

知道了其中一个数如何求第一个数呢？

我们知道：

$$A_1 + A_2 = S_1$$

$$A_2 + A_3 = S_2$$

$$A_3 + A_4 = S_3$$

$$…$$

$$A_{N-1} + A_N = S_{N-1}$$

假设$ \ A_4 \ $为幸运数$ \ x \ $，那么通过上面的等式可以计算出$ \ A_1 \ $为$ \ S_1 - S_2 + S_3 - x \ $。

假设$ \ A_3 \ $为幸运数$ \ x \ $，那么通过上面的等式可以计算出$ \ A_1 \ $为$ \ S_1 - S_2 + x \ $。

注意当$ \ A_i \ $的位数偶数时需要$ \ -x \ $，而当$ \ A_i \ $的位数奇数时需要$ \ +x \ $。

为了更快速的统计出$ \ \sum S \ $，我们可以通过一个$ \ sum \ $数组来记录$ \ \sum_{i=1}^n (-1)^{n+1}S_i \ $

$Code$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>

using namespace std;

const int N = 100010;

typedef long long LL;

int a[N], s[N];
LL sum[N];
int n, m;

int main()
{
	scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= n - 1; i ++ ) scanf("%d", s + i);
	for(int i = 1; i <= m; i ++ ) scanf("%d", a + i);
	
	for(int i = 2; i <= n; i ++ )  // 求出1 ~ n的sum，记得下标处理一下 
	{
		if(i - 1 & 1) sum[i] = sum[i - 1] + s[i - 1];
		else sum[i] = sum[i - 1] - s[i - 1];
	}
	
	map<LL, int> cnt;
	
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= m; j ++ )
		{
			int x = a[j];
			if(i & 1) cnt[sum[i] + x] ++ ;
			else cnt[sum[i] - x] ++ ;
		}
		
	int ans = 0;
	for(auto &t : cnt) ans = max(ans, t.second);	
	
	printf("%d\n", ans);
	
	return 0;
}

$ \ $
$ \ $

题目分析

时间复杂度：$O(1)$。

$Code$

$ \ $
$ \ $

F(先空着-。-)

题目描述

题目分析

时间复杂度：$O(1)$。

$Code$

$ \ $
$ \ $