BZOJ NOI十连测 9thTest
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------------------------------------
QAQ
T2不知道为什么暴力挂了
T1不知道为什么A了
------------------------------------------------------------------------------
T1:
首先不为0的位置一定是已经确定的
考虑为0的位置，有多少种可行的颜色
从他前一个沿着next一直向前跳一直向前跳，跳到开头为止，这中间为0的位置的颜色一定互不相同并且与当前位置颜色不相同，所以这个位置的方案数就是(c-为0的位置个数-1),-1是因为不能和第一个位置相同,因此答案就是(c*各个位置的答案),一开始的c是第一个位置,可以随便选
标算:叉姐说不相等关系是一个弦图,然后套用弦图染色算法就行了
------------------------------------------------------------------------------
T2:
暴力的做法和玛里苟斯挺像的
标算:
先把线性基求出来,如果他的大小小于等于24就暴搜,现在考虑大于24怎么办
首先这个集合中的元素互相xor,答案一定不变
因此可以把线性基消成这样:
100000xxx
010000xxx
001000xxx
000100xxx
000010xxx
000001xxx
然后因为线性基大于等于24,所以前面那一坨的长度>=24,所以后面xxx那一坨<=16,然后就可以dp了:
设f[i][j][k]表示线性基中的前i个元素,前面那一坨有j个1(因为互不相交,所以统计个数就行了),后面那一坨xor和为k,然后暴力转移就行了
这样求出来的期望和原序列的期望是一样的...
------------------------------------------------------------------------------
T3:
不会。
------------------------------------------------------------------------------
2016年6月28日 11:11
orz
2022年12月14日 18:58
BZOJ NOI ten continuous test 9thTest will be held on December 21, 2019. This real estate agent Surprise test is for the participants of theNOI who have not yet been ranked. The test will consist of 10 problems, and the participants will have 3 hours to solve them.