ABC 400 题解

经验分享区
1

首先庆祝ABC又有一次整百的比赛！！:partying_face::partying_face::partying_face:

T1

AtCoder 400 T1 题面

题面翻译：

问题陈述：

在纪念 ABC400 的仪式上，我们想要将 400 人排列成一个 A 行 B 列的矩形方阵，且不能有任何空缺。

给定一个正整数 A ，请输出一个满足条件的正整数 B 。如果不存在这样的正整数 B ，则输出 -1 。

约束条件

A是一个介于 1 到 400 之间的整数，包含 1 和 400 。

输入

输入通过标准输入给出，格式如下：

A

输出

根据问题描述输出 B 的值或 -1 。

思考：

  • 我们想要将 400 人排列成一个 A 行 B 列的矩形方阵，就说明 400 一定是 A 的倍数。
  • 那么就简单了，直接输出是否是 400 的因数就可以了。
AC代码（禁止抄袭！！）： 
#include <bits/stdc++.h>
using namespace std;

int main (  )
{
//	freopen ( ".in", "r", stdin );
//	freopen ( ".out", "w", stdout );
	ios::sync_with_stdio ( false );
	cin.tie ( 0 );
	cout.tie ( 0 );
	int n;
	cin >> n;
	if ( 400 % n == 0 )
	{
		cout << 400 / n << "\n";
	}
	else
	{
		cout << -1 << "\n";
	}
//	system ( "pause" );
	return 0;
}

T2

AtCoder 400 T2 题面

题面翻译：

问题陈述：

给定两个正整数 N 和 M 。

定义 X 为从 i=0 到 i=M 的 N 的 i 次方之和 。如果 X ≤ 10^9 ，则输出 X 的值；如果 X > 10^9 ，则输出 inf 。

约束条件

1 ≤ N ≤ 10^9
1 ≤ M ≤ 100
所有输入均为整数。

输入

输入通过标准输入给出，格式如下：

N M

输出

根据问题描述输出 X 的值或 inf

思考：

  1. 计算 X 的值： X 是 N_0+N_1+N_2+⋯+N_M 的和，这是一个等比数列求和问题。

  2. 处理大数问题：在计算过程中， NM+1 可能会非常大，尤其是当 N 和 M 较大时，直接计算可能会导致数值溢出。因此，我们需要在计算过程中检查是否超过 10^9 ，如果超过则提前终止计算并返回 inf。

  3. 逐步计算：我们可以通过循环逐次累加 N_i ，并在每次累加后检查是否超过 10^9 。这样可以避免直接计算大数，同时提高效率。

AC代码（禁止抄袭！！）： 
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int N, M;
	cin >> N >> M;
	long long X = 0;
	long long term = 1;
	for (int i = 0; i <= M; i++)
	{
		X += term;
		if (X > 1e9)
		{
			cout << "inf" << "\n";
			return 0;
		}
		if (i < M)
		{
			term *= N;
			if (term > 1e12)
			{
				cout << "inf" << "\n";
				return 0;
			}
		}
	}
	cout << X << "\n";
	return 0;
}

T3

AtCoder 400 T3 题面

题面翻译：

问题陈述

如果一个正整数 X 满足以下条件，则称其为好整数：

存在一对正整数 (a,b)，使得 X=2^a×b^2。
例如，400 是一个好整数，因为 400=2^2 × 10^2。

给定一个正整数 N，求在 1 到 $N$（含）之间的所有好整数的个数。

约束条件

  • 1≤N≤10^18

  • N 是整数。

输入

输入通过标准输入给出，格式如下：

N

输出

输出 1 到 $N$（含）之间的所有好整数的个数。

思路：

解题思路

为了统计所有满足 1≤X≤N 的好整数的数量，我们需要找到所有可能的$ (a,b)$ 组合，使得 X=2^a × b^2 ≤N。为了避免重复计数（因为不同的 (a,b) 可能生成相同的 X ），我们需要使用一个集合（或哈希集合）来存储已经生成的好整数。

关键观察：

  1. b 的范围：由于 b^2≤X≤N，所以 b 的最大可能值是 N ​。因此，b 的取值范围是 1≤b≤N。

  2. a 的范围：对于每个固定的 b。因此，a 的最大值是 log⁡2(Nb2)。由于 a 是正整数，a≥1。

  3. 然后，我们需要确保这些 X 是唯一的。

  4. 为了避免重复计数，我们需要确保 X 不被多次计数。注意到 X 的形式是 2^a × b^2，其中 b 是奇数（因为如果 b 是偶数，可以提取更多的 2 的幂次到 a 中）。

  5. 因此，我们可以限制 b 为奇数，这样 X 的唯一性可以得到保证。

  6. 注意到 sqrt的精度可能不够，所以可以用sqrtl或者手写二分求根

