题解
2025/7/15 DAY1
刘渊 LV11 玄仙 LV 5 @ 2025-7-17 12:02:25

Solution * 2025 - 暑期集训 DAY1

数据截止至2025/7/17 11:00

A. 矩阵转置 `通过人数：22/51 AC率：43% 难度：2/10`

题目已将如何转置描述得非常清晰了， $b_{i,j}=a_{j,i}$ ，双循环模拟即可。注意：数组最大能开约 $10^7$ 个int，这题用数组肯定会MLE，所以需要使用动态数组 vector。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

int main() {
	int h, w;
	cin >> h >> w;
	vector<vector<int> > a(h, vector<int>(w)), b(w, vector<int>(h));
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++) cin >> a[i][j];
	for (int i = 0; i < w; i++)
		for (int j = 0; j < h; j++) b[i][j] = a[j][i];
	
	for (int i = 0; i < w; i++) {
		for (int j = 0; j < h; j++) printf("%d ", b[i][j]);
		puts("");
	}
	return 0;
}

水题+1

B. chess960 `22/35 62% 1/10`

模拟判断：

第一个条件，两个 B 的下标奇偶性不同。建立两个变量分别储存两个 B 的位置，最后判断即可；
第二个条件，K 要在两个 R 之间。只需要建立一个变量，记录到当前位置时一共出现了多少个 R，如果当前位置是 K 时 R只出现了 1 次，则说明 K 在 R 之间。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
using namespace std;

bool PiD(int x, int y) {    // 判断奇偶性
	if ((x%2) != (y%2)) return true;
	else return false;
}

int main() {
	string s;
	cin >> s;
	int B1 = -1, B2 = -1;  // 记录两个B的位置
	int Rn = 0;      // 当前位置时R的数量
	for (int i = 0; i < s.size(); i++) {
		// 记录B
		if (s[i] == 'B' and B1 == -1) B1 = i;
		else if (s[i] == 'B' and B1 != -1) B2 = i;
		// 记录R
		if (s[i] == 'R') Rn++;

		if (s[i] == 'K' and Rn != 1) {
			printf("No");
			return 0;
		}
	}
	
	if (PiD(B1, B2)) printf("Yes");
	else printf("No");
	return 0;
}

水题+1 （没做对的想想自己在干什么）

C. 暑假打工 `16/48 33% 4/10`

这个问题要求我们在不超过 $M$ 天的时间内，选择一些工作来最大化总报酬。每天只能完成一个工作，且每个工作只能完成一次。工作的报酬是在完成后的 $A_i$ 天获得的，我们需要确保所有选择的工作的完成时间加上其对应的 $A_i$ 不超过 $M$ 天。

我们需要在 $M$ 天内选择若干工作，使得它们的总报酬最大。关键在于如何高效地选择这些工作。由于每天只能做一个工作，我们需要在每一天选择当前可选的报酬最高的工作。这样的问题一般选择贪心算法。

贪心策略：对于每一天 $d\,(0\le d<M)$ ，我们可以在所有满足 $A_i\le M-d$ 的工作中选择 $B_i$ 最大的工作。这样，我们确保在剩下的 $M-d$ 天内能够完成该工作并获得报酬。
实现步骤：
- 按 $\bold{A_i}$ 分组：将工作按照 $A_i$ 的值分组，这样我们可以快速访问所有 $A_i=k$ 的工作。
- 维护候选工作：对于每一天 $d$ ，可用的工作是那些 $A_i\le M-d$ 的工作。想要用最快的时间维护报酬的最大值，可以使用大根堆，这样可以在 $O(\log N)$ 时间内获取当前最大 $B_i$ 的工作。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int N = 1e5 + 10;
vector<int> works[N];

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		if (a <= m) works[a].push_back(b);
	}

	priority_queue<int> heap;
	long long total = 0;

	for (int day = 1; day <= m; day++) {
		// 所有元素入堆
		for (int b : works[day]) heap.push(b);
		if (!heap.empty()) {
			total += heap.top();
			heap.pop();
		}
	}

	printf("%d", total);
	return 0;
}

D. 我喜欢因式分解 `22/59 37% 3/10`

~~我一点也不喜欢因式分解！！！~~

要解决这个问题，我们需要找到一对整数 $(A,B)$ 使得 $A^5−B^5=X$ 。给定的约束条件保证这样的整数对存在，因此我们需要高效地找到这对整数。直接枚举所有可能的 $A$ 和 $B$ 在较大数值时效率极低，因此需要优化。

我们注意到 $A^5−B^5$ 可以因式分解为 $(A−B)(A^4+A^3B+A^2B^2+AB^3+B^4)$ 。不过，这种因式分解对直接求解没有帮助。

可以考虑枚举 $A$ 和 $B$ 。考虑到 $X$ 的范围是 $1$ 到 $10^9$ ，所以 $A$ 和 $B$ 的绝对值不会太大。具体来说， $A$ 的绝对值不会超过 $120$ ，因为 $120^5=24883200000$ ，远大于 $10^9$ ， $B$ 同理。

枚举可用双循环或单循环。枚举 $A$ 的可能值，然后对于每个 $A$ ，检查是否存在 $B$ 使得 $B^5=A^5−X$ 。由于 $B$ 可以是正数或负数，我们需要检查所有可能的 $B$ 值。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
using namespace std;

