CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 2022-2023 BUAA XCPC Team Supplementary Training 01 ======

===== C-Cactus Determinant =====
给定 $n$ 个点，$m$ 条边组成的仙人掌图，求其邻接矩阵的行列式的值。

根据行列式的定义 $\sum_{p \in P(N)}{(-1)^{inv(p)}(\prod_{i=1}^{n}{A_{i, p_i}})}$，根据行列式的定义在 $1\sim n$ 行中各取一个点，其编号构成一个长度为 $n$ 的排列，其中会形成多个环。\\
设一个环的长度为 $L$，由于邻接矩阵对称，长度大于 $2$ 的环可以有顺时针、逆时针两种顺序，在计算是一起统计答案，其对答案的贡献为
$$
S=
\begin{cases}
2 &  n\&1 = 1 \\
-2 & n\& 1= 0\ \&\&\ n\ne2\\
-1 & n=2\\
\end{cases}
$$
$n=2$ 时显然为 $-1$，考虑 $n>2$ 的情况，对于任意一个行列式，同时交换 $i,j$ 行和 $i,j$ 列行列式值不变，于是可将环 $v_1,v_2,\cdots,v_L,v_1$ 变换为 $1,2,\cdots,L,1$，此时逆序对数为 $L-1$，则环的贡献为 $(-1)^{L-1} * 2$。\\
将仙人掌图转化为圆方树，对于圆点，设 $dp[i][0/1]$ 表示是/否当前该点的答案，对于方点，设 $dp[i][0/1]$ 表示是/否当前该点的父亲的答案。\\
时间复杂度 $O(n)$

===== H-Hard To Explain =====
**题目大意：给定一棵$n$个点的树，每个节点上有三个值$A_i,B_i,C_i$。有$Q$次询问，每次询问给定$V,T$，需要求出，从$V$到根路径上的所有节点中，满足$C_i\geq T$的最小的$A_i+B_i*T$**

**建立李超线段树，对树进行DFS，若当前访问节点$i$，则在$x\in[1,C_i]$区间插入线段$y=B_ix+A_i$，维护最小值**

**对于一个询问，当DFS访问到$V$时，查询李超线段树上$x=T$的最小值即可，之后回溯时对李超线段树进行操作撤销**

===== Replay =====

首先看到的是A。想了许久也没啥好的思路。总是不易实现，或者会存在一些反例。

之后高湘一打了个表，发现了一些规律，然后罗皓天大概就把思路整出来了。于是就过了。

E和F两道题都有一些坐牢。

F是一个还算简单的主席树，但是最开始先入为主，因为要找大于一半的，所以直接就想到了一个随机化的算法，大概是两个log的样子。按理来说3s，250000的两个log怎么也该是可以过的，但是没有过。然后不断调整随机次数进行尝试，依然没过，浪费了挺多时间和罚时。最后发现是可以做到一个log的，写了一个log就过了。事后发现其实随机化也可以一个log，无所谓了。

E题大体是一个听说叫做模拟费用流的算法，算是很贴切的名字了。（感觉许多优先队列的奇怪操作都有一个单独的名字？）因为细节wa掉了两发。

I题其实是高湘一最开始开的一个题，上来就拍了一个错解上去，wa了几发。被高湘一提醒了一波，想起了支配树这个东西，写完就过了。

===== Dirt =====

F题：交了六发，全是错解在调随机次数。

E题：多组数据要清空

I题：上来给了两发错解。之后是一些细节错误。
CVBB ACM Team

用户工具

站点工具

页面工具
