Day8 题解

T1 一千万零一只斑点狗

题目大意

给定一个正整数 N（1 ≤ N ≤ 1e15），将其转换为一个由小写字母组成的字符串。转换规则类似于 Excel 表格的列名：

  • 1 → "a", 2 → "b", ..., 26 → "z"
  • 27 → "aa", 28 → "ab", ..., 52 → "az"
  • 53 → "ba", ..., 702 → "zz"
  • 703 → "aaa", ...

解题思路

这个问题类似于将十进制数转换为26进制数，但有一个关键区别：通常的26进制数是0-25表示a-z，而这里是1-26表示a-z。因此，我们需要对N进行一些调整：

  1. 每次处理当前位时，先将N减1，这样0-25对应a-z。
  2. 不断将N除以26，直到N为0。每次的余数就是当前位的字母。
  3. 由于我们从低位到高位计算，最后需要将结果字符串反转。

解决代码

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    freopen("dog.in", "r", stdin);
    freopen("dog.out", "w", stdout);
    long long n;
    cin >> n;
    string ans;
    while (n > 0) {
        n--; // 调整到0-25的范围
        char c = 'a' + (n % 26);
        ans += c;
        n /= 26;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}

T2 金字塔

问题重述

给定nn个点的坐标(xi,yi)(x_i, y_i)和高度hih_i。所有点满足以下条件：

  • 中心点(Cx,Cy)(C_x, C_y)的高度HH满足：H=max(0,H−∣x−Cx∣−∣y−Cy∣)H = max(0, H - |x - C_x| - |y - C_y|) 需要确定唯一的(Cx,Cy,H)(C_x, C_y, H)。题目保证解存在且唯一。

解题思路

  1. 对于任意一个点，如果h_i > 0，那么它直接给出了H的约束：H=hi+∣xi−Cx∣+∣yi−Cy∣H = h_i + |x_i - C_x| + |y_i - C_y|。
  2. 由于坐标范围较小（0≤Cx,Cy≤100）（0≤C_x,C_y≤100），可以枚举所有可能的(Cx,Cy)(C_x, C_y)。
  3. 对于每个候选(Cx,Cy)(C_x, C_y)，根据h_i>0的点计算H，并验证是否所有点都满足条件。
  4. 确保计算出的H对于所有点都成立.
#include<bits/stdc++.h>
using namespace std;

struct Point {
    int x, y, h;
};

int main() {
	freopen("tower.in", "r", stdin);
    freopen("tower.out", "w", stdout);
    int N;
    cin >> N;
    vector<Point> points(N);
    for (int i = 0; i < N; ++i) cin >> points[i].x >> points[i].y >> points[i].h;

    for (int cx = 0; cx <= 100; ++cx) { //枚举中心点
        for (int cy = 0; cy <= 100; ++cy) {
            int H = -1;
            bool flag = true;
            //用h[i] > 0的点确定H
            for (auto p : points) {
                if (p.h > 0) {
                    int tempH = p.h + abs(p.x - cx) + abs(p.y - cy);
                    if (H == -1) {
                        H = tempH;
                    } else if (H != tempH) {
                        flag = false;
                        break;
                    }
                }
            }
            
            //验证所有点
            if (flag) {
                for (auto p : points) {
                    int hh = max(H - abs(p.x - cx) - abs(p.y - cy), 0);
                    if (p.h != hh) {
                        flag = false;
                        break;
                    }
                }
            }
            if (flag) {
                cout << cx << " " << cy << " " << H << endl;
                return 0;
            }
        }
    }
    return 0;
}

T3 走迷宫

题目大意

给定一个H×W的迷宫，包含空地（'.'）和墙壁（'#'）。你需要选择两个不同的空地作为起点和终点，找到它们之间的最短路径（只能上下左右移动）。题目要求所有可能的起点和终点组合中最长最短路径的长度。

解题思路

这道题的核心是对于每个空地，计算它到其他所有空地的最短路径，然后取所有最短路径中的最大值。具体步骤如下：

  1. 遍历迷宫中的所有空地
  2. 对于每个空地，使用BFS计算它到其他所有空地的最短距离
  3. 在所有BFS结果中，记录最大的最短距离

算法分析

  • 时间复杂度：O((H×W)2)O((H×W)^2)，最坏情况下需要为每个空地做一次BFS
  • 空间复杂度：O(H×W)O(H×W)，用于存储迷宫和BFS队列

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
int n, m;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int g[25][25];
int dist[25][25];


int bfs(int a, int b)
{
	memset(dist, -1, sizeof dist);
	queue<PII> q;
	q.push({a, b});
	dist[a][b] = 0;
	int res = 0;
	while(!q.empty())
	{
		auto p = q.front();
		q.pop();
		
		for(int i = 0; i < 4; i++)
		{
			int nx = p.first + dx[i], ny = p.second + dy[i];
			
			if(nx < 1 || nx > n || ny < 1 || ny > m || g[nx][ny] == 0 || dist[nx][ny] != -1)
				continue;
			
			q.push({nx, ny});
			dist[nx][ny] = dist[p.first][p.second] + 1;
			res = max(res, dist[nx][ny]);
		}
		
		
	}
	return res;
}

int main()
{
	freopen("maze.in", "r", stdin);
	freopen("maze.out", "w", stdout);
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			char c;
			cin >> c;
			if(c == '.') g[i][j] = 1;
			else g[i][j] = 0;
		}
	int ans = -1;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			if(g[i][j] == 0 ) continue;
			ans = max(ans, bfs(i, j));
		}
	cout << ans << endl;
	return 0;
}

T4 划分问题

思路1：

1.标记所有数字出现的个数

2.枚举k，同时累加小于k的所有数字个数，判断剩下的数字和小于k的数字是否相同，累加答案。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20;
int f[N];
int main()
{
	freopen("hf.in", "r", stdin);
	freopen("hf.out", "w", stdout);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		f[x] ++;
	}
	int ans = 0, res = 0;
	for(int i = 1; i <= N; i++)
	{
		if(res == n - res) ans ++;
		res += f[i];
	}
	cout << ans;
	return 0;
}

思路2：

答案一定在中间两个数之间

代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N];

int main()
{
	freopen("hf.in", "r", stdin);
	freopen("hf.out", "w", stdout);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1, a+n+1);
	int d = n/2;
	cout << a[d+1]-a[d];
	
	return 0;
}

T5 序列查询

平衡树模板题

可以用多重集合平替。

题目要求：维护一个动态多重集合，支持三种操作：

  1. 插入元素 1 x：将 x 加入集合。
  2. 查询第 k 大 2 x k：输出所有 ≤ x 的元素中第 k 大的值（从大到小排序的第 k 个）。
  3. 查询第 k 小 3 x k：输出所有 ≥ x 的元素中第 k 小的值（从小到大排序的第 k 个）。
    若不存在则输出 -1。

核心思路：multiset + 迭代器操作

利用 C++ STL 的 multiset（自动排序、允许重复元素）和边界查找函数 upper_bound()、lower_bound() 高效处理查询：

  • 插入操作：直接调用 insert(x)。
  • 查询操作 2（≤ x 的第 k 大）：
    1. 用 upper_bound(x) 找到第一个 大于 x 的位置 it（[begin, it) 区间即所有 ≤ x 的元素）。
    2. 从 it 向前移动 k 次（即从大到小遍历）。
    3. 若移动中遇到 begin() 或移动次数不足 k，输出 -1。
  • 查询操作 3（≥ x 的第 k 小）：
    1. 用 lower_bound(x) 找到第一个 ≥ x 的位置 it（[it, end) 区间即所有 ≥ x 的元素）。
    2. 从 it 向后移动 k-1 次（当前位置为第 1 小，移动 k-1 次到第 k 小）。
    3. 若移动中遇到 end()，输出 -1。

