Skip to content

2018 Multi-University Training Contest 7

Contents

A. Age of Moyu

题意：

给出一张图，从 1 走到 n，如果相邻两次走的边的权值不同，花费 +1，否则花费相同，求最小花费。

思路：

用 set 记录有当前点的最小花费有多少种方案到达，然后最短路。

Code 
#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;

struct Edge {
    int to, nxt, val;
    Edge() {}
    Edge(int to, int nxt, int val) : to(to), nxt(nxt), val(val){};
} edge[maxn << 1];

set<int> s[maxn];
int head[maxn], tot;

void Init(int n) {
    for (int i = 0; i <= n; ++i) head[i] = -1, s[i].clear();
    tot = 0;
}

void addedge(int u, int v, int val) {
    edge[tot] = Edge(v, head[u], val);
    head[u] = tot++;
}

struct qnode {
    int v, c;
    int pre;
    int fa;
    qnode() {}
    qnode(int v, int c, int pre, int fa) : v(v), c(c), pre(pre), fa(fa) {}
    bool operator<(const qnode &r) const {
        return c > r.c;
    }
};

int n, m;
int dist[maxn];

void BFS(int st) {
    for (int i = 1; i <= n; ++i) dist[i] = INF;
    priority_queue<qnode> q;
    dist[st] = 0;
    q.push(qnode(st, 0, 0, 0));
    while (!q.empty()) {
        qnode tmp = q.top();
        q.pop();
        int u = tmp.v;
        if (tmp.c > dist[u])
            continue;
        else if (tmp.c == dist[u]) {
            if (s[u].find(tmp.pre) != s[u].end())
                continue;
            s[u].insert(tmp.pre);
        } else {
            dist[u] = tmp.c;
            s[u].clear();
            s[u].insert(tmp.pre);
        }
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            int cost = edge[i].val;
            if (v == tmp.fa)
                continue;
            if (dist[u] + (cost != tmp.pre) <= dist[v]) {
                dist[v] = dist[u] + (cost != tmp.pre);
                if (v != n) {
                    q.push(qnode(v, dist[v], cost, u));
                }
            }
        }
    }
}

int main() {
    int t;
    while (scanf("%d %d", &n, &m) != EOF) {
        Init(n);
        for (int i = 1; i <= m; ++i) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        BFS(1);
        if (dist[n] == INF)
            dist[n] = -1;
        printf("%d\n", dist[n]);
    }
    return 0;
}

B. AraBellaC

留坑。

C. YJJ’s Stack

留坑。

D. Go to school

留坑。

E. GuGuFishtion

留坑。

F. Lord Li's problem

留坑。

G. Reverse Game

留坑。

H. Traffic Network in Numazu

题意：

两种操作：

  • 第一种是更改一条边权的值。
  • 第二种是查询 x \rightarrow y 的最短路径。

给出的是一颗树加一条边。

思路：

将形成环的边单独拿出来考虑。

那么考虑是否经过这条边使得答案更优。

修改操作用线段树或者树状数组维护。

Code 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;
const int DEG = 20;

struct EDGE {
    int u, v, w;
} EDGE[maxn], TEMP;

struct Edge {
    int to, nxt, val;
    Edge() {}
    Edge(int to, int nxt, int val) : to(to), nxt(nxt), val(val) {}
} edge[maxn << 1];

int head[maxn], tot, cnt;
int father[maxn];

void Init(int n) {
    for (int i = 0; i <= n; ++i) head[i] = -1, father[i] = i;
    tot = cnt = 0;
}

int find(int x) {
    return x == father[x] ? father[x] : father[x] = find(father[x]);
}

void mix(int x, int y) {
    x = find(x), y = find(y);
    if (x != y)
        father[x] = y;
}

bool same(int x, int y) {
    return find(x) == find(y);
}

void addedge(int u, int v, int val) {
    edge[tot] = Edge(v, head[u], val);
    head[u] = tot++;
}

int dro[maxn];
int ord[maxn], son[maxn];
int fa[maxn][DEG];
int deg[maxn];

void DFS(int u, int pre) {
    ord[u] = ++cnt;
    dro[cnt] = u;
    for (int i = 1; i < DEG; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].to;
        if (v == pre)
            continue;
        fa[v][0] = u;
        deg[v] = deg[u] + 1;
        DFS(v, u);
    }
    son[u] = cnt;
}

