首页 > 冥古之潮
开通博客写题解
头像 AliLexiWalker
发表于 2026-04-01 01:09:26
先从 x 做一遍 BFS，把每个点到 x 的距离分层统计成 c[d]；题目要求锚点距离严格递增，其实就是“每一层最多选 1 个点”。 所以答案就是从这些层里选 k 层、每层选一个点的方案数：做个 0/1 背包 DP，遇到第 d 层就把 f[j] 转移到 f[j+1] 并乘 c[d]，最后 f[k] 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 FoolBlade
发表于 2026-04-01 12:58:45
BFS+DP先按照到达x节点的距离 ，将所有节点进行分类，求出每一类的节点的数量，用cnt数组存储；然后对cnt数组进行 dp , dp[ i ][ j ] 视作 当最大距离为 i 时，选取 j 个点，有多少种方案，则dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i-1 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 此在Dasein
发表于 2026-04-01 02:21:27
1. 问题分析 本问题的核心在于无权联通图中基于距离约束的组合计数。我们需要从图中选取 个点组成集合 ，满足这些点到给定中心点 的最短路径长度（记为 ）呈严格升序且不为 。 拓扑结构与距离：由于所有边长均为 1，且不存在重边与自环，点 到其他点的最短距离可以通过广度优先搜索（BFS）在 时 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 少女SKIKO
发表于 2026-04-02 01:37:38
在x处bfs一遍，随后用cnt[5005]存入拥有i距离的点个数。期间维护max_point（距离x的最远距离）剪枝。预处理二维01背包节省时间状态方程如下：i表示选择的距离，j表示当前已经选择的方案数dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*cnt[i] #include 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 chenlan114
发表于 2026-04-01 11:06:42
#include<bits/stdc++.h> using namespace std; using ll = long long; const ll N = 1e6 + 5; const ll MOD = 1e9 + 7; vector<vector<ll>&g 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 腌萝卜干
发表于 2026-04-01 14:05:04
计数题 很容易想到求一下所有点到的距离 然后问题就转化成了, 在个筐中选个东西, 框里面的东西的编号不同, 编号不同代表不同的方案数的问题 可以用类似背包问题的方法去考虑, 定义状态表示考虑前个框并且已经选了个的方案数 预处理这个 表即可 #include <bits/stdc++.h> 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 olone
发表于 2026-04-01 14:46:06
import java.util.*; public class Main{ static final int N = 1000005; static final int mod = 1000000007; static ArrayList<Integer>[] 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 IA3000
发表于 2026-04-01 21:15:09
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5, M = 5e3 + 5, mod =1e9 + 7; int n, m, q, x; vector<int> e[N]; bool vi 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”