HBSX2018day1游记

我一个非正式选手，怎么就rank2了呢？你们还是……（误） 本来是不准备写游记的，但一不小心就rank2了，sup琪盛onlysubxch 去年NOIP怎么考的.. 考完的感觉和清北模拟赛d1一样，A了一题就上天了，暴力打的还没别人好.而且同样是dpA掉. t1是人生第一次写状压，清北讲状压的时候也没认真听，神奇的a了 题目大约是一个n*m棋盘，每个格子有aij,bij两个数，两个人轮流下棋，只能下在上面和左边的所有格子都下了的地方，一个人下了得aij的分，另一个人下了得bij的分，两人都希望自己的分减对方的分最大，双方都用且都知道对方用最优策略，问最后一个人的分减另一个人的分是多少。 画图之后发现每行的棋子数是一个递增序列，然后莫名想到了小学奥数排列组合的“插板法”，然后就试了一下，先画m个球，然后每排有几个棋子就在第几个球后面插一块板 e.g. xxxxo xxooo xoooo xoooo ooooo 就是|o||o|oo|o 然后发现，这不就是1011010010吗？ 于是状压dp，细节就不讲了，半个小时草稿，20分钟码，40分钟调试，过样例 P.S.后来看到洛谷上有这题，就写了个较详细的题解 t2是给一个序列d和浮点数k，求满足d[i]>=int(d[i/k])的字典序最大排列，n！暴力得30分 t3（coat,Counting on a Tree）是给一颗点带权的树，求所有节点数大于等于k的联通子图第k大节点的权值和。本来想写coal（有15分保证是一条链），结果写了个n³的coal，然后还写了个n==k的特判，几种情况都不是的时候猜了个答案，最后奇迹15分，不知道是有n==k还是猜对了那个 一题AC，全场上天，暴力是啥，全靠奇迹。