Tips

仅含题解,代码详见github喜欢的话点个star

A. Banana

直接暴力。

B. Out-out-control cars

可以看作相对运动,然后三条射线跟三条线段判相交。
要注意的是大三角形的射线不碰到小三角形也可以yes,这个我们可以通过两个都判一遍来解决。
还有一种情况(数据里好像没有)是两者相对静止并且一个套一个,按照题意也是yes。

C. Coconut

直接模拟。

D. Hack Portals

poj原题。没做过,所以比赛的时候也没做
按照坐标排序后,有一个贪心的结论:i到j这一段区间中,最优情况下最后一个做的不是i就是j。
考虑区间dp,我们用dp[i][j][0]表示i到j这一段最后做i的最小花费,dp[i][j][1]表示i到j这一段最后做j的最小花费。
转移还是挺容易的,转移了以后还要再考虑一下开放的时间。

E. Half-consecutive Numbers

打表。反正我们队只会打表了
q巨题解

F. Islands

hdu原题。
缩点以后看出度为0的点数和入度为0的点数,答案为较大值。注意特判只有1个scc。

G. Query on a string

因为模式串的长度很短,小于等于10,所以修改一个字符最多只会影响主串中10个位置的匹配情况。那么操作可以转化为10次单点修改和区间求和,用一个树状数组维护就可以了。有影响的那个部分可以用kmp匹配一下。

H. Skiing

队友一下子就读懂了,加个源跑最长路就行。

I. Colored Graph

比赛的时候直接抄的论文。还抄错了好多次
回忆同色三角形的计数过程,其实是算了异色三角形的个数$S$,$S=\frac{1}{2}\sum_{i=1}^{V}{a_{i}(V-1-a_{i})}$ 。
现要使得同色三角形个数尽量小,那么就要使每个点的${a_{i}(V-1-a_{i})}$尽量大。
由于和一定,两项自然是越接近结果越大。考虑把点集分为两个,每个集合内部的边都是白色,两个集合之间的都是黑色。
若$V$是偶数,那么每个点的值都是一模一样的,不用调整。
下面重点讨论$V$是奇数的情况,记$n=\lfloor \frac{V}{2} \rfloor$,则两个点集$V1$,$V2$的大小分别为$n$,$n+1$。
在$V1$中,每个点有$n+1$条黑边和$n-1$条白边,这一定是可以更优的。
首先把黑边分散地改成白边,即把在$i$和$n+i$之间的黑边改成白边,此时$V1$的点会很平衡,不过$V2$中有$n$个点变成了$n-1$条黑边和$n+1$条白边。
所以还能更优,当然这时不能再改$n$条边了,要不然就会没完了。将$V2$修改过的$n$个点分成$\frac{n}{2}$组点对,各点对中的白边改成黑边,那么这$n$个点有$n$条黑边和$n$条白边,非常恰好。如果$n$也是奇数,那么就不能这么恰好了,但是大体是一样的,见代码。

J. Our Journey of Dalian Ends

hdu原题。
中转站为源做一遍最小费用流。