AtCoder Beginner Contest 254 A~E 题解

A - Last Two Digits

题目大意

给定正整数$N$，求$N$的后两位。
$100\le N\le 999$

输入格式

$N$

输出格式

输出$N$的后两位，注意输出可能有前导0。

样例

$N$ 输出
$254$ 54
$101$ 01

分析

题目已经规定$N$是三位数，因此无需使用整数输入，直接将输入看成字符串，输出后两位即可。

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <cstdio>
using namespace std;

int main()
{
	getchar();
	putchar(getchar());
	putchar(getchar());
	return 0;
}

B - Practical Computing

题目大意

输出$N$个整数序列$A_0,\dots,A_{N-1}$。它们按如下定义：

  • $A_i$的长为$i+1$。
  • $A_i$的第$j+1$个元素记为$a_{i,j}$（$0\le j\le i < N$），即：
    • 当$j=0$或$j=i$时，$a_{i,j}=1$；
    • 否则，$a_{i,j}=a_{i-1,j-1}+a_{i-1,j}$。

$1\le N\le 30$

输入格式

$N$

输出格式

输出$N$行。第$i$行上有$A_{i-1}$中的$i$个数，用空格分隔。

样例

样例输入1 

1

3

样例输出1 

1
2
3

1
1 1
1 2 1

样例输入2 

1

10

样例输出2 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

分析

其实不用读题，看一眼样例，是不是很眼熟？没错，就是著名的杨辉三角。
不知道也没关系（不过应该也没人不知道），直接按题目要求（$i,j$正序）依次计算即可。时间复杂度$\mathcal O(n^2)$，空间复杂度$\mathcal O(n)$或$\mathcal O(n^2)$。详见代码$1,2$。

继续考虑，杨辉三角中$a_{i,j}=C_j^i$，所以可以用$\mathcal O(1)$的空间计算，时间不变，代码待会补。

代码

  • 代码$1$（普通方法+无优化+cin/cout，$7\text{ms}~3604\text{KB}$）
    时间：$\mathcal O(n^2)$
    空间：$\mathcal O(n^2)$
    难度：低 
     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

    #include <iostream>
ing namespace std;

t arr[35][35];

t main()

   int n;
   cin >> n;
   for (int i = 0; i < n; i++)
   {
       arr[i][0] = 1;
       arr[i][i] = 1;
   }
   for (int i = 2; i < n; i++)
   {
       for (int j = 1; j < i; j++)
       {
           arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
       }
   }
   for (int i = 0; i < n; i++)
   {
       for (int j = 0; j <= i; j++)
       {
           cout << arr[i][j] << " ";
       }
       cout << endl;
   }
   return 0;
  • 代码$2$（普通方法+滚动表+scanf/printf，$6\text{ms}~1656\text{KB}$）
    时间：$\mathcal O(n^2)$
    空间：$\mathcal O(n)$
    难度：中低 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

    nclude <cstdio>
ing namespace std;

t a[35];

t main()

   int n;
   scanf("%d", &n);
   a[0] = 1, puts("1");
   for(int i=1; i<n; i++)
   {
   	putchar('1');
   	for(int j=i-1; j>0; j--)
   		a[j] += a[j - 1];
   	for(int j=1; j<i; j++)
           printf(" %d", a[j]);
       a[i] = 1, puts(" 1");
   }
   return 0;

C - K Swap

题目大意

给定长度为$N$的序列$A=(a_1,a_2,\dots,a_N)$和整数$K$，你可以重复下列操作任意次：

  • 选择整数$1\le i\le N-K$，交换$a_i$和$a_{i+K}$。

问：是否能通过上述操作将$A$按升序排列？

$2\le N\le 2\times 10^5$
$1\le K\le N-1$
$1\le a_i\le 10^9$

输入格式

$N~K$
$a_1~\dots~a_N$

输出格式

如果可以达到目标，输出Yes；否则，输出No。

样例

样例输入1 

1
2

5 2
3 4 1 3 4

样例输出1 

1

Yes

该样例中，$A=(3,4,1,3,4),K=2$。一种完成任务的操作如下：

  • 交换$a_1$和$a_3$，此时$A=(1,4,3,3,4)$；
  • 交换$a_2$和$a_4$，此时$A=(1,3,3,4,4)$，排序完成。

样例输入2 

1
2

5 3
3 4 1 3 4

样例输出2 

1

No

$K=3$，无法将$A$排序。

样例输入3 

1
2

7 5
1 2 3 4 5 5 10

样例输出3 

1

Yes

可以不进行操作。

分析

题目可以看成：在$a_i,a_{K+i},a_{2K+i},\dots$（$1\le i < K$）中的元素是可以两两相邻交换的。那么，根据冒泡排序的原理，这些元素是可以直接排序并放入原位置上的。此时，只需依次对于$i=1,2,\dots,K-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

#include <cstdio>
#include <set>
#include <algorithm>
#define maxn 200005
using namespace std;

