제1 8 회 상하 이 대학 프로 그래 밍 리그 봄 경기 및 대학교 인터넷 친선 경기 A ~ F 문제 풀이

A. 팀 경기 매 거 법

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#include <climits>
int st[2002], gt[2002];
int main()
{
    int a[22], k = 0;
    for (int i = 0; i < 4; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < 4; i++)
    {
        for (int j = i + 1; j < 4; j++)
        {
            st[k] = a[i] + a[j];//4  2     
            for (int w = 0; w < 4; w++)
            {
                if (w != i && w != j)//      
                {
                    gt[k] += a[w];
                }
            }
            k++;
            //printf("%d
", st[k - 1]);
        }
    }
    int t = st[0];
    int MIN = 0x3f3f3f3f;
    for (int i = 1; i < k; i++)//  
    {
        if (fabs(st[i] - gt[i]) < MIN)
        {
            MIN = fabs(st[i] - gt[i]);
        }
    }
    printf("%d
", MIN);
}

B. 매일 구조 체, 정렬 규칙 함수

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
using namespace std;
struct node//         
{
    int day;
    int id;
    double temp;
}p[502];
struct cmp//      
{
    bool operator()(const node& t1, const node& t2)
    {
        if (t1.day != t2.day)
        {
            return t1.day > t2.day;
        }
        else if (t1.temp != t2.temp)
        {
            return t1.temp > t2.temp;
        }
        return t1.id < t2.id;
    }
};
int main()
{
    int n, a, b, k = 0;
    double c;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d%lf", &a, &b, &c);
        if (c < 38)//       
        {
            continue;
        }
        p[k].day = a, p[k].id = b, p[k++].temp = c;
    }
    sort(p, p + n, cmp());
    printf("%d
", k);
    for (int i = 0; i < k; i++)
    {
        printf("%d %d %.1lf
", p[i].day, p[i].id, p[i].temp);
    }
};

C. 최 장 비 공공 서브 시퀀스 는 처음에 DP 라 고 생각 했 는데 나중에 두 가지 상황 만 발견 되 었 다. 즉, 문자열 이 똑 같 고 다른 상황 이다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    char p[5005], q[5005];
    scanf("%s%s", p, q);
    if (strcmp(p, q) == 0)//     
    {
        printf("-1
");
        return 0;
    }
    printf("%d
", max(strlen(p), strlen(q)));//     
}

D. 최대 문자 집합 구조 문 제 는 일정한 길이 범위 내 에 있 는 모든 독립 된 01 문자열 집합 (즉, 집합 내 다른 문자열 이 포함 되 지 않 는 문자열) 을 찾 아야 합 니 다. 이 파 는 데이터 범위 가 비교적 작 기 때 문 입 니 다 (n < 300). 그리고 제목 마다 길이 가 제한 되 는 문자열 은 1 개 만 있 을 수 있 습 니 다. 요구 하 는 풀이 공간 범위 가 비교적 작 습 니 다.(우 리 는 먼저 111111 과 같이 0 의 위 치 를 분명히 바 꾸 면 111110, 111101, 111011, 110111, 101111, 011111, 011111, 011111 등 서로 다른 독립 문자열 을 만 들 수 있 습 니 다. 제목 의 요구 에 따라 각 길이 의 문자열 은 한 가지 만 있 을 수 있 기 때문에 매번 검색 할 때마다 끝 에 있 는 1 을 버 리 고 0 대 1 의 위치 인 111111 - > 111110 - > 11101 - > 1011 을 이동 합 니 다.맨 왼쪽 끝 에 도착 하면 어떻게 구 조 를 해 야 합 니까? n > 2 시의 문자열 수 는 n - 1 에 이 르 러 야 이론 적 최대 치 에 이 를 수 있 습 니 다. 0 과 1 은 반드시 다른 문자열 의 하위 문자열 이기 때 문 입 니 다. 우 리 는 한 문자열 에서 두 개의 0 을 사용 하여 계속 구 조 를 할 수 있 습 니 다. 두 개의 0 은 문자열 을 많이 유연 하 게 만 들 고 구조 가 쉬 워 집 니 다. 예 를 들 어 011110 - > 01110 - > 010 - > 00 과 같은 구조 방식 은 쉽게 이 루어 집 니 다.우리 가 첫 번 째 검색 이 불가능 할 때 두 번 째 검색 을 사용 합 니 다.

// An highlighted block
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void dfs2(int len)//                  
{
    if (len < 2)
        return;
    printf("0");
    for (int i = i = 0; i < len - 2; i++)
    {
        printf("1");
    }
    printf("0
");
    dfs2(len - 1);
}
void dfs(int len, int pos, int count)
{
    if (count > len)//0              
    {
        return;
    }
    for (int i = 0; i < len; i++)//     
    {
        if (i == pos)
        {
            int j;
            for (j = 0; j < count; j++)
            {
                printf("0");
            }
            i += j - 1;
            continue;
        }
        printf("1");
    }
    printf("
");
    if (pos > 1)
    {
        dfs(len - 1, pos - 2, count);//     -1，0     2 
    }
    else dfs2(len - 1);//0            ，       
}
int main()
{
    int n;
    scanf("%d", &n);
    if (n < 3)
    {
        printf("%d
", n);
    }
    else printf("%d
", n - 1);
    dfs(n, n, 1);//     ，0   (    0）,0   
}

E. 맛 있 는 서열 욕심, 수치 가 큰 데 이 터 를 우선 선택 하면 더 큰 이윤 을 창 출 할 수 있 습 니 다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[100005];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    int count = 0;
    long long sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += a[i] - count;
        count++;
    }
    printf("%lld
", sum);
}

F. 날짜 조수 시 뮬 레이 션, 날짜 류 문 제 는 윤년 처리, 분류 토론, 그리고 몇 주 동안 의 날짜 순환 처리 에 주의해 야 한다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int moon[3000];
int fa[3000];
int main()
{
    moon[2000] = 14;
    for (int i = 2001; i <= 2100; i++)//      
    {
        if (!(i % 4 == 0 && i % 100 != 0))
        {
            moon[i] = moon[i - 1] - 1;
            if (moon[i] == 7)
                moon[i] = 14;
        }
        else {
            moon[i] = moon[i - 1] - 2;
            if (moon[i] == 7)
                moon[i] = 14;
            if (moon[i] == 6)
                moon[i] = 13;
        }
    }
    fa[2000] = 18;
    for (int i = 2001; i <= 2100; i++)//      
    {
        if (!(i % 4 == 0 && i % 100 != 0))
        {
            fa[i] = fa[i - 1] - 1;
            if (fa[i] == 14)
                fa[i] = 21;
        }
        else {
            fa[i] = fa[i - 1] - 2;
            if (fa[i] == 14)
                fa[i] = 21;
            if (fa[i] == 13)
                fa[i] = 20;
        }
    }
    int n, a, b, c;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d%d", &a, &b, &c);//      
        if (b < 5 || b == 5 && c < moon[a])
        {
            if (moon[a] == 1 || moon[a] == 21 || moon[a] == 31)
                printf("Mother's Day: May %dst, %d
", moon[a], a);
            else if (moon[a] == 2 || moon[a] == 22)
                printf("Mother's Day: May %dnd, %d
", moon[a], a);
            else if (moon[a] == 3 || moon[a] == 23)
                printf("Mother's Day: May %drd, %d
", moon[a], a);
            else printf("Mother's Day: May %dth, %d
", moon[a], a);
        }
        else if (b > 6 || b == 6 && c >= fa[a])
        {
            if (moon[a + 1] == 1 || moon[a + 1] == 21 || moon[a + 1] == 31)
                printf("Mother's Day: May %dst, %d
", moon[a + 1], a + 1);
            else if (moon[a + 1] == 2 || moon[a + 1] == 22)
                printf("Mother's Day: May %dnd, %d
", moon[a + 1], a + 1);
            else if (moon[a + 1] == 3 || moon[a + 1] == 23)
                printf("Mother's Day: May %drd, %d
", moon[a + 1], a + 1);
            else printf("Mother's Day: May %dth, %d
", moon[a + 1], a + 1);
        }
        else {
            if (fa[a] == 1 || fa[a] == 21 || fa[a] == 31)
                printf("Father's Day: June %dst, %d
", fa[a], a);
            else if (fa[a] == 2 || fa[a] == 22)
                printf("Father's Day: June %dnd, %d
", fa[a], a);
            else if (fa[a] == 3 || fa[a] == 23)
                printf("Father's Day: June %drd, %d
", fa[a], a);
            else printf("Father's Day: June %dth, %d
", fa[a], a);
        }
    }
}