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
;
}
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
