自强组模拟赛

Suger_zhy🤔

2026-10-06 19:47:33

发布于：湖北

25阅读

0回复

0点赞

T1 送信卒

题目信息

时间限制: 1s
空间限制: 256M
输入文件: msg.in
输出文件: msg.out

题目描述

在 $n \times m$ 的网格图中，大头兵 u 需要将长官的信件从 $(sx, sy)$ 送到 $(tx,ty)$ 。每个格子上可能有障碍物，有障碍物的格子用 1 表示，这些格子无法通行，其余格子用 0 表示，没有障碍物的格子可以自由通行。u 每次可以选择上下左右任意方向走一格，上下移动需要穿越河流，移动一次耗时为 $k$ 秒；左右移动是在陆地行进，移动一次耗时 1 秒。

因为某些原因，u 需要保证从 $(sx, sy)$ 到 $(tx,ty)$ 的最短路恰好耗时 $s$ 秒，幸运的是，u 可以任意选择过河交通工具，也就是说过河耗时 $k$ 秒可以由 u 决定。但是 u 只能选择同种类型的过河交通工具，也就是说在这次送信任务中所有的 $k$ 是统一的。

那么合适的 $k$ 是多少呢？

输入格式

第一行两个正整数 $n, m$ 。
第二行四个正整数 $sx, sy,tx,ty$ ，分别表示送信任务的起点和终点坐标。
接下来 $n$ 行，每行 $m$ 个数，描述网格图。
最后一行一个正实数 $s$ 。

输出格式

输出仅一行一个实数 $k$ ，表示答案，四舍五入保留 3 位小数，评测时开启逐行比较模式以保证精度。
数据保证有解。如有多解， $k$ 应当尽可能小，最小值为 0。

样例

输入1

4 4
1 1 4 4
0 0 1 1
1 0 0 0
0 0 1 0
0 0 0 0
5.00

输出1

0.667

数据范围与提示

对于所有数据，满足 $1 ≤ n, m ≤ 100, 1 ≤ s ≤ 10^5, 1 ≤ sx,tx ≤ n, 1 ≤ sy,ty ≤ m$ 。

子任务编号	分值	特殊性质
1	30	$n, m ≤ 10$
2	10	特殊性质A
3	60	无

特殊性质 A： $n, m ≤ 10$ ，且保证从起点到终点只有一条不重复经过同一个点的路径。

T2 BOSS 树

题目信息

时间限制: 1s
空间限制: 1024M
输入文件: boss.in
输出文件: boss.out

题目描述

A 是刺客兄弟会某个年代的传奇刺客，为了探寻 A 的传奇故事，A 的后代 a 借助 Animus 进入了 A 的记忆世界。已知 A 在他的时代刺杀了 $n$ 位圣殿骑士，但是 a 目前只知道 A 第一天刺杀了圣殿骑士 1，而第 $i$ 位圣殿骑士的情报必须通过刺杀圣殿骑士 $f_i$ 来取得（保证 $f_i ≤ i - 1$ ）。

a 的精力有限，一天最多只能在 Animus 刺杀 $m$ 位圣殿骑士，并且若 $f_j = i$ ，无论 $m$ 是多少，a 都不可能在同一天刺杀 $i,j$ ，因为 a 必须得离开 Animus 和战友们研究完 $i$ 的情报才能确定 $j$ 的位置。例如，圣殿骑士 3 满足 $f_3 = 1$ ，a 可以在第一天刺杀圣殿骑士 1，但是必须在当天结束 Animus，同战友们研究完 1 提供的情报后，才能锁定 3 的位置，在之后的任意一天都可以对 3 展开刺杀任务。

当代的圣殿骑士团依然在追杀刺客兄弟会，a 必须尽快探索完 A 的记忆帮助刺客兄弟会力挽狂澜，那么 a 最少需要多少天才能在 Animus 刺杀所有 $n$ 位圣殿骑士呢？

输入格式

第一行两个整数 $n, m\ (1 ≤ n ≤ 10^5, 1 ≤ m ≤ n)$ 。
第二行 $n-1$ 个整数，分别表示 $f_2, f_3,…, f_n$ 。

输出格式

第一行一个整数 $ans$ ，表示 a 至少要花费的天数。
接下来一共 $ans$ 行，每行第一个整数 $s_i(s_i ≤ m)$ 表示第 $i$ 天刺杀的圣殿骑士数量，接下来 $s_i$ 个整数表示当天刺杀的圣殿骑士们的编号。

样例

输入1

5 2
1 1 1 2

输出1

3
1 1
2 2 3
2 4 5

数据范围与提示

对于所有数据， $1 ≤ n ≤ 10^5, 1 ≤ m ≤ n, 1 ≤ f_i < i$ 。

子任务编号	分值	其他限制
1	24	$n ≤ 10$
2	26	$m = 1$
3	12	$n ≤ 16$
4	38	无

T3 共轭树图

题目信息

时间限制: 1s
空间限制: 512M
输入文件: reflection.in
输出文件: reflection.out

题目描述

