2020-08-11 17:06 门头沟学院 Java

关注

2020牛客暑期多校训练营（第九场）

A.Groundhog and 2-Power Representation

题意：

要求计算给定的式子的值

题解：

将式子中的"("替换成"**("用python的eval()函数即可

print(eval(input().replace('(','**(')))

B.Groundhog and Apple Tree

题意：

现在有一棵树，你要从 $1$ 开始跳一遍所有的点并且每条边只能走两次，再回到 $1$ ，每条边都有一个边权，你走过这条边会先消耗 $w_i$ 点HP，每个点都有一个果子，吃掉这个果子会上升 $a_i$ 点HP，你在任何时候的HP不能小于 $0$ .并且你如果休息一秒钟会恢复 $1$ 点HP。问你最少要休息多少时间才能走完这棵树。

题解：

观察题目意思，我们发现遍历整棵树其实就是从根节点出发遍历每一个子树，最后回到根节点，对于根节点的每个子树其实是一样的，没有后效性，就可以用动态规划来做

优先走能加HP的节点
在都能加HP的节点中优先去能加HP多的节点
在要消耗HP的节点总优先去T(最短时间)+HP大的节点
再去减HP的节点

所以我们只要排一下序再按以上策略跑树形dp $dp[u].first$ 表示 $u$ 节点及其子树所需的HP， $dp[u].second$ 表示 $u$ 节点及其子树所能增加的HP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int maxn = 1e6 + 5;
pll dp[maxn];
bool cmp(pll x, pll y)
{
    if (x.second >= x.first)
    {
        if (y.second < y.first)
            return true;
        return x.first < y.first;
    }
    else
    {
        if (y.second >= y.first)
            return false;
        return x.second > y.second;
    }
}
vector<pll> G[maxn];
int a[maxn], n;
void dfs(int u, int fa)
{
    vector<pll> tor;
    for (auto i : G[u])
    {
        ll v = i.first, dis = i.second;
        if (v == fa)
            continue;
        dfs(v, u);
        dp[v] = {dp[v].first + dis, dp[v].second - dis};
        if (dp[v].second < 0)
            dp[v] = {dp[v].first - dp[v].second, 0};
        tor.push_back(dp[v]);
    }
    sort(tor.begin(), tor.end(), cmp);
    ll mn = a[u], now = a[u];
    for (int i = 0; i < tor.size(); i++)
    {
        pair<ll, ll> v = tor[i];
        mn = min(mn, now - v.first);
        now += v.second - v.first;
    }
    if (mn >= 0)
        dp[u] = {0, now};
    else
        dp[u] = {-mn, now - mn};
}
int main()
{
    int t;

    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            G[i].clear();
        }
        for (int i = 1; i < n; i++)
        {
            ll u, v, dis;
            scanf("%lld%lld%lld", &u, &v, &dis);
            G[u].push_back(make_pair(v, dis));
            G[v].push_back(make_pair(u, dis));
        }
        dfs(1, -1);
        printf("%lld\n", dp[1].first);
    }
}

E.Groundhog Chasing Death

题意：

求 $\prod_{i=a}^{b}\coprod_{j=c}^{d}gcd(x^{i},y^{j})$

题解：

将 $x$ 和 $y$ 分解质因数，可以发现最终对答案有贡献的就是那些公共的质因子，因此枚举每种公共的质因子。计算 $gcd(x^{i},y^{j})$ 肯定不可能一一枚举，但是可以发现对于固定的 $x^{i},gcd(x^{i},y^{j}),c \leq j \leq d$ 是可求的

当 $x^{i} < y^{c}$ 时，即 $c \leq j \leq d$ 的 $gcd$ 均为 $x^i$
当 $x%{i} > y^{d}$ 时，即 $c \leq j \leq d$ 的 $gcd$ 均为 $y^j$
当 $y^{c} \leq x^{i} \leq y^{d}$ 时，即 $c \leq j \leq \frac{x^{i}}{y}$ 的 $gcd$ 为 $y^{j}$ ， $\frac{x^{i}}{y} \leq j \leq d$ 的 $gcd$ 为 $x^{i}$

要注意的是这题有点卡常，因此对每个质因子求一次快速幂，而不是对每个质因子的每个 $a \leq i \leq b$ 求，因此对于 $a \leq i \leq b$ 的贡献累加可能会超long long,需要用到费马小定理对每次的结果 $\% (mod-1)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const ll mod = 998244353;
map<ll, ll> num1;
map<ll, ll> num2;
ll ksm(ll a, ll b, ll mod)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll get(ll x, ll y)
{
    return (x + y) * (y - x + 1) / 2;
}
int main()
{
    ll a, b, c, d, x, y;
    scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &x, &y);
    for (ll i = 2; i * i <= x; i++)
        if (x % i == 0)
            while (x % i == 0)
            {
                num1[i]++;
                x /= i;
            }
    if (x > 1)
        num1[x]++;
    for (int i = 2; i * i <= y; i++)
        if (y % i == 0)
            while (y % i == 0)
            {
                num2[i]++;
                y /= i;
            }
    if (y > 1)
        num2[y]++;
    ll res = 1;
    for (auto i : num1)
    {
        if (num2.count(i.first) != 0)
        {
            ll k = i.first, k1 = i.second, k2 = num2[i.first];
            ll sum = 0;
            for (ll j = a; j <= b; j++)
            {
                if (j * k1 < c * k2)
                    sum += (d - c + 1) * j * k1;
                else if (j * k1 > d * k2)
                    sum += get(c, d) * k2;
                else
                    sum += get(c, j * k1 / k2) * k2 + j * k1 * (d - j * k1 / k2);
                sum %= (mod - 1);
            }
            res = res * ksm(k, sum, mod) % mod;
        }
    }
    printf("%lld\n", res);
}

