【2019暑假集训】07.08比赛总结

又双㕛叕自闭了。。。

比赛思路

  • 一上来看到T1感觉是什么奇奇怪怪的数论题目,又看了看T2发现是一道水题,再看看T3感觉可以搞一搞DP。
  • T1思考了一会儿只会一个NM的DP(暴力),转战T2,不久就把T2搞定了。
  • 然后开始看一看T3,设了一个状态,感觉可以搞,但是又感觉很复杂,果断做T1。
  • T1奇思妙想,先是想优化DP,看一看有没有什么单调队列,做一下O(1)的查询啥的,结果发现我并不会搞这一类跟模有关的东西。然后又想贪心,无果。
  • 曾经想到过对于i<j,fi<=fj的这个东西,但是不知道为什么感觉有些i无解并不满足单调性(实际上大于这个i的所有位置都无解),于是就把这个正解的苗头断送了。。。无奈。

赛后消化

  • T1( Brunhilda的生日):实际上根据i<j,fi<=fj的结论可以得出f是单调不下降的,然后扫一遍过去得到下一个f+1的区间的右端点是什么,每一个i能更新的区间为[i+1,i+p-1],p为i的最大质因子。预处理p后扫一遍过去就好了。
  • T2( 雪地踪迹):水题,BFS裸题。少爷机GMOJ比本地还慢,一个程序多交几次的时间还不一样???本地都过了上去就T了。开了O3才跑过去。
  • T3(文本编辑器):线头DP???https://blog.csdn.net/qq_43649416/article/details/95088475

其他

  • EXkmp

总结

  • 常数真烂。新OJ真卡。
  • 惯性思维太严重,有的时候要切实可行地去推一推,而不是根据一点点看似不合法的东西影响了正确的思维。
  • 今天的思路还是比较清晰的,却没有很好地去实现它们。
原文地址:https://www.cnblogs.com/DeepThinking/p/11700928.html