题外话

这一次考试由boshi大佬负责译题,出数据,评测。
然而boshi大佬显然不满足于译题,出数据,评测。
于是他更改数据范围,缩短时间限制,出卡常数据,提前评测。
litble同学,您的L降为0,F降为1,还剩1次怼大佬机会。[^HNOI2017 Day2 T1 大佬的题目描述]

考试策略

看完题目发现只会做T2,于是高高兴兴花了40多分钟的时间打好T2,调试。

接下来就懵逼了。根据CY喜欢把T1作为最难的题目定律,我去看了T3,然后灵机一动想到了一个解法,高高兴兴打好T3。

又看了T4,首先以为T4是一个以状态作为点的最短路,打完发现样例都过不了(QAQ),接下来又以为T4是网络流,打完发现样例都过不了(QAQ),接下来想到了一个暴力搜索+最短路解法,因为n的数据范围很小,所以应该还能过一些点,就写了,当时估计会爆栈(结果拿了85分?boshi大佬数据水了?)。

T4打了一个半小时多,心态爆炸。距离下考还有半个小时,T1果断输出“0.000”骗分,然后检查打了的题,发现T3我的解法只能做第一问不能做第二问(QAQ),心想自己要爆0了,可是时间又不够了,默默膜了一发boshi大佬(弱的人膜强的人会涨RP的),就咬牙交了知道是错的程序。

以及......boshi大佬出的这套题的数据范围全部只给最大范围然后“数据有梯度”,梯度个鬼啊!天知道是太阳山的梯度还是珠穆朗玛峰的梯度!!!!

T1

期望得分:10 实际得分:15

题目描述:poj3621

题目分析

赋一首押韵的诗:

分数规划
那是个啥
我不会啊
不如爆炸

首先我们令X={0,1},Y={0,1}。$V_i$表示点权,$W_i$是边权,那么 $ANS=\frac{\sum X_iV_i}{\sum Y_jW_j}$。把原式变形可得:$ANS\sum Y_j W_j=\sum X_i V_i$。如果$ANS$小于$\frac{\sum X_iV_i}{\sum Y_jW_j}$即$ANS\sum Y_j W_j $小于$\sum X_i V_i$时,我们需要把ANS缩小。变形得$ANS \sum Y_j W_j - \sum X_i V_i$小于0时。

我们知道奶牛走过的路径一定是一个环(不会是多个环联合,可以用数学方法证明多个环得不到最优解),二分答案,把环上每条边变成(ANS乘边权-起点点权),然后用spfa判断是否有负环即可判断二分下一步干什么。

代码

(在poj上要使用C++而非G++才能A掉,是因为%lf的问题)

T2

期望得分:100 实际得分:100

题目描述:HDU3768,其中去的超市数量改为小于等于15,n小于等于10000

题目分析

显然只有超市和家是有用的节点。我们以每一个超市为起点跑一遍spfa,得到每个超市和家之间的最短距离,然后状态压缩dp。用f(i,zt)表示当前在i号节点(当然超市和家重编号了)时,遍历状态为zt的最短路。zt写成二进制后,如果某一位是1,则该节点去过了。

方程:f(i,zt)=min(f(j,zt-bin[i])),bin表示i在二进制下哪一位是1.

细节看代码,另外在HDU上可过的搜索做法此处会T得很惨。

代码

T3

期望得分:0 实际得分:12

题目描述:HDU2363,n改为小于等于1000

题目分析

二分海拔差,枚举最小高度,spfa判断解可行性。

听着不是很难,不过可能被卡时?:

1.把所有海拔都排个序,二分查找,可以进行spfa的最小海拔要求是$h(i) \leq h(1),h(n) \leq h(i)+lim$。因为1号和n号节点是必然经过的。

2.spfa发现满足条件的海拔差后,直接记录答案跳出这次二分枚举。最后再根据记录的答案重新枚举最低点,求出最短路。

关于第二点:显然出题人boshi大佬并没有注意这一点,他在记录答案挑出二分枚举的同时直接记录的最短路,这种行为是非常不对的,我用HDU的discuss区的这组数据Hack掉了他的代码(我才不说我Hack的理由是看别人的代码都跑得比我的快非常不爽呢):

不过或许是因为在纯随机数据中,出现相同海拔差但是最低最高点不同,导致最短路不同的情况非常罕见,所以像boshi大佬那样的代码依然可以AC。可惜HDU没有Hack功能啊。

代码

## T4

期望得分:20 实际得分:85

题目描述:HDU3311

题目分析

—斯坦纳树是什么,能吃吗?

—不能。

—那为什么要考(烤)?

好吧好吧,此题其实是一道斯坦纳树模板题...

我也是无话可说。

或者你说就是一个状压dp也行。

我们把开凿水井看作有一个水源,引水入城[^noip2010]。则水源要和所有寺庙连通。

首先我们玩n+m+1次spfa来求出任意两点之间的距离dis(i,j)(很暴力,我喜欢)

我们令f(zt,i)为树根为i,寺庙与树根的连通状态为zt的最小权值。那么我们有两种转移方法:

1.更改树根 f(zt,i)=min(f(zt,j)+dis(i,j))

2.枚举子集 f(zt,i)=min(f(s,i)+f(zt^s,i)) (s是zt的子集)

具体是为什么我也不知道...

什么?你问我85分咋拿的?暴力搜索+贪心思想啊。(显然贪心思想是错的,但是boshi大佬的数据比较水...)

然后,boshi大佬这题标程跑了4秒多(卡常技巧多到令人发指),就给5秒时限,把我们卡得嗷嗷嗷的。

不过,我有特殊的卡常技巧[^“我有特殊的××技巧”体,实际上我没有]