2019 Multi-University Training Contest 5

12017 단어
나는 또 반찬이 되었을 뿐만 아니라 연기도 배웠다

1002 - three arrays


분석: 매번 욕심을 부리는 것은 두 개의 집합 중 이차나 값이 가장 작은pair를 취하면 먼저 사전 트리를 사용하여 해결할 수 있다.두 개의 사전 나무로 유지할 생각을 하기 쉽다. 문제는 어떻게 최소치를 취하는가이다. 왜냐하면 두 나무가 동시에 0을 걷는지 1을 걷는지 확정할 수 없기 때문이다.
사실 같이 가면 돼요. 같은 노드의 0과 1은 서로 영향을 주지 않기 때문에 0에서 아래로 귀속되고 1에서 아래로 귀속됩니다. 그들의 결과도 서로 영향을 주지 않기 때문에 나무 전체를 끝까지 완주하고 순서를 정하면 됩니다.
그러면 마지막 방법은 두 그루의 나무를 동시에 뛰고, 우선적으로 00과 11을 뛰고, 01과 10을 뛰는 것이다.
#include "bits/stdc++.h"

using namespace std;
struct node {
    int nxt[2], num;
} a[100004 * 32], b[100004 * 32];
int cnt1, cnt2;
int ans[100004];
int cnt;

void init() {
    cnt1 = cnt2 = cnt = 0;
    a[0].nxt[0] = a[0].nxt[1] = b[0].nxt[0] = b[0].nxt[1] = -1;
    a[0].num = b[0].num = 0;
}

void ins(node t[], char s[], int root, int &cnt) {
    int len = strlen(s);
    for (int i = 0; i < len; ++i) {
        if (t[root].nxt[s[i] - '0'] == -1) {
            t[root].nxt[s[i] - '0'] = ++cnt;
            root = cnt;
            t[root] = {{-1, -1}, 0};
        } else root = t[root].nxt[s[i] - '0'];
        t[root].num++;
    }
}

int qu(int rt1, int rt2, int w, int base) {
    bool ok = 1;
    int res = 0;
    while ((~a[rt1].nxt[0]) && (~b[rt2].nxt[0])) {
        int temp = qu(a[rt1].nxt[0], b[rt2].nxt[0], w, base >> 1);
        res += temp;
        a[rt1].num -= temp;
        b[rt2].num -= temp;
        int nx1 = a[rt1].nxt[0], nx2 = b[rt2].nxt[0];
        if (a[nx1].num == 0)
            a[rt1].nxt[0] = -1;
        if (b[nx2].num == 0)
            b[rt2].nxt[0] = -1;
        ok = 0;
    }
    while ((~a[rt1].nxt[1]) && (~b[rt2].nxt[1])) {
        int temp = qu(a[rt1].nxt[1], b[rt2].nxt[1], w, base >> 1);
        res += temp;
        a[rt1].num -= temp;
        b[rt2].num -= temp;
        int nx1 = a[rt1].nxt[1], nx2 = b[rt2].nxt[1];
        if (a[nx1].num == 0)
            a[rt1].nxt[1] = -1;
        if (b[nx2].num == 0)
            b[rt2].nxt[1] = -1;
        ok = 0;
    }
    while ((~a[rt1].nxt[0]) && (~b[rt2].nxt[1])) {
        int temp = qu(a[rt1].nxt[0], b[rt2].nxt[1], w + base, base >> 1);
        res += temp;
        a[rt1].num -= temp;
        b[rt2].num -= temp;
        int nx1 = a[rt1].nxt[0], nx2 = b[rt2].nxt[1];
        if (a[nx1].num == 0)
            a[rt1].nxt[0] = -1;
        if (b[nx2].num == 0)
            b[rt2].nxt[1] = -1;
        ok = 0;
    }
    while ((~a[rt1].nxt[1]) && (~b[rt2].nxt[0])) {
        int temp = qu(a[rt1].nxt[1], b[rt2].nxt[0], w + base, base >> 1);
        res += temp;
        a[rt1].num -= temp;
        b[rt2].num -= temp;
        int nx1 = a[rt1].nxt[1], nx2 = b[rt2].nxt[0];
        if (a[nx1].num == 0)
            a[rt1].nxt[1] = -1;
        if (b[nx2].num == 0)
            b[rt2].nxt[0] = -1;
        ok = 0;
    }
    if (ok) {
        ans[cnt++]=w;
        res++;
        a[rt1].num -= res;
        b[rt2].num -= res;
    }
    return res;
}

char s[35];

