A 문제 진행 시 -- 절 대 PAT 1001 - 1010

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
",c/1000000,(c/1000)%1000,c%1000);
13 else if(c>=1000)
14 printf("%d,%03d
",c/1000,c%1000);
15 else
16 printf("%d
",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
",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
":" %d %.1f",i,a[i]);
32 }
33  return 0;
34 }

 최대 1000 밖 에 안 되 기 때문에 공간 을 이용 하여 절 차 를 간소화 하고 용량 이 1000 인 배열 을 만 든 다음 에 1 부터 1000 까지 옮 겨 다 닐 수 있 습 니 다.
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
",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 까지 의 거리 값 이 짧 아 지면 이 거리 값 을 수정 합 니 다.
S 에 모든 정점, 즉 W = Vi 가 포 함 될 때 까지 상기 절 차 를 2, 3 반복 합 니 다.
사실은 복잡 하지 않 아 요. 앞으로 비슷 한 문 제 를 쉽게 풀 었 으 면 좋 겠 어 요.
 
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("
");
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 를 롱 롱 롱 으로 바 꿔 도 지나 갈 수 없다.내 가 이해 하 는 제목 에 문제 가 있 는 것 같다.큰 데 이 터 는 이분법 을 써 야 지나 갈 수 있 습 니 다. 먼저 이렇게 하고 시간 이 있 으 면 이분법 의 알고리즘 을 쓰 세 요. 계속 하 세 요.
이분법 검색 의 구체 적 인 방법 을 보 았 습 니 다. 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
");
 86     else if(eq==2) printf("%d
",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;
    }
}