Atcoder ABC380个人游记（A~D）

比赛链接

A. 9x9

题面

给你一个 33 个字符的字符串 SS ，其中第一个字符是数字，第二个字符是字符 x，第三个字符是数字。

求 SS 中两个数字的乘积。

思路

嗯嗯嗯嗯嗯嗯模拟就好了

代码

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin >> s;
	cout << (s[0] - '0')*(s[2] - '0');
	return 0;
}

B. tcaF

题面

给你一个不小于 22 的整数 XX 。

求正整数 NN ，使得 N!=XN! = X .

这里， N!N! 表示 NN 的阶乘，可以保证正好有一个这样的 NN 。

  • 2≤X≤3×10182 \leq X \leq 3 \times 10^{18}

思路

可以看一眼样例22，这里2020的阶乘都超过101810^{18}了，所以答案不会太大，从11枚举直到X=1X=1就行了。

（看不出标题和题目有神马关系…)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
// 这里我赛时急匆匆的就直接写ULL了，这里统一放赛时代码
using namespace std;
int main()
{
	unsigned long long x;
	cin >> x;
	for (unsigned long long i = 1;; i++) {
		x /= i;
		if (x == 0) {
			cout << i - 1;
			return 0;
		}
	}
}

C. Snake Queue

题面

有一个蛇队列。最初，队列是空的。

你会得到 QQ 个查询，这些查询应按给出的顺序处理。查询有三种类型：

  • 类型 11 ：以 1 l 的形式给出。一条长度为 ll 的蛇会被添加到队列的末尾。如果添加前队列为空，则新添加的蛇的头部位置为 00 ；否则，它就是队列中最后一条蛇的头部坐标与最后一条蛇的长度之和。
  • 类型 22 ：以 "2 "的形式给出。队列最前面的蛇离开队列。保证此时队列不是空的。假设 mm 是离开的蛇的长度，那么队列中剩余的每条蛇的头部坐标都会减少 mm 。
  • 类型 33 ：以 3 k 的形式给出。输出距离队列最前面 kk 的蛇的头部坐标。保证此时队列中至少有 kk 条蛇。

思路

我们可以维护一个动态数组（今天起猛了，不想用STL）来干掉它，标题很明显吧？

然后我们说这33种操作：

1：插入

如果队列是空的，那这个插入的蛇头坐标就是0

如果队列不是空的，则新蛇的蛇头坐标就是=队尾那条蛇的绝对头部+队尾那条蛇的长度

当然，很简单

2：弹出

设出队的蛇长度为m。
我们令offset-=m等效于把余下所有蛇的实际坐标都往前挪了mm，这里
front+1front+1，队列大小 count−1count-1。
若出队后队列变空，则重置 offset=0offset=0（因为下次再进队时，题目规定空队进来的蛇头部要从00开始）。

差点忘了，这里offsetoffset表示因为出队操作产生的整体平移量，这样就可以方便修改，不用遍历整个数组了

3：查询

这条蛇在动态数组里的下标应该是k+front−1k+front-1，所以得到答案是它的坐标加上整体平移量offsetoffset就可以了

怎么样，是不是并不是很难？

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int Q;
	cin >> Q;
	vector<long long> heads(Q), lengths(Q);
	long long offset = 0;
	int front = 0, back = 0, count = 0;
	while (Q--) {
		int ch;
		cin >> ch;
		if (ch == 1) {
			long long l;
			cin >> l;
			if (count == 0) {
				offset = 0;
				heads[back] = 0;
				lengths[back] = l;
				back++;
				count = 1;
			} else {
				heads[back] = heads[back - 1] + lengths[back - 1];
				lengths[back] = l;
				back++;
				count++;
			}
		} else if (ch == 2) {
			long long m = lengths[front];
			offset -= m;
			front++;
			count--;
			if (count == 0) {
				offset = 0;
			}
		} else {
			int k;
			cin >> k;
			long long ans = offset + heads[front + k - 1];
			cout << ans << '\n';
		}
	}
	return 0;
}

D. Squares In Circle

题面

在二维坐标平面上，有一个由 1×11 \times 1 个正方形组成的无限平铺。

考虑以其中一个正方形的中心为圆心，画一个半径为 RR 的圆。有多少个正方形完全包含在圆内？

更精确地说，求使所有四个点 (i+0.5,j+0.5)(i+0.5,j+0.5) 、 (i+0.5,j−0.5)(i+0.5,j-0.5) 、 (i−0.5,j+0.5)(i-0.5,j+0.5) 和 (i−0.5,j−0.5)(i-0.5,j-0.5) 与原点的距离最多为 RR 的整数对 (i,j)(i,j) 的个数。

思路

平面直角坐标系会吧？那这题就不难了

因为坐标(i,j)(i,j)里面这俩数可正可负可对称，所以我们只统计第一象限里面的答案，然后统计其他象限就ok辣！

具体地说就是这样：
i>0,j>0i>0,j>0 那些方格数记为 c0c0；

i=0,j>0i=0,j>0 或 i>0,j=0i>0,j=0 那些在坐标轴上的方格数记为 c1c1 (注意区分一下行/列)；

i=0,j=0i=0,j=0 原点处那一个方格(如果它满足条件)记为 c2c2 ；实际只要 R2≥0.5R2 \geq 0.5 就会包含那个原点方格。

答案就是：

4×c0​+2×(那些在轴上但不含原点的方格)+1×(原点方格)

其他细节看代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
//代码较长所以我写的变量名相对完整防止自己白内障
long long maxAxis(long long RR)
{
	long double tmp = (long double)RR * RR - 0.25L;
	if (tmp < 0) return 0LL;
	long double side = sqrtl(tmp) - 0.5L;
	if (side < 0) return 0LL;
	return (long long)floor(side);
};
long long solve(long long R)
{
	long long c_origin = 0;
	if ( (long double)R * R >= 0.5L ) {
		c_origin = 1;
	}
	long long axisCount = maxAxis(R), c0 = 0;
	long long j = axisCount;
	for (long long i = 1; i <= axisCount; i++) {
		while (j >= 1) {
			long double dx = (long double)i + 0.5L;
			long double dy = (long double)j + 0.5L;
			if (dx * dx + dy * dy <= (long double)R * R) {
				break;
			}
			j--;
		}
		if (j < 1) break;
		c0 += j;
	}
	long long ans = 4LL * c0 + 4LL * axisCount + c_origin;
	return ans;
}

int main()
{
	long long R;
	cin >> R;
	cout << solve(R) << '\n';
	return 0;
}

总结

无语，才4题。

GOODBYE