A. Assignment For Princess

先构造出一个 1->2->3->...->n->1 的环，前 $n-1$ 条边的值分别为 $1,2,..,n-1$，最后一条边满足环的值模 $3$ 余 $0$。

然后对每一条边，暴力找一条可以满足的边即可。

#include <bits/stdc++.h>
#define pii pair<int, int>

const int N = 111;
const int M = N * N / 7;

bool done[M], vis[N][N];
int n, m, dis[N][N];

struct Node {
    int x, y, z;
    Node() {}
    Node(int x, int y, int z): x(x), y(y), z(z) {}
};

std::vector<Node> res;
std::vector<std::pii> vec[N];
#define fi first
#define se second

int cal(int i, int j) {
    int ans = 0;
    while (i != j) {
        ans += vec[i][0].se;
        i = vec[i][0].fi;
    }
    return ans;
}

bool solve(int val) {
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) if (i != j) {
            if (vis[i][j] || vis[j][i]) continue;
            if (dis[i][j] % 3 == val % 3) {
                vis[i][j] = 1;
                res.push_back(Node(i, j, val));
                done[val] = 1;
                return 1;
            }
        }
    return 0;
}

bool solve() {
    for (int i = 1; i <= n; i++) {
        vec[i].clear();
        for (int j = 1; j <= n; j++)
            vis[i][j] = dis[i][j] = 0;
    }
    for (int i = 1; i <= m; i++)
        done[i] = 0;
    res.clear();
    int sum = 0;
    for (int i = 1; i <= n - 1; i++) {
        res.push_back(Node(i, i + 1, i));
        vec[i].push_back(std::pii(i + 1, i));
        sum += i;
        vis[i][i + 1] = 1;
        done[i] = 1;
    }
    for (int i = n; i <= m; i++) {
        if ((i + sum) % 3 == 0) {
            done[i] = 1;
            vec[n].push_back(std::pii(1, i));
            vis[n][1] = 1;
            res.push_back(Node(n, 1, i));
            break;
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) if (i != j) {
            dis[i][j] = cal(i, j);
        }
    for (int i = 1; i <= m; i++) if (!done[i]) {
        if (!solve(i)) return 0;
    }
    return 1;
}

int main() {
    int T;
    scanf("%d", &T);
    for (int kase = 1; kase <= T; kase++) {
        scanf("%d%d", &n, &m);
        printf("Case #%d:\n", kase);
        if (solve()) {
            for (int i = 0; i < m; i++) 
                printf("%d %d %d\n", res[i].x, res[i].y, res[i].z);
        } else {
            puts("-1");
        }
    }
    return 0;
}

View Code

 

B. Beautiful Soup

模拟

#include <bits/stdc++.h>

const int N = 215;
const char *last = "</html>";

char ch;

bool isSpace(char ch) {
    return ch == 32 || ch == 9 || ch == 10;
}

void printSpace(int n) {
    while (n--) putchar(' ');
}

void removeSpace() {
    while ((ch = getchar()) && isSpace(ch));
}

void Enter() {
    puts("");
}

void gettag(char *tag) {
    int len = 0;
    tag[len++] = '<';
    while ((ch = getchar()) && ch != '>') 
        tag[len++] = ch;
    tag[len++] = '>';
    tag[len] = 0;
}

void printtag(char *tag, int cnt) {
    if (tag[1] == '/') {
        printSpace(cnt - 1);
    } else {
        printSpace(cnt);
    }
    puts(tag);
}

void updateSpace(char *tag, int &cnt) {
    int len = strlen(tag);
    if (tag[1] != '/' && tag[len - 2] != '/')
        ++cnt;
    else if (tag[1] == '/')
        --cnt;
}

void printText(int cnt) {
    printSpace(cnt);
    putchar(ch);
    while ((ch = getchar()) && ch != '<') {
        if (isSpace(ch)) {
            removeSpace();
            if (ch == '<') break;
            else {
                printSpace(1);
                putchar(ch);
            }
        } else {
            putchar(ch);
        }
    }
    Enter();
}

int main() {
    int T;
    int kase = 0;
    scanf("%d", &T);
    getchar();
    while (T--) {
        static char tag[N];
        int cnt = 0;
        ch = getchar();
        printf("Case #%d:\n", ++kase);
        while (1) {
            if (isSpace(ch)) removeSpace();
            else if (ch == '<') {
                gettag(tag);
                printtag(tag, cnt);
                if (strcmp(tag, last) == 0) break;
                updateSpace(tag, cnt);
                ch = getchar();
            } else {
                printText(cnt);
            }
        }
    }
}

View Code

 

D. Dinner Coming Soon

用 $dp[i][j][k][l]$ 表示在第 $i$ 个空间的第 $j$ 个点，带有 $k$ 个包，花费时间为 $l$ 的最大值。

时间做第一维进行 dp 即可。注意不能走到别的空间的 $1$ 和 $n$，以及交易只能转移一次，不要多转移了。

#include <bits/stdc++.h>

const int N = 207;
const int INF = 0x3f3f3f3f;
int n, m, B, K, R, T, p[10][N];
int dp[7][110][7][N];
int cnt, head[N];
 // dp[i][j][k][l] 在第 i 个空间的第 j 个点，带有 k 个包，花费时间为 l 的最大值

bool check(int i, int j) {
    if (j == 1 || j == n) return i == 0;
    return 1;
}

struct E {
    int v, ne, t, c;
} e[N << 1];

void add(int u, int v, int t, int c) {
    e[++cnt].v = v; e[cnt].ne = head[u]; e[cnt].t = t; e[cnt].c = c; head[u] = cnt;
}

template<class T>
inline bool chkmax(T &a, T b) {
    return a < b ? a = b, 1 : 0;
}

int main() {
    int C;
    scanf("%d", &C);
    for (int kase = 1; kase <= C; kase++) {
        printf("Case #%d: ", kase);
        scanf("%d%d%d%d%d%d", &n, &m, &B, &K, &R, &T);
        for (int i = 0; i < K; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", p[i] + j);
        cnt = 1;
        memset(head, 0, sizeof(head));
        for (int i = 1; i <= m; i++) {
            int u, v, t, c;
            scanf("%d%d%d%d", &u, &v, &t, &c);
            add(u, v, t, c);
        }
        for (int i = 0; i < K; i++)
            for (int j = 1; j <= n; j++)
                for (int k = 0; k <= B; k++)
                    for (int t = 0; t <= T; t++)
                        dp[i][j][k][t] = -INF;
        dp[0][1][0][0] = R;
        for (int t = 0; t <= T; t++) for (int i = 0; i < K; i++) 
            for (int u = 1; u < n; u++) for (int k = 0; k <= B; k++) if (dp[i][u][k][t] >= 0 && check(i, u)) {
                int nexttime = t + 1;
                int nextmoney = dp[i][u][k][t];
                if (u != 1 && nexttime <= T) {
                    chkmax(dp[(i + 1) % K][u][k][nexttime], nextmoney);
                    if (k + 1 <= B && nextmoney - p[i][u] >= 0)
                        chkmax(dp[(i + 1) % K][u][k + 1][nexttime], nextmoney - p[i][u]);
                    if (k + 1 >= 0)
                        chkmax(dp[(i + 1) % K][u][k - 1][nexttime], nextmoney + p[i][u]);
                }
                for (int j = head[u]; j; j = e[j].ne) {
                    int v = e[j].v;
                    int nexttime = t + e[j].t;
                    int nextmoney = dp[i][u][k][t] - e[j].c;
                    if (nexttime > T || nextmoney < 0) continue;
                    if (!check(i, v)) continue;
                    chkmax(dp[i][v][k][nexttime], nextmoney);
                    if (u != 1) {
                        if (k + 1 <= B && nextmoney - p[i][u] >= 0)
                            chkmax(dp[i][v][k + 1][nexttime], nextmoney - p[i][u]);
                        if (k - 1 >= 0)
                            chkmax(dp[i][v][k - 1][nexttime], nextmoney + p[i][u]);
                    }
                }
            }
        int ans = -INF;
        for (int t = 0; t <= T; t++)
            for (int k = 0; k <= B; k++)
                chkmax(ans, dp[0][n][k][t]);
        if (ans < 0)
            puts("Forever Alone");
        else 
            printf("%d\n", ans);
    }
    return 0;
}

View Code

 

F. Fibonacci Tree

大概就是，最大生成树和最小生成树之间的斐波那契数都可以。

#include <bits/stdc++.h>

const int N = 1e5 + 7;
int n, m, f[N], fa[N];

struct Edge {
    int u, v, c;
} edge[N];

void init() {
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}

bool cmp1(const Edge &a, const Edge &b) {
    return a.c < b.c;
}

bool cmp2(const Edge &a, const Edge &b) {
    return a.c > b.c;
}

int find(int u) {
    return fa[u] == u ? u : fa[u] = find(fa[u]);
}

bool check(int min, int max) {
    for (int i = 1; i <= 25; i++)
        if (min <= f[i] && max >= f[i]) return 1;
    return 0;
}

int main() {
    f[0] = 1, f[1] = 1;
    int cnt;
    for (int i = 2; f[i - 1] <= N; i++)
        f[i] = f[i - 1] + f[i - 2], cnt = i;
    //printf("%d\n", f[25]);
    int T;
    scanf("%d", &T);
    for (int kase = 1; kase <= T; kase++) {
        printf("Case #%d: ", kase);
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; i++)
            scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].c);
        std::sort(edge, edge + m, cmp1);
        init();
        int tol1 = 0, min = 0, max = 0, tol2 = 0;
        for (int j = 0; j < m; j++) {
            int u = find(edge[j].u), v = find(edge[j].v);
            if (u != v) {
                min += edge[j].c;
                fa[u] = v;
                tol1++;
            }
        }
        std::sort(edge, edge + m, cmp2);
        init();
        for (int j = 0; j < m; j++) {
            int u = find(edge[j].u), v = find(edge[j].v);
            if (u != v) {
                max += edge[j].c;
                fa[u] = v;
                tol2++;
            }
        }
        //printf("%d %d\n", min, max);
        if (tol1 + 1 == n && tol2 + 1 == n && check(min, max)) puts("Yes");
        else puts("No");
    }
    return 0;
}

View Code

 

G. GRE Words Revenge

要做一个在线的AC自动机。

法一就用一个大的和一个小的，小的自动机用于每次重构加入新串，当节点数大于某个定值就把它合并上大的自动机。

法二直接哈希，因为加入的串总长不超过 $10^5$，那么最多只有 $sqrt{10^5}$ 种长度的字符串，复杂度就是 $O(n sqrt n)$

哈希只有 seed = $2$ 和 mod = $10^9+9$ 能过。。

#include <bits/stdc++.h>
#define ll long long

const int N = 1e5 + 100;
const int M = 5e6 + 100;
char s[M], s0[M];
bool vis[N];
std::set<int> st[N];
int base[N];
const int seed = 2, MOD = 1e9 + 9;
int ha[M];

int main() {
    int T, kase = 0;
    scanf("%d", &T);
    for (int i = base[0] = 1; i < N; i++)
        base[i] = 1LL * seed * base[i - 1] % MOD;
    while (T--) {
        int n;
        scanf("%d", &n);
        printf("Case #%d:\n", ++kase);
        std::vector<int> vec;
        memset(vis, 0, sizeof(vis));
        int last = 0;
        while (n--) {
            scanf("%s", s0);
            int len = strlen(s0 + 1);
            for (int i = 1; i <= len; i++)
                s[i] = s0[(i + last - 1) % len + 1];
            if (s0[0] == '+') {
                int temp = 0;
                for (int i = 1; i <= len; i++)
                    temp = (1LL * seed * temp + s[i] - '0') % MOD;
                st[len].insert(temp);
                if (!vis[len]) {
                    vis[len] = 1;
                    vec.push_back(len);
                }
            } else {
                int cnt = 0;
                for (int i = 1; i <= len; i++) {
                    ha[i] = (1LL * ha[i - 1] * seed + s[i] - '0') % MOD;
                    for (int v: vec) {
                        if (i - v < 0) continue;
                        int h = (ha[i] - (ll)ha[i - v] * base[v] % MOD + MOD) % MOD;
                        if (st[v].find(h) != st[v].end()) cnt++;
                    }
                }
                printf("%d\n", last = cnt);
            }
        }
        for (int v: vec)
            st[v].clear();
    }
    return 0;
}