AC代码（禁止抄袭！！）： 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll work(ll x)
{
	ll sqrt_x = sqrt(x);
	while (sqrt_x * sqrt_x > x)
	{
		sqrt_x--;
	}
	while ((sqrt_x + 1) * (sqrt_x + 1) <= x)
	{
		sqrt_x++;
	}
	return sqrt_x;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll N;
	cin >> N;
	ll cnt = 0;
	for (ll a = 1; (1LL << a) <= N; a++)
	{
		ll tpa = 1LL << a;
		ll mbs = N / tpa;
		if (mbs < 1)
		{
			break;
		}
		ll sqrt_mbs = work(mbs);
		ll max_b = (sqrt_mbs - 1) / 2;
		cnt += max_b + 1;
	}
	cout << cnt << "\n";
	return 0;
}

T4

AtCoder 400 T4 题面

题面翻译：

问题陈述

高桥君准备去鱼店买鳗鱼。

他所居住的城镇被划分为一个H行W列的网格，每个格子要么是道路（可通行），要么是墙壁（不可通行）。
我们用 (i, j) 表示从上往下第 i 行（1 ≤ i ≤ H）、从左往右第 j 列（1 ≤ j ≤ W）的格子。
每个格子的信息由 H 个长度为 W 的字符串 S₁, S₂, …, S_H 给出。具体来说：

  • 如果 S_i 的第 j 个字符是 .，则 (i, j) 是道路；

  • 如果是 #，则 (i, j) 是墙壁。

高桥君可以无限次执行以下两种操作（顺序不限）：

  1. 移动：向上、下、左、右四个方向之一移动一格，目标格子必须在城镇范围内且是道路。

  2. 前踢：选择上、下、左、右四个方向之一，对该方向进行前踢。

    • 前踢的效果：在该方向上最多 2 格范围内的所有墙壁（#）会变成道路（.）。

    • 如果该方向上的某些格子超出城镇范围，前踢仍然可以执行，但超出部分不会发生任何变化。

高桥君初始位于 (A, B)，目标是到达鱼店所在的 (C, D)。
题目保证起点 (A, B) 和终点 (C, D) 都是道路。
求他最少需要多少次前踢才能到达鱼店。

约束条件

  • 1 ≤ H, W ≤ 1000

  • 每个 S_i 是由 . 和 # 组成的长度为 W 的字符串。

  • 1 ≤ A, C ≤ H

  • 1 ≤ B, D ≤ W

  • (A, B) ≠ (C, D)

  • 起点和终点都是道路。

  • H, W, A, B, C, D 均为整数。

输入格式

输入通过标准输入给出，格式如下：

H W
A B
C D
S₁
S₂
...
S_H

输出格式

输出高桥君到达鱼店所需的最少前踢次数。

思路：

考虑转成图论问题求解。

将每个位置 ( x , y ) 看做节点，向其上下左右 1 ∼ 2 步处，共 8 个位置 ( x x , y y ) 分别建边。

如果 ( x , y ) 到 ( x x , y y ) 中途（不包括 ( x , y ) ）没有经过墙壁，那么边权就是 0，否则边权就是 1。

最后，从起点到终点的最短路即为答案。

由于边权只有 0 和 1 ，我们可以使用 bfs 来求解单源最短路。

时间复杂度 O ( n m )，其中 n 分别表示点数，m 表示边数。

AC代码（禁止抄袭！！）： 
#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int main()
{
	int H, W;
	cin >> H >> W;
	vector<string> S(H);
	for (int i = 0; i < H; i++)
	{
		cin >> S[i];
	}
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	--A;
	--B;
	--C;
	--D;
	vector < vector < int > > dis(H, vector<int>(W, INF));
	dis[A][B] = 0;
	deque<pair<int, int>> dq;
	dq.push_back({A, B});
	while (!dq.empty())
	{
		auto current = dq.front();
		dq.pop_front();
		int i = current.first;
		int j = current.second;
		if (i == C && j == D)
		{
			cout << dis[i][j] << "\n";
			return 0;
		}
		for (int dir = 0; dir < 4; dir++)
		{
			int ni = i + dx[dir];
			int nj = j + dy[dir];
			if (ni >= 0 && ni < H && nj >= 0 && nj < W && S[ni][nj] == '.' && dis[ni][nj] > dis[i][j])
			{
				dis[ni][nj] = dis[i][j];
				dq.push_front({ni, nj});
			}
		}
		for (int dir = 0; dir < 4; dir++)
		{
			for (int step = 1; step <= 2; ++step)
			{
				int ni = i + step * dx[dir];
				int nj = j + step * dy[dir];
				if (ni >= 0 && ni < H && nj >= 0 && nj < W)
				{
					if (dis[ni][nj] > dis[i][j] + 1)
					{
						dis[ni][nj] = dis[i][j] + 1;
						dq.push_back({ni, nj});
					}
				}
			}
		}
	}
	return 0;
}

