Seventh Mist

GDKOI2016 赛前集训

Day 1

第二题一看就是个很simpIe的树上倍增维护一些乱七八糟的东西, 然后就打了.

第一题没怎么细想, 设了个242^4的状态, 然后随便转移一下, 过了样例就没管了……感觉不是很会拍……

后两题比较神, 想了很久都没想法. 最后一题想骗点分也没有骗到QAQ.

结果第三题是个暴力题, 直接follow the problem就好了.

Day 2

第一题是树上莫队, 然而这东西我之前从来没打过, 想办法证了一下复杂度才敢开始打……

然而我不记得判断一条边是否一定/可能在割集上, 就随便乱搞了一下, 然后只拿了60……

第三题比较神, 是判DFA等价性, 正解是随便设个状态乱搜一通, 然后记忆化一下.

Day 3

第一题是上下界网络流, 打完程序之后测了一发随机数据, 发现TLE了……然后给加了一个动态加边优化, 发现跑得飞快, 但我又不敢保证是对的, 就让两个程序(有/无动态加边)对拍……

第二题我做过, 然后也能回忆起来做法, 就不管了……

第三题比较神, 考试的时候硬是没想起Polya, 要不然就A掉了……

第四题是比较simpIe的数据结构维护连通性, 切掉了.

Day 4

第一题是比较神的数据结构, 算了一下复杂度发现O(nlog3n)O(n \log^3 n)很勉强了, 就没有先做这个……

然后我就去做第二题, 一开始以为是把割点找出来然后随便搞搞, 本来预计1hr能结束这题的……后来发现我太乐观了, 最后我在大概11:00才拍过这题. 本来其他题比较有思路的都来不及了……

然后赶快去做第三题, 因为之前大概看了一遍题意, 就是求多变量单峰函数的极值. 我脑补了梯度下降法, 懒得求导就直接用(f(x+eps,y)/eps,f(x,y+eps)/eps)(f(x +eps, y) / eps, f(x, y + eps) / eps)代替了……然而精度不够, 而且题目说指定有效数字, 但数据里面他认为200200只有一个有效数字……并且coutsetprecision是四舍五入输出的, 但题目要求截断, 于是在多重因素作用下这题就狗带了.

这一场最大的错误可能就是没有去看第四题. 第四题实际上是一个非常simpIe的暴力题……

总结

  1. 经典的验证正确性的方法: 开O2测, 对拍, 测极限, 手算;
  2. 看完所有题再做, 想不出的时候好好写一写思路, keep calm;
  3. 不要嫌难打就不打暴力, 要本着能拿一分是一分的精神;
  4. 注意手算内存.