Codeforces #677 Div.3 七题题解

A | B | C

过于傻逼。放个代码,估计连代码都没人看(摊手)

D | Districts Connection

是个构造题。

不同团块内部不能连,判断是否能构造生成树 (MST) 并输出方案。

考虑最经典的树——菊花图。我们强行选择第一个团块第一个点。让它和其他不同团块的所有点都连一条边。

这样只有一号团块没在生成树里。我们拿出二号团块的第一个点把一号团块除第一个点都连一遍。OK

所以团块数 \leqslant 2 即可。不然无解。

E | Two Round Dances

经典圆排列裸题。这里要分成等份的两部分。

让原题的输入是 N ,我们记 n \xlongequal{\mathrm{def}} \frac{N}{2}

我们就直接拿出圆排列公式:

Q_{n}^{r}=\frac{A_{n}^{r}}{r}=\frac{n!}{r\cdot \left( n-r \right) !}

证明就无所谓了,百度百科就有(直球),或者 Polya 直接推。

代公式 ,OK。

F | Zero Remainder Sum

总的来说这玩意类似一个背包。

一开始被那个 \lfloor \frac{m}{2} \rfloor 搞到怀疑人生。一直在找这条件有什么结论。

不过显然没有(摊手)其实你任给一个 lim 这题都能做。

设计状态 dp[i=当前行数][j=已选个数][k=当前行选 j 个且 mod K 余数为 k]

然后可以背包 – like 地转移。

然后最后把每行看成一个整体继续背包。完了。复杂度达到了惊人的 \mathcal{O}(n^4)

G | Reducing Delivery Cost

先对全图跑最短路, \mathcal{O}(n^2 \log n)

然后枚举边,把边权设为 0 之后统计答案。

总复杂度 \mathcal{O}(n^2 \log n)

我跑的就尼玛很慢,估计是 STL 的问题(大嘘)。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据