int LCA(int u, int v) {
    if (deg[u] > deg[v])
        swap(u, v);
    int hu = deg[u], hv = deg[v];
    int tu = u, tv = v;
    for (int det = hv - hu, i = 0; det; det >>= 1, ++i) {
        if (det & 1) {
            tv = fa[tv][i];
        }
    }
    if (tu == tv)
        return tu;
    for (int i = DEG - 1; i >= 0; --i) {
        if (fa[tu][i] == fa[tv][i])
            continue;
        tu = fa[tu][i];
        tv = fa[tv][i];
    }
    return fa[tu][0];
}

struct node {
    int l, r;
    ll val, lazy;
    node() {}
    node(int l, int r, ll val, ll lazy) : l(l), r(r), val(val), lazy(lazy) {}
} tree[maxn << 2];

void pushup(int id) {
    tree[id].val = tree[id << 1].val + tree[id << 1 | 1].val;
}

void pushdown(int id) {
    if (tree[id].lazy) {
        ll lazy = tree[id].lazy;
        tree[id << 1].val += lazy;
        tree[id << 1 | 1].val += lazy;
        tree[id << 1].lazy += lazy;
        tree[id << 1 | 1].lazy += lazy;
        tree[id].lazy = 0;
    }
}

void build(int id, int l, int r) {
    tree[id] = node(l, r, 0, 0);
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}

void update(int id, int l, int r, ll val) {
    if (l <= tree[id].l && r >= tree[id].r) {
        tree[id].val += val;
        tree[id].lazy += val;
        return;
    }
    pushdown(id);
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (mid >= l)
        update(id << 1, l, r, val);
    if (r > mid)
        update(id << 1 | 1, l, r, val);
    pushup(id);
}

ll query(int id, int pos) {
    if (tree[id].l == pos && tree[id].r == pos) {
        return tree[id].val;
    }
    pushdown(id);
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (pos <= mid)
        return query(id << 1, pos);
    if (pos > mid)
        return query(id << 1 | 1, pos);
    pushup(id);
}

ll getdis(int u, int v) {
    int root = LCA(u, v);
    return query(1, ord[u]) + query(1, ord[v]) - 2 * query(1, ord[root]);
}

int n, q;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &q);
        Init(n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d %d %d", &EDGE[i].u, &EDGE[i].v, &EDGE[i].w);
            int u = EDGE[i].u, v = EDGE[i].v, w = EDGE[i].w;
            if (same(u, v)) {
                TEMP = EDGE[i];
                continue;
            }
            mix(u, v);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        fa[1][0] = 1;
        deg[1] = 0;
        DFS(1, -1);
        build(1, 1, n);
        for (int i = 1; i <= n; ++i) {
            int u = EDGE[i].u, v = EDGE[i].v, w = EDGE[i].w;
            if (u == TEMP.u && v == TEMP.v)
                continue;
            if (fa[u][0] == v) {
                update(1, ord[u], son[u], w);
            } else if (fa[v][0] == u)
                ;
            { update(1, ord[v], son[v], w); }
        }
        //        for(int i = 1; i <= n; ++i) cout << ord[i] << endl;
        //        for(int i = 1; i <= n; ++i) cout << i << " " << query(1, ord[i]) << endl;
        while (q--) {
            int op, x, y;
            scanf("%d %d %d", &op, &x, &y);
            if (op == 0) {
                int u = EDGE[x].u, v = EDGE[x].v, w = EDGE[x].w;
                if (u == TEMP.u && v == TEMP.v) {
                    EDGE[x].w = y;
                    TEMP.w = y;
                }
                if (fa[u][0] == v) {
                    update(1, ord[u], son[u], y - w);
                } else if (fa[v][0] == u) {
                    update(1, ord[v], son[v], y - w);
                }
                EDGE[x].w = y;
            } else if (op == 1) {
                ll ans = getdis(x, y);
                ans = min(ans, getdis(x, TEMP.u) + TEMP.w + getdis(y, TEMP.v));
                ans = min(ans, getdis(y, TEMP.u) + TEMP.w + getdis(x, TEMP.v));

                printf("%lld\n", ans);
            }
        }
    }
    return 0;
}

I. Tree

题意：

一棵树种，每个点有一个权值，表示可以向上跳几步，两种操作，一种是修改某点权值，还有一种是询问某个点需要跳几次跳出。

思路：

DFS 序分块，弹飞绵阳升级版，注意更新的时候，维护一个 In[u] 表示最远跳到块内是第几块，这样就不用多一个 log 复杂度。

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

