彩色圆环circle命题报告

1、【命题思路试题 A：一个环上有 N 个点，每个点染为 M【命题思路试题 A：一个环上有 N 个点，每个点染为 M 种颜色之一，求相邻两点均不同色的（N1018j 的方案数，故有fi, j = jj fi 1, j；fi, j, ki jk 故有fi,j,k = kk fi 1,j,k。若令f_sumi,j = k fi,j,k 前ifigi-1;gifi-1*(M-+ gi-1*(M-2)O(1) A B试题 B：一个环上有 N 个点，每个点染为 M 种颜色之一，求同色连续段长度均不K 的方案数（N1018M109B 与试题A AO(N3)fi, f_len, l_leniB 与试题A AO(

2、N3)fi, f_len, l_leni 第fi,f_len,l_len = fi 1,f_len,l_len1 (l_len Kgi 1,f_len,len (l_len = fi,f_len,l_len = gi,f_len,l_len = gi1,f_len,l_len 1(l_len Kfi 1,f_len,len + (M gi,f_len,l_len = (M1) Kgi 1,f_len,len (l_len = 如进一步使用部分和优化即令f_sumi,j,k len len B C B A NOI 试题 C：一个环上有 N 个点，每个点随机染为 M 种颜色之一。求环上同色连续段之

3、积的期望（N200, fi, f_col, l_col,l_lenil_coll_lenfi, f_len, l_leni 续段颜色相同时所求的期望值(续段的长度)gif_len,l_leni相异时所求的期望值(续段的长度),_,_ ,_,_ (_ ,_, 续段颜色相同时所求的期望值(续段的长度)gif_len,l_leni相异时所求的期望值(续段的长度),_,_ ,_,_ (_ ,_, ,_,_ (_ = ,_,_ ,_,_ (_ () ,_,+,_,) (_ = _,_ =,_, ,_ _,_,_ 上述计算完毕后，只需再计算_,_,_ (_ + _) _,_ _ _ , _= ,_,_ =

4、 ( _ +_ ,_,_ (_ = _ = ,_,_ = ( _ +_ O(N3)O(1)C fi+j+kjkj, k O(N)和降为 O(1)C 即最终的试题彩色圆环(circle)C O(N)C D试题D：一个环上有N 个C 即最终的试题彩色圆环(circle)C O(N)C D试题D：一个环上有N 个点，每个点染为 M 种颜色之一。求所有环状上同续段长度之积的期望值，结果用最简分数形式（N2000, C 简洁地实现。本题是试题 C 【考查要点【数据设计103060 【期望得分NOI NOI 30%20 5%10 【感谢B 的【期望得分NOI NOI 30%20 5%10 【感谢B 的 【

5、附录一彩色圆环(circle)彩色圆环时间限制：1 秒AN 颗彩色宝石，闪A 很爱惜这个圆环，天天把它带在身边。A 突然发现圆环上宝石的颜色是会变化的。他十分惊讶，仔细观概率地MA发现了这个又经过了一段时间，小 A 发现因为圆环上宝石的颜色不断变化，圆环有时A 这样定义圆环的“美观程度1. 设圆环上相同颜色的连续段a1a22. 定义圆环的“美观程度Ra1 *a2 * 2. 定义圆环的“美观程度Ra1 *a2 * ana1= 3,a2 = 2, a3 = 1R= 6A想知道，在上述前提下，圆环的“美观程度”的期望值E(R)是多少。因为如果知道了 E(R)，他就可以判断每天变化出的新圆环是否比一般

6、情况circle.out E(R)，表示圆环的“美 3 200 20%1N, M 50%1N, M 100%1N 200, 1 M 109对每个测试点，若你给出的 E(R)与标准程序给出的 E(R)的相对误差不超10-7，则该测试点得满分；否则该测试点。 10-7，则该测试点得满分；否则该测试点。 .说明：相对误二彩色圆环(circle)【时空限制1 64M【问题描述N M 【数据规模和约定20%1NM50%1NM100%1N200, 1 M109【算法描述 续段的颜色col，长度len 所求的期望值(暂不乘续段的长度)。递推公式fi 1,col,len (len =M 续段的颜色col，长度

7、len 所求的期望值(暂不乘续段的长度)。递推公式fi 1,col,len (len =M fi1,col,lencol fi,col,len (len = M_, , 续段的颜色为f_colf_len，当前最续段颜色为 l_col，长度为 l_len 时所求的期望值(暂不乘续段的长度)递推公式和链的递推公式大致相同样可以使用部分和优化和最注意到这样的递推设计使得仅状态总数就高达 O(N3M2)f_col 确定的情况下，任何f_col 不等l_col 的值都是等价的。进一关的只f_coll_col的异同，而并非f_col l_col 的具体取值fi, f_len, l_len表示考虑了i 个点

8、续段的长度为 f_len，当前最后一连续段的长l_len续段颜色相同时所求的期望值(暂不续段与最续段的长度)gi, f_len, l_len表示考虑了i 个点以第一个和续段的长度为 f_len，当前最续段的长度为 l_len续段与续颜色相异时所求的期望值(暂不乘以第一个和最续段的长度)。从而有递推fi 1,f_len,l_lenfi,f_len,l_len (l_len Mgi 1,f_len,len Mfi,f_len,l_len (l_len = gi1,f_len,l_len (l_len gi,f_len,l_len M1gi,f_len,gi 1,f_len,len Mfi,f_le

9、n,l_len (l_len = gi1,f_len,l_len (l_len gi,f_len,l_len M1gi,f_len,l_len (M2)gi1,f_len,lenlen +(MMfi 1,f_len,len len + fi 1,f_len,i (l_len = ,_, _,_ =,_ _,_,_ 上述计算完毕后，只需再计算_,_,_ (_ + _) _= _,_ _ _ , fi,f_len,l_len = 0 (i f_len+l_len 1fi,f_len,l_len (f_len = l_len = gi,f_len,l_len = 0 (i f_len+ l_len

10、O(N3)O(1)考虑到试题的思维难度和编写难度，本题的数据规模使得 O(N3)首先 可以发现,_ ,_ (_ )l_len 尝试削去冗余，用fi, f_len表示考虑了前i 个点，续段长度为 f_len，第一连续段与第i 个点之后的续段同色时所求的积的和gi, f_len表示考虑了前i 个点续段长度为 f_len，续段与第i 个点之后的第续段异色时所求的的和。从而= gi,f_len (i gi,f_len = (M2)gi,f_len(ii)+(M1)fi,f_len (i iifi,fi,f_len f_sumi,f_len = mi,f_len = iigi,gi,iifi,fi,f_len f_sumi,f_len = mi,f_len = iigi,gi,f_len g_sumi,f_len = mi,f_len = ,_ = ,_ (_ )f_len f_len 用 fi表示考虑了续段之后的i个点，续段与第 i 个点之后的第连续