int main() {
	long long x;
	cin >> x;
	for (long long a = -120; a <= 120; a++)
		for (long long b = -120; b <= 120; b++)
			if (pow(a, 5) - pow(b, 5) == x) {
				printf("%d %d", a, b);
				return 0;
			}
	return 0;
}

水题？

E. 阶乘与倍数 `9/48 18% 7/10`

解决此题的关键在于高效地确定满足条件的最小 $N$ ，尤其是考虑到 $K$ 可以达到 $10^{12}$ ，直接计算阶乘直到找到符合条件的 $N$ 显然不现实。

正解：

首先，我们需要对 $K$ 进行质因数分解，得到其所有质因数及其指数。例如，如果 $K=30$ ，则分解结果为 $2\times3\times5$ 。
对于每个质因数 $p$ 及其指数 $e$ ，我们需要找到最小的 $N$ 使得 $N!$ 包含至少 $e$ 个 $p$ 的因子。这一步可以通过二分搜索来高效完成。具体来说，对于每个质因数 $p$ ，计算满足条件的 $N_p$ ，然后最终的 $N$ 就是所有 $N_p$ 中的最大值。
计算 $N!$ 中质因数的次数：使用勒让德公式，即在 $N!$ 中质数 $p$ 的指数为

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

using ll = long long;

vector<pair<ll, ll> > Divisor(ll k) {     // 质因数分解
    vector<pair<ll, ll> > divisors;
    for (ll p = 2; p * p <= k; p++) {
        if (k % p == 0) { 
            ll cnt = 0;
            while (k % p == 0) {
                k /= p;
                cnt++;
            }
            divisors.emplace_back(p, cnt);
        }
    }
    if (k > 1) divisors.emplace_back(k, 1);
    return divisors;
}

ll PEn(ll n, ll p) {    // Number of Power Exponent 幂指数个数
    ll count = 0;
    while (n > 0) {
        n /= p;
        count += n;
    }
    return count;
}

ll BS_min(ll p, ll e) {        // Binary Search for Min n 二分查找 (LowerBound)
    ll l = 0, r = p * e;
    ll result = r;
    while (l <= r) {
        ll mid = l+r >> 1;
        if (PEn(mid, p) >= e) {
            result = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return result;
}

int main() {
    ll k;
    cin >> k;
    if (k == 1) {
        printf("1");
        return 0;
    }
    vector<pair<ll, ll> > divisors = Divisor(k);
    ll maxN = 0;
    for (auto [p, e] : divisors) {
        ll nowN = BS_min(p, e);
        if (nowN > maxN) maxN = nowN;
    }
	printf("%lld", maxN);
    return 0;
}

F. 黄金商人 `8/24 33% 7/10`

我们需要计算所有可能的起点~终点城市对（包括起点和终点相同的情况），要求从起点可以通过零条或多条单向道路到达终点。由于图是有向的且可能包含环，我们需要对每个起点城市进行深度优先搜索（DFS），统计从该城市可达的所有城市数量（包括自身），然后将所有起点的可达城市数量累加即可得到答案。

图的表示：使用邻接表存储有向图
可达性计算：对每个城市作为起点进行DFS遍历
避免重复访问：每次DFS使用独立的访问标记数组
计数累加：累加每个起点可达的城市数量

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

const int N = 2e5 + 10;
int a[N], _min[N];
vector<vector<int> > adjt(N);    // Adjacency table 邻接表   

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adjt[x].push_back(y);
    }

    fill(_min+1, _min+1+n, INT_MAX);
    int _max = -INT_MAX;
    for (int u = 1; u <= n; u++)
        for (int v : adjt[u]) {
            if (_min[u] > a[u]) _min[v] = min(_min[v], a[u]);
            else _min[v] = min(_min[v], _min[u]);
            _max = max(_max, a[v] - _min[v]);
        }

    printf("%d", _max);
    return 0;
}

目前还没有评论...

2025/7/15 DAY1

Solution * 2025 - 暑期集训 DAY1

A. 矩阵转置 `通过人数：22/51 AC率：43% 难度：2/10`

B. chess960 `22/35 62% 1/10`

C. 暑假打工 `16/48 33% 4/10`

D. 我喜欢因式分解 `22/59 37% 3/10`

E. 阶乘与倍数 `9/48 18% 7/10`

F. 黄金商人 `8/24 33% 7/10`

0 条评论

状态

开发

支持

关于

2025/7/15 DAY1

Solution * 2025 - 暑期集训 DAY1

A. 矩阵转置 通过人数：22/51 AC率：43% 难度：2/10

B. chess960 22/35 62% 1/10

C. 暑假打工 16/48 33% 4/10

D. 我喜欢因式分解 22/59 37% 3/10

E. 阶乘与倍数 9/48 18% 7/10

F. 黄金商人 8/24 33% 7/10

0 条评论

状态

开发

支持

关于

登录

A. 矩阵转置 `通过人数：22/51 AC率：43% 难度：2/10`

B. chess960 `22/35 62% 1/10`

C. 暑假打工 `16/48 33% 4/10`

D. 我喜欢因式分解 `22/59 37% 3/10`

E. 阶乘与倍数 `9/48 18% 7/10`

F. 黄金商人 `8/24 33% 7/10`