对于以 1 为根的有根树 $T$ ，保证 $T$ 中每个节点的父节点编号一定大于自身的编号。将 $T$ 的边编号为 $1,…, n-1$ ，可通过如下方式生成 $T$ 的共轭树图 $G$ ：

选择 $1,…, n-1$ 的一个排列 $p_1,…, p_{n-1}$ ；
依次考虑 $i = 1,…, n - 1$ ；
删除编号为 $p_i$ 的边，设其端点分别为 $a, b$ ，选择当前树中分别与 $a, b$ 连通的编号最大的点 $u, v$ ，在 $G$ 中连接边 $(u, v)$ 。

对于树 $T$ ，总共可能生成出多少种不同共轭树图 $G$ 呢？答案对 998244353 取模。

输入格式

第一行一个整数 $n$ 。
接下来 $n-1$ 行，每行两个整数 $a, b$ ，表示一条树边。

输出格式

一行一个整数表示答案对 998244353 取模的结果。

样例

输入1

4
1 4
2 3
3 4

输出1

2
样例解释1：令第 $i$ 条输入的边编号为 $i$ 。当 $p$ 为 $\{1, 3, 2\}$ 或 $\{3, 1, 2\}$ 或 $\{3, 2, 1\}$ 时会生成 $E(G) = \{(1, 4),(2, 3),(3, 4)\}$ 。另外三种 $p$ 会生成 $E(G) = \{(1, 4),(2, 4),(3, 4)\}$ 。

输入2

11
1 4
2 6
3 11
4 6
5 6
6 7
7 9
8 9
9 10
10 11

输出2

4605

数据范围与提示

对于 100% 的数据: $1 ≤ n ≤ 3 × 10^3$ 。

Subtask	分值	限制
1	24 pts	$n ≤ 5$
2	16 pts	$n ≤ 14$
3	8 pts	$n ≤ 10^3$ ，所有其他结点与 1 直接相连
4	8 pts	$n ≤ 10^3$ ，树的形态为一条链
5	22 pts	$n ≤ 50$
6	22 pts	无特殊限制

有帮助，赞一个

去预览

0/2000

全部评论 3

Suger_zhy🤔

置顶

有正解，谁能帮我解释一下

#include<bits/stdc++.h>
#define maxn 2000005
using namespace std;
int s[maxn],n,m,k,mxdep;
int dep[maxn];
vector<int>e[maxn],q;
priority_queue<pair<int,int> >Q;
void ins() {
	printf("%d",q.size());
	for(int x:q) printf(" %d",x); puts("");
	for(int x:q) for(int y:e[x]) Q.emplace(dep[y],y);
	q.clear();
}
void dfs(int u) { dep[u]=0; for(int v:e[u]) dfs(v),dep[u]=max(dep[u],dep[v]); dep[u]++; }
int main() {
	scanf("%d%d",&n,&k); s[0]=1;
	for(int i=2,x;i<=n;i++) scanf("%d",&x),s[dep[i]=dep[x]+1]++,e[x].emplace_back(i);
	for(int i=n;i>=1;i--) s[i-1]+=s[i];
	for(int i=1;i<=n;i++) mxdep=max(mxdep,dep[i]);
	int ans=0,p=0;
	for(int i=1,x;i<=mxdep;i++) if(ans<(x=i+(s[i]+k-1)/k)) ans=x,p=i;
	dfs(1);
	printf("%d\n",ans); q.push_back(1); ins();
	for(int i=1;i<ans;i++) {
		int T=k;
		while(T&&Q.size()) T--,q.push_back(Q.top().second),Q.pop();
		ins();
	}
}

16小时前来自湖北

Suger_zhy🤔
有人类会做T3嘛

16小时前来自湖北
0
- Suger_zhy🤔
  回复
  Suger_zhy🤔
  @cjdst @prediction @yxdl1 @Xylophone
  
  16小时前来自湖北
  0
- Suger_zhy🤔
  回复
  Suger_zhy🤔
  如果觉得被@不太好，请提醒我删掉
  
  16小时前来自湖北
  0
- 古希腊掌管AC和WA的神
  回复
  Suger_zhy🤔
  可以考虑树形DP吧，将删边改为合并，新连通块的代表=两个旧中的最大值、
  设 $dp_{u,v}$ 为 $u$ 为根的子树合并完后以 $v$ 为代表的方案数，那么将 $u$ 的子节点分为在 $v$ 前合并和之后合并，转移方程等我再推下（
  
  16小时前来自上海
  0
Suger_zhy🤔
有大佬帮我看看T2和T3的嘛，T2只有62分，后面全超时了；T3我不会写

17小时前来自湖北
0
- Suger_zhy🤔
  回复
  Suger_zhy🤔
  要不要@啊
  
  17小时前来自湖北
  0
- 古希腊掌管AC和WA的神
  回复
  Suger_zhy🤔
  T2可以考虑拓扑吧
  
  17小时前来自上海
  0
- Suger_zhy🤔
  回复
  古希腊掌管AC和WA的神
  我不会啊
  
  17小时前来自湖北
  0