s组

· · 个人记录

得分

期望得分:100+20+30+10=160

预估得分:100+10+30+0=140

实际得分:100+0+0+0=100

赛时挂分原因

1.t2特殊性质多,想把所有都拿了，但是没考虑到不同性质代码可能很大不同，所以最后没有写完

2.t3暴力30tps由于判断写错位置，调了太久，但是也没调出来

3.t4思路基本没有，想打暴力偷10分，但是时间不够了

策略

优点

每个部分分都考虑了

缺点

时间分配不合理，多的分数分到的时间却少

解题思路

1.t2在图上存变更信息，如果一行要变另一行也变就连权值为0的边，反之则连权值为1的边，最后统计连通块数量2x，答案为2^x

2.t3通过a_i-a_{i-1}=1 想到 a_i-i=a_{i-1}-i+1，就把问题转化为了让区间的数变得相同，最好情况变成中位数。用双指针和大小根堆维护中位数，求出操作次数。

3.t4根号分治，当m<=1000时用n \times n \div k 的dp，否则就用n \times k 的dp。

启示

1.要学会转化问题，例:t2,t3.

2.可以考虑在能够构造出两种算法且时间复杂度相差较大时用根号分治优化，例:t4.

改进

1.合理安排时间

2.多思考转化问题