int main() {
    int t;cin>>t;
    while (t--) {
        int n,x;cin>>n;
        init();
        for (int i = 0; i < n; ++i) {
            scanf("%d",&x);
            for (int j = 30; j >= 0; --j) {
                s[j] = '0' + (x & 1);
                x >>= 1;
            }
            s[31] = '\0';
            ins(a, s, 0, cnt1);
        }
        for (int i = 0; i < n; ++i) {
            scanf("%d",&x);
            for (int j = 30; j > 0; --j) {
                s[j] = '0' + (x & 1);
                x >>= 1;
            }
            s[31] = '\0';
            ins(b, s, 0, cnt2);
        }
        qu(0, 0, 0, 1 << 30);
        sort(ans,ans+cnt);
        for (int i = 0; i < cnt; ++i) {
            printf("%d%c", ans[i], (i == cnt - 1 ? '
' : ' '));
        }
    }
}

1004 - equation


분석: 이것은 분단 함수로 n+1단이 있고 각 단락의 함수의 해가 존재하는지 계산하면 된다.1년 동안 버그를 썼어요.
#include "bits/stdc++.h"

using namespace std;

struct node {
    int up, dw;

    bool friend operator v, ans;
int a[100004], b[100004];

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, c;
        scanf("%d%d", &n, &c);
        v.clear();
        ans.clear();
        int A = 0, B = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &a[i], &b[i]);
            v.push_back({-b[i], a[i]});
            A += -a[i];
            B += -b[i];
        }
        B -= c;
        sort(v.begin(), v.end());
        bool ok = 0;
        for (int i = 0; i < v.size() && !ok; ++i) {
            if (A == 0 && B == 0)ok = 1;
            else if (A == 0 && B != 0) {
                A += v[i].dw * 2;
                B -= v[i].up * 2;
                continue;
            } else {
                node t;
                if (B == 0) {
                    t = {0, 1};
                } else {
                    int g = __gcd(A, B);
                    t = {-B / g, A / g};
                }
                node s = {v[i].up, v[i].dw};
                node las;
                if (i != 0)las = {v[i - 1].up, v[i - 1].dw};
                if (i == 0 && (t < s || t == s)) {
                    ans.push_back(t);
                } else if ((t < s || t == s) && (las < t || las == t)) {
                    ans.push_back(t);
                }
                A += v[i].dw * 2;
                B -= v[i].up * 2;
            }
        }
        node t;
        if (A == 0 && B == 0)ok = 1;
        else if (A == 0 && B != 0);
        else if (B == 0) {
            t = {0, 1};
            if (v[v.size() - 1] < t || v[v.size() - 1] == t)ans.push_back(t);
        } else {
            int g = __gcd(abs(A), abs(B));
            t = {-B / g, A / g};
            if (v[v.size() - 1] < t || v[v.size() - 1] == t)ans.push_back(t);
        }
        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        if (ok) {
            puts("-1");
        } else {
            printf("%d", ans.size());
            printf("%c", ans.size() == 0 ? '
' : ' ');
            for (int i = 0; i < ans.size(); ++i) {
                if (ans[i].dw < 0) {
                    ans[i].dw *= -1;
                    ans[i].up *= -1;
                }
                printf("%d/%d%c", ans[i].up, ans[i].dw, (i == ans.size() - 1 ? '
' : ' '));
            }
        }
    }
}

1005 - permutation 1


분석: 우선 사전 서열이 가장 작은 두 자리는 n, 1이다.그렇다면 (n-2)! >=k 앞의 두 개가 n, 1이다.그러면 n<=9의 예처리 타표에 대해 n>9의 것은 선형적으로 추출할 수 있다. 우선 n>9의 앞자리는 n, 1이 틀림없다.그러면 사전서의 관계에 따라 3위의 수는 점차적으로 증가해야 하고 3위의 수는 개수에 대해fac[3]이어야 한다. 그러면 이때 k와fac[n-3]의 관계를 비교하고 작은 것부터 큰 것까지 일일이 열거하면 된다.
#include "bits/stdc++.h"

using namespace std;
long long fac[24];
int ans[24];
bool vis[24];
int init[10][10004][10];

struct node {
    int d[34];
    int x[34];
    int n;

    bool friend operator b.d[i])return 0;
        }
        return 0;
    }
} a[1000000];

vector v;
int cnt;

