2018 HDU多校第三场赛后补题

从易到难来写吧，其中题意有些直接摘了Claris的，数据范围是就不标了。
如果需要可以去hdu题库里找。题号是6319 ～ 6331。

L. Visual Cube

题意：

题解：

代码：

#include <bits/stdc++.h>
using namespace std;

int a, b, c, R, C;
char g[505][505];
int main () {
    int T; cin >> T;
    for ( ; T; --T) {
        cin >> a >> b >> c;
        R = c * 2 + b * 2 + 1;
        C = a * 2 + b * 2 + 1;
        memset(g, '.', sizeof g);
        for (int i = R; i >= R - c * 2; i -= 2) {
            for (int j = 1; j <= a; ++j) {
                g[i][j * 2 - 1] = '+';
                g[i][j * 2] = '-';
            }
            g[i][a * 2 + 1] = '+';
            if (i == R - c * 2) continue;
            for (int j = 1; j <= a; ++j) {
                g[i - 1][j * 2 - 1] = '|';
            }
            g[i - 1][a * 2 + 1] = '|';
        }
        int ed = R, st = R - c * 2;
        for (int j = a * 2 + 1; j <= C; ++j) {
            int x = j - (a * 2);
            if (x & 1) {
                for (int i = st; i <= ed; ++i) {
                    int y = ed - i;
                    if (y & 1) g[i][j] = '|';
                    else g[i][j] = '+';
                }
            } else {
                for (int i = st; i <= ed; ++i) {
                    int y = ed - i;
                    if (y & 1) g[i][j] = '.';
                    else g[i][j] = '/';
                }
            }
            --ed, --st;
        }

        ed = b * 2 + 1, st = 1;
        for (int j = 1; j <= a * 2; ++j) {
            int x = j;
            if (x & 1) {
                for (int i = ed; i >= st; --i) {
                    int y = i - st;
                    if (y & 1) g[i][j + ed - i] = '/';
                    else g[i][j + ed - i] = '+';
                }
            } else {
                for (int i = ed; i >= st; --i) {
                    int y = i - st;
                    if (y & 1) ;
                    else g[i][j + ed - i] = '-';
                }
            }
        }

        for (int i = 1; i <= R; ++i) {
            for (int j = 1; j <= C; ++j) printf("%c", g[i][j]);
            puts("");
        }
    }
    return 0;
}

D. Euler Function

题意：

题解：

代码：

#include<bits/stdc++.h>
using namespace std;
int main () {
    int T,n;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        if (n==1) printf("5\n");
        else printf("%d\n",5+n);
    }
    return 0;
}

F. Grab The Tree

题意：

题解：

代码：

#include<bits/stdc++.h>
#define N 100010
using namespace std;
int main () {
    int T,n,u,v,w;
    scanf("%d",&T);
    while (T--) {
        int sum=0;
        scanf("%d",&n);
        for(int i=1; i<=n; ++i) scanf("%d",&w),sum^=w;
        for(int i=1; i<n; ++i) scanf("%d%d",&u,&v);
        if (sum==0) printf("D\n"); else printf("Q\n");
    }
    return 0;
}

C. Dynamic Graph Matching

题意：

题解：

代码：

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int mo = 1e9 + 7, N = 11;
int n, m, bc[1 << N], f[1 << N], ans[N]; char op[5];

