Atcoder经典题_atcoder题库

ABC—273 B（整数四舍五入）

B - Broken Rounding (atcoder.jp)

题意：求一个整数进行K轮操作后的值是多少。

操作：第一轮对个位进行四舍五入，第二轮对百位进行四舍五入，第三轮对百位进行四舍五入......以此类推到K轮

重点: if (abs(x / g * g - x) < abs((x / g + 1) * g - x))//四舍五入

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
 
typedef long long ll;
 
ll x, k, g, res;
 
int main()
{
	cin >> x >> k;
 
	for (int i = 1; i <= k; i++) {
		g = pow(10, i);
		//四舍五入
		if (abs(x / g * g - x) < abs((x / g + 1) * g - x)) {
			x = x / g * g;
		}
		else {
			x = (x / g + 1) * g;
		}
	}
 
	cout << x;
	return 0;
}

ABC—275 B（求%公式）

B - ABC-DEF (atcoder.jp)

题意: 一共有六个数A，B，C，D，E，F。求A*B*C - D*E*F最后%998244353的值。

• 0≤ A,B,C,D,E,F ≤ 1e18

这道题如果直接算在求模部分例题是过不了的。所以我们需要边算边取模

取模公式: ( A - B) % mod = ((A % mod) - (B % mod) + mod) % mod.

#include <iostream>
using namespace std;
 
int mod = 998244353;
typedef long long ll;
 
int main()
{
	ll a, b, c, d, e, f;
	cin >> a >> b >> c >> d >> e >> f;
 
	ll x = (a % mod) * (b % mod) % mod;
	x = (x * (c % mod)) % mod;
	ll y = (d % mod) * (e % mod) % mod;
	y = (y * (f % mod)) % mod;
 
	ll nums = (x + mod - y) % mod;
	cout << nums << endl;
	return 0;
}

ABC—275 C(正方形的偏移量)

C - Counting Squares (atcoder.jp)

题意：一共有九行字符串，分别由' . '和' # '组成。#为顶点，判断图形中一共有多少个长方形?

思路:遍历整个图形然后通过偏移量来判断是不是正方形。

对于四个顶点的判断：check(i, j) && check(i + di, j + dj) &&check(i + di - dj, j + dj + di) && check(i - dj, j + di);

其实上面是一种写法；

还有一种写法：check(i, j) && check(i + di, j + dj) &&check(i + di + dj, j + dj - di) && check(i + dj, j - di);

至于判断方法可以自己去画个斜正方形来考虑。

#include <iostream>
using namespace std;
const int n = 9;
char s[n][n + 1];
bool check(int x, int y) {
  if (x < 0 || x >= n || y < 0 || y >= n) return false;
  return s[x][y] == '#';
}
 
int main() {
  for (int i = 0; i < n; i++) cin >> s[i];
  int ans = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int di = 1; di < n; di++)
        for (int dj = 0; dj < n; dj++)
          ans += check(i, j) && check(i + di, j + dj) &&
                 check(i + di - dj, j + dj + di) && check(i - dj, j + di);
  cout << ans;
  return 0;
}

ABC—270 B（负号转正解决问题）

B - Hammer (atcoder.jp)

题意：一共有X, Y, Z三个点。三个点都在x轴坐标上。其中Y会阻挡去路，而Z可以解开Y的阻挡。问到达X需要的最小距离是多少?

思路：由于x, y, z的正负号都不确定，所以考虑起来会有很多情况。

但由于y是解决该题目的唯一阻碍，所以我们可以把y给转正（也就是保证y是正数）。然后再对x和z进行处理。

#include <iostream>
#include <algorithm>
using namespace std;
 
int x, y, z;
 
int main()
{
	cin >> x >> y >> z;
	if (y < 0) {
		x = -x;
		y = -y;
		z = -z;
	}
 
	if (x < y) {
		cout << abs(x) << endl;
	}
	else {
		if (z > y) cout << -1 << endl;
		else {
			cout << abs(z) + x - z << endl;
		}
	}
	
	return 0;
}

ABC—269 C（二进制1的子序列数）

C - Submask (atcoder.jp)

题意：打印一个数x二进制中所有1的子序列数组成的数，可以看下例题

思路：利用一个数组储存所有(x - 1) & x的数，最后反过来打印即可

-1的目的可以让x二进制中的1一个一个去除，最后&x保证新出现的1是x原本就含有的。

