2016년 낙산사범대학 프로그래밍대회 문제풀이 보고서

29849 단어

A:절단 회문


먼저 모든 하위 문자열이 회문 문자열인지 계산해 낸다. 이 단계의 시간 복잡도는 O(N*N)이어야 한다. 그리고 동적 계획을 해야 한다. 현재의 최소 절단은 앞의 최소 절단이 유도한 것이고 전체적인 최악의 시간 복잡도는 O(N*N)이다.
#include 
#include 
#define MAXN 1000
#define MIN(a, b) (a < b ? a : b)
int sub[MAXN][MAXN];
void preprocess(char str[], int len) {
    int a, b, l, r;
    for (a = 0; a < MAXN; ++a) {
        for (b = 0; b < MAXN; ++b) {
            sub[a][b] = 0;
        }
    }
    for (a = 0; a < len; ++a) {
        l = a, r = a;
        while (0 <= l && r < len && str[l] == str[r]) {
            sub[l][r] = 1;
            l -= 1, r += 1;
        }
        l = a, r = a + 1;
        while (0 <= l && r < len && str[l] == str[r]) {
            sub[l][r] = 1;
            l -= 1, r += 1;
        }
    }
}
int main() {
    int T, dp[1000], len, a, b, c;
    char str[1001];
    scanf("%d", &T);
    while (T--) {
        scanf("%s", str);
        len = strlen(str);
        preprocess(str, len);
        //for (a = 0; a < MAXN; ++a) dp[a] = 0;
        dp[0] = 1;
        for (a = 1; a < len; ++a) {
            dp[a] = dp[a - 1] + 1;
            for (b = a - 1; b >= 0; --b) {
                if (sub[b][a]) {
                    if (b == 0) dp[a] = 1;
                    else dp[a] = MIN(dp[a], dp[b - 1] + 1);
                }
            }
        }
        printf("%d
", dp[len - 1] - 1);
    }
    return 0;
}

B:특수 비밀번호 자물쇠


각 버튼은 최대 한 번 누릅니다. 따라서 현재 버튼의 누름 또는 누름 여부는 현재 버튼의 상태와 이전 버튼의 상태에 따라 달라집니다. 따라서 다음 검색을 진행하고 가장자리를 특수하게 처리하면 됩니다.아마도 나의 상태 표시 방법이 약간 타당하지 않은 것 같으니 스스로 고려할 수 있다.
#include 
#include 
#define INF 30
#define MIN(a, b) (a < b ? a : b)
char str[30], check[30];
void change(int pos, int len) {
    if (pos == 0) {
        if (str[pos] == '1') str[pos] = '0';
        else str[pos] = '1';
        if (pos + 1 == len) return;
        if (str[pos + 1] == '1') str[pos + 1] = '0';
        else str[pos + 1] = '1';
        return;
    }
    if (str[pos - 1] == '1') str[pos - 1] = '0';
    else str[pos - 1] = '1';
    if (str[pos] == '1') str[pos] = '0';
    else str[pos] = '1';
    if (pos + 1 == len) return;
    if (str[pos + 1] == '1') str[pos + 1] = '0';
    else str[pos + 1] = '1';
    return;
}
int solve(int pos, int len, int step) {
    int res = INF, tmp;
    if (pos == len) {
        return str[pos - 1] == check[pos - 1] ? step : INF;
    }
    if (pos == 0) {
        tmp = solve(pos + 1, len, step);
        res = MIN(res, tmp);
        change(pos, len);
        tmp = solve(pos + 1, len, step + 1);
        res = MIN(res, tmp);
        change(pos, len);
        return res;
    }
    if (str[pos - 1] == check[pos - 1]) {
        tmp = solve(pos + 1, len, step);
        res = MIN(res, tmp);
    } else {
        change(pos, len);
        tmp = solve(pos + 1, len, step + 1);
        res = MIN(res, tmp);
        change(pos, len);
    }
    return res;
}
int main() {
    int res = INF, len;
    while (scanf("%s%s", str, check) != EOF) {
        len = strlen(str);
        if (len != strlen(check)) printf("impossible
");
        res = solve(0, len, 0);
        if (res == INF) printf("impossible
");
        else printf("%d
", res);
    }
    return 0;
}

C:최적 시퀀스


현재 최악의 시간 복잡도가 O(N*logN *logN)라는 사고방식이 있는데 코드를 다 치지 못했기 때문에 토론에 관심이 있는 친구는 저를 믿어도 됩니다.

D:문자열 등급


먼저 모든 대문자를 소문자로 바꾸고 빈칸을 하나씩 지워라.
#include 
#include 

void to_lowercase(char *str) {
    int a, len = strlen(str);
    for (a = 0; a < len; ++a) {
        if (str[a] < 97 && str[a] != ' ') str[a] += 32;
    }
}

void remove_space(char *str) {
    int a, b = 0, len = strlen(str);
    for (a = 0; a < len; ++a) {
        if (str[a] != ' ') str[b++] = str[a];
    }
    for (a = b; a < len; ++a) str[a] = 0;
}

int main() {
    char stra[10000], strb[10000];
    int a, lena, lenb, res = 1;
    gets(stra), gets(strb);
    to_lowercase(stra), to_lowercase(strb);
    remove_space(stra), remove_space(strb);
    lena = strlen(stra), lenb = strlen(strb);
    if (lena != lenb) res = 0;
    //printf("%s
%s
", stra, strb);
    for (a = 0; a < (lena & lenb); ++a) {
        if (stra[a] != strb[a]) res = 0;
    }
    printf("%s
", (res ? "YES" : "NO"));
    return 0;
}

E:구간 결합


먼저 순서를 정한 다음에 모든 구간이 연결될 수 있는지 없는지를 판단한다.그러나 데이터 범위 내에서도 해시로 이 문제를 해결할 수 있다.O(N*N)의 최악의 시간 복잡도는 이론적으로 넘길 수 없지만 마지막에 누군가가 이렇게 해서 Accepted를 얻었다는 것은 과학적이지 않다.
#include 
typedef struct pair {
    int l, r;
}pair;
int compare(const void *a, const void *b) {
    return ((pair *)a)->l - ((pair *)b)->l;
}
int main() {
    int a, b, l, r, ok = 1, N;
    pair region[50000];
    scanf("%d", &N);
    for (a = 0; a < N; ++a) {
        scanf("%d%d", &region[a].l, &region[a].r);
    }
    qsort(region, N, sizeof(pair), compare);
    l = region[0].l;
    r = region[0].r;
    for (a = 1; a < N; ++a) {
        if (r < region[a].l) {
            ok = 0;
            break;
        }
        r = r < region[a].r ? region[a].r : r;
    }
    if (ok) printf("%d %d
", l, r);
    else printf("no
");
    return 0;
}

F:문자 루프


이 문제의 중점은 링에 있다. 원래 간단한 문제였어야 했는데 아마도 대다수 학우들이 이런 유형의 문제를 처리하는 경험이 부족했을 것이다.이 문제에 대한 데이터 범위는 매우 작기 때문에 이 문제를 해결하려면 각 열을 배로 늘린 다음에 가장 긴 공공 서브열을 폭력적으로 찾아내면 된다.
#include 
#include 
#define MAX(a, b) a > b ? a : b
int main() {
    char stra[10000], strb[10000];
    int a, b, tmp, res = 0, lena, lenb;
    scanf("%s%s", stra, strb);
    lena = strlen(stra), lenb = strlen(strb);
    for (a = 0; a < lena; ++a) stra[a + lena] = stra[a];
    for (a = 0; a < lenb; ++a) strb[a + lenb] = strb[a];
    stra[lena * 2] = 0, strb[lenb * 2] = 0;
    //printf("%s
%s
", stra, strb);
    for (a = 0; a < lena * 2; ++a) {
        for (b = 0; b < lenb * 2; ++b) {
            tmp = 0;
            while (tmp + a < lena * 2 &&
                   tmp + b < lenb * 2 &&
                   stra[tmp + a] == strb[tmp + b] &&
                   tmp < lena && tmp < lenb) tmp += 1;
            res = MAX(res, tmp);
        }
    }
    printf("%d
", res);
    return 0;
}

G:세그먼트 함수


이번 시합에서 프로그램 설계 경기를 접해 본 적이 없는 학생들에게는 아직도 많은 출석 문제가 있는데 이 문제가 그 중의 하나이다.
#include 
int main() {
    double N, fN;
    scanf("%lf", &N);
    if (0 <= N && N < 5) fN = -N + 2.5;
    else if (5 <= N && N < 10) fN = 2 - 1.5 * (N - 3) * (N - 3);
    else if (10 <= N && N < 20) fN = N * 1.0 / 2 - 1.5;
    printf("%.3lf
", fN);
    return 0;
}

H:최신 정수


열 자리 미만의 숫자, 0이 없으면 K자리를 삭제한다.가능한 모든 수를 직접 들어 가장 작은 것을 찾아라.모든 가능한 수를 다 들면 C(10,5)개밖에 안 되니까 코드 능력만 고찰하는 거죠.
#include 
#include 
#define MIN(a, b) (a < b ? a : b)
#define INF 1e9
int solve(char *number, int len, int n, int K) {
    int a, b;
    for (a = 0; a < len; ++a) {
        if (n >> a & 1) continue;
        K -= 1;
    }
    if (K) return INF;
    for (a = 0, b = 0; a < len; ++a) {
        if (n >> a & 1) {
            b = b * 10 + (number[a] - '0');
        }
    }
    return b;
}
int main() {
    int T, K, len, res, a, b;
    char number[10];
    scanf("%d", &T);
    while (T--) {
        scanf("%s%d", number, &K);
        len = strlen(number);
        res = INF;
        for (a = 0; a < 1 << len; ++a) {
            b = solve(number, len, a, K);
            res = MIN(res, b);
        }
        printf("%d
", res);
    }
    return 0;
}

I:하루하루 건강하게 살다


출석 문제.
#include 
int main() {
    int N, x, ok;
    double t;
    char flag[5];
    scanf("%d", &N);
    while (N--) {
        scanf("%lf%d%s", &t, &x, flag);
        ok = 1;
        if (t < 7.0 || t > 8.0) ok = 0;
        if (x < 1500) ok = 0;
        if (flag[0] == 'N' && flag[1] == 'o') ok = 0;
        //printf("flag: %s
", flag);
        printf(ok ? "Yes
" : "No
");
    }
    return 0;
}

J:3개 수 정렬


출석 문제.
#include 
void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}
int main() {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (a < b) swap(&a, &b);
    if (a < c) swap(&a, &c);
    if (b < c) swap(&b, &c);
    printf("%d %d %d
", a, b, c);
    return 0;
}

K:짝수 찾기


먼저 정렬한 다음에 두 개의 순환이 두 개의 다른 수를 매거한 다음에 이분 검색을 통해 집합에 이 두 개의 수의 곱셈이 존재하는지 판단하면 O(N*N*logN)의 최악의 시간 복잡도는Accepted를 얻을 수 있다.인트 폭발에 주의하고 무게 제거에 주의하세요.
#include 
#define ll long long

int compare(const void *a, const void *b) {
    return (int)((*(ll *)a) - (*(ll *)b));
}

int find(ll *arr, int len, ll val) {
    int l = 0, r = len, mid;
    while (l < r) {
        mid = l + (r - l) / 2;
        if (val == arr[mid]) return 1;
        if (val < arr[mid]) r = mid;
        else l = mid + 1;
    }
    return val == arr[l];
}

int main() {
    int N, res = 0;
    ll arr[1000];
    int a, b, c;
    scanf("%d", &N);
    for (a = 0; a < N; ++a) scanf("%lld", arr + a);
    qsort(arr, N, sizeof(arr[0]), compare);
    for (a = 0; a < N; ++a) {
        for (b = a + 1; b < N; ++b) {
            if (arr[a] != 1 && find(arr, N, arr[a] * arr[b])) {
                res += 1;
            }
        }
    }
    printf("%d
", res);
    return 0;
}

L:조합수


이 문제는 여러 가지 다른 해법이 있는데, 주로 자신이 공식을 어떻게 유도하는가에 있다.
#include 
#define ll long long
int main() {
    int N, M;
    ll arr[21], a;
    for (arr[0] = arr[1] = 1, a = 2; a <= 20; ++a) {
        arr[a] = arr[a - 1] * a;
    }
    while (scanf("%d%d", &N, &M) != EOF) {
        if (N < M) {
            printf("0
");
            continue;
        }
        printf("%lld
", arr[N] / arr[N - M] / arr[M]);
    }
    return 0;
}

M:분해 인수


어떤 학우들은 반드시 먼저 소수를 선별할 것이라는 것을 알고 있지만, 자세히 생각해 보면 확실히 필요없다.
#include 
int main() {
    int N, a;
    scanf("%d", &N);
    printf("%d=", N);
    for (a = 2; a <= N; ++a) {
        while (N % a == 0) {
            printf("%d", a);
            if ((N /= a) != 1) printf("*");
        }
    }
    printf("
");
    return 0;
}
#1. DB 연동하여 Web 만들기
M1Mac의 VScode에서 Unity 개발을 위한 최소한의 설정

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage