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

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

竞赛时间：8:30 – 11:30
（附解题思路及参考程序）

试题名称
花园
扑克牌
租用游艇
均衡发展
提交文件
garden
poker
boat
balance
输入文件
garden.in
poker.in
boat。in
balance。in
输出文件
garden.out
poker。out
boat。out
balance.out
时间限制
1s
1s
1s
1s
内存限制
256M
256M
256M
256M
本题分值
100
100
100
100

福建省计算机学会

花园(garden）

【问题描述】
小L有一座环形花园,沿花园的顺时针方向，他把各个花圃编号为1～N(2<=N<=1015)。他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则，任意相邻M(2<=M〈=5,M〈=N）个花圃中有不超过K(1〈=K〈M）个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(n≤10000)张的扑克牌[显然每张扑克牌都不相同］中，分给m(m≤100)个人，第i个人得到ai （0≤ai≤100）张牌，求一共有几种分法，这个数可能非常大，请输出此数模10007后的结果。

【输入文件】
第一行两个整数 为 n m
第二行 m个整数 ai
【样例输入1】
5 2
3 1
【样例输出1】
20

【样例输入2】
20 19
1 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〈=i<j<=n，编程计算从游艇出租站1 到游艇出租站n所需的最少租金.
保证计算过程中任何时刻数值都不超过106

【输入文件】
由文件提供输入数据。文件的第1 行中有1 个正整数n(n〈=200），表示有n个游艇出租站.接下来的n—1 行是一个半矩阵r(i，j）,1〈=i〈j〈=n。

【输出文件】
程序运行结束时，将计算出的从游艇出租站1 到游艇出租站n所需的最少租金输出到文件中。

【输入样例】
3
5 15
7

【输出样例】
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 3
7
6
7
2
1
4
2

【样例输出】
4

【样例解释】
每天被提升的能力种类分别为：
第一天:1，2,3
第二天:2,3
第三天:1，2，3
第四天：2
第五天：1
第六天：3
第七天：2
第三天到第六天为长度最长的均衡时期
因为 这四天 每种能力分别提升了 2次

【数据规模】对于50％的数据，N <= 1000。
花园
M=2(K=1)且不是环状： Fibonacci数
M=2（K=1) 环状： Lucas数（类似Fibonacci）F*（n) = F＊（n-1） + F＊(n—2) F*(2）=3 F＊(3）=4
状态压缩动态规划+矩阵乘法
枚举：头M个花圃的状态（二进制)
每M个花圃的状态进行压缩
参考程序:
const
maxn=1000000007;
type arr=array［0。.64，0。。64]of int64;
var
can,ans,d：arr;
tot，m,k,i，j，L，kk，ans_：longint;
n,t：int64；
flag:boolean；
a,p：array［0。.1000］of boolean；
f，b:array[0.。1000］of longint;

function cheng(a，b：arr):arr；
var c：arr; i,j，k:longint;
begin
fillchar（c，sizeof(c）,0）;
for i：=0 to 1 shl m—1 do
for j：=0 to 1 shl m-1 do
for k：=0 to 1 shl m-1 do
c[j,k]：=（c[j,k]+a［j,i]＊b[i,k]）mod maxn；
exit（c);
end；

procedure ok(L，i：longint);
var j,k，t，tot：longint；
begin
if p[i］ then
begin
flag：=true；
t：=i shl m+L;
tot：=0；
for j：=1 to 2*m do
begin
b[j］：=t and 1；
t:=t shr 1;
end;
for j：=1 to m do
begin
tot:=0;
for k：=j to j+m-1 do
if b［k]=1 then
inc(tot)；
if tot>kk then
begin
flag：=false;
break;
end；
end；
if flag then
ans_:=(ans_+f[i］)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 m—1 do
begin
t：=i;
tot:=0;
while t〉0 do
begin
if t and 1=1 then
inc（tot);
t：=t shr 1；
end;
if tot<=kk then
p[i］:=true；
end;
for i：=0 to 1 shl m—1 do
for j：=0 to 1 shl m—1 do
if p[i] and p［j］ then
if (j shr 1)=(i and （1 shl (m—1)-1)） then
can［i，j］：=1;
t:=1;
tot:=0；
n:=n-m；
while t<=n do
begin
t:=t＊2;
inc(tot）；
end；
t：=t div 2;
for i：=tot downto 1 do
begin
if n>=t then
begin
n：=n-t；
a[i]:=true；
end；
t：=t div 2;
end;
fillchar（ans,sizeof(ans）,0）；
for i:=0 to 1 shl m—1 do
ans［i，i]：=1;
for i：=1 to tot do
begin
if a[i] 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 m—1 do
if p[L] then
begin
fillchar（d,sizeof(d），0）;
d[0,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 m—1 do
f[i]:=f［i]+d［j,i］;
for i：=0 to 1 shl m-1 do
ok（L,i）；
end;
writeln（（ans_）mod maxn）；
close(output）;
end.
扑克牌
简单组合数计算
tot：=(tot*c[n,a[i]])mod 10007；
n：=n-a［i];
参考程序：
var
n,k,i，j:longint;
c:array［0。.20000,0..200]of longint;
tot:longint;
a：array[0.。200]of longint;
begin
assign（input，’poker.in’);
reset（input）；
readln(n，k);
for i：=1 to k do
read（a[i])；
close(input)；
for i:=1 to 10000 do
c[i,1］：=i;
for i:=2 to 10000 do
for j：=2 to 100 do
begin
if i=j then c［i,j］:=1；
if i〈=j then
break;
c［i，j］:=(c［i-1，j—1］+c［i—1，j]）mod 10007;
end;
tot:=1；
for i:=1 to k do
begin
if a［i］〈>0 then
tot:=(tot*c［n,a［i］］）mod 10007；
n:=n-a［i］;
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：array［0。。1000]of longint;
a：array[0..1000,0。.1000]of 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(a［i,j]）；
readln;
end;
close(input);
fillchar（dis，sizeof（dis)，$6F）;
dis[1]:=0；
for i:=1 to n-1 do
for j:=i+1 to n do
if dis［j]>dis[i］+a[i,j] then
dis［j］:=dis[i］+a[i，j］；
assign(output，'boat。out’）;
rewrite（output）;
writeln（dis[n］);
close（output）；
end.
均衡发展
第i天的能力值是一个数列d[1］,d［2］。..d[n］,通过hash寻找最早出现的d［1]—k，d[2］—k。。。d［n]—k这种数列
处理的方法是可以始终将数列的每一个数减去数列中最小的一个数
这样的话只要能够通过hash向前找到一个相同的数列，就能发现一个平衡时期
参考程序：
＃include <iostream〉
#include <cstdio>
＃include <cstdlib〉
#include 〈cstring>
using namespace std；
#define FOR(i,a，b） for(int i=a;i<=b；i++）
#define MST(a，b) memset（a,b,sizeof（a)）
#define MAXN 100050
#define MAXM 40
#define M 9999997
int n,m,s［MAXM］;
long long a［MAXN];
int hash［10000000]，st［MAXN]［MAXM］，no[MAXN］,tot;
int lhash(int *a，int inow）
｛
long long now=0；
FOR(i,1,m) now=(now*97+a[i］)％M；
while (hash[now]！=0)
｛
int ok=1,s=hash［now];
FOR(i,1，m) if (st［s］［i］!=a［i]） ｛ok=0;break;}
if (ok） return no［s］;
now=（now+1)％M；
}
hash[now]=++tot；
FOR(i,1，m）st[tot］[i]=a[i］;
no[tot]=inow；
return inow;
｝
void init（)
{
scanf（"%d％d”,&n,＆m）;
FOR（i，1,n）scanf（”%d”，&a［i]）;
}

void work(）
{
tot=0;
MST(hash,0);
MST（s，0);
int ans=0；
lhash（s，0)；
FOR（i，1，n)
{
int t=a［i］,min=10000000；
FOR(j，1,m）
{
s[j］+=t&1;
t=t>>1;
if (s[j]<min) min=s［j];
｝
FOR(j,1,m） s［j］-=min;
int now=lhash(s,i）；
if (i—now>ans） ans=i—now；
// printf(”％d ％d\n”，now，i)；
｝
printf("％d\n”,ans）；
}
int main()
{
freopen(”balance.in"，”r”，stdin);
freopen("balance.out”，"w”,stdout);
init(）;
work(）;
}