namespace FastIO {
#define BUF_SIZE 10000005
bool IOerror = false;
inline char NC() {
    static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
    if (p1 == pend) {
        p1 = buf;
        pend = buf + fread(buf, 1, BUF_SIZE, stdin);
        if (pend == p1) {
            IOerror = true;
            return -1;
        }
    }
    return *p1++;
}

inline bool blank(char ch) {
    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}

template <typename T>
inline void read(T &x) {
    char ch;
    while (blank(ch = NC()))
        ;
    if (IOerror) {
        x = -1;
        return;
    }
    bool flag = false;
    if (ch == '-') {
        flag = true;
        ch = NC();
    }
    if (!isdigit(ch))
        while (!isdigit(ch = NC()))
            ;
    for (x = ch - '0'; isdigit(ch = NC()); x = x * 10 + ch - '0')
        ;
    if (flag)
        x *= -1;
}

void out(int x) {
    if (x / 10)
        out(x / 10);
    putchar(x % 10 + '0');
}

inline void print(int x) {
    out(x);
    puts("");
}
#undef BUF_SIZE
}  // namespace FastIO
using namespace FastIO;

#define N 100010
#define DEG 20
#define block 400

int t, n, q;
int a[N], b[N], In[N], Out[N], fa[N][20], deep[N], p[N], fp[N], cnt;
vector<int> G[N];

void Init() {
    for (int i = 1; i <= n; ++i) G[i].clear();
    cnt = 0;
    fa[1][0] = 1;
    deep[1] = 0;
}

void DFS(int u) {
    p[u] = ++cnt;
    fp[cnt] = u;
    for (int i = 1; i < DEG; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto v : G[u])
        if (v != fa[u][0]) {
            deep[v] = deep[u] + 1;
            DFS(v);
        }
}

int GetK(int x, int k) {
    bitset<20> b;
    b = k;
    for (int i = 19; i >= 0; --i)
        if (b[i])
            x = fa[x][i];
    return x;
}

int query(int x) {
    int res = 0;
    x = p[x];
    while (x) {
        res += b[x];
        x = Out[x];
    }
    return res;
}

void update(int x) {
    if (a[x] > deep[x]) {
        b[p[x]] = 1;
        Out[p[x]] = 0;
        In[p[x]] = p[x];
    } else {
        int root = GetK(x, a[x]);
        if ((p[root] - 1) / block != (p[x] - 1) / block) {
            b[p[x]] = 1;
            Out[p[x]] = p[root];
            In[p[x]] = p[x];
        } else {
            b[p[x]] = b[p[root]] + 1;
            Out[p[x]] = Out[p[root]];
            In[p[x]] = p[root];
        }
    }
    x = p[x];
    for (int i = x + 1; i <= n && (i - 1) / block == (x - 1) / block; ++i) {
        if (In[i] != i) {
            b[i] = b[In[i]] + 1;
            Out[i] = Out[In[i]];
        }
    }
}

