火柴棒等式(2008年NOIP提高组第二题)
(matches.pas/c/cpp)
【问题描述】
给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：
注意：
1. 加号与等号各自需要两根火柴棍
2. 如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）
3. n根火柴棍必须全部用上
【输入】
输入文件matches.in共一行，又一个整数n（n<=24）。
【输出】
输出文件matches.out共一行，表示能拼成的不同等式的数目。
【输入输出样例1】
| matches.in | matches.out |
| 14 | 2 |
【输入输出样例1解释】
2个等式为0+1=1和1+0=1。
【输入输出样例2】
| matches.in | matches.out |
| 18 | 9 |
【输入输出样例2解释】
9个等式为：
0+4=4
0+11=11
1+10=11
2+2=4
2+7=9
4+0=4
7+2=9
10+1=11
11+0=11
program noip2008t2;
const
u:array[0..9]of integer = (6,2,5,5,4,5,6,3,7,6);
var
i,n,j,k,s:integer;
function us(x:integer):integer;
var
i,l:integer;
st:string;
begin
us := 0;
str(x,st);
l := length(st);
for i := 1 to l do us := us + u[ord(st[i])-48];
end;
begin
read (n);
n := n - 4;
s := 0;
for i := 0 to 1000 do
for j := 0 to 1000 do
begin
k := i + j;
if (us(i)+us(j)+us(k)=n) then inc(s);
end;
writeln (s);
end.
把i,j刷到1000完全是种冒险的举动，因为在本机测试时n取最大24时，i,j开到1000出的是128,开到500出的是124，一狠心用1000交上去了，0分or满分，最后居然真的没有超时！
不过花了800ms+，距离1s的限制也差不了多少了，万一评测机NC了考试时很可能就是0分~
------------------------------------------------------
VijosNT Mini 2.0.5.6
Free Pascal Compiler version 2.4.2 [2010/11/10] for i386
Copyright (c) 1993-2010 by Florian Klaempfl
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
28 lines compiled, 0.0 sec , 28656 bytes code, 1560 bytes data
#01: Accepted (75ms, 632KB)
#02: Accepted (59ms, 632KB)
#03: Accepted (75ms, 632KB)
#04: Accepted (90ms, 632KB)
#05: Accepted (90ms, 632KB)
#06: Accepted (106ms, 632KB)
#07: Accepted (75ms, 632KB)
#08: Accepted (90ms, 632KB)
#09: Accepted (90ms, 632KB)
#10: Accepted (129ms, 632KB)
Accepted / 100 / 882ms / 632KB
----------------------------------------------------------
交上去想到因为i，j的值交换一下就是一种不同的情况所以很值得优化一下，于是尝试修改一下~：
program noip2008t2;
const
u:array[0..9]of integer = (6,2,5,5,4,5,6,3,7,6);
var
i,n,j,k,s:integer;
function us(x:integer):integer;
var
i,l:integer;
st:string;
begin
us := 0;
str(x,st);
l := length(st);
for i := 1 to l do us := us + u[ord(st[i])-48];
end;
begin
read (n);
n := n - 4;
s := 0;
for i := 0 to 1000 do
for j := i to 1000 do
begin
k := i + j;
k := us(i)+us(j)+us(k);
if (k=n)and(i=j) then inc(s);
if (k=n)and(i<>j)then s:=s+2;
end;
writeln (s);
end.
完美的结果，时间减少了整整一半！
VijosNT Mini 2.0.5.6
Free Pascal Compiler version 2.4.2 [2010/11/10] for i386
Copyright (c) 1993-2010 by Florian Klaempfl
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
29 lines compiled, 0.1 sec , 28704 bytes code, 1560 bytes data
#01: Accepted (90ms, 632KB)
#02: Accepted (43ms, 632KB)
#03: Accepted (51ms, 632KB)
#04: Accepted (67ms, 632KB)
#05: Accepted (35ms, 632KB)
#06: Accepted (12ms, 632KB)
#07: Accepted (28ms, 632KB)
#08: Accepted (28ms, 632KB)
#09: Accepted (28ms, 632KB)
#10: Accepted (12ms, 632KB)
Accepted / 100 / 398ms / 632KB