BZOJ NOI10十连测 7thtest
BZOJ NOI十连测 8thTest

BZOJ NOI十连测 9thTest

YYY posted @ 2016年6月27日 16:46 in 算法竞赛 with tags 线性基 乱搞 弦图染色 DP 状态压缩 期望 , 333 阅读
------------------------------------------------------------------------------
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:
不会。
------------------------------------------------------------------------------
LOL

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter