Skip to content

2018 Multi-University Training Contest 10

Contents

Problem A.Alkane

留坑。

Problem B. Beads

留坑。

Problem C. Calculate

留坑。

Problem D. Permutation

留坑。

Problem E. TeaTree

题意：

每个点会存下任意两个以他为 LCA 的点对的 GCD，求每个点存的 GCD 的最大值。

思路：

DSU on tree。

用 set 维护子树中的因子，对于重儿子不要处理多次。

每次查找的时候，枚举轻儿子中的因子。

还有一种线段树合并的写法。

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

#define N 100010

int n;
vector<int> G[N], num[N];
set<int> s;
int sz[N], son[N], cnt[N], cnt2[N], arr[N], ans[N], Max;
bool isbig[N];

void Init() {
    for (int i = 1; i <= 100000; ++i) {
        int limit = sqrt(i);
        for (int j = 1; j < limit; ++j)
            if (i % j == 0) {
                num[i].push_back(j);
                num[i].push_back(i / j);
            }
        if (i % limit == 0) {
            num[i].push_back(limit);
            if (limit * limit != i)
                num[i].push_back(i / limit);
        }
    }
}

void DFS(int u) {
    sz[u] = 1;
    for (auto v : G[u]) {
        DFS(v);
        sz[u] += sz[v];
        if (son[u] == -1 || sz[v] > sz[son[u]])
            son[u] = v;
    }
}

void update(int u) {
    for (auto it : num[arr[u]]) ++cnt[it];
    for (auto v : G[u])
        if (!isbig[v])
            update(v);
}

void work(int u, int fa) {
    for (auto it : num[arr[u]]) s.insert(it);
    for (auto v : G[u])
        if (!isbig[v])
            work(v, fa);
}

void query(int u) {
    for (auto v : G[u])
        if (!isbig[v]) {
            s.clear();
            work(v, u);
            for (auto it : s)
                if (cnt[it] >= 1 || cnt2[it] >= 1)
                    Max = max(Max, it);
            for (auto it : s) ++cnt2[it];
        }
    for (auto it : num[arr[u]])
        if (cnt[it] >= 1 || cnt2[it] >= 1)
            Max = max(Max, it);
}

void clear(int u) {
    for (auto it : num[arr[u]]) cnt[it] = cnt2[it] = 0;
    for (auto v : G[u]) clear(v);
}

void DSU(int u) {
    for (auto v : G[u])
        if (v != son[u])
            DSU(v);
    if (son[u] != -1) {
        isbig[son[u]] = 1;
        DSU(son[u]);
    }
    Max = -1;
    query(u);
    ans[u] = Max;
    if (isbig[u])
        update(u);
    if (son[u] != -1)
        isbig[son[u]] = 0;
    if (!isbig[u])
        clear(u);
}

int main() {
    Init();
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) G[i].clear();
        memset(son, -1, sizeof son);
        memset(cnt, 0, sizeof cnt);
        memset(cnt2, 0, sizeof cnt2);
        Max = -1;
        s.clear();
        for (int i = 2, u; i <= n; ++i) {
            scanf("%d", &u);
            G[u].push_back(i);
        }
        for (int i = 1; i <= n; ++i) scanf("%d", arr + i);
        DFS(1);
        DSU(1);
        for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    }
    return 0;
}
Code 
#include <bits/stdc++.h>
using namespace std;

#define N 100010
vector<int> num[N], G[N];

int n;
int arr[N], rt[N], ans[N];

void Init() {
    for (int i = 1; i <= 100000; ++i)
        for (int j = i; j <= 100000; j += i) num[j].push_back(i);
}

struct SEG {
#define M N * 400
    int lson[M], rson[M], c[M], cnt;
    void init() {
        cnt = 0;
    }
    void pushup(int id) {
        c[id] = max(c[lson[id]], c[rson[id]]);
    }
    void update(int &x, int l, int r, int pos) {
        if (!x)
            x = ++cnt;
        if (l == r) {
            c[x] = pos;
            return;
        }
        int mid = (l + r) >> 1;
        pos <= mid ? update(lson[x], l, mid, pos) : update(rson[x], mid + 1, r, pos);
        pushup(x);
    }
    int merge(int u, int v, int &sum) {
        if (!u || !v)
            return u | v;
        if (c[u] == c[v])
            sum = max(sum, c[u]);
        if (lson[u] | lson[v])
            lson[u] = merge(lson[u], lson[v], sum);
        if (rson[u] | rson[v])
            rson[u] = merge(rson[u], rson[v], sum);
        return u;
    }
} seg;

void DFS(int u) {
    ans[u] = -1;
    for (auto v : G[u]) {
        DFS(v);
        seg.merge(rt[u], rt[v], ans[u]);
    }
}

void Run() {
    Init();
    while (scanf("%d", &n) != EOF) {
        seg.init();
        for (int i = 2, u; i <= n; ++i) {
            scanf("%d", &u);
            G[u].push_back(i);
        }
        for (int i = 1; i <= n; ++i) scanf("%d", arr + i);
        for (int i = 1; i <= n; ++i)
            for (auto it : num[arr[i]]) seg.update(rt[i], 1, 100000, it);
        DFS(1);
        for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    }
}

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

    Run();
    return 0;
}

Problem F. NewNippori

留坑。

Problem G. Cyclic

打表找规律即可。

F[n] = (n - 2) * F[n - 1] + (n - 1) * F[n - 2] + (i \& 1 ? 1 : -1)
Code 
#include <bits/stdc++.h>
using namespace std;

#define N 100010
#define ll long long

const ll MOD = 998244353;

ll arr[N];

int main() {
    arr[4] = 1, arr[5] = 8;
    for (int i = 6; i <= 100000; ++i)
        arr[i] = ((i - 2) * arr[i - 1] % MOD + (i - 1) * arr[i - 2] % MOD + ((i & 1) ? 1 : -1) + MOD) % MOD;
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        printf("%lld\n", arr[n]);
    }
}

Problem H. Pow

水。

Code 
import java.util.Scanner;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- != 0) {
            int n = in.nextInt();
            System.out.println(BigInteger.valueOf(2).pow(n));
        }
    }
}

Problem I. Count

题意：

求：

\sum_{i = 1} ^ {i = n} \sum_{j = 1} ^ {j = i - 1} [gcd(i + j, i - j) == 1]

思路：

找规律。

如果是奇数就加上 \frac {\varphi(n)}{2}，否则加上 \varphi(n)。

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

using namespace std;

typedef long long ll;
const int MAXN = 20000000;
bool check[MAXN + 10];

ll ans[MAXN + 10];
int phi[MAXN + 10];
int prime[MAXN + 10];
int tot;

void phi_ans_prime_table() {
    memset(check, false, sizeof check);
    phi[1] = 1;
    tot = 0;
    for (int i = 2; i <= MAXN; ++i) {
        if (!check[i]) {
            prime[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < tot; ++j) {
            if (i * prime[j] > MAXN)
                break;
            check[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
        }
        if (i & 1)
            ans[i] = ans[i - 1] + phi[i] / 2;
        else
            ans[i] = ans[i - 1] + phi[i];
    }
}

int main() {
    phi_ans_prime_table();
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        printf("%lld\n", ans[n]);
    }
    return 0;
}

Problem J. CSGO

题意：

有 n 把主武器和 m 把副武器，每把武器有 k 种属性，选取一把主武器和副武器，求题中式子最大值。

思路：

对于每种属性又有加减两种状态，枚举每把武器的每种属性的加减状态，求最大值。

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

using namespace std;

typedef long long ll;

const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5 + 10;

ll arr[maxn][10], brr[maxn][10];
ll crr[maxn];

int n, m, k;

void RUN() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d %d", &n, &m, &k);
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j <= k; ++j) scanf("%lld", &arr[i][j]);
        for (int i = 1; i <= m; ++i)
            for (int j = 0; j <= k; ++j) scanf("%lld", &brr[i][j]);
        memset(crr, 0, sizeof crr);
        ll ans = 0;
        int limit = (1 << k);
        for (int i = 1; i <= n; ++i) {
            for (int S = 0; S < limit; ++S) {
                ll tmp = arr[i][0];
                for (int j = 0; j < k; ++j) {
                    if (S & (1 << j)) {
                        tmp += arr[i][j + 1];
                    } else {
                        tmp -= arr[i][j + 1];
                    }
                }
                crr[S] = max(crr[S], tmp);
            }
        }

        for (int i = 1; i <= m; ++i) {
            for (int S = 0; S < limit; ++S) {
                ll tmp = brr[i][0];
                for (int j = 0; j < k; ++j) {
                    if (S & (1 << j)) {
                        tmp += brr[i][j + 1];
                    } else {
                        tmp -= brr[i][j + 1];
                    }
                }
                ans = max(ans, tmp + crr[limit - 1 - S]);
            }
        }
        printf("%lld\n", ans);
    }
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("Text.txt", "r", stdin);
#endif  // LOCAL_JUDGE

    RUN();

#ifdef LOCAL_JUDGE
    fclose(stdin);
#endif  // LOCAL_JUDGE
    return 0;
}
Code 
#include <bits/stdc++.h>
using namespace std;

#define N 100010
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f