int a[maxn], b[maxn];

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	for(int i=0; i<n; i++)
	{
		scanf("%d", a + i);
		b[i] = a[i];
	}
	sort(b, b + n);
	for(int i=0; i<k; i++)
	{
		multiset<int> s1, s2;
		for(int j=i; j<n; j+=k)
		{
			s1.insert(a[j]);
			s2.insert(b[j]);
		}
		if(s1 != s2)
		{
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	return 0;
}

特别: 本题涉及到很多数组操作，使用Python代码量非常小（使用数组切片和sorted()），所以也是一道很好的Python数组练习题。因此，这里破例提供Python示例代码：

1
2
3
4
5

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
	a[i::k] = sorted(a[i::k])
print('Yes' if a == sorted(a) else 'No')

D - Together Square

题目大意

给定整数$N$。求正整数对$(i,j)$的个数，满足：

  • $1\le i,j\le N$
  • $i\times j$是一个完全平方数（即$1^2,2^2,3^2,\dots$）

$1\le N\le 2\times 10^5$

输入格式

$N$

输出格式

输出答案。

样例

$N$ 输出
$4$ $6$
$254$ $896$

分析

注意$N$较大，所以最容易想到的$\mathcal O(n^2)$暴力枚举肯定是不行的，然后仔细思考后发现可以枚举整数对$(x,y)$（$1\le x,y\le\lfloor\sqrt N\rfloor$），当$x,y$互质时将答案加上$\frac N {\max\{x^2,y^2\}}$，这样答案正确，建议读者自行思考原因。

时间复杂度计算：

  • 循环（次数$\sqrt N$，枚举$x$）
    • 循环（次数$\sqrt N$，枚举$y$）
      • gcd最大公约数算法（辗转相除法$\log\max\{x,y\}\approx\log\sqrt N$，判断互质）

综上，总时间复杂度为$\mathcal O(\sqrt N\times\sqrt N\times\log\sqrt N)=\mathcal O(N\log\sqrt N)$。

代码 

 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

#include <cstdio>
using namespace std;

inline int gcd(int a, int b)
{
	while(b ^= a ^= b ^= a %= b);
	return a;
}

int main()
{
	int n = 0; char c;
	while((c = getchar()) != '\n')
		n = (n << 3) + (n << 1) + (c ^ 48);
	int t = __builtin_sqrt(n);
	long long ans = 0LL, x;
	for(int i=1; i<=t; i++)
		for(int j=i; j<=t; j++)
			if(gcd(i, j) == 1)
			{
				ans += (x = n / (i > j? i * i: j * j));
				if(i != j) ans += x;
			}
	printf("%lld\n", ans);
	return 0;
}

E - Small d and k

题目大意

给定一个由$N$个点和$M$条边组成的简单无向图。
对于每个$i=1,2,\dots,M$，第$i$条边连接顶点$a_i$和$b_i$。

已知 ==每个顶点的度数不超过3==，回答下列$Q$个查询，第$i$个查询为：

  • 求与顶点$x_i$距离不超过$k_i$的点的下标之和。

$1\le N,Q\le 1.5\times 10^5$
$0\le M\le \min\{\frac{N(N-1)}2,\frac32N\}$
$1\le a_i < b_i\le N$，$(a_i,b_i)$互不相同。
$1\le x_i\le N$，==$0\le k_i\le 3$==

输入格式

$N~M$
$a_1~b_1$
$\vdots$
$a_M~b_M$
$Q$
$x_1~k_1$
$\vdots$
$x_Q~k_Q$

输出格式

输出$Q$行。第$i$行应包含第$i$个查询的答案。

样例

样例输入 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

6 5
2 3
3 4
3 5
5 6
2 6
7
1 1
2 2
2 0
2 3
4 1
6 0
4 3

样例输出 

1
2
3
4
5
6
7

1
20
2
20
7
6
20

样例解释：AtCoder 254E - Small d and k #sample

分析

注意这题数据范围，这是解体的关键：

  • 减少算法耗时：
    • $0\le k\le 3$
    • 顶点度数$~\le3$
    • 根据乘法原理，一次查询最大符合条件的顶点数为$3^3+1=28$个
  • 防止常数问题：
    • $1\le N\le \textbf{1.5}\times 10^5$
    • 时间限制$3.5\text{s}$

因此，使用简单的暴力$\text{BFS}$正好符合题目数据范围。详见代码。

代码

注意dis数组的清零操作，无需全部清零，只需把刚刚改过的清零即可。

 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
46
47
48
49

#include <cstdio>
#include <queue>
#define maxn 150005
using namespace std;

vector<int> G[maxn];
int dis[maxn];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int Q; scanf("%d", &Q);
	for(int i=1; i<=n; i++) dis[i] = -1;
	while(Q--)
	{
		int x, k;
		scanf("%d%d", &x, &k);
		vector<int> ans;
		queue<int> q;
		q.push(x);
		dis[x] = 0;
		while(!q.empty())
		{
			int v = q.front(); q.pop();
			int d = dis[v];
			if(d <= k) ans.push_back(v);
			if(++d > k) continue;
			for(int u: G[v])
				if(dis[u] == -1)
				{
					dis[u] = d;
					q.push(u);
				}
		}
		int res = 0;
		for(int v: ans)
			res += v, dis[v] = -1;
		printf("%d\n", res);
	}
	return 0;
}
© 2020 - 2025 GoodCoder's Blog
使用 Hugo 构建
主题 Stack 由 Jimmy 设计