noip2015总结与反思
Day0:
也没什么特别啦,复习了一下数论的模板(然而一点都没用上,果然大家还是不喜欢数论题呢)
Day1:
总体感觉和去年差不多
T1:按照题目模拟即可
T2:有向图最小环。题目性质保证所有的都是简单环,bfs一下就好了
T3:防AK题?这是我的第一感觉...然而数据随机是在告诉我们:大家尽情乱搞吧,乱搞就能过...无力吐槽,随便的爆搜都能过,然而随便构造个数据都能卡掉爆搜啊...
我的做法是类似状压dp,考虑每个牌是否被用了,这样就有2^n个状态,然后暴力转移,复杂度大概是2^n*n^3,然后常数优化一下极限数据卡着2sTAT。实现的话用dfs+hash比较方便
至此,奇怪的Day1结束
考试的时候就想到两张王是否算是一对的一定是个坑点,然后问了出题人,得到的回复是:题目说的很清楚...个卵啊,既然出了这种背景就应该抱着所有人都不会玩斗地主的心态去写题目描述啊,题面的图片居然连超链接都没去掉...
Day1.5:
立了个"Day2会考数论"的flag,事实证明这个flag救了像我这样的数论渣
Day2:
T1:二分+贪心,我记得考前的某场模拟赛好像也出了这个算法
T2:字符串匹配,DP。用f[i][j][k][0/1]表示第1个串匹配到第i位,分成了j个子串,匹配到了第二个串的前k位,最后一个串是否为空串的方案。然后O(1)转移就好了
T3:防AK题?这又是我的第一感觉。然后一开始看错了题目,以为是求“总时间最短”,然后很开心的20min搞完,然后发现看错题了TAT。然后yy了20min一个log的算法,最后弃疗写了两个log的树链剖分,然后自爆...n为300000的时候炸成4s,100000的数据勉勉强强1s卡过
倒数第二次noip结束了
感觉过了一年没什么长进啊,还是该会的会,不会的依然不会,大家水平差不多啦,感觉随便抓出一个都是500+,本来两道防AK的题目结果来了个数据随机直接打回普及组
总之还是要不断努力,训练难题的思维,不能苟且于简单题和模板题,还要补补自己的弱项
就这样了...
发表回复