int bitcnt (int x) {
    return x ? bitcnt(x >> 1) + (x & 1) : 0;
}
int main () {
    int T; cin >> T;
    for (int i = 0; i < (1 << N); ++i) bc[i] = bitcnt(i);
    for ( ; T; --T) {
        cin >> n >> m, f[0] = 1;
        for (int s = 1; s < (1 << n); ++s) f[s] = 0;
        for (int i = 1, x, y; i <= m; ++i) {
            scanf("%s%d%d", op, &x, &y), --x, --y;
            if (op[0] == '+') {
                for (int s = 0, t; s < (1 << n); ++s) {
                    if ((s >> x & 1) || (s >> y & 1)) continue;
                    t = s | 1 << x | 1 << y;
                    f[t] += f[s];
                    if (f[t] >= mo) f[t] -= mo;
                }
            } else {
                for (int s = (1 << n) - 1, t; ~s; --s) {
                    if ((s >> x & 1) || (s >> y & 1)) continue;
                    t = s | 1 << x | 1 << y;
                    f[t] -= f[s];
                    if (f[t] < 0) f[t] += mo;
                }
            }
            for (int i = 1; i <= (n >> 1); ++i) ans[i] = 0;
            for (int s = 1, t; s < (1 << n); ++s) {
                t = bc[s]; if (t & 1) continue; else t >>= 1;
                ans[t] += f[s];
                if (ans[t] >= mo) ans[t] -= mo;
            }
            for (int i = 1; i <= (n >> 1); ++i) {
                printf("%d%c", ans[i], i < (n >> 1) ? ' ' : '\n');
            }
        }
    }
    return 0;
}

G. Interstellar Travel

题意：

题解：

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 200005;

int n, top;

struct point {
    int x, y, i;
    point () {}
    point (int _x,int _y,int _i = 0) :
        x(_x), y(_y), i(_i) {}
} a[N], s[N];
point operator - (point u, point v) {
    return point(u.x - v.x, u.y - v.y, u.i);
}
bool cmp (point u, point v) {
    ll t = 1ll * u.x * v.y - 1ll * u.y * v.x;
    return t == 0 ? (u.x == v.x ? u.i < v.i: u.x < v.x) : t < 0;
}

bool cmp2 (point u, point v) {
    ll t = 1ll * u.x * v.y - 1ll * u.y * v.x;
    return t == 0 ? u.i < v.i : t < 0;
}
void solve () {
    s[top = 1] = a[1];
    for (int i = 2; i <= n; ++i) {
        if (a[i].x == a[i - 1].x && a[i].y == a[i - 1].y) continue;
        while (top >= 2 && cmp2(a[i] - s[top - 1], s[top] - s[top - 1])) --top;
        s[++top] = a[i];
    }
}

int main () {
    int T; cin >> T;
    for ( ; T; --T) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &a[i].x, &a[i].y);
            a[i].i = i;
        }
        sort(a + 2, a + n, cmp);
        solve();
        for (int i = 1; i <= top; ++i) {
            printf("%d%c", s[i].i, i < top ? ' ' : '\n');
        }
    }
    return 0;
}

A. Ascending Rating

题意：

题解：

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 10000005;
int n, m, k, p, q, r, mo, a[N];
int h, t, Q[N];
ll A, B;

int read () {
    int x = 0; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar());
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
    return x;
}
int main () {
    int T; cin >> T;
    for ( ; T; --T) {
        cin >> n >> m >> k >> p >> q >> r >> mo;
        for (int i = 1; i <= k; ++i) a[i] = read();
        for (int i = k + 1; i <= n; ++i) a[i] = (1ll * p * a[i - 1] + 1ll * q * i + r) % mo;
        h = 0, t = 1, A = B = 0;
        for (int i = n; i >= n - m + 1; --i) {
            if (a[i] < a[Q[h]]) Q[++h] = i;
            else {
                for ( ; t <= h && a[i] >= a[Q[h]]; ) --h;
                Q[++h] = i;
            }
        }
        A += a[Q[t]] ^ (n - m + 1);
        B += (h - t + 1) ^ (n - m + 1);
        for (int i = n - m; i; --i) {
            if (Q[t] == i + m) ++t;
            if (a[i] < a[Q[h]]) Q[++h] = i;
            else {
                for ( ; t <= h && a[i] >= a[Q[h]]; ) --h;
                Q[++h] = i;
            }
            A += a[Q[t]] ^ i;
            B += (h - t + 1) ^ i;
        }
        cout << A << " " << B << endl;
    }
    return 0;
}

I. Random Sequence

题意：

题解：

代码：

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 105, mo = 1e9 + 7;
int n, m, g[N][N], inv[N], a[N], v[N];
int f[2][N][N][N];

int ksm (int b, int p) {
    if (p < 2) return p ? b : 1;
    int t = ksm(b, p >> 1); t = 1ll * t * t % mo;
    return p & 1 ? 1ll * t * b % mo : t;
}
int main () {
    int T; cin >> T;
    for (int i = 0; i <= 100; ++i) g[0][i] = g[i][0] = i;
    for (int i = 1; i <= 100; ++i)
    for (int j = 1; j <= 100; ++j) g[i][j] = __gcd(i, j);
    for (int i = 1; i <= 100; ++i) inv[i] = ksm(i, mo - 2);
    for ( ; T; --T) {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        for (int i = 1; i <= m; ++i) scanf("%d", &v[i]);
        memset(f, 0, sizeof f);
        int nx, ny, nz, tmp;
        for (int z = 1; z <= m; ++z)
        for (int y = 1; y <= m; ++y)
        for (int x = 1; x <= m; ++x) {
            if (a[1] && a[1] != z) continue;
            if (a[2] && a[2] != y) continue;
            if (a[3] && a[3] != x) continue;
            nx = x, ny = g[x][y], nz = g[ny][z];
            tmp = 1;
            if (!a[1]) tmp = 1ll * tmp * inv[m] % mo;
            if (!a[2]) tmp = 1ll * tmp * inv[m] % mo;
            if (!a[3]) tmp = 1ll * tmp * inv[m] % mo;
            f[1][nx][ny][nz] += tmp;
            if (f[1][nx][ny][nz] >= mo) f[1][nx][ny][nz] -= mo;
        }
        for (int i = 3, c; i <= n; ++i) {
            c = i & 1, memset(f[c ^ 1], 0, sizeof f[c ^ 1]);
            for (int z = 1; z <= m; ++z)
            for (int y = z; y <= m; y += z)
            for (int x = y; x <= m; x += y) if (f[c][x][y][z]) {
                if (a[i + 1]) {
                    nx = a[i + 1], ny = g[x][a[i + 1]], nz = g[y][a[i + 1]];
                    f[c ^ 1][nx][ny][nz] += 1ll * f[c][x][y][z] * v[g[a[i + 1]][z]] % mo;
                    if (f[c ^ 1][nx][ny][nz] >= mo) f[c ^ 1][nx][ny][nz] -= mo;
                    continue;
                }
                for (int j = 1; j <= m; ++j) {
                    nx = j, ny = g[x][j], nz = g[y][j];
                    f[c ^ 1][nx][ny][nz] += 1ll * f[c][x][y][z] * v[g[j][z]] % mo * inv[m] % mo;
                    if (f[c ^ 1][nx][ny][nz] >= mo) f[c ^ 1][nx][ny][nz] -= mo;
                }
            }
        }
        int ans = 0;
        for (int z = 1; z <= m; ++z)
        for (int y = z; y <= m; y += z)
        for (int x = y; x <= m; x += y) ans = (ans + f[n & 1][x][y][z]) % mo;
        cout << ans << endl;
    }
    return 0;
}

M. Walking Plan

题意：

题解：

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 55, K = 10005, S = 105, inf = 0x3f3f3f3f;
int n, m, q, ans, g[N][N], f[N][N], A[S][N][N], B[S][N][N];