代码

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main()
{
	freopen("list.in", "r", stdin);
	freopen("list.out", "w", stdout);
	multiset<LL> s;
	int q;
	cin >> q;
	while(q --)
	{
		LL op, x, k;
		cin >> op >> x;
		if(op == 1)
		{
			s.insert(x);
		}
		else if(op == 2) { //找到第k大的数
			cin >> k;
			auto it = s.upper_bound(x); //找到第一个>x的位置
			bool flag = true;
			while(k -- && it != s.begin()) it --;
			if(k >= 0 || it == s.end()) flag = false;
			cout << (flag?*it:-1) << endl;
		}
		else {
			cin >> k;
			auto it = s.lower_bound(x) ;//找到第一个>= x的位置
			while(--k && it != s.end()) it ++;
			if(it == s.end()) cout << -1 << endl;
			else cout << *it << endl;
		}
	}
	return 0;
}

复杂度：

  • 插入和查询均为 O(log⁡n)O(\log n)（multiset 的平衡树特性），总复杂度 O(qlog⁡n)O(q \log n)。

T6 模i

题目概述

给定一个长度为N N 的序列 AA，要求将序列分成连续的若干段（每段非空），使得第i i 段（从1开始计数）的元素之和能被ii整除。求满足条件的分段方案数，结果对 109+710^9 + 7取模。

解题思路

使用动态规划解决该问题，具体思路如下：

  1. 状态定义：定义dp[i][j]\text{dp}[i][j] 表示将前jj 个元素分成 ii段的方案数。
  2. 状态转移：对于dp[i][j]\text{dp}[i][j]，其值等于所有满足以下条件的 dp[i−1][k]\text{dp}[i-1][k] 的和：
    • k<jk < j
    • 前缀和 sum[k]≡sum[j](modi)\text{sum}[k] \equiv \text{sum}[j] \pmod{i}
  3. 优化转移：使用辅助数组cnt[i][r]\text{cnt}[i][r]记录模 i i 余数为 rr 的dp[i−1][k] \text{dp}[i-1][k]的和。这样，计算dp[i][j]\text{dp}[i][j] 时只需查询cnt[i][sum[j] mod i] \text{cnt}[i][\text{sum}[j] \bmod i]。
  4. 更新：在计算过程中，先计算所有dp[i][j]\text{dp}[i][j]的值，再更新cnt\text{cnt} 数组，确保同一 jj 的不同 i i之间互不干扰。

复杂度分析

  • 时间复杂度：O(N2)O(N^2)，其中NN 最大为 3000，内层循环总操作次数约为N(N+1)2\frac{N(N+1)}{2} 。
  • 空间复杂度：O(N2)O(N^2)，用于存储 cnt\text{cnt} 数组。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const int N = 3005;
LL a[N], sum[N];
LL dp[N][N], cnt[N][N];
// dp[i][j]：前 j 个元素分成 i 段的方案数
// cnt[i][r]：模 i 余数为 r 的 dp[i-1][k] 的和
int main() {
	freopen("mod.in", "r", stdin);
	freopen("mod.out", "w", stdout);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) cin >>a[i];
	
	// 计算前缀和
	for (int i = 0; i < N; ++i) sum[i + 1] = sum[i] + a[i];
	
	
	dp[0][0] = 1;  // 初始状态：0 个元素分成 0 段的方案数为 1
	cnt[1][0] = 1;  // 对应 dp[0][0] = 1
	
	LL ans = 0;
	for (int j = 1; j <= n; ++j) {
		// 第一步：计算所有 dp[i][j]（i 从 1 到 j）
		for (int i = 1; i <= j; ++i) {
			LL r = sum[j] % i;
			dp[i][j] = cnt[i][r];
		}
		
		// 第二步：更新 cnt[i+1] 数组
		for (int i = 1; i <= j; ++i) {
			LL r = sum[j] % (i + 1);
			cnt[i + 1][r] = (cnt[i + 1][r] + dp[i][j]) % mod;
		}
		
		// 如果 j 是最后一个位置，累加答案
		if (j == n) {
			for (int i = 1; i <= n; ++i) {
				ans = (ans + dp[i][j]) % mod;
			}
		}
	}
	
	cout << ans << endl;
	return 0;
}

