第一题
题目描述
小x非常喜欢小鸡翅。他得知NSC超市为了吸引顾客，举行了如下的活动：一旦有顾客在其他超市找到更便宜的小鸡翅，NSC超市将免费送给顾客1000g小鸡翅。小x为了尽可能的省钱，走遍了各大超市，统计了小鸡翅的价格。NSC的工作人员通过不法手段盗取了这些资料。现在NSC的工作人员希望你能帮他们定一个尽可能低的价格（1000g小鸡翅的价格），使小x吃不到免费的小鸡翅。
输入
第一行两个正整数 XNSC (1 ≤ XNSC ≤ 100) 和 YNSC (1 ≤ YNSC ≤ 1000)，表示现在在NSC超市，YNSCg小鸡翅要卖XNSC元。
第二行一个正整数N，表示其他超市的个数。
接下来N行，每行两个正整数 Xi(1 ≤ Xi ≤ 100) 和 Yi(1 ≤ Yi ≤ 1000),表示在第i家超市，Yig小鸡翅卖Xi元。
输出
有且仅有一行，包含一个实数A，表示NSC超市可以定的最高价格：A元/千克。A保留两位小数。
样例输入
Input1
5 100
3
4 100
3 100
7 100
Input2
13 6
5
56 679
35 120
99 999
56 73
37 532
Input3
100 5
3
99 8
65 14
78 10
样例输出
Output1
30.00
Output2
69.55
Output3
4642.86
数据范围限制
N<=100
这是道水题，将每种鸡翅一千克的价格求出来，找到最小的输出。（注意要判断NSC本身）
代码如下：
var a,b,i,n:longint;
min:real;
begin
assign(input,'chicken.in');
assign(output,'chicken.out');
reset(input);
rewrite(output);
readln(a,b);
min:=1000000000.0;
if a/b*1000<min then min:=a/b*1000;
readln(n);
for i:=2 to n+1 do
begin
readln(a,b);
if a/b*1000<min then min:=a/b*1000;
end;
write(min:0:2);
close(input);
close(output);
end.
第二题
题目描述
小x在解说F7决赛时的搭档是韩乔生，以至于小x没有任何能说上话的机会。无聊的他玩起了填字游戏。一个3*3的九宫格里，每个格子里都被填上了一个字母，从而我们得到了6个单词。现在，小x随手写了6个单词，他想让你帮他找到一种填字母的方案，使得这6个单词都出现在了九宫格里。
输入
共六行，每行一个长度为3的单词（全部大写）。
输出
如果找不到方案，输出“0”（不包含引号）
如果能找到，输出包含3行，第i行对应九宫格的第i行（最后一行行末要换行）。
如果有多种方案，请输出每种方案对应的字符串中字典序最前的一种（将行与行首尾相连，就可以得到一个字符串）。
样例输入
Input1
ANA
ANA
DAR
DAR
RAD
RAD
Input2
EVO
HEP
HIR
IVA
PAD
ROD
Input3
AKO
CES
DOC
DON
ESI
KES
样例输出
Output1
DAR
ANA
RAD
Output2
HEP
IVA
ROD
Output3
0
数据范围限制
如果找不到方案，输出“0”（不包含引号）
这题我们只用枚举横排的三个，再每次判断是否都存在这六个单词，如果找到就输出矩阵。如果搜到最后找不到就输出0。
代码如下：
var b:array[1..3,1..3]of string;
a:array[0..6]of string;
f:array[1..6]of boolean;
i,j:longint;
procedure print;
var i,j:longint;
begin
for i:=1 to 3 do
begin
for j:=1 to 3 do write(b[i,j]);
writeln;
end;
close(input);
close(output);
halt;
end;
procedure pd;
var min,i,j:longint;
y:array[1..6]of string;
c:array[1..6]of boolean;
begin
fillchar(c,sizeof(c),false);
min:=0;
for i:=1 to 6 do y[i]:='';
for i:=1 to 3 do
for j:=1 to 3 do y[i]:=y[i]+b[j,i];
for i:=1 to 3 do
for j:=1 to 3 do
y[i+3]:=y[i+3]+b[i,j];
for i:=1 to 6 do
for j:=1 to 6 do
if (y[j]=a[i])and(c[j]=false) then begin c[j]:=true; inc(min); break;end;
if min=6 then print;
end;
procedure dfs(l:longint);
var i,j:longint;
begin
if l>3 then
begin
pd;
exit;
end;
for i:=1 to 6 do
if f[i]=true then
begin
for j:=1 to 3 do b[l,j]:=a[i,j];
f[i]:=false;
dfs(l+1);
f[i]:=true;
for j:=1 to 3 do b[l,j]:='';
end;
end;
begin
assign(input,'match.in');
assign(output,'match.out');
reset(input);
rewrite(output);
fillchar(f,sizeof(f),true);
for i:=1 to 6 do readln(a[i]);
for i:=1 to 5 do
for j:=i+1 to 6 do
if a[i]>a[j] then
begin
a[0]:=a[i];
a[i]:=a[j];
a[j]:=a[0];
end;
dfs(1);
write(0);
close(input);
close(output);
end.第三题
题目描述
Czyzoiers都想知道小x为什么对鸡蛋饼情有独钟。经过一番逼问，小x道出了实情：因为他喜欢圆。最近小x又发现了一个关于圆的有趣的问题：在圆上有2N个不同的点，小x想用N条线段把这些点连接起来（每个点只能连一条线段），使所有的线段都不想交，他想知道这样的连接方案有多少种？
输入
有且仅有一个正整数N。
输出
要求的方案数（结果mod 100000007）。
样例输入
Input1
2
Input2
3
Input3
24
样例输出
Output1
2
Output2
5
Output3
4057031
数据范围限制
【数据范围】
对于30%的数据：N<=5。
对于60%的数据：N<=10。
对于100%的数据：N<=3000。
提示
【样例1解释】
1号点与2号点连接：2种。
1号点与4号点连接：1种。
1号点与6号点连接：2种。
这题用动态规划来做，得出式子为a[i]:=(a[i]+a[j]*a[i-1-j])mod 100000007;
代码如下：
var i,j,n:longint;
a:array[0..3000] of int64;
begin
assign(input,'cirs.in');
assign(output,'cirs.out');
reset(input);
rewrite(output);
readln(n);
a[0]:=1;
for i:=1 to n do
for j:=0 to i-1 do
a[i]:=(a[i]+a[j]*a[i-1-j])mod 100000007;
writeln(a[n]);
close(input);
close(output);
end.第四题
题目描述
话说小x有一次去参加比赛，虽然学校离比赛地点不太远，但小x还是想坐出租车去。大学城的出租车总是比较另类，有“拼车”一说，也就是说，你一个人坐车去，还是一堆人一起，总共需要支付的钱是一样的（每辆出租上除司机外最多坐下4个人）。刚好那天同校的一群Oier在校门口扎堆了，大家果断决定拼车去赛场。
问题来了，一辆又一辆的出租车经过，但里面要么坐满了乘客，要么只剩下一两个座位，众Oier都觉得坐上去太亏了，小x也是这么想的。
假设N位Oier准备拼车，此时为0时刻，从校门到目的地需要支付给出租车师傅D元（按车次算，不管里面坐了多少Oier），假如S分钟后恰能赶上比赛，那么S分钟后经过校门口的出租车自然可以忽略不计了。现在给出在这S分钟当中经过校门的所有的K辆出租车先后到达校门口的时间Ti 及里面剩余的座位Zi (1 <= Zi <= 4)，Oier可以选择上车几个人（不能超过），当然，也可以选择上0个人，那就是不坐这辆车。
俗话说，时间就是金钱，这里小x把每个Oier在校门等待出租车的分钟数等同于花了相同多的钱（例如小x等待了20分钟，那相当于他额外花了20元钱）。
在保证所有Oier都能在比赛开始前到达比赛地点的情况下，聪明的你能计算出他们最少需要花多少元钱么？
输入
每组数据以四个整数N , K , D , S开始，具体含义参见题目描述。
接着K行，表示第i辆出租车在第Ti分钟到达校门，其空余的座位数为Zi（时间按照先后顺序）。
N <= 100，K <= 100，D <= 100，S <= 100，1 <= Zi <= 4，1<= T(i) <= T(i+1) <= S
输出
对于每组测试数据，输出占一行，如果他们所有人能在比赛前到达比赛地点，则输出一个整数，代表他们最少需要花的钱（单位：元），否则请输出“impossible”。
样例输入
Input
2 2 10 5
1 1
2 2
样例输出
Output
14
数据范围限制
N <= 100，K <= 100，D <= 100，S <= 100，1 <= Zi <= 4，1<= T(i) <= T(i+1) <= S
此题有两种方法，一种是dp，每次循环判断这部车上多少人，dp式为f[i,j]:=min(f[i,j],f[i-1,j-t]+d+t*a[i]);
第二种是暴力+dfs，只有两种情况一种是要上就坐满，一种是不上车，再将其费用加起来。找出全部人都上车的最少费用。
①代码如下：
var n,k,d,s,i,j,t:longint;
a,b:array[0..100]of longint;
f:array[0..100,-505..100]of longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x)
else exit(y);
end;
begin
assign(input,'wtaxi.in');
assign(output,'wtaxi.out');
reset(input);
rewrite(output);
readln(n,k,d,s);
for i:=1 to k do readln(a[i],b[i]);
for i:=0 to 100 do for j:=-505 to 100 do f[i,j]:=10000;
f[0,0]:=0;
for i:=1 to k do
for j:=0 to n do begin
f[i,j]:=f[i-1,j];
for t:=0 to b[i] do
if j>=t then f[i,j]:=min(f[i,j],f[i-1,j-t]+d+t*a[i]);
end;
if f[k,n]=10000 then write('impossible') else write(f[k,n]);
close(input);
close(output);
end.②代码如下：
uses math;
var
n,k,d,s,i,j,ans:longint;
z,t:array[1..1000]of longint;
b:array[1..1000,1..1000]of longint;
procedure gc(c,r,q:longint);
begin
if b[c,r]<=q then exit
else b[c,r]:=q;
if c>k then
begin
if r<=0 then
begin
ans:=min(ans,q);
end;
exit;
end;
gc(c+1,r,q);
gc(c+1,r-min(r,z[c]),q+t[c]*min(r,z[c])+d);
end;
begin
assign(input,'wtaxi.in');reset(input);
assign(output,'wtaxi.out');rewrite(output);
readln(n,k,d,s);
ans:=maxlongint;
fillchar(b,sizeof(b),$7);
for i:=1 to k do readln(t[i],z[i]);
gc(1,n,0);
if ans=maxlongint then writeln('impossible')else writeln(ans);
close(input);close(output);
end.