首页 > 其他分享 >P6147 [USACO20FEB] Delegation G

P6147 [USACO20FEB] Delegation G

时间:2022-12-11 19:44:26浏览次数:73  
标签:tau 匹配 P6147 Delegation mathcal USACO20FEB

\(\mathcal Link\)

非常套路,神似 NOIp2018D1T3。

首先,只有能整除 \(n-1\) 的数才有可能。

然后考虑判定。一个节点只能向上延伸出一条链,所以其他的链必须两两匹配掉。考虑到由于匹配一条链不会比不匹配更劣,故能匹配则匹配。可以用桶实现。

复杂度 \(\mathcal O(n\tau(n-1))\)

标签:tau,匹配,P6147,Delegation,mathcal,USACO20FEB
From: https://www.cnblogs.com/pref-ctrl27/p/16973991.html

相关文章

  • 洛谷 P6147
    和这题有点类似。首先不难发现,如果当前check的值不是\(n-1\)的约数,一定无解。然后进行一遍DFS,每次用一个multiset保存子树传来的残链长度,然后贪心的配对。最后如......
  • P6143 [USACO20FEB]Equilateral Triangles P & ZLOJ 练习70 C
    writtenon2022-08-22有关曼哈顿距离的题目,同时涉及斜对角线前缀和。此题要求寻找曼哈顿距离意义下的等边三角形,那么涉及曼哈顿距离,我们可以想到,到一个点曼哈顿距离相......
  • P6144 [USACO20FEB]Help Yourself P(DP+线段树)
    P6144[USACO20FEB]HelpYourselfP将线段按照了\(r\)排序,设右端点为\(r\)的答案为\(f_r\),发现这样转移非常困难。\(\color{yellow}{\bigstar\texttt{Trick}}\):区间......