int t, n, m, K;

struct node {
    int x[10];
    void scan(int vis) {
        scanf("%d", x + vis);
        for (int i = 2; i <= K + 1; ++i) scanf("%d", x + i);
    }
} a[N], b[N];

void Run() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &K);
        for (int i = 1; i <= n; ++i) a[i].scan(0);
        for (int i = 1; i <= m; ++i) b[i].scan(1);
        ll res = 0;
        for (int i = 0; i < (1 << (K + 2)); ++i) {
            bitset<7> bit;
            bit = i;
            ll Max[2] = {-INF, -INF};
            ll Min[2] = {INF, INF};
            for (int j = 1; j <= n; ++j) {
                ll tmp = 0;
                for (int k = 0; k <= K + 1; ++k) tmp += a[j].x[k] * (bit[k] ? 1 : -1);
                Max[0] = max(Max[0], tmp);
                Min[0] = min(Min[0], tmp);
            }
            for (int j = 1; j <= m; ++j) {
                ll tmp = 0;
                for (int k = 0; k <= K + 1; ++k) tmp += b[j].x[k] * (bit[k] ? 1 : -1);
                Max[1] = max(Max[1], tmp);
                Min[1] = min(Min[1], tmp);
            }
            res = max(res, max(Max[0] - Min[1], Max[1] - Min[0]));
        }
        printf("%lld\n", res);
    }
}

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

    Run();
    return 0;
}

Problem K. Pow2

留坑。

Problem L.Videos

题意：

每天有 n 个小时，有 m 部电影，k 个人。

每部电影只能被一个人看，得到 w 快乐值。

电影种类有 A,B 两种，同一人连着看同种电影要减去 W 快乐值，如何安排使得快乐值最大。

思路：

将一部电影拆成两个点 S 和 T 流为 1，费用为 -w。

电影与电影之间如果是可以连着看的，就连边，如果是同种类，费用就是 W, 否则就是 0，流为 1。

源点连出来加一个点，流量为 k，限制为 k 个人。

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

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 10;
const int maxm = 1e5 + 10;

struct Edge {
    int to, nxt, cap, flow, cost;
} edge[maxm];

int head[maxn], tot;
int pre[maxn], dis[maxn];
bool vis[maxn];
int N;

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

void addedge(int u, int v, int cap, int cost) {
    edge[tot].to = v;
    edge[tot].cap = cap;
    edge[tot].cost = cost;
    edge[tot].flow = 0;
    edge[tot].nxt = head[u];
    head[u] = tot++;

    edge[tot].to = u;
    edge[tot].cap = 0;
    edge[tot].cost = -cost;
    edge[tot].flow = 0;
    edge[tot].nxt = head[v];
    head[v] = tot++;
}

bool SPFA(int s, int t) {
    queue<int> q;
    for (int i = 0; i < N; ++i) dis[i] = INF, pre[i] = -1, vis[i] = false;
    dis[s] = 0;
    vis[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    if (pre[t] == -1)
        return false;
    else
        return true;
}

int minCostMaxflow(int s, int t, int &cost) {
    int flow = 0;
    cost = 0;
    while (SPFA(s, t)) {
        int Min = INF;
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
            if (Min > edge[i].cap - edge[i].flow) {
                Min = edge[i].cap - edge[i].flow;
            }
        }
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
            edge[i].flow += Min;
            edge[i ^ 1].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
    return flow;
}

struct node {
    int si, ti, wi, op;
} arr[maxn];

int n, m, K, W;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d %d %d", &n, &m, &K, &W);
        for (int i = 1; i <= m; ++i) scanf("%d %d %d %d", &arr[i].si, &arr[i].ti, &arr[i].wi, &arr[i].op);
        Init(2 * m + 3);
        addedge(0, 2 * m + 1, K, 0);
        for (int i = 1; i <= m; ++i) addedge(2 * m + 1, 2 * i - 1, 1, 0);
        for (int i = 1; i <= m; ++i) addedge(2 * i - 1, 2 * i, 1, -arr[i].wi);
        for (int i = 1; i <= m; ++i) addedge(2 * i, 2 * m + 2, 1, 0);
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (i == j)
                    continue;
                if (arr[i].ti <= arr[j].si) {
                    if (arr[i].op == arr[j].op) {
                        addedge(2 * i, 2 * j - 1, 1, W);
                    } else {
                        addedge(2 * i, 2 * j - 1, 1, 0);
                    }
                }
            }
        }
        int cost = 0;
        minCostMaxflow(0, 2 * m + 2, cost);
        printf("%d\n", -cost);
    }
    return 0;
}
Last update: March 29, 2022
Created: March 29, 2022
Back to top