2018 中国大学生程序设计竞赛

Contents

A. Buy and Resell
B. Congruence equation
C. Dream
D. Find Integer
E. GuGu Convolution
F. Neko and Inu
G. Neko's loop
H. Search for Answer
I. Tree and Permutation
J. YJJ's Salesman

A. Buy and Resell

题意：

给出 $n$ 个交易点，每次能够选择买或者卖，求获得最大利润。

思路：

维护两个优先队列，一个是卖，一个是替换，当价格差相同时，优先替换，因为次数要最少。

Code

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

#define ll long long
#define N 100010

int t, n;
ll arr[N];
priority_queue<ll, vector<ll>, greater<ll> > q[2];

inline void Run() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%lld", arr + i);
        for (int i = 0; i < 2; ++i)
            while (!q[i].empty()) q[i].pop();
        ll ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (q[0].empty() && q[1].empty())
                q[0].emplace(arr[i]);
            else if (q[1].empty()) {
                ll top = q[0].top();
                if (arr[i] > top) {
                    q[0].pop();
                    ans += arr[i] - top;
                    q[1].emplace(arr[i]);
                } else
                    q[0].emplace(arr[i]);
            } else if (q[0].empty()) {
                ll top = q[1].top();
                if (arr[i] > top) {
                    q[1].pop();
                    ans += arr[i] - top;
                    q[0].emplace(top);
                    q[1].emplace(arr[i]);
                } else {
                    q[0].emplace(arr[i]);
                }
            } else {
                ll top1 = q[0].top(), top2 = q[1].top();
                if (top1 < top2) {
                    if (arr[i] > top1) {
                        q[0].pop();
                        ans += arr[i] - top1;
                        q[1].emplace(arr[i]);
                    } else {
                        q[0].emplace(arr[i]);
                    }
                } else {
                    if (arr[i] > top2) {
                        q[1].pop();
                        ans += arr[i] - top2;
                        q[0].emplace(top2);
                        q[1].emplace(arr[i]);
                    } else {
                        q[0].emplace(arr[i]);
                    }
                }
            }
        }
        printf("%lld %d\n", ans, q[1].size() * 2);
    }
}

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

    Run();

    return 0;
}

B. Congruence equation

留坑。

C. Dream

题意：

给出一个 $p$ ，重定义加法和乘法，使得：

(m + n)^p = m^p + n^p

思路：

有费马小定理： $a^p \equiv a \pmod p$ 。

那只需要重定义：

\begin{eqnarray*} (m + n) &=& (m + n) \pmod p \\ (m \cdot n) &=& (m \cdot n) \pmod p \end{eqnarray*}

原根可以保证两个集合相等。

Code

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

#define ll long long
#define N 2010

int t, p;
int a[N][N], b[N][N];

inline void Run() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &p);
        for (int i = 0; i < p; ++i) {
            for (int j = 0; j < p; ++j) {
                a[i][j] = (i + j) % p;
                b[i][j] = (i * j) % p;
            }
        }
        for (int i = 0; i < p; ++i) {
            for (int j = 0; j < p; ++j) {
                printf("%d%c", a[i][j], " \n"[j == p - 1]);
            }
        }
        for (int i = 0; i < p; ++i) {
            for (int j = 0; j < p; ++j) {
                printf("%d%c", b[i][j], " \n"[j == p - 1]);
            }
        }
    }
}

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

    Run();

    return 0;
}

D. Find Integer

题意：

给出一个 $n$ 和一个 $a$ 。

找出：

a^n + b^n = c^n

思路：

根据费马大定理 $n \gt 2$ 无解。
显然 $n = 0$ 无解。
$n = 1$ ，直接凑。

$n = 2$ ：

如果是奇数，有 $\displaystyle a^2 + (\frac{a \cdot a}{2})^2 = (\frac{(a \cdot a) + 1}{2}) ^2$ 。
如果是偶数，一直除下去，直到是奇数，然后把多余的偶数加到 $b$ 和 $c$ 上去。

或者：

Code

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

#define ll long long
#define INF 0x3f3f3f3f
#define N 40010

int t;
ll n, a, cnt;

ll arr[N][2];

