a355: CTSC2006 Day1.1.歌唱王国
標籤 :
通過比率 : 9人/10人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 02:46

內容

在歌唱王国,所有人的名字都是一个非空的仅包含整数1~n 的字符串。
王国里生活着一大群咕噜兵,他们靠不停的歌唱首领——牛人酋长们的名字
来获取力量。咕噜兵每一次歌唱过程是这样的:


首先,他从整数生成器那儿获得一个数字,然后花一个时间单位将此数字唱
出来,如果他发现某个牛人酋长的名字已经被歌唱出来(即此名字是歌唱序列的
一个连续子串),那么这次歌唱过程就立即结束。


相关名词定义


歌唱序列:如果某人歌唱了x 个数字,第i 次歌唱的数字为ai,那么歌
唱序列=(a1,a2,…,ax)。


整数生成器:歌唱王国的神物,它有一个按钮,如果你按一下按钮,将
从1~n 数字中等概率的随机返回一个整数。


歌唱时间:在一次歌唱过程中花费的时间。


歌唱时间是随机的,无法预料;不过歌唱时间的期望值是固定的,此期望值
即平均来说歌唱时间有多长,亦可称作平均歌唱时间。


王国里的人非常喜欢歌唱,他们希望歌唱的时间越长越好,所以他们决定罢
免一些牛人酋长,使得平均歌唱时间变长。但是他们不能罢免掉所有的牛人酋长,
否则他们每次歌唱都无法停止,无法获取力量;于是他们决定只保留一个牛人酋
长而罢免其余的牛人酋长。


你的任务是:对于给定的n、牛人酋长的个数t 以及每一个牛人酋长的名字,
告诉王国里的人们,对于1≤i≤t,如果保留第i 个牛人酋长,罢免掉其余的,那
么平均歌唱时间将是多少。


提示:此数为一个非负整数!


输出要求:由于这个数字太大,所以你只需输出这个数的末4 位数字。如果
不足4 位,则前面补0(见样例)。

 

輸入說明

第一行,两个整数n、t;以下t 行描述t 个牛人酋长名字。


文件第i+1(1≤i≤t)行格式如下


第一个数为mi 表示第i 个牛人酋长的名字的长度,在一个空格之后,接
下来有mi 个数,用来描述这个牛人酋长的名字,相邻两个整数之间用一个空
格分开。

輸出說明

共t 行,第i 行为一个整数,表示若保留第i 个牛人酋长而罢免其余的,则平
均歌唱时间最长的末四位数字是多少。

範例輸入
2 2
1 1
3 1 2 1

26 1
6 1 2 3 1 2 3
範例輸出
0002
0010

3352
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 3.0s , <1K
公開 測資點#1 (10%): 3.0s , <1K
公開 測資點#2 (10%): 3.0s , <1K
公開 測資點#3 (10%): 3.0s , <1M
公開 測資點#4 (10%): 3.0s , <1M
公開 測資點#5 (10%): 3.0s , <1M
公開 測資點#6 (10%): 3.0s , <1M
公開 測資點#7 (10%): 3.0s , <10M
公開 測資點#8 (10%): 3.0s , <10M
公開 測資點#9 (10%): 3.0s , <10M
提示 :

解释1:
保留第 1 个牛人酋长罢免其余酋长时,一次歌唱结束时可能的歌唱序列为:
"1","2,1","2,2,1","2,2,2,1",……,它们的概率分别为1/2,1/4,1/8,1/16,……,歌唱时
间为1,2,3,4,……。不难证明∑i/2^i=2。
保留第2 个牛人酋长罢免其余酋长时,平均歌唱时间为10。

解释2:
平均歌唱时间为 308933352。

【约定】
1≤n≤10^5,t≤50,1≤mi≤10^5。
有30%的数据满足n≤10^3,mi≤10^3
有50%的数据满足n≤10^4,mi≤10^4

 

標籤:
出處:
CTSC2006Day1第一题 [管理者:
liouzhou_101 (王启圣)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」