为什么需要满足前缀和条件 sum[k]≡sum[j](modi)\text{sum}[k] \equiv \text{sum}[j] \pmod{i}？

在动态规划的状态转移中，我们定义 dp[i][j]\text{dp}[i][j] 表示将前 jj 个元素分成 ii 段的方案数。为了确保第 ii 段（即从第 k+1k+1 到第 jj 个元素）的和能被 ii 整除，我们需要满足以下条件：

  1. 第 ii 段的和：第 ii 段的和为 sum[j]−sum[k]\text{sum}[j] - \text{sum}[k]。
  2. 整除条件：prefix[j]−prefix[k]\text{prefix}[j] - \text{prefix}[k] 必须能被 ii 整除，即 sum[j]−sum[k]≡0(modi)\text{sum}[j] - \text{sum}[k] \equiv 0 \pmod{i}。
  3. 模运算等价：这意味着 sum[j]≡sum[k](modi)\text{sum}[j] \equiv \text{sum}[k] \pmod{i}。

因此，sum[k]≡sum[j](modi)\text{sum}[k] \equiv \text{sum}[j] \pmod{i} 是确保第 ii 段的和能被 ii 整除的关键条件。

T7 直径集合

题目概述

给定一棵包含 nn 个节点的树，需要选出两个或更多节点，使得集合中任意两节点之间的距离均等于树的直径 DD。求方案数对 998244353998244353 取模的结果。

解题思路

  1. 求树的直径：通过两次 BFS 找到树的一条直径（最长路径）的两个端点 uu 和 vv，并记录路径。直径长度 DD 为路径的边数。
  2. 分类讨论：
    • 直径 DD 为偶数：存在唯一中心节点 cc。方案数为从 cc 的不同子树中选取至少两个深度为 D/2D/2 的节点的组合数。
    • 直径 DD 为奇数：存在一条中心边 (u0,v0)(u_0, v_0)。方案数为 u0u_0 侧距离 u0u_0 为 (D−1)/2(D-1)/2 的节点数与 v0v_0 侧距离 v0v_0 为 (D−1)/2(D-1)/2 的节点数的乘积。
  3. 方案计算：
    • 偶数情况：以中心节点 cc 为根进行 BFS，统计每个子树中深度为 D/2D/2 的节点数。设子树计数为 a1,a2,…,aka_1, a_2, \ldots, a_k，则方案数为 ∏i=1k(ai+1)−1−∑i=1kai\prod_{i=1}^{k} (a_i + 1) - 1 - \sum_{i=1}^{k} a_i。
    • 奇数情况：分别以 u0u_0 和 v0v_0 为根，避开中心边的另一节点进行 BFS，统计距离为 (D−1)/2(D-1)/2 的节点数，两者相乘即为方案数。

解释偶数情况的方案数计算

在偶数情况下，树的直径 DD 是偶数，存在一个唯一的中心节点 cc，使得所有直径路径都经过 cc。我们需要选择两个或更多节点，使得它们之间的距离都等于 DD。这意味着：

  1. 节点选择条件：

    • 每个选中的节点必须位于 cc 的不同子树中（否则它们之间的距离会小于 DD）。
    • 每个选中的节点必须距离 cc 为 D/2D/2（否则它们之间的距离不会等于 DD）。

  2. 问题转化：

    • 以 cc 为根，统计每个子树中距离 cc 为 D/2D/2 的节点数。设子树为 T1,T2,…,TkT_1, T_2, \ldots, T_k，对应的节点数为 a1,a2,…,aka_1, a_2, \ldots, a_k。
    • 我们需要从这些子树中选至少两个节点，且每个子树最多选一个节点（因为如果从同一子树选两个节点，它们之间的距离会小于 DD）。

  3. 组合数学推导：

    • 对于每个子树 TiT_i，可以选择不选它（贡献 11 种情况），或者选它的一个节点（贡献 aia_i 种情况）。因此，子树 TiT_i 的总贡献是 (1+ai)(1 + a_i)。
    • 所有子树的组合贡献是 ∏i=1k(1+ai)\prod_{i=1}^{k} (1 + a_i)。
    • 但我们需要去掉以下情况：
      • 不选任何节点（对应 −1-1）。
      • 只选一个节点（对应 −∑i=1kai-\sum_{i=1}^{k} a_i）。
    • 因此，合法方案数为： prodi=1k(1+ai)−1−∑i=1kaiprod_{i=1}^{k} (1 + a_i) - 1 - \sum_{i=1}^{k} a_i

  4. 直观理解：

    • ∏i=1k(1+ai)\prod_{i=1}^{k} (1 + a_i) 是所有可能的选法（包括不选和选一个）。
    • 减去 11 是去掉“什么都不选”的情况。
    • 减去 ∑i=1kai\sum_{i=1}^{k} a_i 是去掉“只选一个节点”的情况。
    • 剩下的就是“至少选两个节点”的情况。

例子

假设 k=3k=3，a1=2a_1=2，a2=1a_2=1，a3=1a_3=1：

  • 总选法：(1+2)(1+1)(1+1)=3×2×2=12(1+2)(1+1)(1+1) = 3 \times 2 \times 2 = 12。
  • 去掉不选：12−1=1112 - 1 = 11。
  • 去掉只选一个：11−(2+1+1)=711 - (2 + 1 + 1) = 7。
  • 合法方案数为 77，对应：
    • 选 T1T_1 和 T2T_2：2×1=22 \times 1 = 2 种。
    • 选 T1T_1 和 T3T_3：2×1=22 \times 1 = 2 种。
    • 选 T2T_2 和 T3T_3：1×1=11 \times 1 = 1 种。
    • 选 T1T_1、T2T_2 和 T3T_3：2×1×1=22 \times 1 \times 1 = 2 种。
    • 总计 2+2+1+2=72 + 2 + 1 + 2 = 7 种。

代码实现（C++14）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200000 + 5;  // 最大节点数
const int mod = 998244353;    // 模数

int n;                        // 树的节点数
vector<vector<int>> g;    // 树的邻接表表示

// BFS函数：从start出发，避开block节点，统计距离为depth的节点数
int bfs(int start, int block, int depth, int n) {
	vector<bool> vis(n, false);  // 标记节点是否访问过
	queue<pair<int, int>> q;     // BFS队列，存储节点和当前深度
	q.push({start, 0});          // 起点入队，初始深度为0
	vis[start] = true;           // 标记起点已访问
	int cnt = 0;                 // 统计满足条件的节点数
	while (!q.empty()) {
		int u = q.front().first;   // 当前节点
		int dep = q.front().second; // 当前深度
		q.pop();
		if (dep == depth) {   // 如果深度等于目标深度，计数+1
			cnt++;
		}
		if (dep >= depth) {  // 如果深度超过目标深度，不再继续
			continue;
		}
		for (int v : g[u]) {   // 遍历当前节点的邻居
			if (v == block) continue;  // 避开block节点
			if (!vis[v]) {          // 如果邻居未访问过
				vis[v] = true;      // 标记已访问
				q.push({v, dep + 1}); // 入队，深度+1
			}
		}
	}
	return cnt;  // 返回满足条件的节点数
}

