Atcoder ABC 400

compaq · 2025-04-06 13:13:56 · 题解

400C

方法一：找规律

b的平方有1，4 ， 9， 16， 25， 36， 49， 64， 81， 100

枚举2^a，只有a == 1 和a == 2的数字不会重复，其他情况都重复:

所以我们要计算个数 只需要枚举2^1和2^2就可以了，直接输出答案即可。

注意要靠long double

方法二：

考虑枚举2^a，然后求有多少个满足条件的b.

• 当a确定时，N = 2^a \times b^2 \rightarrow b \leq \sqrt {N/2^a} , 所以b的取值范围[1, \sqrt {N/2^a}]。

• 但是注意一个情况，2^1 \times 2^2 = 8, 2^3 \times 1^2 = 8，此时数字8被记录了两次，所以需要去重。

• 重复的原因，若b = 2 \times x的形式，则\times 2可以移到2 ^ a中的a里。

• 所以防止重复的计数方法就是b只能为奇数，把2都归到2^a里，即只取[1, \sqrt{N / 2^a}]内的奇数。

400D

题意：

高桥打算去鱼店买鳗鱼。

他居住的城镇被划分为一个 H 行 W 列的网格。每个单元格要么是道路，要么是墙壁。

我们将从上往下数第 i 行(1 \leq i \leq H)、从左往右数第 j 列(1 \leq j \leq W)的单元格记为单元格 (i, j)。

关于每个单元格的信息由 H 个长度为 W 的字符串(S_1, S_2, \dots, S_H)给出。具体来说，如果S_i的第 j 个字符(1 \leq i \leq H)，(1 \leq j \leq W)是 .，则单元格 (i, j)是道路；如果是 #，则单元格 (i, j) 是墙壁。

他可以按任意顺序重复执行以下两种操作：

• 移动到城镇内且为道路的相邻单元格（上、下、左或右）。
• 选择四个方向（上、下、左或右）中的一个方向并在该方向上进行一次前踢。
  • 当他进行一次前踢时，在他当前所在单元格的该方向上至多 2 步距离内的每个单元格，如果该单元格是墙壁，就会变成道路。
  • 如果至多 2 步距离内的某些单元格在城镇范围外，仍然可以进行前踢，但城镇范围外的部分不会发生变化。

他从单元格 (A, B) 出发，想要前往位于单元格 (C, D) 的鱼店。

保证他的起始单元格和鱼店所在单元格都是道路。

求他到达鱼店所需的最少前踢次数。

方法一：双端队列代替普通队列：

• 当边权为 0 时，将对应的节点插入到双端队列的头部。因为边权为 0 意味着走这条边不会增加路径长度，所以优先考虑扩展这些节点。

• 当边权为 1 时，将对应的节点插入到双端队列的尾部。因为边权为 1 会增加路径长度，所以相对靠后处理。

方法二： 最短路算法

400E

题意：

一个正整数 N 被称为 “400 数”，当且仅当它同时满足以下两个条件：

• 对于 N 的每个质因数 p，p 整除 N 的次数为偶数次。更正式地说，使得 (p^k) 能整除 N 的最大非负整数 k 是偶数。

处理 Q 次查询。每次查询会给你一个整数 A，请找出不超过 A 的最大 “400 数”。在本题的数据范围限制下，不超过 A 的 “400 数” 总是存在的。

思路:

埃氏筛法筛质数的时候，记录一下合数是多少个质数的倍数，如果这个合数是2个质数的倍数，那么这个合数一定是两个质数相乘得到的（可能多次相乘）。那么我们可以把这个数的平方放入vector，然后二分求答案；