8-15-Exercise

8-15 - 연습
이번 제목은...눈물이 쏟아질 것 같아..T T
A. HDU 1042    N!
0<=n<=1000이기 때문에 반드시 수조나 문자열을 사용해야 한다[마찬가지로 n<=1000이기 때문에 수조를 사용하면 충분하다~~~].
코드:

 1 #include <iostream>

 2 #include <cstdio>

 3 using namespace std;

 4 

 5 int a[40000];

 6 

 7 int main()

 8 {

 9     int n,i,j;

10     while(~scanf("%d",&n))

11     {

12         if(n==1 || n==0){printf("1
"); continue;}

13         a[0]=1;            //         

14         a[1]=1;

15         for(i=2;i<=n;i++)

16         {

17             int sum=0;

18             for(j=1;j<=a[0];j++)

19             {

20                 int temp=a[j]*i+sum;

21                 sum=temp/10;

22                 a[j]=temp%10;

23             }

24             while(sum)

25             {

26                 a[j]=sum%10;

27                 a[0]=j;

28                 sum/=10;

29                 j++;

30             }

31         }

32         for(i=a[0];i>=1;i--)

33             printf("%d",a[i]);

34         printf("
");

35     }

36     return 0;

37 }

//memory:372KB     time:1546ms
B. HDU 1050       Moving Tables
다음은 인터넷의 코드입니다. 제가 이 문제를 풀 때 제 사고방식은 아래 코드의 사고방식과 약간 다르게 생겼습니다.나는 구간을 큰 줄에서 작은 줄로 옮긴 후에 같은 시간에 작업할 수 있는 구간을 찾아서 몇 번을 찾아야 하는지 보았다.인터넷 코드의 사고방식은 중첩 구역을 찾아 중첩 횟수를 보는 것이다.사실, 실질적으로 나의'찾은 횟수'와 인터넷의'중첩 횟수'는 모두 같지만, 왜 WA인지 모르겠지만, 여러 그룹의 데이터를 테스트한 것은 모두 옳았다.
나의 코드는 다음과 같다 [고수의 아낌없는 가르침을 바랍니다]:

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <algorithm>

 4 #include <cstring>

 5 using namespace std;

 6 

 7 class N

 8 {

 9 public:

10     int x,y,id;

11 }a[1000];

12 

13 bool comp(N w,N q)

14 {

15     return w.x<q.x;

16 }

17 

18 int main()

19 {

20     int t,n,i,j;

21     scanf("%d",&t);

22     while(t--)

23     {

24         memset(a,0,sizeof(a));

25         scanf("%d",&n);

26         for(i=0;i<n;i++)

27         {

28             int x,y;

29             scanf("%d%d",&x,&y);

30             if(x<y)

31                 {a[i].x=x;a[i].y=y;}

32             else

33                 {a[i].x=y;a[i].y=x;}

34         }

35         sort(a,a+n,comp);

36         int sum=0;

37         for(i=0;i<n;i++)

38             if(a[i].id==0)

39             {

40                 a[i].id=1;

41                 int minn=a[i].y;

42                 for(j=i+1;j<n;j++)

43                     if(a[j].id==0 && a[j].x>minn)

44                     {

45                         a[j].id=1;

46                         minn=a[j].y;

47                     }

48                 sum++;

49             }

50         printf("%d
",sum*10);

51     }

52     return 0;

53 }

온라인 AC 코드:

#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <string.h>

using namespace std;



#define maxn 460



int main()

{

    int t,i,n,b,e;

    scanf("%d",&t);

    while (t--)

    {

        int c[200]={0},m=0;

        scanf("%d",&n);

        while (n--)

        {

            scanf("%d%d",&b,&e);

            if (b>e)

            {

                i=b;

                b=e;

                e=i;

            }

            for (i=(b-1)/2;i<=(e-1)/2;++i)

                ++c[i];

        }

        for (i=0;i<200;++i)

            if (m<c[i])m=c[i];

        printf("%d
",10*m);

    }

    return 0;

}

//memory:228KB   time:0ms
C.HDU 1181변형과
제목: 문자열 무더기에서 'b' 가 'm' 으로 변환될 수 있는지 확인하는 것입니다.[관계 변환: 모든 문자열의 알파벳은 알파벳으로 바꿀 수 있습니다.]
 BFS~

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <queue>

 4 #include <cstring>

 5 using namespace std;

 6 

 7 const int inf=1<<30;

 8 bool vis[11111];

 9 int a[55][55];

10 char c[11111];

11 

12 void bfs()

13 {

14     int q1=1,q2,i;

15     queue<int> q;

16     memset(vis,0,sizeof(vis));

17     q.push(q1);

18     vis[q1]=1;

19     while(!q.empty())

20     {

21         q2=q.front();

22         q.pop();

23         for(i=0;i<26;i++)       //i      【example：i=0,  A】

24             if(!vis[i] && a[q2][i]==1)     

25             {

26                 if(i=='m'-'a')

27                 {

28                     puts("Yes.");

29                     return;

30                 }

31                 q.push(i);

32                 vis[i]=1;

33             }

34     }

35     puts("No.");

36     return;

37 }

38 

39 int main()

40 {

41     int t,n,i,j,len;

42     memset(a,0,sizeof(a));

43     while(~scanf("%s",c))

44     {

45         len=strlen(c);

46         a[c[0]-'a'][c[len-1]-'a']=1;          //        

47         if(c[0]=='0')

48         {

49             bfs();

50             memset(a,0,sizeof(a));

51         }

52     }

53     return 0;

54 }

//memory:268KB     time:0ms
D. HDU 3501       Calculation 2
코올라 함수다~
출처: http://gzhu-101majia.iteye.com/blog/1296950
코드:

 1 #include <iostream>

 2 #include <cstdio>

 3 using namespace std;

 4 

 5 #define M 1000000007

 6 

 7 int eular(__int64 n)     //    

 8 {

 9     int i,ans=n;

10     for(i=2;i*i<=n;i++)

11         if(n%i==0)

12         {

13             ans-=ans/i;

14             while(n%i==0)

15                 n/=i;

16         }

17     if(n>1) ans-=ans/n;

18     return ans;

19 }

20 

21 int main()

22 {

23     __int64 n,ans;

24     while(scanf("%I64d",&n),n)

25     {

26         ans=n*(n+1)/2-n;

27         ans-=eular(n)*n/2;

28         ans%=M;

29         printf("%I64d
",ans);

30     }

31     return 0;

32 }

//memory:228KB    time:15ms
E. HDU 2601        An easy problem
i*i+i+j=n은 다음과 같이 쓸 수 있다. (i+1)*(j+1)=n-1
모양이 위에 이 모양으로 바뀌었는데...정답은 화려하게 나왔습니다.
코드:

 1 #include<stdio.h>

 2 #include<math.h>

 3 int main()

 4 {

 5 

 6     int t;

 7     scanf("%d",&t);

 8     while(t--)

 9     {

10         __int64 n;

11         scanf("%I64d",&n);

12         n++;

13        __int64 i;

14         __int64 sum=0;

15         for(i=2;i*i<=n;i++)

16             if(n%i==0)

17             sum++;

18          printf("%I64d
",sum);

19 

20     }

21     return 0;

22 }

//memory:228KB   time:2000ms