int main () {
    int T; cin >> T;
    for ( ; T; --T) {
        cin >> n >> m;
        memset(g, 0x3f, sizeof g);
        memset(A, 0x3f, sizeof A);
        memset(B, 0x3f, sizeof B);
        for (int i = 1, x, y, z; i <= m; ++i) {
            scanf("%d%d%d", &x, &y, &z);
            g[x][y] = min(g[x][y], z);
            B[1][x][y] = g[x][y];
        }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) A[0][i][j] = B[0][i][j] = i == j ? 0 : inf;
        for (int k = 2; k <= 100; ++k) {
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    for (int x = 1; x <= n; ++x)
                    B[k][i][j] = min(B[k][i][j], B[k - 1][i][x] + B[1][x][j]);
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) A[1][i][j] = B[100][i][j];
        }
        for (int k = 2; k <= 100; ++k) {
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    for (int x = 1; x <= n; ++x)
                    A[k][i][j] = min(A[k][i][j], A[k - 1][i][x] + A[1][x][j]);
        }
        for (int i = 1; i <= n; i++) g[i][i] = 0;
        for (int x = 1; x <= n; ++x) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) g[i][j] = min(g[i][j], g[i][x] + g[x][j]);
            }
        }
        for (int k = 0; k <= 100; ++k) {
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j) f[i][j] = inf;
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    for (int x = 1; x <= n; ++x) f[i][j] = min(f[i][j], B[k][i][x] + g[x][j]);
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j) B[k][i][j] = f[i][j];
        }
        cin >> q;
        for (int s, t, k, u, v; q; --q) {
            scanf("%d%d%d", &s, &t, &k), ans = inf;
            u = k / 100, v = k % 100;
            for (int i = 1; i <= n; ++i) {
                ans = min(ans, A[u][s][i] + B[v][i][t]);
            }
            if (ans >= inf) ans = -1;
            printf("%d\n", ans);
        }
    }
    return 0;
}

H. Monster Hunter

题意：

题解：

代码：

#include <bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;

const int N = 100005;

int n, P, a[N], b[N];
int tot, lnk[N], nxt[N << 1], son[N << 1], fa[N];
bool dead[N];

struct mons {
    ll a, b; int i, t;
    mons () {}
    mons (ll _a, ll _b, int _i = 0,int _t = 0) :
        a(_a), b(_b), i(_i), t(_t) {}
    bool operator < (const mons &o) const {
        bool k1 = a < b, k2 = o.a < o.b;
        if (k1 != k2) return k1 < k2;
        else return a >= b ? b < o.b : a > o.a;
    }
    void operator += (const mons &o) {
        ll na = max(a, a - b + o.a), nb = - a + b - o.a + o.b + na;
        a = na, b = nb;
    }
} m[N], cur;
priority_queue <mons> q;

int read () {
    int x = 0; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar());
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
    return x;
}
void add (int x, int y) {
    nxt[++tot] = lnk[x], lnk[x] = tot, son[tot] = y;
}
void dfs (int x, int p) {
    fa[x] = p;
    for (int j = lnk[x]; j; j = nxt[j]) {
        if (son[j] == p) continue;
        dfs(son[j], x);
    }
}
int get (int x) {
    return dead[fa[x]] ? fa[x] = get(fa[x]) : fa[x];
}
int main () {
    for (int T = read(); T; --T) {
        n = read(), tot = 0;
        for (int i = 1; i <= n; ++i) lnk[i] = 0, dead[i] = 0;
        for (int i = 1; i <= n * 2; ++i) nxt[i] = 0;
        for ( ; !q.empty(); q.pop());
        m[1] = mons(0, 0, 1, 0);
        for (int i = 2; i <= n; ++i) {
            m[i].a = read(), m[i].b = read();
            m[i].i = i, m[i].t = 0, q.push(m[i]);
        }
        for (int i = 1, x, y; i < n; ++i) {
            x = read(), y = read();
            add(x, y), add(y, x);
        }
        dfs(1, 0), dead[1] = 0;
        for (int sec = 1; !q.empty(); ++sec) {
            cur = q.top(), q.pop();
            if (cur.t != m[cur.i].t || dead[cur.i]) continue;
            get(cur.i), dead[cur.i] = 1;
            P = get(cur.i);
            m[P] += m[cur.i], m[P].t = sec;
            if (P > 1) q.push(m[P]);
        }
        cout << max(0ll, m[1].a) << endl;
    }
    return 0;
}

剩下的题可能有点难搞了。。