pat链接：
http://pat.zju.edu.cn
1001
1
#include<stdio.h>
2
int
main(){
3
int
a,b;
4
int
c;
5
while
(scanf(
"
%d %d
"
,&a,&b)!=
EOF){
6
c=a+
b;
7
if
(c<
0
){
8
c=-
c;
9
printf(
"
-
"
);
10
}
11
if
(c>=
1000000
)
12
printf(
"
%d,%03d,%03d\n
"
,c/
1000000
,(c/
1000
)%10
00
,c%1000);
13
else
if
(c>=
1000
)
14
printf(
"
%d,%03d\n
"
,c/
1000
,c%1000);
15
else
16
printf(
"
%d\n
"
,c);
17
}
18
return
0
;
19
}
关键是代码的长度有限制所以简化了整个程序
1002
自己的代码总是有两组过不去。。真心崩溃了，自己的确实有点复杂，记录了不该记录的东西
1
#include<stdio.h>
2
int
main(){
3
int
k1,k2;
4
int
m[
10
],n[
10
];
5
double
a[
10
],b[
10
],c[
10
];
6
int
i,count;
7
memset(m,
0
,
sizeof
(m));
8
memset(n,
0
,
sizeof
(m));
9
memset(a,
0
,
sizeof
(a));
10
memset(b,
0
,
sizeof
(a));
11
memset(c,
0
,
sizeof
(a));
12
scanf(
"
%d
"
,&
k1);
13
for
(i=
0
;i<k1;i++
){
14
scanf(
"
%d
"
,&
m[i]);
15
scanf(
"
%lf
"
,&
a[m[i]]);
16
}
17
scanf(
"
%d
"
,&
k2);
18
for
(i=
0
;i<k2;i++
){
19
scanf(
"
%d
"
,&
n[i]);
20
scanf(
"
%lf
"
,&
b[n[i]]);
21
}
22
count=
0
;
23
for
(i=
0
;i<=(k1>k2?k1:k2);i++
){
24
c[i]=a[i]+
b[i];
25
if
(c[i]!=
0
)
26
count++
;
27
}
28
printf(
"
%d
"
,count);
29
for
(i=count;i>=
0
;i--
){
30
if
(c[i]!=
0
&&i!=
0
){
31
printf(
"
%d %.1f
"
,i,c[i]);
32
}
33
else
if
(c[i]!=
0
&&i==
0
)
34
printf(
"
%d %.1f\n
"
,i,c[i]);
35
}
36
return
0
;
37
}
AC代码：
1
#include<stdio.h>
2
#include<
string
.h>
3
using
namespace
std;
4
5
double
a[
1002
];
6
double
b[
1002
];
7
8
int
main(
void
){
9
int
n,i,temp;
10
memset(a,
0
,
sizeof
(a));
11
memset(b,
0
,
sizeof
(b));
12
scanf(
"
%d
"
,&
n);
13
for
(i=
0
;i<n;i++
){
14
scanf(
"
%d
"
,&
temp);
15
scanf(
"
%lf
"
,&
a[temp]);
16
}
17
scanf(
"
%d
"
,&
n);
18
for
(i=
0
;i<n;i++
){
19
scanf(
"
%d
"
,&
temp);
20
scanf(
"
%lf
"
,&
b[temp]);
21
}
22
int
count =
0
;
23
for
(i=
0
;i<
1002
;i++
){
24
a[i]+=
b[i];
25
if
(a[i]!=
0
) count++
;
26
}
27
printf(
"
%d
"
,count);
28
for
(i=
1001
;i>=
0
;i--
)
29
if
(a[i]!=
0
){
30
count--
;
31
printf(count==
0
?
"
%d %.1f\n
"
:
"
%d %.1f
"
,i,a[i]);
32
}
33
return
0
;
34
}
因为最大只有1000，所以完全可以利用空间来简化程序，建立容量为1000的数组，然后从1到1000开始遍历（其实好笨的方法）注意memeset的用法，初始化太重要，c语言没初始化各种弊病
1003:（重要！！）
1
#include<stdio.h>
2
#include<
string
.h>
3
int
map[
501
][
501
];
4
int
dis[
501
];
5
bool
mark[
501
];
6
int
team[
501
];
7
int
maxteam[
501
];
8
int
pathnum[
501
];
9
const
int
max=
123123123
;
10
int
n,m,c1,c2;
11
void
dij(){
12
int
i,j;
13
int
k;
14
dis[c1]=
0
;
15
//
mark[c1]=1;
16
pathnum[c1]=
1
;
17
maxteam[c1]=
team[c1];
18
19
for
(i=
0
;i<n;i++
){
20
int
min=
max;
21
for
(j=
0
;j<n;j++
){
22
if
(dis[j]<min&&!
mark[j]){
23
min=
dis[j];
24
k=
j;
25
}
26
}
27
if
(k==c2)
return
;
//
因为终点已经固定，已经找到直接返回
28
mark[k]=
1
;
29
for
(j=
0
;j<n;j++
){
30
if
(mark[j]==
0
){
31
if
(dis[k]+map[k][j]<
dis[j]){
32
dis[j]=dis[k]+
map[k][j];
33
pathnum[j]=
pathnum[k];
34
maxteam[j]=maxteam[k]+
team[j];
35
}
36
else
if
(dis[k]+map[k][j]==
dis[j]){
37
pathnum[j]+=
pathnum[k];
38
if
(maxteam[k]+team[j]>
maxteam[j]){
39
maxteam[j]=maxteam[k]+
team[j];
40
}
41
}
42
}
43
}
44
}
45
}
46
int
main(){
47
int
i,j;
48
int
a,b;
49
freopen(
"
in.txt
"
,
"
r
"
,stdin);
50
51
scanf(
"
%d%d%d%d
"
,&n,&m,&c1,&
c2);
52
for
(i=
0
;i<n;i++
){
53
dis[i] =
max;
54
mark[i] =
0
;
55
//
maxteam[i] = 0;
56
//
pathcount[i] = 0;
57
team[i]=
0
;
58
for
(j=
0
;j<n;j++
)
59
map[i][j]=map[j][i] =
max;
60
}
61
for
(i=
0
;i<n;i++
)
62
scanf(
"
%d
"
,&
team[i]);
63
for
(i=
0
;i<m;i++
){
64
scanf(
"
%d%d
"
,&a,&
b);
65
scanf(
"
%d
"
,&
map[a][b]);
66
map[b][a]=map[a][b];
//
end of input
67
}
68
dij();
69
70
printf(
"
%d %d\n
"
,pathnum[c2],maxteam[c2]);
71
return
0
;
72
}
一直没解决的一个难题，只是因为涉及到最短路径算法，不熟悉就一直空着没做，终于还是做了。
这是标准的一个使用邻接矩阵的dijkstra算法的最短路径题目。看资料看了好久才明白了实现的思路，一定要记住这个思路，写出来的代码基本是差不多的：
1. 初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值
若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值
若不存在<V0,Vi>，d(V0,Vi)为∞
2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S
3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止
其实并不复杂，希望以后可以轻松a过类似的题目。
1005:
1
#include<stdio.h>
2
#include<
string
.h>
3
char
eng[
10
][
10
]=
{
4
"
zero
"
,
5
"
one
"
,
6
"
two
"
,
7
"
three
"
,
8
"
four
"
,
9
"
five
"
,
10
"
six
"
,
11
"
seven
"
,
12
"
eight
"
,
13
"
nine
"
14
};
15
int
main(){
16
char
snum[
10000
],rnum[
100
];
17
int
i;
18
long
r;
19
int
count;
20
scanf(
"
%s
"
,snum);
21
r=
0
;
22
for
(i=
0
;i<strlen(snum);i++
){
23
r+=snum[i]-
48
;
24
}
25
sprintf(rnum,
"
%d
"
,r);
26
for
(i=
0
;i<strlen(rnum);i++
){
27
count=rnum[i]-
48
;
28
if
(i==strlen(rnum)-
1
)
29
printf(
"
%s
"
,eng[count]);
30
else
31
printf(
"
%s
"
,eng[count]);
32
}
33
}
一遍AC！！感觉还是很爽的有木有！！关键是用好全局的数组来进行转换，利用好字符串和数字的转换！例如i=c-48;利用码来进行单个数字字符的转换，以及sprintf(char,"%d",int);进行整个数字转字符串。
1006:
1
#include<stdio.h>
2
#include<
string
.h>
3
struct
PERSON{
4
char
id[
20
];
5
char
intime[
10
];
6
char
outime[
10
];
7
8
}p[
200
];
9
int
main(){
10
int
i,n;
11
int
first,last;
12
scanf(
"
%d
"
,&
n);
13
for
(i=
0
;i<n;i++
){
14
scanf(
"
%s %s %s
"
,p[i].id,p[i].intime,p[i].outime);
15
}
16
first=
0
;
17
for
(i=
1
;i<n;i++
){
18
if
(strcmp(p[i].intime,p[first].intime)<
0
)
19
first=
i;
20
}
21
last=
0
;
22
for
(i=
1
;i<n;i++
){
23
if
(strcmp(p[i].outime,p[last].outime)>
0
)
24
last=
i;
25
}
26
printf(
"
%s %s
"
,p[first].id,p[last].id);
27
return
0
;
28
}
还是挺简单的，一会就AC了，出了小问题是结构数组不够大，加大了就OK了。
1007：
1
#include<stdio.h>
2
#include<
string
.h>
3
int
a[
10000
];
4
int
main(){
5
int
i,k;
6
int
sum=
0
,start=
0
,end=
0
,max=
0
,rs=
0
;
7
int
flag=
0
;
8
memset(a,
0
,
sizeof
(a));
9
scanf(
"
%d
"
,&
k);
10
for
(i=
0
;i<k;i++
){
11
scanf(
"
%d
"
,&
a[i]);
12
if
(a[i]>
0
) flag=
1
;
13
sum+=
a[i];
14
if
(sum>
max){
15
max=
sum;
16
end=
i;
17
rs=
start;
18
}
19
if
(sum<
0
){
20
sum=
0
;
21
start=i+
1
;
22
}
23
}
24
if
(flag==
0
)
25
printf(
"
0 %d %d
"
,a[
0
],a[k-
1
]);
26
else
27
printf(
"
%d %d %d
"
,max,a[rs],a[end]);
28
return
0
;
29
}
动态规划最典型的一道题，也是入门级别的一道题。自己对动态规划理解还不够深刻，这是通过阅读别人的代码后自己再改写的。整个过程差不多理解了这道题的思想。其实不复杂，就是两种情况，sum大于max的话，把值赋给max，将当前的次序号当做end，重新记录一个rs来确定本段的起始；一旦sum<0，则前边的都舍弃不要，将start定为下一个。懂了基本思想就好些了。但是有一组过不去，不知道什么原因。。。
1008:
1
#include<stdio.h>
2
#include<
string
.h>
3
int
main(){
4
int
i,n,s;
5
int
a[
105
];
6
scanf(
"
%d
"
,&
n);
7
memset(a,
0
,
sizeof
(a));
8
for
(i=
0
;i<n;i++
)
9
scanf(
"
%d
"
,&
a[i]);
10
s=n*
5
;
11
for
(i=
1
;i<n;i++
){
12
if
(a[i]>a[i-
1
])
13
s+=
6
*(a[i]-a[i-
1
]);
14
else
15
s+=
4
*(a[i-
1
]-
a[i]);
16
}
17
s+=a[
0
]*
6
;
18
printf(
"
%d
"
,s);
19
return
0
;
20
}
太简单了，懒得说。
1009:
1
#include<stdio.h>
2
#include<
string
.h>
3
double
a[
1002
];
4
double
b[
1002
];
5
double
c[
2004
];
6
int
main(){
7
int
i,j,n;
8
int
k1,k2;
9
int
count;
10
memset(a,
0
,
sizeof
(a));
11
memset(b,
0
,
sizeof
(b));
12
memset(c,
0
,
sizeof
(c));
13
scanf(
"
%d
"
,&
k1);
14
for
(i=
0
;i<k1;i++
){
15
scanf(
"
%d
"
,&
n);
16
scanf(
"
%lf
"
,&
a[n]);
17
}
18
scanf(
"
%d
"
,&
k2);
19
for
(i=
0
;i<k2;i++
){
20
scanf(
"
%d
"
,&
n);
21
scanf(
"
%lf
"
,&
b[n]);
22
}
23
count=
0
;
24
for
(i=
0
;i<
1001
;i++
){
25
if
(a[i]!=
0
){
26
for
(j=
0
;j<
1001
;j++
){
27
if
(b[j]!=
0
){
28
c[i+j]+=a[i]*
b[j];
29
}
30
}
31
}
32
}
33
for
(i=
0
;i<
2001
;i++
)
34
if
(c[i])
35
count++
;
36
printf(
"
%d
"
,count);
37
for
(i=
2000
;i>=
0
;i--
){
38
if
(c[i])
39
printf(
"
%d %.1lf
"
,i,c[i]);
40
}
41
printf(
"
\n
"
);
42
return
0
;
43
}
核心的算法其实就一句话：c[i+j]+=a[i]*b[j];这题和1002很相似。PS：把最后输出条件c[i]!=0改成c[i]就A过了，不然有几组死活通不过，这是什么问题。。以后记得注意这个问题，少用!=0的判断式
1010：
1
#include<stdio.h>
2
#include<
string
.h>
3
#include<math.h>
4
long
long
todec(
char
*n,
int
rad);
5
int
main(){
6
int
tag,radt;
7
char
n1[
15
],n2[
15
];
8
long
long
int
d1=
0
,d2=
0
;
9
long
long
i;
10
scanf(
"
%s %s %d %d
"
,&n1,&n2,&tag,&
radt);
11
if
(tag==
1
){
12
d1=
todec(n1,radt);
13
for
(i=
1
;;i++
){
14
if
(d1==
todec(n2,i)){
15
printf(
"
%d
"
,i);
16
break
;
17
}
18
else
if
(todec(n2,i)>
d1){
19
printf(
"
Impossible
"
);
20
break
;
21
}
22
}
23
}
24
else
{
25
d2=
todec(n2,radt);
26
for
(i=
1
;;i++
){
27
if
(d2==
todec(n1,i)){
28
printf(
"
%d
"
,i);
29
break
;
30
}
31
else
if
(todec(n1,i)>
d2){
32
printf(
"
Impossible
"
);
33
break
;
34
}
35
}
36
}
37
return
0
;
38
}
39
long
long
todec(
char
*n,
int
rad){
40
int
i,l;
41
long
d=
0
;
42
if
(rad!=
10
){
43
//
sprintf(s1,"%d",n1);
44
l=
strlen(n);
45
for
(i=
0
;i<l;i++
){
46
if
(n[i]<=
'
9
'
&&n[i]>=
'
0
'
)
47
d+=(n[i]-
48
)*pow(rad,l-i-
1
);
48
else
if
(n[i]<=
'
z
'
&&n[i]>=
'
a
'
)
49
d+=(n[i]-
'
a
'
+
10
)*pow(rad,l-i-
1
);
50
}
51
}
52
else
53
sscanf(n,
"
%ld
"
,&d);
//
从n中读取%d格式的d1
54
return
d;
55
56
}
最崩溃的一道题。。本来觉得很难，根本无法下手，其实想清楚也没那么难，关键是要把所有的数据都转换为10进制然后再比较。结果发现只能过一小部分。接着把int改成long long型，还是有的过不去。。貌似我理解的题意有问题。。有一组超大数据要用二分法才能过去，先这样了，有时间再写个二分法的算法吧，待续。。
看到一个二分法搜索的具体做法： http://blog.csdn.net/whosemario/article/details/8734508
1
#include <iostream>
2
#include <
string
.h>
3
using
namespace
std;
4
5
int
equal(
char
* A,
char
*
B){
6
int
i,j;
7
for
(
int
i=
0
;i<strlen(A);i++)
if
(A[i]!=
'
0
'
)
break
;
8
for
(
int
j=
0
;j<strlen(B);j++)
if
(B[j]!=
'
0
'
)
break
;
9
int
lenA =
strlen(A);
10
int
lenB =
strlen(B);
11
if
(lenA-i != lenB-j)
return
-
1
;
12
for
(
int
k=
0
;k<lenA-i;k++
)
13
if
(A[lenA-
1
-k]!=B[lenB-
1
-k])
return
false
;
14
if
(lenA-i==
1
&&A[lenA-
1
]==
'
1
'
)
return
1
;
15
return
2
;
16
}
17
18
long
long
str2Num(
char
* A,
long
long
radix){
19
int
len =
strlen(A);
20
long
long
ret =
0
;
21
long
long
p =
1
;
22
23
for
(
int
i=len-
1
;i>=
0
;i--
){
24
int
num ;
25
if
(A[i]>=
'
0
'
&& A[i]<=
'
9
'
) num = A[i]-
'
0
'
;
26
else
num = A[i]-
'
a
'
+
10
;
27
ret += p*
num;
28
p*=
radix;
29
}
30
31
return
ret;
32
}
33
34
long
long
calcRadix(
char
*
B){
35
long
long
ret =
0
;
36
int
len =
strlen(B);
37
for
(
int
i=
0
;i<len;i++
){
38
int
num ;
39
if
(B[i]>=
'
0
'
&& B[i]<=
'
9
'
) num = B[i]-
'
0
'
;
40
else
num = B[i]-
'
a
'
+
10
;
41
if
(num+
1
>ret) ret=num+
1
;
42
}
43
return
ret;
44
}
45
46
int
compare(
char
* B,
long
long
radix,
long
long
target){
47
int
len =
strlen(B);
48
long
long
ret =
0
;
49
long
long
p =
1
;
50
for
(
int
i=len-
1
;i>=
0
;i--
){
51
int
num;
52
if
(B[i]>=
'
0
'
&& B[i]<=
'
9
'
) num = B[i]-
'
0
'
;
53
else
num = B[i]-
'
a
'
+
10
;
54
ret += p*
num;
55
if
(ret > target)
return
1
;
56
p*=
radix;
57
}
58
if
(ret > target)
return
1
;
59
else
if
(ret<target)
return
-
1
;
60
else
return
0
;
61
}
62
63
long
long
binarySearch(
char
* B,
long
long
low,
long
long
high,
long
long
target){
64
long
long
mid;
65
while
(low<=
high){
66
mid = (low+high)/
2
;
67
int
res =
compare(B,mid,target);
68
if
(res >
0
)
69
high = mid-
1
;
70
else
if
(res<
0
)
71
low = mid+
1
;
72
else
return
mid;
73
}
74
return
-
1
;
75
}
76
77
int
main() {
78
char
A[
12
];
79
char
B[
12
];
80
int
chose;
81
long
long
radix;
82
83
cin>>A>>B>>chose>>
radix;
84
int
eq =
equal(A,B);
85
if
(eq==
1
) printf(
"
2\n
"
);
86
else
if
(eq==
2
) printf(
"
%d\n
"
,radix);
87
else
{
88
if
(chose==
1
){
89
long
long
target =
str2Num(A,radix);
90
long
long
least =
calcRadix(B);
91
long
long
most = (target)>(least)?(target):(least);
//
input : 11 b 1 10
92
long
long
res =
binarySearch(B,least,most,target);
93
if
(res==-
1
) cout<<
"
Impossible
"
<<
endl;
94
else
cout<<res<<
endl;
95
}
96
else
{
97
long
long
target =
str2Num(B,radix);
98
long
long
least =
calcRadix(A);
99
long
long
most = (target)>(least)?
(target):(least);
100
long
long
res =
binarySearch(A,least,most,target);
101
if
(res==-
1
) cout<<
"
Impossible
"
<<
endl;
102
else
cout<<res<<
endl;
103
}
104
}
105
return
0
;
106
}
发现基本思想都不一样额。。最小的进制就是它的某位最大的数字，最大就是被比较的另一个变量的值，然后再进行二分法搜索。而我的算法是从0到最大暴力搜索。
1059
1
#include<stdio.h>
2
#include<math.h>
3
int
isp(
long
l);
4
int
main(){
5
long
int
n,t,cnt;
6
long
int
i;
7
scanf(
"
%ld
"
,&
n);
8
t=
n;
9
i=
2
;
10
if
(n==
1
||
isp(n)){
11
printf(
"
%d=%d
"
,n,n);
12
return
0
;
13
}
14
printf(
"
%ld=
"
,n);
15
while
(!
isp(t)){
16
if
(isp(i)){
17
cnt=
0
;
18
if
(t%i==
0
){
19
20
while
(t%i==
0
){
21
t/=
i;
22
cnt++
;
23
}
24
if
(cnt==
1
)
25
printf(
"
%ld
"
,i);
26
else
27
printf(
"
%d^%d
"
,i,cnt);
28
29
if
(t!=
1
)
30
printf(
"
*
"
);
31
32
i++
;
33
}
34
else
35
i++
;
36
}
37
else
38
i++
;
39
}
40
printf(
"
%d
"
,t);
41
return
0
;
42
}
43
int
isp(
long
l){
44
long
i=
2
;
45
while
(i<sqrt(l)+
1
){
46
if
(l==
2
)
47
return
1
;
48
if
(l%i==
0
){
49
return
0
;
50
}
51
if
(i==l-
1
)
52
return
1
;
53
i++
;
54
}
55
56
}
纠结了好久的一道题，终于还是过了。。首先是判断素数，可以用sqrt来简化复杂度。如果是素数则直接输出，如果不是则进入循环来寻找它的因数。之前最初我用两组数组来记录每一个因数和它的次方，实在是复杂多余，后来改成了直接算一个输出一个，明显简化了许多。还有要注意特殊情况的输出，素数直接输出自身即可。还有最重要的一点是：循环结束条件的判断。余数如果是素数即可结束循环，我的程序一直超时，就是没有利用这个循环结束条件。
PS:关于找出所有素数的解法，还有一个高效的方法：素数筛选法
void
init(){
primgsize
=
0
;
for
(
int
i=
2
;i<=
10000
;i++
){
if
(mark[i]==
true
)
continue
;
prime[primesize
++]=
i;
for
(
int
j=i*i;j<=
10000
;j+=
i){
mark[j]
=
true
;
}
}