int main() {
	freopen("set.in", "r", stdin);
	freopen("set.out", "w", stdout);
	cin >> n;  // 输入节点数
	g.resize(n);  // 调整邻接表大小
	for (int i = 0; i < n - 1; i++) {  // 输入树的边
		int u, v;
		cin >> u >> v;
		u--; v--;  // 转换为0-based
		g[u].push_back(v);  // 无向图，双向连接
		g[v].push_back(u);
	}
	
	// 第一次BFS：找到直径的一个端点u
	vector<int> dist1(n, -1);  // 距离数组，初始化为-1
	queue<int> q;
	dist1[0] = 0;  // 从节点0开始
	q.push(0);
	int u = 0;      // 记录距离最远的节点
	while (!q.empty()) {
		int cur = q.front(); 
		q.pop();
		if (dist1[cur] > dist1[u]) u = cur;  // 更新最远节点
		for (int v : g[cur]) {
			if (dist1[v] == -1) {  // 如果未访问过
				dist1[v] = dist1[cur] + 1;  // 更新距离
				q.push(v);  // 入队
			}
		}
	}
	
	// 第二次BFS：找到直径的另一个端点v_end，并记录路径
	vector<int> dist2(n, -1);  // 距离数组
	vector<int> pre(n, -1);     // 前驱数组，用于记录路径
	queue<int> q2;
	dist2[u] = 0;  // 从u开始
	q2.push(u);
	int v_end = u;  // 记录最远节点
	while (!q2.empty()) {
		int cur = q2.front(); 
		q2.pop();
		if (dist2[cur] > dist2[v_end]) v_end = cur;  // 更新最远节点
		for (int next : g[cur]) {
			if (dist2[next] == -1) {  // 如果未访问过
				dist2[next] = dist2[cur] + 1;  // 更新距离
				pre[next] = cur;      // 记录前驱
				q2.push(next);        // 入队
			}
		}
	}
	
	// 重建直径路径
	vector<int> path;
	int cur_node = v_end;
	while (cur_node != -1) {  // 从v_end回溯到u
		path.push_back(cur_node);
		cur_node = pre[cur_node];
	}
	reverse(path.begin(), path.end());  // 反转路径，使其从u到v_end
	int D = path.size() - 1;  // 直径长度（边数）
	
	if (D % 2 == 0) {  // 直径长度为偶数，存在中心节点
		int center = path[D / 2];  // 中心节点
		vector<int> depth_arr(n, -1);  // 记录每个节点的深度
		vector<int> from(n, -1);       // 记录节点属于哪个子树
		queue<int> q3;
		depth_arr[center] = 0;  // 中心节点深度为0
		q3.push(center);
		while (!q3.empty()) {
			int cur = q3.front(); q3.pop();
			for (int next : g[cur]) {
				if (depth_arr[next] == -1) {  // 如果未访问过
					depth_arr[next] = depth_arr[cur] + 1;  // 更新深度
					if (cur == center) {
						from[next] = next;  // 直接邻居属于自己的子树
					} else {
						from[next] = from[cur];  // 否则继承父节点的子树
					}
					q3.push(next);  // 入队
				}
			}
		}
		
		// 统计每个子树中深度为D/2的节点数
		unordered_map<int, int> countMap;
		for (int neighbor : g[center]) {
			countMap[neighbor] = 0;  // 初始化子树计数器
		}
		for (int i = 0; i < n; i++) {
			if (i == center) continue;
			if (depth_arr[i] == D / 2) {  // 如果深度为D/2
				countMap[from[i]]++;      // 对应子树计数+1
			}
		}
		vector<int> counts;
		for (int neighbor : g[center]) {
			counts.push_back(countMap[neighbor]);  // 收集各子树的计数
		}
		
		// 计算方案数：乘积减去单点和空集
		LL ans = 1;
		LL total = 0;
		for (int cnt : counts) {
			ans = (ans * (cnt + 1)) % mod;  // 乘积部分
			total = (total + cnt) % mod;     // 单点部分
		}
		ans = (ans - 1 - total) % mod;      // 减去空集和单点
		if (ans < 0) ans += mod;            // 处理负数
		cout << ans << endl;
	} 
	else {  // 直径长度为奇数，存在中心边
		int u0 = path[(D - 1) / 2];  // 中心边的左端点
		int v0 = path[(D + 1) / 2];  // 中心边的右端点
		// 分别统计u0侧和v0侧距离为(D-1)/2的节点数
		int cnt1 = bfs(u0, v0, (D - 1) / 2, n);
		int cnt2 = bfs(v0, u0, (D - 1) / 2, n);
		LL ans = 1LL * cnt1 * cnt2 % mod;  // 方案数为两部分的乘积
		cout << ans << endl;
	}
	
	return 0;
}

时间复杂度为 O(n)O(n)

  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 82ms
  4. Powered by Hydro v5.0.0-beta.13 Community