Solve

USACO 2.3.3 Zerosum

题目解答

本题不难，但是由于没有好的算术方案，所以编的时间长，又因为pascal递归不稳定，所以调试时间长，提交了三次

运行结果

Compiling…
Compile: OK

Executing…
Test 1: TEST OK [0.000 secs, 204 KB]
Test 2: TEST OK [0.000 secs, 204 KB]
Test 3: TEST OK [0.000 secs, 208 KB]
Test 4: TEST OK [0.000 secs, 208 KB]
Test 5: TEST OK [0.000 secs, 204 KB]
Test 6: TEST OK [0.011 secs, 208 KB]
Test 7: TEST OK [0.011 secs, 208 KB]

All tests OK.
Your program (‘zerosum’) produced all correct answers! This is your
submission #3 for this problem. Congratulations!

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
program test;
type node=array[0..8]of integer;
var n:3..9;
         a:array[1..9]of integer;
         b1:array[1..9]of integer;
         total:longint;
         b:node;
procedure print(c:node);
var i:integer;
begin
         for i:=2 to n do
         begin
                   case c[i-1] of
                   1:begin
                            write(a[i-1],' ');
                            end;
                   2:begin
                            write(a[i-1],'+');
                            end;
                   3:begin
                            write(a[i-1],'-');
                            end;
                   end;
         end;
         writeln(a[n]);
         {for i:=1 to n-1 do
                   write(c[i],' ');
         writeln;}
end;
procedure pd(c:node);
var i,temp,temp2:integer;
begin
         fillchar(b1,sizeof(b1),0);
         total:=0;temp:=0;
         for i:=1 to n do
         begin
                   if c[i]=1 then
                   begin
                            if c[i-1]=1 then total:=total*10+a[i+1];
                            if c[i-1]<>1 then
                            begin
                                     total:=a[i];
                                     total:=total*10+a[i+1];
                            end;
                            if c[i+1]<>1 then
                            begin inc(temp);b1[temp]:=total;end;
                   end;
         end;
         temp:=1;temp2:=0;
         if c[1]=1 then begin total:=b1[1];inc(temp2);end
                   else total:=a[1];
         while temp<n do
         begin
                if c[temp]<>1 then
                   begin
                   if c[temp+1]<>1 then
                            case c[temp] of
                                     2:total:=total+a[temp+1];
                                     3:total:=total-a[temp+1];
                            end
                   else
                            begin
                                     inc(temp2);
                                     case c[temp] of
                                     2:total:=total+b1[temp2];
                                     3:total:=total-b1[temp2];
                                     end;
                                     for i:=temp+1 to n do
                                               if i<>1 then
                                               begin
                                                        temp:=i;
                                                        break;
                                               end;
                            end;
                end;
                inc(temp);
         end;
         if total=0 then print(c)
                   else exit;
end;
procedure dfs(x:integer;b:node);
var i:integer;
begin
         if (x=n) then
         begin
                   pd(b);
                   exit;
         end;
         for i:=1 to 3 do
         begin
                   b[x]:=i;
                   if x+1<=n then dfs(x+1,b);
         end;
end;
procedure init;
var i:integer;
begin
         readln(n);
         fillchar(a,sizeof(a),0);
         for i:=1 to n do
                   a[i]:=i;
         b[0]:=0;
end;
begin
  assign(input,'zerosum.in');
  reset(input);
  assign(output,'zerosum.out');
  rewrite(output);
  init;
  dfs(1,b);
  close(input);
  close(output);
end.

后记

本文是原新浪博客的移植，附：全部USACO题目解答。