2024.04.11NOIP模拟赛 #1 记录

AT_arc160_e [ARC160E] Make Biconnected

给你一棵 \(n\) 个节点由无向边组成的二叉树，树上每个点有权值 \(w_i\)。你可以把两个点之间连无向边，如果将 \(u\) 与 \(v\) 连边，代价是 \(w_u+w_v\)。
请给出一种连边方式，使得连边后，图中去掉任何一个点仍然联通，即图是一个点双连通图。在此基础上，你要使代价最小。
对于全部数据，\(1\leq T\leq 2\times 10^5\)，\(3\leq n\leq 2\times 10^5\)，\(1\leq w_i\leq 10^9\)。

AT_arc160_f [ARC160F] Count Sorted Arrays

给定一个 \(n\)，初始有 \(n!\) 个 \(n\) 的排列 \(S_1,S_2,\dots,S_{n!}\)。给出 \(m\) 次询问，每次两个数 \(a\) 和 \(b\)（\(1 \leq a < b \leq n\)），对于任意一个序列 \(S\)，如果 \(S_a > S_b\)，那么交换 \(S_a\) 和 \(S_b\)，操作结束后输出此时已经排好序的序列个数。
本题强制在线，每次输入两个数 \(x\), \(y\)，上一次的答案为 \(last\)，初始为 \(1\)。
数据以如下方式生成。
\(•\) \(c_i=((x_i+ last)\bmod n)+1\)。
\(•\) \(d_i=((y_i+ last \times 2)\bmod n)+1\)。
\(•\) \(a_i=\min(c_i,d_i)\)。
\(•\) \(b_i=\max(c_i,d_i)\)。
对于全部数据，\(2\leq n\leq 15\)，\(1\leq m\leq 10^5\)，\(1\leq a_i<b_i\leq n\)，\(0\leq x_i,y_i<n\)。

AT_agc062_e [AGC062E] Overlap Binary Tree

定义一个长度为 \(n\) 的二元组序列 \([(l_1,r_1),(l_2,r_2),\cdots,(l_n,r_n)]\) 是好的，当且仅当：
\(•\) \((l_1,r_1,l_2,r_2,\cdots,l_n,r_n)\) 构成一个 \(1\sim 2n\) 的排列。
\(•\) \(l_1<l_2<l_3<\cdots<l_n\)。
\(•\) \(\forall 1\le i\le n,l_i<r_i\)。
\(•\) 恰好存在 \(k\) 个 \(i\) 满足 \(l_i+1=r_i\)。
\(•\) 存在一个有 \(n\) 个节点的有根树满足对于任意 \(i,j\)，\(i,j\) 在树上有祖先-后代关系当且仅当区间 \([l_i,r_i],[l_j,r_j]\) 有交（可以是包含关系），并且该树满足每个节点有零个或两个儿子。
给定 \(n,k\)，数有多少个好的二元组序列，对 \(998244353\) 取模。
对于全部数据，\(1\leq k\leq n\leq 2\times 10^5\)。保证 \(n\) 为奇数。