void Run() {
    read(t);
    while (t--) {
        read(n);
        Init();
        for (int i = 2; i <= n; ++i) {
            read(fa[i][0]);
            G[fa[i][0]].push_back(i);
        }
        DFS(1);
        for (int i = 1; i <= n; ++i) read(a[i]);
        for (int i = 1; i <= n; ++i) {
            int x = fp[i];
            if (a[x] > deep[x]) {
                b[i] = 1;
                Out[i] = 0;
                In[i] = i;
                continue;
            }
            int root = GetK(x, a[x]);
            if ((p[root] - 1) / block != (i - 1) / block) {
                b[i] = 1;
                Out[i] = p[root];
                In[i] = i;
            } else {
                b[i] = b[p[root]] + 1;
                Out[i] = Out[p[root]];
                In[i] = p[root];
            }
        }
        read(q);
        for (int i = 1, op, x, v; i <= q; ++i) {
            read(op);
            read(x);
            if (op == 1)
                print(query(x));
            else {
                read(v);
                a[x] = v;
                update(x);
            }
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("Test.in", "r", stdin);
#endif

    Run();
    return 0;
}

J. Sequence

题意：

求：

F_n = C * F_{n - 2} + D * F_{n - 1} + \lfloor{\frac {p}{n}}\rfloor

思路：

考虑最后一项最多有 \sqrt n 项，按这个值分块矩阵快速幂即可。

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

#define ll long long

const ll MOD = (ll)1e9 + 7;

int t, n;
ll A, B, C, D, P;

ll Biner(ll x) {
    ll l = x, r = n, res = l;
    x = P / x;
    while (r - l >= 0) {
        ll mid = (l + r) >> 1;
        ll tmp = P / mid;
        if (tmp >= x) {
            l = mid + 1;
            res = mid;
        } else
            r = mid - 1;
    }
    return res;
}

struct node {
    ll a[3][3];
    node() {
        memset(a, 0, sizeof a);
    }
    node operator*(const node &r) const {
        node ans = node();
        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < 3; ++j)
                for (int k = 0; k < 3; ++k) ans.a[i][j] = (ans.a[i][j] + a[i][k] * r.a[k][j] % MOD) % MOD;
        return ans;
    }
} base;

node qmod(node base, int n) {
    node res = node();
    res.a[0][0] = B, res.a[0][1] = A;
    res.a[0][2] = 1;
    while (n) {
        if (n & 1)
            res = res * base;
        base = base * base;
        n >>= 1;
    }
    return res;
}

ll work() {
    if (n == 1)
        return A;
    if (n == 2)
        return B;
    int l = 3, r;
    while (l <= n) {
        r = Biner(l);
        base.a[2][0] = P / l;
        node res = qmod(base, r - l + 1);
        B = res.a[0][0], A = res.a[0][1];
        l = r + 1;
    }
    return B;
}

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%lld%lld%lld%lld%lld%d", &A, &B, &C, &D, &P, &n);
        memset(base.a, 0, sizeof base.a);
        base.a[0][0] = D, base.a[1][0] = C, base.a[0][1] = 1;
        base.a[2][2] = 1;
        printf("%lld\n", work());
    }
    return 0;
}

K. Swordsman

题意：

有五种攻击属性，怪物有五种防御属性，所有攻击属性要大于其对应的防御属性便能将其击杀，击杀后有经验加成，求最多杀死多少怪物。

思路：

用 5 个 set 依次维护即可。

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

namespace FastIO {
#define BUF_SIZE 10000005
bool IOerror = false;
inline char NC() {
    static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
    if (p1 == pend) {
        p1 = buf;
        pend = buf + fread(buf, 1, BUF_SIZE, stdin);
        if (pend == p1) {
            IOerror = true;
            return -1;
        }
    }
    return *p1++;
}

inline bool blank(char ch) {
    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}

template <typename T>
inline void read(T &x) {
    char ch;
    while (blank(ch = NC()))
        ;
    if (IOerror) {
        x = -1;
        return;
    }
    bool flag = false;
    if (ch == '-') {
        flag = true;
        ch = NC();
    }
    if (!isdigit(ch))
        while (!isdigit(ch = NC()))
            ;
    for (x = ch - '0'; isdigit(ch = NC()); x = x * 10 + ch - '0')
        ;
    if (flag)
        x *= -1;
}
#undef BUF_SIZE
}  // namespace FastIO
using namespace FastIO;

const int maxn = 1e5 + 10;

struct node {
    int id;
    int v;
    node() {}
    node(int id, int v) : id(id), v(v) {}
    bool operator<(const node &r) const {
        return v > r.v;
    }
};

priority_queue<node> q[10];

int n, k;
int ans[maxn];
int arr[maxn][20];

int main() {
    int t;
    read(t);
    while (t--) {
        read(n), read(k);
        for (int i = 1; i <= k; ++i)
            while (!q[i].empty()) q[i].pop();
        for (int i = 1; i <= k; ++i) read(ans[i]);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= (k * 2); ++j) {
                read(arr[i][j]);
            }
            q[1].push(node(i, arr[i][1]));
        }
        int cnt = 0;
        while (1) {
            bool flag = false;
            for (int i = 1; i <= k; ++i) {
                while (!q[i].empty()) {
                    node tmp = q[i].top();
                    if (tmp.v <= ans[i]) {
                        if (i == k) {
                            cnt++;
                            flag = true;
                            for (int j = 1; j <= k; ++j) ans[j] += arr[tmp.id][j + k];
                        } else {
                            tmp.v = arr[tmp.id][i + 1];
                            q[i + 1].push(tmp);
                        }
                        q[i].pop();
                    } else
                        break;
                }
            }
            if (!flag)
                break;
        }
        printf("%d\n", cnt);
        for (int i = 1; i <= k; ++i) printf("%d%c", ans[i], " \n"[i == k]);
    }
    return 0;
}
Last update: March 29, 2022
Created: March 29, 2022
Back to top