int main() {
    fac[0] = 1;
    v.resize(30);

    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= 20; ++i) {
        fac[i] = fac[i - 1] * i;
    }
    v[1] = 1;
    for (int i = 2; i <= 9; ++i) {
        v[i] = i;
        for (int j = 1; j <= fac[i]; ++j) {
            for (int k = 1; k < i; ++k) {
                a[j].d[k] = v[k + 1] - v[k];
            }
            for (int k = 1; k <= i; ++k) {
                a[j].x[k] = v[k];
            }
            a[j].n = i;
            next_permutation(v.begin() + 1, v.begin() + i + 1);
        }
        sort(a + 1, a + fac[i] + 1);
        for (int k = 1; k <= min(fac[i], 10000LL); ++k) {
            for (int j = 1; j <= i; ++j) {
                init[i][k][j] = a[k].x[j];
            }
        }
    }
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);
        if (n > 9) {
            memset(vis, 0, sizeof(vis));
            ans[1] = n;
            ans[2] = 1;
            vis[n] = 1;
            vis[1] = 1;
            for (int i = 3; i <= n; ++i) {
                int base;
                for (int j = 1; j <= n; ++j) {
                    if (!vis[j]) {
                        base = j;
                        break;
                    }
                }
                while (k > fac[n - i]) {
                    k -= fac[n - i];
                    base++;
                    while (vis[base])base++;
                }
                ans[i] = base;
                vis[base] = 1;
            }
            for (int i = 1; i <= n; ++i) {
                printf("%d%c", ans[i], (i == n ? '
' : ' '));
            }
        } else {
            for (int i = 1; i <= n; ++i) {
                printf("%d%c", init[n][k][i], (i == n ? '
' : ' '));
            }
        }
    }
}

1006 - string matching


exkmp 판자.공헌을 누적해서 계산하면 됩니다. 정답은 모든 위치의lcp를 더하고, 모든 check가 마지막 자리에 일치하는지 여부입니다. 그렇지 않으면 답은 +1입니다.
#include

using namespace std;


void EX_ten(char *a, char *b, int M, int N, long long *Next, long long *ret) {
    int i, j, k;
    for (j = 0; 1 + j < M && a[j] == a[1 + j]; j++);
    Next[1] = j;
    k = 1;
    for (i = 2; i < M; i++) {
        int Len = k + Next[k], L = Next[i - k];
        if (L < Len - i) {
            Next[i] = L;
        } else {
            for (j = max(0, Len - i); i + j < M && a[j] == a[i + j]; j++);
            Next[i] = j;
            k = i;
        }
    }
    for (j = 0; j < N && j < M && a[j] == b[j]; j++);
    ret[0] = j;
    k = 0;
    for (i = 1; i < N; i++) {
        int Len = k + ret[k], L = Next[i - k];
        if (L < Len - i) {
            ret[i] = L;
        } else {
            for (j = max(0, Len - i); j < M && i + j < N && a[j] == b[i + j]; j++);
            ret[i] = j;
            k = i;
        }
    }
}

char s1[1000005], s2[1000005];
long long ret[1000005];
long long Next[1000005];


int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s1);
        int n = strlen(s1);
        for (int i = 0; i <= n; i++) ret[i] = Next[i] = 0;
        for (int i = 0; i <= n; i++) s2[i] = s1[i];
        EX_ten(s1, s2, n, n, Next, ret);
        long long ans = 0;
        for (int i = 1; i < n; i++) {
            ans += ret[i];
            ans += (ret[i] != n - i);
        }
        printf("%lld
", ans);
    }
    return 0;
}

1007 - permutation 2


분석: n, 1, n의 데이터를 쉽게 얻을 수 있는 것은 점차적인 F[N]=F[N-1]+F[N-3]이며, 동시에 답을 얻을 수 있는 것은 x, y와 1, n의 차이와 관련이 있다.x는 x-2, x-4... 1, 3... x-3, x-1, 즉 예시 12 3 9, [4,8], 즉 515에 해당한다. x=1과 y=n을 특별히 판정하면 된다.
#include "bits/stdc++.h"

using namespace std;
const int mod = 998244353;
long long f[100004];

int main() {
    int t;
    f[0] = 0;
    f[1] = 1;
    f[2] = 1;
    for (int i = 3; i < 100004; ++i) {
        f[i] = f[i - 1] + f[i - 3];
        f[i] %= mod;
    }
    cin >> t;
    int n, x, y;
    while (t--) {
        scanf("%d%d%d", &n, &x, &y);
        int dx = x - 1, dy = n - y;
        int pos = n;
        if (dx == 0 && dy == 0) {
            printf("%lld
", f[pos]);
        } else {
            if (dx)pos -= 1;
            if (dy)pos -= 1;
            pos -= dx;
            pos -= dy;
            pos = max(0, pos);
            if ((x == 1 || y == n) && y - x == 1) {
                puts("1");
            } else printf("%lld
", f[pos]);
        }
    }
}

실패자에 가입하여 우리는 체인 논리를 하고 있다
LeetCode: 486. 승자 예측(구간사상, 귀속)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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