九省联考 2018 Day 1 复现

作者: wjyyy 分类: 记录 发布时间: 2019-03-22 14:52

点击量:90

前言

今年省选还有 15 天。每天针对性刷题学知识点有点枯燥,想到真题还没刷,就对着 pdf 做了一遍。

A. 一双木棋

去年省选得了 25,应该是 \(n=2,m=2\) 的贪心和 \(m=1\) 的递推。

差不多暑假的时候把 DP 做法弄出来了。

然后 WC2019 试机题的传统题是这道题。当时写+调一共 1h20min 1A 了。

这会想半天写不出来……一直在想 dp 怎么转移。

实际上轮廓线是状态啊!就是 dp 数组的下标作为状态,然后针对这个转移,这才是 dp 的本质。

此外,我好像只在这个题里见过“最优策略”,就是指会使后面状态尽可能对自己优。所以应该从后往前转移,也就是从前往后记忆化搜索。

码量 1kb 左右。

今年最简单的题 HB 能有多少人 A 掉呢

—— 匿名用户《如何评价NOI2018九省联合省选?》

B. IIIDX

写了个贪心吧,还是比较好想的。先排个序,然后构造出这棵多叉树

分配给下标最小的子树的数一定最大。而为了保证这个最大,它们一定是连续的最大值。即如果子树大小为 \(sz\),那么分配给它 \(a_{n-sz+1}\sim a_n\) 会使这个根上的数最优。

由此可以推出根上的数是子树中最小的。然后递归贪心就可以了。(说不定能根据推论搞出正解

C. 秘密袭击

前 15 分傻瓜 \(O(n\cdot 2^n)\) 枚举。

链的情况 \(O(n^2\log n)\) 主席树搞定。

但是注意是要求出第 \(k\) 大不是小,不然样例都过不了。

主席树找左儿子的时候会减去一个值,如果是表达式的话要注意打括号(带减法的)。

总结

数据分治一定要检查每个 namespace 的正确性,一个错误考虑会不会在多个 namespace 里同时出现。检查完之后不要把分治时的 if 注释删了。

如果发现一直没有思路,就先 return; 吧。

对问题要考虑本质而不是表象。尤其是状态。

5 分也是分。

多组数据一定要清空(虽然这套没有)。

多读题多读题。

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
lrz Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
lrz
游客

orz wjyyy win!

/* */