ACM 합숙 훈련 day1

16456 단어 합숙 훈련
7.11
요점: 0.매거법최대 공인수 구하기 2.기억화 사상
note: 시간 복잡도 계산에 능하다
0
1
매거법
분류 매거, 폭력
최대 공인수를 구하다
전전상제>발산->최소 공배수
기억화 사상
예처리, 접두어와 사상
사고문제 0.0:
피보나치 수열과 전전 상제법의 상관성을 지적하고, 전전 상제법의 시간 복잡도를 대체적으로 분석하였다.
사고문제 0.1:
             
#include 
using namespace std;

int fib(int n)
{
    if (n==0 || n==1) return 1;
    int ans=fib(n-2)+fib(n-1);
    return ans;
}

int main()
{
    int n; 
    scanf("%d",&n);
    printf("%d
"
,fib(n)); return 0; }

==========================나는 분할선 ====================================
연습 문제
A번 Least Common Multiple
**사고방식: 서로 인접한 두 수의 최소 공배수를 구하고, 세 번째 수와 최소 공배수를 구하며, 이렇게 끝날 때까지 반복한다.
#include
#include
#include
using namespace std;
int gcd(int a,int b);
int main()
{
    int n,m;
    scanf("%d",&n);
    while(n--)
    {
        int a[100];
        int i;
        scanf("%d",&m);
        for(i=0;iscanf("%d",&a[i]);
        for(i=1;i1])*a[i-1];//**     =    /     **(         ),   a[i]

        }
        printf("%d
"
,a[i-1]); } return 0; } int gcd(int a,int b) // { if(a// , a>b swap(a,b); while(b!=0) { int t; t=a; a=b; b=t%b; } if(b==0) return a; }

==========================나는 분할선 ====================================
B 진수 변환
사고방식: 10진법을 회상하여 2진법으로 바꾸고 2로 나눈 것을 2로 나눈 것을... 거꾸로 출력하는 것과 같은 이치
#include

int main()
{
   int n,r,a[1000];
   while(scanf("%d %d",&n,&r)!=EOF)
   {
       int i,j;
       int tag=1;
       if(n<0)        //    ,      ,        
       {
            n=(-1)*n;
          tag=0;
       }
       for(i=0;n!=0;i++) //       
       {
           a[i]=n%r;
           n/=r;
       }
        if(tag==0)
            printf("-");    //       -
       for(j=i-1;j>=0;j--)        //    
       {
           if(a[j]>=10)
           {
               switch(a[j])
           {
               case 10:printf("A");break;   //      ,  16      ,    'A'+i
               case 11:printf("B");break;
               case 12:printf("C");break;
               case 13:printf("D");break;
               case 14:printf("E");break;
               case 15:printf("F");break;
               default:break;
           }
           continue;
           }
           printf("%d",a[j]);
       }

        printf("
"
); } return 0; }

==========================나는 분할선 ====================================
C 문제
이 문제는 더 이상 드릴 말씀이 없는데... 그냥 멀뚱멀뚱 정수를 정수로 보고 와~ 233!
#include

int main()
{
    int i,n;
    scanf("%d",&n);
    for(i=0;idouble a,b,c;
        scanf("%lf%lf%lf",&a,&b,&c);
        if(a+b>c&&a+c>b&&b+c>a&&a&&b&&c)
            printf("YES
"
); //** ( E ) “Yes”, !** else printf("NO
"
); } return 0;

==========================나는 분할선 ====================================
D번 빈 삼각형
** note: 한 문자를 여러 번 읽으면 오류 발생
#include
#include
#include

int main()
{
   int gao;
   char hua,str[10];
   int test=0;
   while(1)
   {
       scanf("%s",str);  //       %c,                   ,      ,    。**      ,                !**
       hua=str[0];
       if(hua=='@')
        return 0;
        else
            if (test) printf("
"
); //** ** @ , test++; scanf("%d",&gao); int i,j,k; for(i=0;iif(i==gao-1) { for(k=0;k<2*gao-1;k++) printf("%c",hua); printf("
"
); } else { for(j=0;j1;j++) printf(" "); printf("%c",hua); if(i==0) { printf("
"
); continue; } for(j=0;j<2*i-1;j++) printf(" "); printf("%c
"
,hua); } } //fflush(stdin); // judge , , } return 0; }

==========================나는 분할선 ====================================
E제
note: 제목을 유의해서 무엇을 출력하라고!YES?!Yes?!yes?!
#include

int main()
{
    int a,b,i;
     while(scanf("%d%d",&a,&b)&&(a||b))
    {
            int tag=0;
            for(i=-10000;i<10000;i++)

            if((a-i)*i==b)
            {
                 printf("Yes
"
); tag=1; break; } if(tag==0) { printf("No
"
); } } return 0; }

F문제는 A가 안 나왔는데... TAT...========================나는 분할선=========================================
G 제
사고방식: 함수 판단 예쁜 수->정의 수조는 1부터 i까지의 예쁜 수 총수를 나타낸다->기억화 사상->지정 구간
#include
#include
#include
#include
#include
using namespace std;

int Isbeauty(int x);

int main()
{
    int n,sum[100001]={0};//   i    
    scanf("%d",&n);

    for(int i=1;i<=100000;i++) //**i 1  **
    {
        sum[i]=sum[i-1]+Isbeauty(i);  **//     ,       ,      1         **
    }
    while(n--)
    {
        int l,r;
        scanf("%d %d",&l,&r);

        printf("%d
"
,sum[r]-sum[l-1]); //[l,r] } return 0; } int Isbeauty(int x) // { int a[11]={0}; while(x!=0) { if(a[x%10]) // return 0; // 0, else a[x%10]++; x/=10; } return 1; // , 1, }

좀 바빠서 못 하겠네요, 당일 연습 미처 정리하지 못했는데...좋은 출발 하시고 ACM길에서 더욱 강해지세요~

좋은 웹페이지 즐겨찾기