2012福建省信息学奥林匹克CCF-NOIP夏令营竞赛(附解题思路及参考程序).doc

(完整版)2012福建省信息学奥林匹克CCF NOIP夏令营竞赛(附解题思路及参考程序)2012福建省信息学奥赛CCF NOIP夏令营竞赛时间：8:30 11:30（附解题思路及参考程序）试题名称花园扑克牌租用游艇均衡发展提交文件gardenpokerboatbalance输入文件garden.inpoker.inboat。inbalance。in输出文件garden.outpoker。outboat。outbalance.out时间限制1s1s1s1s内存限制256M256M256M256M本题分值100100100100福建省计算机学会花园(garden）【问题描述】小L有一座环形花园,沿花园的顺时针方向，他把各个花圃编号为1N(2=N=1015)。他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则，任意相邻M(2=M=5,M=N）个花圃中有不超过K(1=KM）个C形的花圃，其余花圃均为P形的花圃。例如，N=10,M=5，K=3。则CCPCPPPPCC 是一种不符合规则的花圃；CCPPPPCPCP 是一种符合规则的花圃.请帮小L求出符合规则的花园种数Mod 1000000007由于请您编写一个程序解决此题。【输入文件】 一行，三个数N,M,K.【输出文件】花园种数Mod 1000000007【样例输入1】10 5 3【样例输出1】458【样例输入2】6 2 1【样例输出2】18【数据规模】 40%的数据中，N=20; 60的数据中，M=2； 80%的数据中，N=105。扑克牌(poker）【问题描述】组合数学是数学的重要组成部分,是一门研究离散对象的科学，它主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据.今天我们来研究组合数学中的一个有趣的问题，也是一个简单的计数问题:从一副含有n(n10000)张的扑克牌显然每张扑克牌都不相同中，分给m(m100)个人，第i个人得到ai （0ai100）张牌，求一共有几种分法，这个数可能非常大，请输出此数模10007后的结果。【输入文件】第一行两个整数 为 n m第二行 m个整数 ai【样例输入1】5 23 1【样例输出1】20【样例输入2】20 191 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1【样例输出2】8707【数据规模】对于50%的数据，M = 1。租用游艇（boat）【问题描述】长江游艇俱乐部在长江上设置了n 个游艇出租站1，2，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i 到游艇出租站j 之间的租金为r(i，j），1=i=j=n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n 所需的最少租金。对于给定的游艇出租站i 到游艇出租站j 之间的租金为r（i，j)，1=ij=n，编程计算从游艇出租站1 到游艇出租站n所需的最少租金.保证计算过程中任何时刻数值都不超过106【输入文件】由文件提供输入数据。文件的第1 行中有1 个正整数n(n=200），表示有n个游艇出租站.接下来的n1 行是一个半矩阵r(i，j）,1=ij=n。【输出文件】程序运行结束时，将计算出的从游艇出租站1 到游艇出租站n所需的最少租金输出到文件中。【输入样例】35 157【输出样例】12均衡发展(balance）【问题描述】神牛小R在许多方面都有着很强的能力，具体的说，他总共有m种能力,并将这些能力编号为1到m。他的能力是一天一天地提升的，每天都会有一些能力得到一次提升，R对每天的能力提升都用一个数字表示,称之为能力提升数字，比如数字13,转化为二进制为1101,并且从右往左看，表示他的编号为1,3，4的能力分别得到了一次提升。小R把每天表示能力提升的数字的记了下来，如果在连续的一段时间内，小R的每项能力都提升了相同的次数，小R就会称这段时间为一个均衡时期，比如在连续5天内，小R的每种能力都提升了4次，那么这就是一个长度为5的均衡时期。于是，问题来了,给出 小R n天的能力提升数字，请求出均衡时期的最大长度.【输入文件】第一行有两个整数n，m，表示有n天，m种能力。接下来有n行,每行有一个整数，分别表示第1到n天的能力提升数字。能力提升数字转化为二进制后，从右到左的每一位表示对应的能力是否在当天得到了一次提升。n=100000, m=30【输出文件】输出只有一个整数，表示长度最大的均衡时期的长度。【样例输入】7 37672142【样例输出】4【样例解释】每天被提升的能力种类分别为：第一天:1，2,3第二天:2,3第三天:1，2，3第四天：2第五天：1第六天：3第七天：2第三天到第六天为长度最长的均衡时期因为 这四天 每种能力分别提升了 2次【数据规模】对于50的数据，N kk then begin flag：=false; break; end； end； if flag then ans_:=(ans_+fi)mod maxn; end;end；begin assign(input,garden。in); reset（input）； readln(n,m，kk); close（input）; assign(output,garden.out)； rewrite(output)； for i：=0 to 1 shl m1 do begin t：=i; tot:=0; while t0 do begin if t and 1=1 then inc（tot); t：=t shr 1； end; if tot=kk then pi:=true； end; for i：=0 to 1 shl m1 do for j：=0 to 1 shl m1 do if pi and pj then if (j shr 1)=(i and （1 shl (m1)-1)） then cani，j：=1; t:=1; tot:=0； n:=n-m； while t=t then begin n：=n-t； ai:=true； end； t：=t div 2; end; fillchar（ans,sizeof(ans）,0）； for i:=0 to 1 shl m1 do ansi，i：=1; for i：=1 to tot do begin if ai then ans：=cheng(ans,can); can:=cheng(can,can); end； for i：=1 to n do ans：=cheng(ans，can）; for L：=0 to 1 shl m1 do if pL then begin fillchar（d,sizeof(d），0）; d0,L：=1; for i:=1 to n do d:=cheng（d,can); d:=cheng（d，ans)； fillchar（f,sizeof(f），0); for i:=0 to 1 shl m-1 do for j:=0 to 1 shl m1 do fi:=fi+dj,i; for i：=0 to 1 shl m-1 do ok（L,i）； end; writeln（ans_）mod maxn）； close(output）;end.扑克牌简单组合数计算tot：=(tot*cn,ai)mod 10007；n：=n-ai;参考程序：var n,k,i，j:longint; c:array0。.20000,0.200of longint; tot:longint; a：array0.。200of longint;begin assign（input，poker.in); reset（input）； readln(n，k); for i：=1 to k do read（ai)； close(input)； for i:=1 to 10000 do ci,1：=i; for i:=2 to 10000 do for j：=2 to 100 do begin if i=j then ci,j:=1； if i=j then break; ci，j:=(ci-1，j1+ci1，j）mod 10007; end; tot:=1； for i:=1 to k do begin if ai0 then tot:=(tot*cn,ai）mod 10007； n:=n-ai; end； assign(output，poker.out）; rewrite（output）; writeln(tot）mod 10007); close（output）;end。租用游艇Dis j =Min Dis i +a i ， j 参考程序：var i,j，n：longint; dis：array0。1000of longint; a：array0.1000,0。.1000of longint;begin assign（input，boat.in); reset（input）； readln(n）； for i:=1 to n-1 do begin for j：=i+1 to n do read(ai,j）； readln; end; close(input); fillchar（dis，sizeof（dis)，$6F）; dis1:=0； for i:=1 to n-1 do for j:=i+1 to n do if disjdisi+ai,j then disj:=disi+ai，j； assign(output，boat。out）; rewrite（output）; writeln（disn); close（output）；end.均衡发展第i天的能力值是一个数列d1,d2。.dn,通过hash寻找最早出现的d1k，d2k。dnk这种数列处理的方法是可以始终将数列的每一个数减去数列中最小的一个数这样的话只要能够通过hash向前找到一个相同的数列，就能发现一个平衡时期参考程序：include iostream#include include using namespace std；#define FOR(i,a，b） for(int i=a;i1; if (sjans） ans=inow； / printf(”d dn”，now，i)； printf(dn”,ans）；int main() freopen(”balance.in，”r”，stdin); freopen(balance.out”，w”,stdout); init(）; work(）;