论如何让AC代码爆0(然后被CY老师罚款)


T1:frog

题意:

有一个点坐标在实数范围内的凸多边形,有一只青蛙从一号顶点开始跳,每次可以从任意一个顶点跳到任意一个顶点。求这只青蛙不重复遍历多边形的每个顶点的最少跳跃距离和。节点数小于等于720(其实100000+也可以做)

思路:

我们需要脑补一个贪心思路:只有如图的4种遍历方式可能达到最优解:



所以我们可以提前算出从1号节点相邻的两个点分别顺时针和逆时针遍历到每个点的距离,就可以O(n)获得答案。但是这种方法只适用于凸多边形(所以可以通过此题),凹多边形只能用动态规划,详见其他人的题解。本人无能写出那种高深的算法。

*


*

T2:security

题意:

给定一棵树,每个节点i可以花wi元安排守卫,守卫可以守护节点i和i的相邻节点。求守卫整棵树的最小花费。

思路:

多么水的一道树形Dp,而我却爆0,原因很简单:没有开文件。否则这道题就是100。说说思路:令f[x][0]表示x节点所在的子树中,x节点安排守卫的最少花费;f[x][1]表示x被自己的 一个或多个儿子看到的最少花费 ,f[x][2]表示x被自己的爸爸看到的最少花费。
那么这里会有很多转移过程:(y∈x.son)

\begin{equation}
f[x][0]=min(\sum{f[y][0] or f[y][1] or f[y][2]})
\end{equation}
\begin{equation}
f[x][1]=min(\sum{f[y][0] or f[y][1]})
\end{equation}
\begin{equation}
f[x][2]=min(\sum{f[y][0] or f[y][1]})
\end{equation}

其中如果第二个转移中所有子树都选择了f[y][1],那么必须选出一个子树变为f[y][0],否则x节点就没有被任何一个子树看到。

然后我们只要确保了每个状态都正确转移就可以得到一个均摊复杂度O(n)的算法。
(你看头文件多美)

*


*

T3:LIS

题意:

求一个序列包含第k个元素的最长上升子序列

思路:

只需要把k之前的数列抠出来,把新数列中大于等于a[k]的元素删去,再把k之后的数列抠出来,删去小于等于a[k]的元素。分别对两个新序列做O(nlogn)的高速LIS结果相加再加一就是答案。

*


*

T4:palindrome(回文串)

题意:

给定一个字符串,求最少插入几个字母可以获得一个正规的回文串?

思路:

我唯一有把握AC的题,却因为开小了数组挂了(fuck-fuck-fuck-shit)。

*


*