pat链接：http://pat.zju.edu.cn
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)%1000,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 }
关键是代码的长度有限制所以简化了整个程序
自己的代码总是有两组过不去。。真心崩溃了，自己的确实有点复杂，记录了不该记录的东西
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:（重要！！）
#include<stdio.h>
#include<string.h>
int map[][];
int dis[];
bool mark[];
int team[];
int maxteam[];
int pathnum[];
const int max=;
int n,m,c1,c2;
void dij(){
int i,j;
int k;
dis[c1]=;
//mark[c1]=1;
pathnum[c1]=;
maxteam[c1]=team[c1]; for(i=;i<n;i++){
int min=max;
for(j=;j<n;j++){
if(dis[j]<min&&!mark[j]){
min=dis[j];
k=j;
}
}
if(k==c2) return; //因为终点已经固定，已经找到直接返回
mark[k]=;
for(j=;j<n;j++){
if(mark[j]==){
if(dis[k]+map[k][j]<dis[j]){
dis[j]=dis[k]+map[k][j];
pathnum[j]=pathnum[k];
maxteam[j]=maxteam[k]+team[j];
}
else if(dis[k]+map[k][j]==dis[j]){
pathnum[j]+=pathnum[k];
if(maxteam[k]+team[j]>maxteam[j]){
maxteam[j]=maxteam[k]+team[j];
}
}
}
}
}
}
int main(){
int i,j;
int a,b;
freopen("in.txt","r",stdin); scanf("%d%d%d%d",&n,&m,&c1,&c2);
for(i=;i<n;i++){
dis[i] = max;
mark[i] = ;
//maxteam[i] = 0;
//pathcount[i] = 0;
team[i]=;
for(j=;j<n;j++)
map[i][j]=map[j][i] = max;
}
for(i=;i<n;i++)
scanf("%d",&team[i]);
for(i=;i<m;i++){
scanf("%d%d",&a,&b);
scanf("%d",&map[a][b]);
map[b][a]=map[a][b]; //end of input
}
dij(); printf("%d %d\n",pathnum[c2],maxteam[c2]);
return ;
}
一直没解决的一个难题，只是因为涉及到最短路径算法，不熟悉就一直空着没做，终于还是做了。
这是标准的一个使用邻接矩阵的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：
#include<stdio.h>
#include<string.h>
int a[];
int main(){
int i,k;
int sum=,start=,end=,max=,rs=;
int flag=;
memset(a,,sizeof(a));
scanf("%d",&k);
for(i=;i<k;i++){
scanf("%d",&a[i]);
if(a[i]>) flag=;
sum+=a[i];
if(sum>max){
max=sum;
end=i;
rs=start;
}
if(sum<){
sum=;
start=i+;
}
}
if(flag==)
printf("0 %d %d",a[],a[k-]);
else
printf("%d %d %d",max,a[rs],a[end]);
return ;
}
动态规划最典型的一道题，也是入门级别的一道题。自己对动态规划理解还不够深刻，这是通过阅读别人的代码后自己再改写的。整个过程差不多理解了这道题的思想。其实不复杂，就是两种情况，sum大于max的话，把值赋给max，将当前的次序号当做end，重新记录一个rs来确定本段的起始；一旦sum<0，则前边的都舍弃不要，将start定为下一个。懂了基本思想就好些了。但是有一组过不去，不知道什么原因。。。
1008:
#include<stdio.h>
#include<string.h>
int main(){
int i,n,s;
int a[];
scanf("%d",&n);
memset(a,,sizeof(a));
for(i=;i<n;i++)
scanf("%d",&a[i]);
s=n*;
for(i=;i<n;i++){
if(a[i]>a[i-])
s+=*(a[i]-a[i-]);
else
s+=*(a[i-]-a[i]);
}
s+=a[]*;
printf("%d",s);
return ;
}
太简单了，懒得说。
1009:
#include<stdio.h>
#include<string.h>
double a[];
double b[];
double c[];
int main(){
int i,j,n;
int k1,k2;
int count;
memset(a,,sizeof(a));
memset(b,,sizeof(b));
memset(c,,sizeof(c));
scanf("%d",&k1);
for(i=;i<k1;i++){
scanf("%d",&n);
scanf("%lf",&a[n]);
}
scanf("%d",&k2);
for(i=;i<k2;i++){
scanf("%d",&n);
scanf("%lf",&b[n]);
}
count=;
for(i=;i<;i++){
if(a[i]!=){
for(j=;j<;j++){
if(b[j]!=){
c[i+j]+=a[i]*b[j];
}
}
}
}
for(i=;i<;i++)
if(c[i])
count++;
printf("%d",count);
for(i=;i>=;i--){
if(c[i])
printf(" %d %.1lf",i,c[i]);
}
printf("\n");
return ;
}
核心的算法其实就一句话：c[i+j]+=a[i]*b[j];这题和1002很相似。PS：把最后输出条件c[i]!=0改成c[i]就A过了，不然有几组死活通不过，这是什么问题。。以后记得注意这个问题，少用!=0的判断式
1010：
#include<stdio.h>
#include<string.h>
#include<math.h>
long long todec(char *n,int rad);
int main(){
int tag,radt;
char n1[],n2[];
long long int d1=,d2=;
long long i;
scanf("%s %s %d %d",&n1,&n2,&tag,&radt);
if(tag==){
d1=todec(n1,radt);
for(i=;;i++){
if(d1==todec(n2,i)){
printf("%d",i);
break;
}
else if(todec(n2,i)>d1){
printf("Impossible");
break;
}
}
}
else{
d2=todec(n2,radt);
for(i=;;i++){
if(d2==todec(n1,i)){
printf("%d",i);
break;
}
else if(todec(n1,i)>d2){
printf("Impossible");
break;
}
}
}
return ;
}
long long todec(char *n,int rad){
int i,l;
long d=;
if(rad!=){
//sprintf(s1,"%d",n1);
l=strlen(n);
for(i=;i<l;i++){
if(n[i]<=''&&n[i]>='')
d+=(n[i]-)*pow(rad,l-i-);
else if(n[i]<='z'&&n[i]>='a')
d+=(n[i]-'a'+)*pow(rad,l-i-);
}
}
else
sscanf(n,"%ld",&d);//从n中读取%d格式的d1
return d; }
最崩溃的一道题。。本来觉得很难，根本无法下手，其实想清楚也没那么难，关键是要把所有的数据都转换为10进制然后再比较。结果发现只能过一小部分。接着把int改成long long型，还是有的过不去。。貌似我理解的题意有问题。。有一组超大数据要用二分法才能过去，先这样了，有时间再写个二分法的算法吧，待续。。
看到一个二分法搜索的具体做法：http://blog.csdn.net/whosemario/article/details/8734508
#include <iostream>
#include <string.h>
using namespace std; int equal(char* A, char* B){
int i,j;
for(int i=;i<strlen(A);i++) if(A[i]!='') break;
for(int j=;j<strlen(B);j++) if(B[j]!='') break;
int lenA = strlen(A);
int lenB = strlen(B);
if(lenA-i != lenB-j) return -;
for(int k=;k<lenA-i;k++)
if(A[lenA--k]!=B[lenB--k]) return false;
if(lenA-i==&&A[lenA-]=='') return ;
return ;
} long long str2Num(char * A, long long radix){
int len = strlen(A);
long long ret = ;
long long p =; for(int i=len-;i>=;i--){
int num ;
if(A[i]>='' && A[i]<='') num = A[i]-'';
else num = A[i]-'a'+;
ret += p*num;
p*=radix;
} return ret;
} long long calcRadix(char * B){
long long ret = ;
int len = strlen(B);
for(int i=;i<len;i++){
int num ;
if(B[i]>='' && B[i]<='') num = B[i]-'';
else num = B[i]-'a'+;
if(num+>ret) ret=num+;
}
return ret;
} int compare(char* B, long long radix, long long target){
int len = strlen(B);
long long ret = ;
long long p = ;
for(int i=len-;i>=;i--){
int num;
if(B[i]>='' && B[i]<='') num = B[i]-'';
else num = B[i]-'a'+;
ret += p*num;
if(ret > target) return ;
p*=radix;
}
if(ret > target) return ;
else if(ret<target) return -;
else return ;
} long long binarySearch(char* B, long long low, long long high, long long target){
long long mid;
while(low<=high){
mid = (low+high)/;
int res = compare(B,mid,target);
if(res > )
high = mid-;
else if(res<)
low = mid+;
else return mid;
}
return -;
} int main() {
char A[];
char B[];
int chose;
long long radix; cin>>A>>B>>chose>>radix;
int eq = equal(A,B);
if(eq==) printf("2\n");
else if(eq==) printf("%d\n",radix);
else{
if(chose==){
long long target = str2Num(A,radix);
long long least = calcRadix(B);
long long most = (target)>(least)?(target):(least); // input : 11 b 1 10
long long res = binarySearch(B,least,most,target);
if(res==-) cout<<"Impossible"<<endl;
else cout<<res<<endl;
}
else{
long long target = str2Num(B,radix);
long long least = calcRadix(A);
long long most = (target)>(least)?(target):(least);
long long res = binarySearch(A,least,most,target);
if(res==-) cout<<"Impossible"<<endl;
else cout<<res<<endl;
}
}
return ;
}
发现基本思想都不一样额。。最小的进制就是它的某位最大的数字，最大就是被比较的另一个变量的值，然后再进行二分法搜索。而我的算法是从0到最大暴力搜索。
#include<stdio.h>
#include<math.h>
int isp(long l);
int main(){
long int n,t,cnt;
long int i;
scanf("%ld",&n);
t=n;
i=;
if(n==||isp(n)){
printf("%d=%d",n,n);
return ;
}
printf("%ld=",n);
while(!isp(t)){
if(isp(i)){
cnt=;
if(t%i==){ while(t%i==){
t/=i;
cnt++;
}
if(cnt==)
printf("%ld",i);
else
printf("%d^%d",i,cnt); if(t!=)
printf("*"); i++;
}
else
i++;
}
else
i++;
}
printf("%d",t);
return ;
}
int isp(long l){
long i=;
while(i<sqrt(l)+){
if(l==)
return ;
if(l%i==){
return ;
}
if(i==l-)
return ;
i++;
} }
纠结了好久的一道题，终于还是过了。。首先是判断素数，可以用sqrt来简化复杂度。如果是素数则直接输出，如果不是则进入循环来寻找它的因数。之前最初我用两组数组来记录每一个因数和它的次方，实在是复杂多余，后来改成了直接算一个输出一个，明显简化了许多。还有要注意特殊情况的输出，素数直接输出自身即可。还有最重要的一点是：循环结束条件的判断。余数如果是素数即可结束循环，我的程序一直超时，就是没有利用这个循环结束条件。
PS:关于找出所有素数的解法，还有一个高效的方法：素数筛选法
void init(){
primgsize=;
for(int i=;i<=;i++){
if(mark[i]==true) continue;
prime[primesize++]=i;for(int j=i*i;j<=;j+=i){
mark[j]=true;
}
}