T1 COCI2019 Quiz

Description

题面不长但是放个链接算惹

Solution

Description

给定一棵大小为 $n$ 的树，你需要给树上的点两两配对，对于一组对子 $(u,v)$ ，在树上将 $u\rightarrow v$ 的路径染色。定义一个配对方案合法当且仅当所有边都有颜色。
求方案数对 $10^9 + 7$ 取模。
$n\leq 5\times 10^3,2|n$

博主鉴于自己的树形 dp 水平太 low 前段时间专门练习了下树形 dp。
就把题解和方法整理在一篇博客里算了。
希望自己以后遇到树形 dp 的题目能有更多准确的想法吧 🌹。

T1 寿司餐厅

Description

太长了挂个链接算惹

Solution

Description

如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。现在给定一张无自环无重边的无向连通图，求有多少种合法的加边方案，使得加边后原图是张仙人掌图。$T$ 组测试数据。

$\sum n\leq 5\times 10^5,\sum m\leq 10^6$

Solution

考试的时候碰见了这玩意，Kewth 也说挺常见的。
学的时候不太顺利，怕自己以后又忘了，写篇博客合影留念讲讲自己的理解。

概述

Description

给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 以及 $n$ 个整数 $w_1,w_2,\cdots,w_n$ 。称 $a_1,a_2,\cdots,a_n$ 的一个排列 $a_{p_1},a_{p_2},\cdots,a_{p_n}$ 为一个合法排列当且仅当该排列满足：对于任意的 $k$ 和任意的 $j$ ，如果 $j\leq k$ ，那么 $a_{p_j}\ne p_k$ 。定义一个合法排列的权值为 $w_{p_1}+2w_{p_2}+\cdots + nw_{p_n}$ 。
你需要求出所有合法排列中的最大权值。如果不存在，输出 -1 。
$n\leq 5\times 10^5,a_i\in[0,n],\sum w_i\leq 1.5\times 10^{13}$

T1 分段 DP

Description

给定长度为 $n$ 的单调不减序列 $\{a\}$ 。定义一个区间的权值为区间长度与区间最小值的乘积。求将该序列分成 $k\in [1,n]$ 段的权值和的最大值。
$1\leq n\leq 2\times 10^5,1\leq a_i\leq 8\times 10^3$

Description

有一棵树，初始时只有 $4$ 个节点， $2\ 3\ 4$ 的父节点都是 $1$ 。 $q$ 次操作，每次给定一个点 $u$ 。设操作前点数为 $n$ ，那么本次操作就是将 $n+1$ 和 $n+2$ 连在 $u$ 上。操作后输出目前树的直径大小。

$q\leq 5\times 10^5$ 。

Solution

众所周知，在求解费用流的时由于要建反边，必然会有负权边的存在。所以费用流的通常写法是 EK+SPFA。
事实上我们是可以通过一些技巧，使得 dijkstra 也可以跑费用流。这样的好处是保证了复杂度的下限。
本文将探讨如何使得 dijkstra 可以跑费用流。