2021牛客寒假算法基础集训营6 题解

2021-04-02 22:03:58


碎碎念

昨天老板找我交代了担任ACM校队总队长的事情,在感到荣誉的同时,我也感受到了身上肩负的责任与面临的压力——南邮ACM校队的总队长已经连续五年是金牌了,然而我目前却连个牌子都没有(留下了铁首的眼泪.jpg)。为了让历史延续下去,抱大腿是不行的,必须好好提升自身的能力。

A,C,D,I

水题不写了。

J-天空之城

开始看到这题还以为要缩点啥的,后来发现路重复走只计算一次贡献,那不就是最小生成树吗?结果因为最近写代码太少,被多测卡了好久,一度怀疑人生...
代码:

#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;
const int maxn = 5e3 + 7;
int n, q, top, fa[maxn];
long long ans;
string s;
struct node
{
    int val;
    string x, y;
    bool operator<(const node &rhs) const { return val > rhs.val; }
};
priority_queue<node> Q;
map<string, int> M;
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
inline void merge(int x, int y, int val)
{
    x = find(x), y = find(y);
    if (x == y) return;
    fa[x] = y;
    n--;
    ans += val;
}
int main()
{
    while (~scanf("%d%d", &n, &q))
    {
        cin >> s;
        M.clear();
        ans = top = 0;
        for (int i = 1; i <= n; ++i) fa[i] = i;
        string a, b;
        for (int val; q--;) cin >> a >> b >> val, Q.push((node){val, a, b});
        while (!Q.empty())
        {
            node x = Q.top();
            Q.pop();
            if (!M.count(x.x)) M[x.x] = ++top;
            if (!M.count(x.y)) M[x.y] = ++top;
            merge(M[x.x], M[x.y], x.val);
        }
        if (n > 1)
            puts("No!");
        else
            printf("%lld\n", ans);
    }
}

G-机器人

这题乍一看,不就是个贪心水题吗?
根据贪心的证明来得到排序规则:
假设答案第 $i$ 和第 $j$ 个机器前后相邻,属性分别为$a_i,b_i,a_j,b_j$,那么将他们俩的顺序交换应该会使答案变小,可得:$$ \begin{aligned} a_j\times (a_i\times x+b_i)+b_j&>a_i\times (a_j\times x+b_j)+b_i\\ a_ia_jx+a_jb_i+b_j&>a_ia_jx+a_ib_j+b_i\\ (a_j-1)\times b_i&>(a_i-1)\times b_j \end{aligned} $$ 得到排序条件 $(a_j-1)\times b_i>(a_i-1)\times b_j$。
结果写完发现 $n$ 竟然只有 $20$,一度怀疑是不是没那么简单,又写了一下最终结果的式子:$$ ans = \prod_{i=1}^n{a_i\cdot x}+\sum_{i=1}^n\left(\prod_{j=i_1}^na_j\right)\cdot b_i $$ 简单证明发现确实是贪心...
然后意识到原来 $n=20$ 是考虑到了高精度的速度(不过100也跑的出来吧?),套个高精度板子即可:

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100;
int n, x;
struct node
{
    int a, b;
    bool operator<(const node &rhs) const { return (a - 1) * rhs.b < (rhs.a - 1) * b; }
} r[maxn];
struct hll
{
    int v[maxn], len;
    hll()
    {
        v[1] = 0; // memset(v,0,sizeof(v));
        len = 1;
    }
    hll(char *ss) { *this = ss; }
    hll(long long t) { *this = t; }
    hll(int t) { *this = t; }
    hll &operator=(const char *ss)
    {
        len = strlen(ss);
        for (int i = 0; i < len; i++) v[len - i] = ss[i] - 48;
        return *this;
    }
    hll &operator=(const long long &t)
    {
        len = 1;
        if (t == 0)
        {
            v[len] = 0;
            return *this;
        }
        long long ss = t;
        while (ss)
        {
            v[len++] = ss % 10;
            ss /= 10;
        }
        len--;
        return *this;
    }
    hll &operator=(const int &t)
    {
        len = 1;
        if (t == 0)
        {
            v[len] = 0;
            return *this;
        }
        int ss = t;
        while (ss)
        {
            v[len++] = ss % 10;
            ss /= 10;
        }
        len--;
        return *this;
    }
    hll &operator=(const hll &t)
    {
        len = t.len;
        for (int i = 1; i <= len; i++) v[i] = t.v[i];
        return *this;
    }
    inline bool operator==(const hll &t)
    {
        if (t.len > len || len > t.len) return 0;
        for (int i = 1; i <= len; i++)
            if (v[i] != t.v[i]) return 0;
        return 1;
    }
    inline bool operator<(const hll &rhs) const
    {
        if (rhs.len > len) return 1;
        if (rhs.len < len) return 0;
        for (int i = len; i > 0; i--)
        {
            if (v[i] < rhs.v[i]) return 1;
            if (v[i] > rhs.v[i]) return 0;
        }
        return 0;
    }
    hll operator+(const hll &t)
    {
        hll ans;
        ans.len = max(t.len, len);
        for (int i = 1; i <= ans.len + 1; i++) ans.v[i] = 0;
        for (int i = 1; i <= ans.len; i++)
        {
            if (i <= len && i <= t.len)
                ans.v[i] += v[i] + t.v[i];
            else if (i > len)
                ans.v[i] += t.v[i];
            else
                ans.v[i] += v[i];
            if (ans.v[i] >= 10) ans.v[i + 1]++, ans.v[i] -= 10;
        }
        if (ans.v[ans.len + 1]) ans.len++;
        return ans;
    }
    hll operator*(const hll &t)
    {
        hll ans;
        ans.len = len + t.len;
        for (int i = 1; i <= ans.len; i++) ans.v[i] = 0;
        for (int i = 1; i <= len; i++)
            for (int j = 1; j <= t.len; j++)
            {
                ans.v[i + j - 1] += v[i] * t.v[j];
                if (ans.v[i + j - 1] >= 10)
                {
                    ans.v[i + j] += ans.v[i + j - 1] / 10;
                    ans.v[i + j - 1] %= 10;
                }
            }
        while (ans.v[ans.len] >= 10) ans.v[ans.len + 1] = ans.v[ans.len] / 10, ans.v[ans.len] %= 10, ans.len++;
        while (ans.v[ans.len] == 0 && ans.len > 1) ans.len--;
        return ans;
    }
    hll operator/(const long long &t)
    {
        hll tmp = *this, ans;
        ans.len = len;
        for (int i = 1; i <= ans.len; i++) ans.v[i] = 0;
        for (int i = len; i > 0; i--)
        {
            if (tmp.v[i] < t)
                tmp.v[i - 1] += (tmp.v[i] << 1) + (tmp.v[i] << 3);
            else
            {
                ans.v[i] = tmp.v[i] / t;
                tmp.v[i] %= t;
                tmp.v[i - 1] += (tmp.v[i] << 1) + (tmp.v[i] << 3);
            }
        }
        while (ans.v[ans.len] == 0 && ans.len > 1) ans.len--;
        return ans;
    }
    inline void print()
    {
        for (int i = len; i > 0; i--) putchar(v[i] + 48);
    }
} ans;

int main()
{
    scanf("%d%d", &n, &x);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &r[i].a, &r[i].b);
    ans = x;
    sort(r + 1, r + n + 1);
    for (int i = 1; i <= n; ++i) ans = ((hll)r[i].a) * ans + (hll)r[i].b;
    ans.print();
    return 0;
}

F-组合数问题

这题就比较妙妙了,证明用到了复数,技巧性很强。