Nim z utrudnieniem
挺精巧一题。
首先我们知道,nim游戏后手必胜的充要条件为所有堆的数量异或和为\(0\),则相当于要选择一部分数使得异或起来为所有的异或和。
直接dp是\(O(ndA)\)的,不可接受。
发现题目里给了一个非常奇怪的限制:\(\sum A_i\leq 10^7\),考虑从这方面着手。将\(a\)排序以后,前\(i\)个数组成的异或和不会超过\(2^{\lceil\log A_i\rceil}\),也即直接暴力dp总和不会超过\(2m\),时间复杂度\(O(md)\)
Turysta
一眼NP问题,再一眼并不是。
首先下意识缩点,发现缩完点之后是一条链,盲猜每个点最长路是这个点在链上能走到的节点。
DAG之间的边一定存在,所以相当于SCC间相互独立,则只需要构造出每个SCC内部的一个环即可。
考虑先构造一条链,每次加入一个点。如果当前链尾有边指向当前点,则直接加入链尾,否则从后往前找到第一个有边指向它的点然后加入。如果始终加入不了,那么就放在链首。
现在考虑成环,首先找到最大的包含链首的环,然后往后加链中的点。如果一个点它没有指向当前链中的点,那么就先放放,知道第一个指向当前链中的点有边的点,则让链上前一个点指向第一个被放下的点,然后一条链,这个点再指向链上的点,就构造出一个环。时间复杂度\(O(n^2)\)
标签:一个点,submission,指向,加入,POI2016,POI2017,异或,dp From: https://www.cnblogs.com/275307894a/p/17059152.html