期望得分:\(100+0+0+0\)
实际得分:\(100+20+0+0\)
开考先冲T1 发现\(O(n^2)\)暴力30pts很显然
考虑优化 看到数据范围1e6想到树状数组 而题中条件和逆序对条件较为相似 先手树状数组并在20min后发现假了
回来研究柿子 发现可以转化为求\((a[i]-1)(a[j]-1)<1\)且\(i<j\)的数对个数 大力分讨三种情况即可
之后总览T2-T4 发现T3没有太好的思路 T2在摸了十几组数据之后没有太好的思路 先冲T4
想到了用树形DP来求每一个子树全部都不取的代价 用优先队列来维护\(k\)个路径 发现假了 直接放弃回T2
T4正解长链剖分和对顶堆都是甚么啊
T2看到\(300\)的数据明显区间\(dp\) 但是没有好的思路 往贪心上去靠 按照右端点排序而后维护每一个连续颜色段的起始和结尾
小样例过了但大样例没过 苦调1h无果后交卷
总结:
雀实事菜 也没什么可说的 高科技算法不会情有可原 但是暴力分没有拿到是需要反思的
考时认为人均切T1 需要两道题才不会太难看 所以冲T2时间过久 以后需要增强自信 先打暴力再想正解
T2正解区间dp的转移没有想到 需要多加练习
T3一开始因为题意看错了导致样例推不出来白白放弃 (赛后探讨lyq giegie的暴力60分确实非常暴力但是没有想到) 今后需要仔细审题
不过这次也算是涨涨自信罢 至少以后也不会太惧怕模拟力(喜)