Colored Sticks

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e5 + 10;

int p[N];
int son[N][26], idx, num[N], n;
int in[N];

void init() {
    for (int i = 0; i < N; i ++ )

        p[i] = i;
}

int insert(char str[]) {
    int p = 0;

    for (int i = 0; str[i]; i ++ ) {

        int u = str[i] - 'a';

        if (!son[p][u])
            son[p][u] = ++ idx;
        p = son[p][u];
    }

    if (!num[p])
        num[p] = ++ n;
    return num[p];
}

int find(int x) {
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

void merge(int a, int b) {
    int fa = find(a), fb = find(b);

    if (fa != fb)
        p[fa] = fb;
}

bool check() {
    int cnt = 0;

    for (int i = 1; i <= n; i ++ )

        if (p[i] == i)
            cnt ++ ;

    if (cnt >= 2)
        return false;
    int res = 0;

    for (int i = 1; i <= n; i ++ )

        if (in[i] & 1)
            res ++ ;

    if (!res || res == 2)
        return true;
    return false;
}

int main() {
    init();
    char color1[15], color2[15];

    while (scanf("%s%s", color1, color2) != EOF) {
        int x = insert(color1), y = insert(color2);
        in[x] ++, in[y] ++ ;
        merge(x, y);
    }

    if (check())
        puts("Possible");
    else
        puts("Impossible");

    return 0;
}

统计难题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int son[N][26], cnt[N], idx;
char str[N];

void insert(char str[]) {
    int p = 0;

    for (int i = 0; str[i]; i ++ ) {

        int u = str[i] - 'a';

        if (!son[p][u])
            son[p][u] = ++ idx;
        p = son[p][u];
        cnt[p] ++ ;
    }
}

int query(char str[]) {
    int p = 0;

    for (int i = 0; str[i]; i ++ ) {

        int u = str[i] - 'a';

        if (!son[p][u])
            return 0;
        p = son[p][u];
    }

    return cnt[p];
}

int main() {
    bool flag = true;

    while (gets(str)) {
        if (strlen(str) == 0) {
            flag = false;
            continue;
        }

        if (flag)
            insert(str);
        else
            printf("%d\n", query(str));
    }

    return 0;
}

Phone List

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

char str[20];
int son[N][10], cnt[N], idx;

bool insert(char str[]) {
    int p = 0;

    for (int i = 0; str[i]; i ++ ) {

        int u = str[i] - '0';

        if (!son[p][u])
            son[p][u] = ++ idx;
        p = son[p][u];

        if (cnt[p])
            return true;
    }

    for (int i = 0; i < 10; i ++ )

        if (son[p][i])
            return true;
    cnt[p] ++ ;
    return false;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        memset(son, 0, sizeof son);
        memset(cnt, 0, sizeof cnt);
        idx = 0;
        int n;
        scanf("%d", &n);
        bool flag = false;

        while (n -- ) {
            scanf("%s", str);

            if (insert(str))
                flag = true;
        }

        if (flag)
            puts("NO");
        else
            puts("YES");
    }

    return 0;
}