F.Groundhog Looking Dowdy

题意：

给定 $n$ 天，每天有 $k_i$ 件衣服，每件衣服都有个值，现在要求从这 $n$ 天中选出 $m$ 天，每一天都选出一件衣服，询问这 $m$ 件衣服最大值减最小值的差最小

题解：

将所有的衣服按值从小到大进行排序，用尺取的方法计算每个有 $m$ 种不同天衣服的极差，更新极差的最小值即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
vector<pair<int, int>> vec;
unordered_map<int, int> mp;
int main()
{
    int n, m;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int k;
        scanf("%lld", &k);
        for (int j = 1; j <= k; j++)
        {
            int x;
            scanf("%d", &x);
            vec.push_back({x, i});
        }
    }
    sort(vec.begin(), vec.end());
    int num = 0;
    int ans = 0x3f3f3f3f;
    int head = 0;
    for (auto i : vec)
    {
        if (!mp[i.second])
            num++;
        mp[i.second]++;
        while (num == m)
        {
            ans = min(ans, i.first - vec[head].first);
            mp[vec[head].second]--;
            if (!mp[vec[head].second])
                num--;
            head++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

I.The Crime-solving Plan of Groundhog

题意：

给定 $n$ 个 $0 \sim 9$ 的数，将它们组合成两个数，使得这两个数的乘积最小，要求不能有前导 $0$

题解：

稍微试几个数可以发现，当用一个最小的正整数乘上剩下的数组成的最小的数乘积是最小的，因此可以统计出最小的两个正整数，一个作为一个乘数，另一个作为另一个乘数的最高位，剩余的数从小到大接到后面即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 4e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
unordered_map<int, int> mp;
string BigNumMultiply(string str1, string str2)
{
    int size1 = str1.size(), size2 = str2.size();
    string str(size1 + size2, '0');
    for (int i = size2 - 1; i >= 0; --i)
    {
        int mulflag = 0, addflag = 0;
        for (int j = size1 - 1; j >= 0; --j)
        {
            int temp1 = (str2[i] - '0') * (str1[j] - '0') + mulflag;
            mulflag = temp1 / 10;
            temp1 = temp1 % 10;
            int temp2 = str[i + j + 1] - '0' + temp1 + addflag;
            str[i + j + 1] = temp2 % 10 + 48;
            addflag = temp2 / 10;
        }
        str[i] += mulflag + addflag;
    }
    if (str[0] == '0')
        str = str.substr(1, str.size());
    return str;
}
void solve()
{
    int n;
    cin >> n;
    mp.clear();
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        mp[x]++;
    }
    int f1 = 0, f2 = 0;
    for (int i = 1; i <= 9; i++)
    {
        if (f1 == 0 && mp[i] != 0)
        {
            f1 = i;
            mp[i]--;
        }
        if (f2 == 0 && mp[i] != 0)
        {
            f2 = i;
            mp[i]--;
            break;
        }
    }
    string s1, s2;
    s1.push_back(f1 + '0');
    s2.push_back(f2 + '0');
    for (int i = 0; i <= 9; i++)
        s2.insert(s2.size(), mp[i], i + '0');
    cout << BigNumMultiply(s1, s2) << endl;
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

K.The Flee Plan of Groundhog

题意：

给定一棵 $n$ 个节点的树，一个人从节点 $1$ 出发，每 $1m/s$ 向节点 $n$ 走 $ts$ ，然后另一个人从节点 $n$ 以 $2m/s$ 开始追，询问最长多少时间会被追到

题解：

可以先算出 $ts$ 后这个人的位置，然后以这个节点为根节点dfs求出到所有节点的距离，判断两人的距离差和最远距离的大小

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
typedef long long ll;
int to[maxn << 1], nex[maxn << 1], head[maxn], dep[maxn], cnt, mx, rt, dp;
int n, t;
void init()
{
    cnt = 0;
    mx = 0;
    rt = 0;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v)
{
    to[cnt] = v;
    nex[cnt] = head[u];
    head[u] = cnt++;
}
bool dfs(int u, int fa)
{
    if (u == n)
    {
        dp = dep[n];
        if (dep[u] <= t)
        {
            rt = n;
            return false;
        }
        return true;
    }
    for (int i = head[u]; ~i; i = nex[i])
    {
        int v = to[i];
        if (v == fa)
            continue;
        dep[v] = dep[u] + 1;
        if (dfs(v, u))
        {
            if (dep[v] - dep[1] == t)
                rt = v, dp -= dep[v];
            if (!rt)
                dep[v] = -1;
            return true;
        }
    }
    return false;
}
void DFS(int u, int fa)
{
    for (int i = head[u]; ~i; i = nex[i])
    {
        int v = to[i];
        if (v == fa)
            continue;
        if (dep[u] == -1 || dep[v] == -1)
            dep[v] = -1;
        else
            dep[v] = dep[u] + 1;
        if (v != n)
            DFS(v, u);
    }
    mx = max(mx, dep[u]);
}
int main()
{
    init();
    scanf("%d%d", &n, &t);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1, 0);
    if (rt == n)
    {
        puts("0");
        return 0;
    }
    dep[rt] = 0;
    DFS(rt, 0);
    if (mx >= dp)
        printf("%d\n", dp);
    else
        printf("%d\n", (mx + dp + 1) / 2);
    return 0;
}