「NOI2005-2018」的简单题

60%

「NOI2011」道路修建记下每个点左、右分别有多少个国家。
「NOI2015」程序自动分析直接map并查集就搞过去了。
「NOI2014」起床困难综合症贪心，2进制下每一位是独立的，从高到低考虑该位填1/0最终结果。
「NOI2007」社交网络 floyd最短路+最短路计数。
「NOI2015」荷马史诗 $k$ 个点并成一个，不会造哈夫曼树。 Huffman Tree
「NOI2012」随机数生成器 = Codefroces 327C 不小心把 $n$ 多算了一次幂调了半天。
「NOI2014」动物园题面告诉你用KMP做了。
「NOI2009」变换序列 Luogu上套了个匈牙利A了，交到BZOJ上T了然后发现我写的是 $\mathcal{ O } ( n ^ { 3 } )$ 的... 当场自闭
好题，最优复杂度 $\mathcal{ O ( n ) }$ 。这儿有题解： NOI 2009 变换序列 - BYVoid
「NOI2010」能量采集这个模型都被出烂了， $2 \cdot \sum_{i=1}^{n} \sum_{j=1}^{m} \text{gcd} (i,j) -n \cdot m$ 套Mobius反演。
「NOI2014」随机数生成器贪心模拟题，据说有点卡常。
「NOI2005」聪聪与可可 $n , m$ 很小，预处理两人在 $s , t$ 位置聪聪往哪走，然后记忆化搜索。
「NOI2013」向量内积随机算法， $k = 2$ 是个提示。（暂时没看到标准解法
$k=2$ 每两个向量内积模后为 $0 , 1$ ，第 $i$ 向量和前面向量的和内积后不为 $i - 1$ 则该向量会产生解。 $\mathcal O(nd)$
$k = 3$ 两个向量内积的平方模后为 $0 , 1$ ，同样地，可将 $( \sum a_{i} b_{i} )^2$ 暴力拆开，维护 $\sum a_{i} \cdot a_{j}$ 。 $\mathcal O(nd^2)$