eg:4的二进制为100；4 - 1后二进制为011，这里出现的两个1都不是4的二进制里所包含的。所以我们要&4.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
typedef long long ll;
 
vector<ll> ans;
 
int main()
{
	ll x;
	cin >> x;
	
	for (ll a = x; ; a = (a - 1) & x) {
		ans.push_back(a);
		if (a == 0) break;
	}
	reverse(ans.begin(), ans.end());
	for (ll a : ans) cout << a << endl;
	return 0;
}

ABC—278 C

C - Chinese Restaurant (atcoder.jp)

题意:一共有n个人Person0, 1, 2 ,······ ,n - 1围成一桌，每个人的前面都随机放着一道菜(菜也有编号)，桌子可以逆时针旋转。问最多有多少个人能够满意能够满意周围的菜。

满意的条件:Person i周围的菜有dish i, dish (i - 1) % n, dish (i + 1) % n.

思路: 利用数组cnt来记录每次转多少次时有多少个人满意。

cnt[i]：i下标的概念表示桌子转了多少次

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 2e5 + 10;
int p[N];
 
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> p[i];
 
	vector<int> cnt(n);
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cnt[(p[i] - 1 + j - i + n) % n]++;
		}
	}
 
	int mx = 0;
	for (int i = 0; i < n; i++) mx = max(mx, cnt[i]);
	
	cout << mx << endl;
	return 0;
}

ABC—277 C（移动窗口）

C - Index × A(Continuous ver.) (atcoder.jp)

题意：一共有n个数An，求An中m个连续子序列满足1 * B1, 2 * B2, ······ ，m * Bm的值最大。

思路：我们首先可以想到双层循环来一个一个遍历来求到最大值，但这样时间上过不了。所以我们换个思路。既然双层循环过不了，我们可以想下单层循环怎么能过。这里我们就可以想到利用窗口移动来完成。利用窗口移动的话我们每次移动需要加上m * a[i], 然后需要减去a[i]的前m个序列之和。这里我们就可以利用前缀和来完成。最后，一步一步比较得出最大值。

代码：

#include <iostream>
using namespace std;
 
typedef long long ll;
 
const int N = 2e5 + 10;
 
ll a[N], s[N];
 
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
 
	//前缀和
	for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
 
	//初始化移动窗口
	ll cnt = 0;
	for (int i = 1; i <= m; i++) cnt += a[i] * i;
 
	//窗口移动求最大值
	ll res = cnt;
	for (int i = m + 1; i <= n; i++) {
		cnt += a[i] * m - (s[i - 1] - s[i - m - 1]);
		res = max(res, cnt);
	}
 
	cout << res << endl;
	return 0;
}

ABC—266 C（叉乘）

C - Convex Quadrilateral (atcoder.jp)

题意：给定四个点，四个点组成一个图形。判断四个点是否存在一个点的角度大于180度。如果都都小于180度则打印"Yes",否则打印"NO"。

思路：这里需要用到叉乘的概念。两个向量叉乘的值是负的话，那么角度就是大于180度的。

注意：这里的两个的方向是有一点规律的，可以看下代码画个图来判断下。

二维叉乘公式：a（x1，y1），b（x2，y2），则a×b＝（x1y2－x2y1）。

代码：

#include <iostream>
using namespace std;
 
int x[8];
int y[8];
 
int main()
{
	for (int i = 0; i < 4; i++) {
		cin >> x[i] >> y[i];
		x[i + 4] = x[i];
		y[i + 4] = y[i];
	 }
 
	for (int i = 0; i < 4; i++) {
		int e = (x[i + 1] - x[i]) * (y[i + 2] - y[i + 1]) - (x[i + 2] - x[i + 1]) * (y[i + 1] - y[i]);
		if (e <= 0) {
			cout << "No" << endl;
			return 0;
		}
	}
 
	cout << "Yes" << endl;
	return 0;
}

ABC—259（逆时针旋转）

B - Counterclockwise Rotation (atcoder.jp)

题意：给定一个在直角坐标系的一个点（a，b），将该点逆时针旋转d度，求旋转后的点的坐标？

思路：求（x，y）用于旋转的所在圆的半径，然后再求到旋转后的角度，利用x = cosx * r， y = sinx * r。然后求到坐标。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
	double a, b, d;
	cin >> a >> b >> d;
 
	//用于查找给定数字的斜边，接受两个数字并返回斜边的计算结果，即sqrt(x * x + y * y)。
	//这里就是用于求半径
	double r = hypot(a, b);
 
	//atan2(y, x)返回的是原点至点（x，y）的方位角，即与 x 轴的夹角。
	//取值范围为（-π, π]
	double theta = atan2(b, a);
 
	//acos(-1) = π 就相当于cosπ = -1，
	//用acos(-1)的好处是精度更高
	theta += d * acos(-1.0) / 180.0;
	double x = cos(theta) * r;
	double y = sin(theta) * r;
	cout << x << ' ' << y << endl;
	return 0;
}

ABC—254（块存储）

C - K Swap (atcoder.jp)

题意：给一个长度为n的数组A，给定一个数组k。在1  <=  i  <= N - K的范围内，可以交换ai和

ai+k的值。问可以随意按上述交换，最后能形成一个升序有序数组吗

思路：由题意可知ai、ai + k，ai + 2k、ai + 3k······可以随意交换，所以我们可以将每个区间的数（i % k）存入同一个数组中，并把每个区间排好序。再用排好序的数组A与相对应的区间的最小值判断是否相等。

代码：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	vector<vector<int>> p(k);
 
	for (int i = 0; i < n; i++) {
		cin >> a[i];
        //将每个属于同一个随意交换区间的数放入同一个数组中
		p[i % k].push_back(a[i]);
	}
    
    //给每个区间排序
	for (int i = 0; i < k; i++) {
		sort(p[i].rbegin(), p[i].rend());
	}
 
	sort(a.begin(), a.end());
	vector<int> na;
 
	for (int i = 0; i < n; i++) {
		na.push_back(p[i % k].back());//将区间最小的数放入对照数组中
		p[i % k].pop_back();
	}
 
	if (a == na) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

ABC—256（3*3表格表示法求值）

C - Filling 3x3 array (atcoder.jp)

题意：点上面链接看原题。

思路：遍历a，b，d，e，然后将c，f，g，h，i给表示出来。再用H[2] == g + h + i 和c，f，g，h，i五个值不为负数（这个条件必写，不然就错了）作为判断条件。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
 
int H[3], W[3];
long long res = 0;
 
int main()
{
	for (int i = 0; i < 3; i++) cin >> H[i];
	for (int i = 0; i < 3; i++) cin >> W[i];
 
	for (int a = 1; a <= 30; a++) {
		for (int b = 1; b <= 30; b++) {
			for (int d = 1; d <= 30; d++) {
				for (int e = 1; e <= 30; e++) {
					int c = H[0] - a - b;
					int f = H[1] - d - e;
					int g = W[0] - a - d;
					int h = W[1] - b - e;
					int i = W[2] - c - f;
					if (min({c, f, g, h, i}) > 0 && g + h + i == H[2]) res++;
				}
			}
		}
	}
 
	cout << res << endl;
	return 0;
}

ABC—238 B（切割圆求最大的角度）

B - Pizza (atcoder.jp)

题意：给定一个圆，让这个圆顺时针旋转指定角度，并在12点钟方向进行切割。问在选择n次旋转并切割后，圆的最大角度是多少？

思路：创一个长度为361的bool数组，用来当做哈希表，记录切割的位置。然后遍历整个圆的角度，用cnt来计算每两个相邻的切割线之间的角度，进而比较得到最大值。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
 
bool f[361];
int n, x;
 
int main()
{
	cin >> n;
 
	f[0] = true;
	int p = 0;
	for (int i = 0; i < n; i++) {
		cin >> x;
		p += x, p %= 360;
		f[p] = true;
	}
 
	int res = 0, cnt = 0;
	for (int i = 0; i <= 360; i++) {
		if (f[i % 360]) {
			res = max(res, cnt);
			cnt = 0;
		}
		cnt++;
	}
 
	cout << res << endl;
	return 0;
}

ABC—234（二进制表示法）

C - Happy New Year! (atcoder.jp)

题意：在仅由0 和 2组成的数中，找到最小的第k个数。

eg：

 

思路：通过观察可以知道5的二进制：101把1换成2就是题目所要求的数。其他的数也是一样的。所以这里就可以把十进制换成二进制来作答。

代码

#include <iostream>
using namespace std;
 
typedef long long ll;
 
int main()
{
	ll k;
	cin >> k;
 
	string s = "";
	while (k >= 1) {
		if (k % 2 == 0) {
			s = '0' + s;
		}
		else {
			s = '2' + s;
		}
		k /= 2;
	}
 
	cout << s << endl;
	return 0;
}