inline void Run() {
    for (int i = 3; i <= 40000; ++i) {
        cnt = 1;
        ll a = i;
        while ((a & 1) == 0 && a > 4) {
            cnt <<= 1;
            a >>= 1;
        }
        if (a == 4) {
            arr[i][0] = cnt * 3, arr[i][1] = cnt * 4;
        } else {
            ll b = a * a / 2;
            ll c = b + 1;
            arr[i][0] = b * cnt;
            arr[i][1] = c * cnt;
        }
    }
    scanf("%d", &t);
    while (t--) {
        scanf("%lld%lld", &n, &a);
        if (n == 0 || n >= 3) {
            puts("-1 -1");
            continue;
        }
        if (n == 1) {
            printf("1 %lld\n", a + 1);
            continue;
        }
        printf("%lld %lld\n", arr[a][0], arr[a][1]);
    }
}

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

    Run();

    return 0;
}

E. GuGu Convolution

留坑。

F. Neko and Inu

留坑。

G. Neko's loop

题意：

给出一个长度为 $n$ 的数列，每个位置都有自己的权值，你有 $m$ 点能量，每次可以从 $i$ 走到 $(i+k) \bmod n$ 点，可以在任意时刻停止，为达到 $s$ 点能量，需要起始能量为多少。

思路：

可以通过 $\mathcal{O}(n)$ 的时间处理出循环节。

对于每个循环节，我们可以走完循环节或者不走完。

对于不走完这部分的步数可能为 $m \bmod \mbox{循环节长度}循环节长度$ ，也可能为 $m$ 或者循环节长度。

问题就转换为长度不超过限制长度的最大连续子序列，通过 dp + 单调队列来解决。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 10;

int n, m, k;
ll s, ans, val[maxn];
vector<ll> vec;
bool vis[maxn];
ll sum[maxn << 1];
ll que[maxn << 1];

inline ll cal(int count) {
    int len = vec.size();
    for (int i = 0; i < len; ++i) {
        que[i] = que[i + len] = vec[i];
    }
    len <<= 1;
    list<ll> q;
    int st = 0;
    int ed = 0;
    ll res = 0;
    for (int i = 0; i < len; ++i) {
        if (i == 0) {
            sum[i] = que[i];
        } else {
            sum[i] = sum[i - 1] + que[i];
        }
    }
    for (int i = 0; i < len; ++i) {
        while (!q.empty() && sum[q.front()] > sum[i]) {
            q.pop_front();
        }
        q.push_front(i);
        while (!q.empty() && i - q.back() > count) {
            q.pop_back();
        }
        res = max(res, sum[i] - sum[q.back()]);
    }
    return res;
}

inline ll solve() {
    ll mod = m % vec.size();
    ll circle = m / vec.size();
    ll sum = 0;
    for (auto it : vec) {
        sum += it;
    }
    ll max1 = cal(mod);
    ll max2 = cal(vec.size());
    max1 += max(0ll, sum) * circle;
    max2 += max(0LL, sum) * ((circle > 2) ? circle - 1 : 0);
    return max(max1, max2);
}