View Code

 

H. Hard Disk Drive

#include <bits/stdc++.h>

const char s[10][10] = {"B", "KB", "MB", "GB", "TB", "PB", "EB", "ZB", "YB"};

int main() {
    int T;
    scanf("%d", &T);
    int kase = 0;
    while (T--) {
        int n;
        char ch[10];
        scanf("%d[%s]", &n, ch);
        int len = strlen(ch);
        ch[len - 1] = 0;
        int pos = 0;
        for (int i = 0; i < 9; i++) {
            if (strcmp(s[i], ch) == 0) {
                pos = i;
            }
        }
        double ans = 100;
        for (int i = 0; i < 3 * pos; i++)
            ans *= 10.0;
        int cnt = 1024;
        for (int i = 0; i < pos; i++)
            ans /= 1024.0;
        ans = 100 - ans;
        printf("Case #%d: %.2f", ++kase, ans);
        puts("%");
    }
    return 0;
}

View Code

 

J. Just Random

大力讨论一下，发现是等差数列。

#include <bits/stdc++.h>
#define ll long long

int main() {
    int T;
    scanf("%d", &T);
    for (int kase = 1; kase <= T; kase++) {
        ll a, b, c, d, m, p;
        scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &p, &m);
        a += p - m, b += p - m;
        ll fz = 0, fm = (b - a + 1) * (d - c + 1);
        if (a + d >= b + c) {
            ll l = a + c, r = b + c - 1;
            ll st = l + (p - (l % p)) % p, ed = r - (r % p);
            ll n = (ed - st) / p + 1;
            ll a1 = st - l + 1;
            fz += n * a1 + p * n * (n - 1) / 2;

            l = a + d, r = b + d;
            st = l + (p - (l % p)) % p, ed = r - (r % p);
            n = (ed - st) / p + 1;
            a1 = r - ed + 1;
            fz += n * a1 + p * n * (n - 1) / 2;

            l = b + c, r = a + d - 1;
            st = l + (p - (l % p)) % p, ed = r - (r % p);
            if (st > ed) n = 0;
            else n = (ed - st) / p + 1;
            a1 = b - a + 1;
            fz += n * a1;
        } else {
            ll l = a + c, r = a + d;
            ll st = l + (p - (l % p)) % p, ed = r - (r % p);
            ll n = (ed - st) / p + 1;
            ll a1 = st - l + 1;
            fz += n * a1 + p * n * (n - 1) / 2;

            l = b + c, r = b + d;
            st = l + (p - (l % p)) % p, ed = r - (r % p);
            n = (ed - st) / p + 1;
            a1 = r - ed + 1;
            fz += n * a1 + p * n * (n - 1) / 2;

            l = a + d + 1, r = b + c - 1;
            st = l + (p - (l % p)) % p, ed = r - (r % p);
            if (ed < st) n = 0;
            else n = (ed - st) / p + 1;
            a1 = d - c + 1;
            fz += n * a1;
        }
        ll g = std::__gcd(fz, fm);
        printf("Case #%d: %lld/%lld\n", kase, fz / g, fm / g);
    }
    return 0;
}

View Code