T5

题面翻译：

问题陈述

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

  1. N 恰好有 2 个不同的质因数。

  2. 对于 N 的每一个质因数 p，p 在 N 的质因数分解中的指数均为偶数。

    • 更正式地说，对于每个质因数 p，最大的非负整数 k 使得 p^k 整除 N ，必须满足 k 是偶数。

现在需要处理 Q 个查询。每个查询给出一个整数 A，要求你找出不超过 A 的最大的 400数。

题目保证，在本题的限制下，总存在至少一个不超过 A 的 400数。

约束条件

  • 查询次数$Q$的范围：1 ≤ Q ≤ 2×10⁵

  • 每个查询$A$的范围：36 ≤ A ≤ 10¹²

  • 所有输入值均为整数

思路：

由于每个质因数的次数都是偶数，所以满足条件的数$a4一定是平方数。

那么我们不妨直接枚举 $a$​ ，它需要满足：

  • $a$​ 恰有 2 个不同的质因数。

考虑怎么快速计算出 O(a)=O(V)≈10^6 以内满足上述条件的数。

我们可以先筛出此范围内的素数，然后直接暴力枚举就好，并不会超时。

这是因为只要我们枚举的过程没有冗余遍历，那么根据质因数分解定理，枚举出的数一定不会重复，时间复杂度就是 O(V) 。

我们可以用一个桶来记录枚举出的数，每次询问就找桶中的前一个枚举出的数，输出其平方即可。可以使用前缀和+二分在 O(log⁡V) 内解决。

总时间复杂度 O(Qlog⁡V+V) ，其中 log⁡V 是二分求平方根的复杂度。

这道题直接调用sqrt()不会WA，不过数大的时候（比如T3）还是建议手写。

AC代码（禁止抄袭！！）： 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> work()
{
	const ll ml = 1e12;
	const int sl = 1e6;
	vector<bool> ip(sl + 1, true);
	ip[0] = ip[1] = false;
	for (int i = 2; i <= sl; i++)
	{
		if (ip[i])
		{
			for (int j = 2 * i; j <= sl; j += i)
			{
				ip[j] = false;
			}
		}
	}
	vector<ll> pr;
	for (int i = 2; i <= sl; i++)
	{
		if (ip[i])
		{
			pr.push_back(i);
		}
	}
	vector<ll> can;
	int m = pr.size();
	for (int i = 0; i < m; i++)
	{
		ll p = pr[i];
		ll pp = p * p;
		if (pp > ml)
		{
			break;
		}
		while (true)
		{
			for (int j = i + 1; j < m; j++)
			{
				ll q = pr[j];
				ll q_power = q * q;
				if (pp > ml / q_power)
				{
					break;
				}
				ll cur = pp * q_power;
				while (cur <= ml)
				{
					can.push_back(cur);
					if (q_power > ml / (q * q))
					{
						break;
					}
					q_power *= q * q;
					cur = pp * q_power;
				}
			}
			if (pp > ml / (p * p))
			{
				break;
			}
			pp *= p * p;
		}
	}
	sort(can.begin(), can.end());
	can.erase(unique(can.begin(), can.end()), can.end());
	return can;
}
int main()
{
	ios::sync_with_stdio (false);
	cin.tie (0);
	cout.tie (0);
	vector<ll> can = work();
	int Q;
	cin >> Q;
	while (Q--)
	{
		ll A;
		cin >> A;
		auto it = upper_bound(can.begin(), can.end(), A);
		if (it == can.begin())
		{
			cout << 0 << "\n";
		}
		else
		{
			cout << *(--it) << "\n";
		}
	}
	return 0;
}

T6 T7

没写，所以不讲

再见！！
点赞！！
点赞！！
点赞！！
:smiling_face_with_hearts::smiling_face_with_hearts::smiling_face_with_hearts::smiling_face_with_hearts::smiling_face_with_hearts::smiling_face_with_hearts::smiling_face_with_hearts::smiling_face_with_hearts::smiling_face_with_hearts::smiling_face_with_hearts::smiling_face_with_hearts::smiling_face_with_hearts::smiling_face_with_hearts::smiling_face_with_hearts:

2 个赞
2

有问题随时提出