inline void RUN() {
    int t;
    scanf("%d", &t);
    for (int cas = 1; cas <= t; ++cas) {
        memset(vis, false, sizeof vis);
        scanf("%d %lld %d %d", &n, &s, &m, &k);
        for (int i = 0; i < n; ++i) {
            scanf("%lld", val + i);
        }
        ans = 0;
        for (int i = 0; i < n; ++i) {
            if (!vis[i]) {
                vec.clear();
                vis[i] = true;
                vec.push_back(val[i]);
                for (int j = (i + k) % n; j != i && !vis[j]; j = (j + k) % n) {
                    vis[j] = true;
                    vec.push_back(val[j]);
                }
                ans = max(ans, solve());
            }
        }
        if (ans >= s)
            ans = 0;
        else
            ans = s - ans;
        printf("Case #%d: %lld\n", cas, 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;
}

H. Search for Answer

留坑。

I. Tree and Permutation

题意：

一个序列的值为第一个点走到后面 $n-1$ 个点的距离和，求 $n!$ 个序列的和。

思路：

对于每条边，这条边的左右端点均要走向对方。

那么对于每条边的经过的次数为左右端点节点数的乘积。但是每个点都作为起点 $(n-1)!$ 次，求和即可得到答案。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int MOD = (int)1e9 + 7;
const int maxn = (int)1e5 + 10;

struct Edge {
    int u, v;
    ll w;
    inline Edge() {}
    inline Edge(int u, int v, ll w) : u(u), v(v), w(w) {}
};

int n;
ll ans;
int son[maxn];
vector<Edge> G[maxn];

inline void Init() {
    ans = 0;
    memset(son, 0, sizeof son);
    for (int i = 1; i <= n; ++i) {
        G[i].clear();
    }
}

inline void DFS(int u, int pre) {
    son[u] = 1;
    for (auto it : G[u]) {
        int v = it.v;
        if (v == pre)
            continue;
        DFS(v, u);
        son[u] += son[v];
        ans = (ans + (ll)son[v] * (n - son[v]) % MOD * it.w) % MOD;
    }
}

inline void RUN() {
    while (~scanf("%d", &n)) {
        Init();
        for (int i = 1; i < n; ++i) {
            int u, v;
            ll w;
            scanf("%d %d %lld", &u, &v, &w);
            G[u].push_back(Edge(u, v, w));
            G[v].push_back(Edge(v, u, w));
        }
        DFS(1, -1);
        for (int i = 1; i <= n - 1; ++i) {
            ans = (ans * i) % MOD;
        }
        ans = (ans * 2) % MOD;
        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;
}

J. YJJ's Salesman

题意：

给出若干个点，范围属于 $(0, 0) - (10^9, 10^9)$ 。

从 $(0, 0)$ 走到 $(10^9, 10^9)$ ，只能向上走，向右走，或者右上角走，有些点有权值，不能回头，求最后获得的最大权值。

思路：

最大上升子序列的权值和，先按 $x$ 排序，再对 $y$ 离散化，线段树优化。

Code

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

#define N 100010

int t, n, m;
int tmp[N];

struct Data {
    int x, y, v;
    inline void scan() {
        scanf("%d%d%d", &x, &y, &v);
    }
    inline bool operator<(const Data &r) const {
        return x < r.x || x == r.x && y < r.y;
    }
} arr[N];

inline void Init() {
    for (int i = 1; i <= n; ++i) tmp[i] = arr[i].y;
    sort(tmp + 1, tmp + 1 + n);
    m = unique(tmp + 1, tmp + 1 + n) - tmp - 1;
}

inline int Get(int x) {
    return lower_bound(tmp + 1, tmp + 1 + m, x) - tmp;
}

struct node {
    int l, r;
    int Max;
    inline node() {}
    inline node(int l, int r, int Max) : l(l), r(r), Max(Max) {}
} tree[N << 2];

inline void pushup(int id) {
    tree[id].Max = max(tree[id << 1].Max, tree[id << 1 | 1].Max);
}

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

inline void update(int id, int pos, int val) {
    if (tree[id].l == tree[id].r) {
        tree[id].Max = max(tree[id].Max, val);
        return;
    }
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (pos <= mid)
        update(id << 1, pos, val);
    else
        update(id << 1 | 1, pos, val);
    pushup(id);
}

int ansMax;

inline void query(int id, int l, int r) {
    if (l > r)
        return;
    if (tree[id].l >= l && tree[id].r <= r) {
        ansMax = max(ansMax, tree[id].Max);
        return;
    }
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (l <= mid)
        query(id << 1, l, r);
    if (r > mid)
        query(id << 1 | 1, l, r);
}

inline void Run() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) arr[i].scan();
        sort(arr + 1, arr + 1 + n);
        Init();
        build(1, 1, n);
        for (int i = 1; i <= n; ++i) arr[i].y = Get(arr[i].y);
        vector<int> v;
        int ans = arr[1].v;
        v.push_back(1);
        for (int i = 2; i <= n; ++i) {
            if (arr[i].x != arr[i - 1].x) {
                for (auto it : v) {
                    update(1, arr[it].y, arr[it].v);
                }
                v.clear();
            }
            ansMax = 0;
            query(1, 1, arr[i].y - 1);
            ans = max(ans, ansMax + arr[i].v);
            // printf("%d %d %d\n", i, ansMax, arr[i].v);
            arr[i].v += ansMax;
            v.push_back(i);
        }
        printf("%d\n", ans);
    }
}

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

    Run();

    return 0;
}

Last update: March 30, 2022
Created: March 30, 2022