题目名称 |
输入文件 |
输入输出 |
时间限制 |
空间限制 |
路灯改建计划 |
light.in |
Light.out |
1S |
128M |
数独 |
shudu.in |
shudu.out |
10S |
128 M |
Aim Netbar |
netbar.in |
netbar.out |
1S |
128M |
路灯改建计划(light.pas/c/cpp)
【问题描述】
在康杰中学的道路上，新建了若干漂亮的路灯，这给同学们晚上的出行带来很大的方便。但是，问题随之出现了。
一天晚上，我们信息学竞赛班的Z同学正往校门外走，忽然眼前一片漆黑，于是直接把眼镜都摔掉了，再也找不到。后来Z同学从学校管理处了解到昨晚路灯突然熄灭是因为电路不堪重负，导致空气开关跳闸。
善于思考的Z 同学考虑将路灯进行改建，以避免再次出现类似的问题。Z同学仔细了解每盏路灯的耗电量a[i]与照明度z[i]，已知共有N盏电灯，并且每盏电灯都可能有不同的耗电量与照明度，现在的问题是要把这N盏电灯分为M组，新分出的每组灯的耗电量（即是该组所有打开电灯的耗电量之和）不能超过该组的电灯数目的T倍，在满足这样的前提下使得照明度尽可能的大，最后算出M组的最大照明度的和。由于每组耗电量的限制，该组中的某些电灯可能不被使用，但是仍然应该算作该组灯的数目。
特别注意的是电灯按顺序给出，只能把相邻的几盏灯分在一组。由于计算较为复杂，Z同学经过反复的计算仍然不能确定结果，现在就请你为他编写一个程序来解决这个问题。
【输入文件】
文件*有N+1行，第一行三个整数分别为N，M，T。
接下来的N 行每行两个整数，分别为a[i]与z[i]，所有数据之间以一个空格分开。
【输出文件】
文件仅包含一个数，即输出M组的最大照明度的和。
【输入样例1】
2 1 2
2 1
3 2
【输出样例1】
2
【输入样例2】
5 2 2
1 1
2 2
3 3
4 4
5 5
【输出样例2】
10
【数据规模】
对于70％的数据，保证有2<=N<=80，1<=M<=35，1<=T，a[i]，z[i]<=35；
对于全部的数据，保证有2<=N<=160，1<=M<=50，1<=T，a[i]，z[i]<=50。
数独(shudu.pas/c/cpp)
襄樊开展了数独大赛，明明和红红参加了比赛，比赛分数与时间有关。明明和红红想在别人前面做出来一得到更高的分数。他们想到了作弊，利用掌上电脑解决问题。由于题目较难，请你用计算机帮忙做个程序，解决这个问题。由于输入需要时间，掌上电脑不是很快。
你的程序需要在一秒内解决上百个这样的问题。
数独游戏规则
数独游戏在9x9的方格内进行，分为3x3的小方格，被称为“区”：
数独游戏首先从已经填入数字的格子开始：
- 数独游戏的目的是根据下列规则，用1至9之间的数字填满空格，一个格子只能填入一个数字：
1. 每个数字在每一行只能出现一次
2. 每个数字在每一列只能出现一次
3. 每个数字在每一区只能出现一次
- 总结这些规则，即每个数字在每一行、每一列和每一区只能出现一次。
格式
【输入格式】
数独的个数n(n<=300)
下面n行，每行81个数（ai)，当ai=0是未知数，否则为数独里面的已知数。
注意，每2个数之间没有空格。
【输出格式】
输出有n行，每行有81个数为最终的结果。
【样例1】
【样例输入1】
1005000600080701040700060003090205060008040900060109080500090002040308010006000700
【样例输出1】
415923678683751249729864153194285367358647921267139485571496832942378516836512794
【限制】
根据数据的困难程度定时间最多10s最少1s
【提示】
【样例的输入转为表】：
005000600
080701040
700060003
090205060
008040900
060109080
500090002
040308010
006000700
输出转为表：
415923678
683751249
729864153
194285367
358647921
267139485
571496832
942378516
836512794
Aim Netbar(netbar.pas/c/cpp)
【问题背景】
M同学都热衷于大型3D网游，可学校的机子配置相当差，根本不能玩大型3D网游，那就只有去网吧。星期一到星期五都是晚上10：00才下晚自习，几乎没时间玩。
然而星期六下午放假是绝好的时间，但是学校人多啊，一放学去网吧的人就开始狂奔，竞争之激烈，抢到机子的难度非常之大。往往在我们到达网吧之前都坐满了。
学校到网吧的路是错综复杂的，以致于到一个自己想去的网吧都有非常多的路线可以选择，而路线的长度又不相同，这样就决定了要花费的时间，因此想要尽快到达，选择一条最佳的线路是很有必要的。
【问题描述】
为了简化问题，我们把学校与周边的网吧看做图中的顶点，学校与网吧，网吧与网吧之间的路线看做边，每个边都有一个权，表示我们走完这条路的时间，由于放学人流量大，如果反向走会有危险，因此这是一个有向图。
学校在S点，想要去的网吧在T点。你的任务就是选择一条最佳路线，使得从学校到目的地网吧的时间最短，你只需要输出最短到达时间即可。
【输入文件】
netbar.in *有M+2行数据
第一行两个整数N，M，表示点数和边数。
然后M行每行3个正整数(u，v，t)，表示有一条可由u到v耗时为t的边。
最后一行两个正整数S、T。
【输出文件】
netbar.out 中，只有一行，一个整数表示最短时间。如果S、T之间不存在通路则输
出“No Solution!”(双引号不输出，“!”为西文标点)。
【输入样例】
4 4
1 2 3
2 4 10
1 3 5
3 4 5
1 4
【输出样例】
10
【数据规模】
对于30％的数据保证有1<N<=1000，1<=M<=1000；
对于全部的数据保证有1<N<=10000，1<=M<=100000。
解析：
路灯改建计划(light.pas/c/cpp)
Vijos 1488
【问题描述】
在康杰中学的道路上，新建了若干漂亮的路灯，这给同学们晚上的出行带来很大的方便。但是，问题随之出现了。
一天晚上，我们信息学竞赛班的Z同学正往校门外走，忽然眼前一片漆黑，于是直接把眼镜都摔掉了，再也找不到。后来Z同学从学校管理处了解到昨晚路灯突然熄灭是因为电路不堪重负，导致空气开关跳闸。
善于思考的Z 同学考虑将路灯进行改建，以避免再次出现类似的问题。Z同学仔细了解每盏路灯的耗电量a[i]与照明度z[i]，已知共有N盏电灯，并且每盏电灯都可能有不同的耗电量与照明度，现在的问题是要把这N盏电灯分为M组，新分出的每组灯的耗电量（即是该组所有打开电灯的耗电量之和）不能超过该组的电灯数目的T倍，在满足这样的前提下使得照明度尽可能的大，最后算出M组的最大照明度的和。由于每组耗电量的限制，该组中的某些电灯可能不被使用，但是仍然应该算作该组灯的数目。
特别注意的是电灯按顺序给出，只能把相邻的几盏灯分在一组。由于计算较为复杂，Z同学经过反复的计算仍然不能确定结果，现在就请你为他编写一个程序来解决这个问题。
【输入文件】
文件*有N+1行，第一行三个整数分别为N，M，T。
接下来的N 行每行两个整数，分别为a[i]与z[i]，所有数据之间以一个空格分开。
【输出文件】
文件仅包含一个数，即输出M组的最大照明度的和。
【输入样例1】
2 1 2
2 1
3 2
【输出样例1】
2
【输入样例2】
5 2 2
1 1
2 2
3 3
4 4
5 5
【输出样例2】
10
【数据规模】
对于70％的数据，保证有2<=N<=80，1<=M<=35，1<=T，a[i]，z[i]<=35；
对于全部的数据，保证有2<=N<=160，1<=M<=50，1<=T，a[i]，z[i]<=50。
算法动归+01背包
U[I,j]表示从第I个灯到第j个灯的最大照明度；（用01背包求）
g[i,j]表示前j个路灯分i份；（用DP求）
方程
g[i,j]:=max(g[i,j],g[i-1,k]+u[k+1,j]);
{前j个分i组可以是前k个分i-1组，后面的分一组}
program light;
var o:array[0..10000] of longint;
a,z:array[0..165] of longint;
u:array[0..165,0..165] of longint;
g:array[0..55,0..165] of longint;
n,m,q,i:longint;
function max(x,y:longint):longint;
begin if x>y then exit(x)else exit(y);end;
procedure main;
var
i,j,k,mmm:longint;
begin
for i:=1 to n do
begin
fillchar(o,sizeof(o),0);
for j:=i to n do
begin
mmm:=(n-i+1)*q;
for k:=mmm downto a[j] do
if o[k-a[j]]+z[j]>o[k] then o[k]:=o[k-a[j]]+z[j]; {一个建造u[i,j]的01背包}
u[i,j]:=o[(j-i+1)*q];
end;
end;
for i:=1 to m do
for j:=i to n do
for k:=i-1 to j-1 do {注意是i-1到j-1，保证后面K到J中是连续没有分开}
g[i,j]:=max(g[i,j],g[i-1,k]+u[k+1,j]);
writeln(g[m,n]);
end;
begin
readln(n,m,q);
for i:=1 to n do readln(a[i],z[i]);
main;
end.
数独(shudu.pas/c/cpp)
Vijos 1345
襄樊开展了数独大赛，明明和红红参加了比赛，比赛分数与时间有关。明明和红红想在别人前面做出来一得到更高的分数。他们想到了作弊，利用掌上电脑解决问题。由于题目较难，请你用计算机帮忙做个程序，解决这个问题。由于输入需要时间，掌上电脑不是很快。
你的程序需要在一秒内解决上百个这样的问题。
数独游戏规则
数独游戏在9x9的方格内进行，分为3x3的小方格，被称为“区”：
数独游戏首先从已经填入数字的格子开始：
- 数独游戏的目的是根据下列规则，用1至9之间的数字填满空格，一个格子只能填入一个数字：
1. 每个数字在每一行只能出现一次
2. 每个数字在每一列只能出现一次
3. 每个数字在每一区只能出现一次
- 总结这些规则，即每个数字在每一行、每一列和每一区只能出现一次。
格式
【输入格式】
数独的个数n(n<=300)
下面n行，每行81个数（ai)，当ai=0是未知数，否则为数独里面的已知数。
注意，每2个数之间没有空格。
【输出格式】
输出有n行，每行有81个数为最终的结果。
【样例1】
【样例输入1】
1
005000600080701040700060003090205060008040900060109080500090002040308010006000700
【样例输出1】
415923678683751249729864153194285367358647921267139485571496832942378516836512794
【限制】
根据数据的困难程度定时间最多10s最少1s
【提示】
【样例的输入转为表】：
005000600
080701040
700060003
090205060
008040900
060109080
500090002
040308010
006000700
输出转为表：
415923678
683751249
729864153
194285367
358647921
267139485
571496832
942378516
836512794
源代码：
program p02;
type
w=record
x,y,d:integer;
end;
var
g,l,h:array[1..9,1..9] of boolean;{分别为区，列，行}
p:array[1..81] of w;{记录状态}
n,k,m,i,j:integer;
s:array[1..9,1..9] of char;
ok:boolean;
r:char;
procedure print;
var
ii,jj:integer;
begin
for ii:=1 to 9 do
for jj:=1 to 9 do
write(s[ii,jj]);
writeln;
end;
function get(i,j:integer):integer;{取得格子号}
begin
if i<=3 then begin case j of
1..3 :exit(1); 4..6: exit(2); 7..9: exit(3); end; end
else
if i<=6 then begin case j of
1..3 :exit(4); 4..6: exit(5); 7..9: exit(6); end; end
else begin case j of
1..3 :exit(7); 4..6: exit(8); 7..9: exit(9); end; end;
end;
procedure dfs(v:integer);{深搜}
var
t:integer;
begin
if ok=true then exit;
if v>m then begin print; ok:=true; exit; end;
for t:=1 to 9 do
if h[p[v].x,t]=false then
if l[p[v].y,t]=false then
if g[p[v].d,t]=false then
begin
r:=chr(ord(t)+48);
s[p[v].x,p[v].y]:=r;
h[p[v].x,t]:=true;
l[p[v].y,t]:=true;
g[p[v].d,t]:=true;
dfs(v+1);
s[p[v].x,p[v].y]:='0';
h[p[v].x,t]:=false;
l[p[v].y,t]:=false;
g[p[v].d,t]:=false;
end;
end;
procedure init;{读入}
begin
m:=0; ok:=false;
fillchar(s,sizeof(s),'0');
fillchar(g,sizeof(g),false);
fillchar(h,sizeof(h),false);
fillchar(l,sizeof(l),false);
fillchar(p,sizeof(p),0);
for i:=1 to 9 do
for j:=1 to 9 do
begin
read(s[i,j]);
case s[i,j] of
'1'..'9': begin
h[i,ord(s[i,j])-48]:=true; l[j,ord(s[i,j])-48]:=true;
g[get(i,j),ord(s[i,j])-48]:=true;
end;
'0': begin inc(m); p[m].x:=i; p[m].y:=j; p[m].d:=get(i,j); end;
end;
end; readln;
end;
begin
assign(input,'shudu.in'); reset(input);
assign(output,'shudu.out'); rewrite(output);
readln(n);
for k:=1 to n do
begin
init;
if m=0 then begin print; continue; end;{根据数据，其实可以再稍微优化一下，就是把每组的解都记录一下，如果出现重复的数据，直接输出即可，事实证明它是可以过的}
dfs(1);
end;
close(input); close(output);
end.
第三题解析：
解题思路：
题目可以抽象为输入n个顶点，e条边的有向图，再读入源点S和目标点T，求S到T的最短路。输入规模：1<N<=10000，1<=M<=100000。
最短路有三种方法：floyd,dijsktra,spfa。如果用floyd,时间性能为O(n3) , 只能通过1000以内的数据；用dijkstra，时间性能为O(n2)，只能通过10000以内的数据，且用邻接矩阵存储时，10000*10000*4个字节，总内存达到380多MB，会超内存。用spfa算法，时间性能为O(kM)，能通过所有测试数据，k的值平均为2，表示顶点入队的平均次数。此时，可以采用数组模拟链表的存边方法，开一个边的一维数组，把所有边存储起来。如对于如下输入数据：
5 7
1 2 2
1 5 8
1 3 1
1 4 3
2 5 3
3 5 1
4 3 2
1 5
下面这个图的数组模拟链表的形式存储边，把从某个顶点出来的所有边通过链表的形式，链接起来，就象存储普通有序树一样，右儿子挂到左儿子下面。这里的操作原理是，处理某个顶点出来的边时，下一条边挂到前一条边，如下图，第一条边指向0，后面的边都指向前一条边，所以，在处理某个顶点相连的边的松驰操作时，可以很方便的处理以该顶点连出去的边，当指向0时，则以该顶点出去的松驰操作完成。
program netbar;
var
list,dis:array [0..10000] of longint; //list存储当前边的指针,dis存储各点到源点的最短路
next,toit,cost,q:array [0..100000] of longint;//next存储当前边指向前一条边的位置，toit表示当前边的出点，cost表示当前边的边权
n,m,i,a,b,c,s,e,tot:longint;
flag:array [0..10000] of boolean;
procedure add(a,b,c:longint);//数组模拟链表的添边的方法
begin
inc(tot); //边的数目
toit[tot]:=b; //当前边的出点顶点标号
cost[tot]:=c; //当前边的权值
next[tot]:=list[a]; //当前边指向前一条边的位置，如果当前边是顶点a的读入的第一条边，则它指向前面第0条边，表示next[tot]:=0。
list[a]:=tot; //从入点a引出的边的编号存储给lsit[a]
end;
procedure SPFA;
var
i,head,tail,v,k:longint;
begin
fillchar(flag,sizeof(flag),true);
for i:=1 to n do dis[i]:=maxlongint;
head:=1; tail:=1; q[1]:=s; dis[s]:=0; flag[s]:=false;//源点s入队
repeat
v:=q[head]; k:=list[v]; //队列头出队，k存储当前v顶点的边的编号
while k<>0 do //处理v的所有边，直至边指向0，即第一条边也处理了
begin
if dis[v]+cost[k]<dis[toit[k]] then //松驰操作
begin
dis[toit[k]]:=dis[v]+cost[k]; //松驰成功
if flag[toit[k]] then //入队
begin
inc(tail); q[tail]:=toit[k]; flag[toit[k]]:=false;
end;
end;
k:=next[k]; //处理顶点v的前一条边
end;
flag[v]:=true;
inc(head);
until head>tail;
end;
begin
assign(input,'netbar.in'); reset(input);
assign(output,'netbar.out'); rewrite(output);
fillchar(list,sizeof(list),0);
fillchar(next,sizeof(next),0);
fillchar(toit,sizeof(toit),0);
fillchar(cost,sizeof(cost),0);
tot:=0;
readln(n,m);
for i:=1 to m do
begin readln(a,b,c); add(a,b,c); end;
readln(s,e);
SPFA;
if dis[e]<maxlongint then writeln(dis[e])
else writeln('No Solution!');
close(input); close(output);
end.
当N的顶点规模达到10000时，如果用邻接矩阵存储图，容易超内存，且1个亿的运算次数在1S的时限内不一定出得来。