2019.02.15【NOIP提高组】模拟 B 组 总结

考场AK，开心( * ^ ▽ ^ * )
上面的是假的，毕竟总结没认真写，被罚搞卫生这种事情谁也开心不起来。。。
T1：https://blog.csdn.net/Larry1118/article/details/87350624
这题有两种方法可以实现。
第一种是直接DFS。
我们遍历整个树，然后对于一颗子树，求出从根到达子树的叶子节点的所有方案中的最大值，然后再从根节点开始遍历，并贪心求答案。
我们可以知道越接近根节点，它的子树大小越大，所以我们可以从根节点开始贪心看每条路径设置的陷阱数量的最大值，然后在继续DFS.。
第二种方法与第一种类似，就是用人工栈实现。
T2：https://blog.csdn.net/Larry1118/article/details/87351032
这题用状压DP实现。
我们先对于起点和终点，以及朋友家每个跑一遍spfa，将这些点定义为关键点，两两之间都求出了最短路，然后我们可以用状压DP来解决问题。
我们可以设f[i][j]表示当前到达点i，走过朋友家的状态为j的最短路。这是从1到n的！
然后我们再设g[i][j]表示当前到达点j，走过朋友家的状态为j的最短路。这是从n到1的！
而f的初始值为：f[0][0]=0;（0表示起点，k+1表示终点）
g的初始值为：g[k+1]=f[k+1];
最后的答案在g[0]中找即可。
T3：https://blog.csdn.net/Larry1118/article/details/87358976
trie，动态开点。
我们可以将输入的a[],b[]全部看成二进制数。
然后按照二进制中的位置从大到小开始建trie。
如果trie不会的可以自己手动普及一下。
建好a[]的trie后，我们可以对于每个b[i]开始求答案。
答案可以说是贪心来求的。正确性可以保证。
如果对于当前结点：
1：只有一个儿子，那就走那一个儿子。
2：否则的话就按照与b[i]的这一位置上的0/1取反，并走那一个儿子。
这样子我们可以保证答案的最优性了。
下次继续努力！（┭┮﹏┭┮）