NanoApe's Blog

既是咸鱼又是辣鸡

【Sept+Oct+Nov】NOIP校内模拟赛

NanoApe posted @ 2015年9月17日 14:44 in 蒟蒻不比赛何来学费 , 345 阅读

嗯多谢某神牛提供的不知道是哪一年的各地的NOIP模拟赛(质量挺不错的

给我们这个偏远小渔村提供了宝贵的模拟赛资料

怎么我也高二了QAQ

NOIP玩挂就真的退役了(悲伤

[9.14] #15

被腾爷和CZL实力踩脸

B

题意:给K维空间的几个点,求最远点对(距离为曼哈顿距离)

正解:枚举正负然后算(曼哈顿距离的性质)

C

DP,我发现能单调队列,但是写了个堆多了个log,事实上不需要堆。。。

【Think】

以后DP能利用其单调性就利用,为啥每次都要写个堆QAQ

曼哈顿距离的性质还真的是好玩啊

|x1-x2|+|y1-y2|=max(|(x1+y1)-(x2+y2)|,|(x1-y1)-(x2-y2)|),扩展到K维就各个维正负号都取一遍

[9.16] #16

A

正解是直接判断能否用一个石子救能隔断(答案不超过2)

我是S固定然后T每个水的点都跑一遍网络流

B

每个点求最短路网然后求割点

【Think】

重置网络流可以连S-T的边,就不用全部重建了

求割点的姿势(自己理解)就是dfs的时候返回dfs一遍,然后看哪些点没被反向dfs到

[9.18] #17

被标程踩脸。。。

A

其实可以贪心放。。。

B

求出MST后就转化成求树上路径最长边

没想到居然可以\(O(n^2-1)\)。。。

C

考场写了个搜索+map排重剪枝过了40%

后来发现题解写了个DP,然后阐述了一下DP的正确性,瞬间整个人就poi了

【Think】

有时候敲倍增比敲链剖划得来

[9.21] #18

C

有N个矩形,问他们能构成的最大矩形的大小。(其实这道是模版题。。。

\(O(n^2)\)枚举左上角和右下角,\(O(n^2)\)预处理每个点沿边界线能到达的最远处。

【Think】

自己测试的时候可以跑一些能手算的大数据

[9.23] #20

B

高斯消元简直。。。这么基础的算法都不会敲了QAQ

C

把有可能相交的边看成点,然后染色

【Think】

有两个互质数a和b,则最大无法表示成ax+by的数是ab-a-b

高斯消元需要注意无解和自由基的情况

[10.16] #25

【Think】

B题SXBK卡精度,能少用double就用double

常数优化:减少%运算次数

JSZX11556 说:
Sep 20, 2015 12:33:06 AM

ORZkpm
#17B题树链剖分+RMQ(ST)维护(不用线段树)也挺好写的...(虽然我写残了, 太相信对拍了..). 不过还是O(n²)的dfs预处理好写...
"重置网络流可以连S-T的边,就不用全部重建了" 我表示没看懂

Avatar_small
NanoApe 说:
Sep 20, 2015 12:03:36 PM

#17B那道题貌似知道怎么做后就各种搞吧。。。
至于那句话啊,自己用土话总结出来的建图技巧而已。。。一般没用到


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter