Welcome, Guest! Sign Up RSS

Clever Space

Friday, 11.22.2024

Main »

今天装了win7，告别机房的xp了

RT

Views: 250 | Added by: dhy0077 | Date: 11.20.2013

NOIP2013解题报告

Day1:

T1:答案为(m*10^k+x) mod n 表示快速幂写残，30分

T2：可以证明当两个序列的离散序列相同时，sigma((ai-bi)^2)最小

所以，逆序对。

T3:正解为最大生成森林+树上倍增，这东西不会啊，也没想到。

但是对于60%，我想出了O(mq)的算法,离线加边用并查集维护连通性就可以

Day2:

T1:正解为差分序列的正数和，但是我写了分治，一段段消，

数据巨弱，竟然A了。

T2：正解好像是贪心，但是考场上不敢写贪心啊（其实我根本没想到）

可以写DP+优化（类似LIS的树状数组解法）苦逼的我写了segtree

T3:不会优化，直接爆搜60. 正解：加上最短路优化.

好吧，才拿了450.悲惨的day1T1啊

Views: 377 | Added by: dhy0077 | Date: 11.20.2013