啊啊啊啊，多给一些牛币吧，想给女朋友换衣服做圣诞礼物QAQ

A. 排队

Solution

根据题意和样例，发现可以一遍走路一遍掏手机打开健康码，所以不难分析出答案是 $max(x\cdot y,a+b)+cmax(x\; \backslash cdot\; y,\; a\; +\; b)\; +\; c$。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49890331

B.斗地主

Solution

经典dp问题，由于 $k\le 50k\; \backslash leq\; 50$, 我们可以用 $dp[i][j]dp[i][j]$ 表示第 $ii$ 轮时，当前积分在模 $kk$ 后为 $jj$ 的方案数。 显然对于初始状态有 $dp[0][0]=1dp[0][0]\; =\; 1$，对于每次转移都可以枚举手头有哪些牌可以出，所以转移式子是： $dp[i][j]->dp[i+1][j+add]dp[i][j]\; ->\; dp[i\; +\; 1][j\; +\; add]$

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49890376

C.点权

Solution

依据题意，我们知道在一颗树上满足条件1的都是叶子，所以其实可以从叶子节点开始扩展，有点类似于拓扑排序： 先建立一个队列，然后把叶子节点丢进去，如果有一个非叶子节点已经被两个叶子节点连通，就把它丢进队列里（因为它现在权值也是2了）。

由于一个节点扩展后变成-1，相当于被删除了，所以以上做法是能算出可行解的。但是这个做法有一个问题就是无法保证答案是最小的。

于是考虑将队列换成优先队列，类似于堆优化 Dijkstra 的思想，如果当前节点的权值被松弛了，那么它就应该继续被丢到优先队列里继续扩展它的相邻节点。

实现上我们需要维护两个值：最小值 $Min1Min1$ 和次小值$Min2Min2$，当 $Min1+Min2Min1\; +\; Min2$ 的值变小时，说明答案可能会更小，应该放进优先队列里让它继续松弛。

时间复杂度: $O(nlo{g}_{2}n)O(nlog\_2n)$

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49891503

D. 牛牛玩 generals

Soltuion

显然是一道数据结构题，由于出现了捕食关系，考虑用并查集维护这一关系。因为区间只有 $[1,m][1,\; m]$，所以如果将区间用多个线段去表示的话，最多不会超过 $mm$ 个（最坏情况每个线段长度都为1），所以在空间复杂度上是可行的。

随后需要考虑对于每个线段会有合并，分裂，删除的操作，这些操作都可以用 set 每次 $O(logn)O(logn)$ 的时间去维护。 在模拟的时候需要注意一些细节，比如 set 的迭代器的值要在删除前取出来，再想清楚以下三种情况即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49972090&returnHomeType=1&uid=105308122

E. 牛牛选路径

Solution

这个题跟欧拉回路的分析方法类似。

首先我们知道：如果能构造一条欧拉回路的话，只需要选取某个权值最小的点，代价是 $Mi{n}^{2}Min^2$。

那么什么时候构造不出欧拉回路呢?如果你稍微画几个图就会发现：有大于等于4个奇数度数的顶点，你怎么连都不能构成欧拉回路。

因为欧拉回路的要求是最多两个奇数度顶点，剩余全是偶数度。 又因为是无向图，度数总值一定是偶数（入度和出度总是成对出现），所以奇数度顶点的数量一定是偶数的。所以我们可以把奇数度的点两两配对，局部形成欧拉回路。那么问题就转换成了给你 $nn$ 个数字，满足 $nn$ 为偶数，让他们两两配对，求 $\sum a_i\cdot a_j\backslash sum\; a\_i\; \backslash cdot\; a\_j$ 的最小值。显然做法是拿最小的去配对最大的，次小的配对次大的......

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49956985&returnHomeType=1&uid=105308122