Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

CF1654

发表于 分类于
本文字数： 5.1k 阅读时长 ≈ 5 分钟
标签：        

Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round)

A. Maximum Cake Tastiness

翻转一段区间，使得相邻两个数的和的最大值最大。

显然最大值和次大值一定可以翻在一起。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, w[N];
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        int p = 0, q = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> w[i];
            if (!p || w[i] > w[p])
                q = p, p = i;
            else if (!q || w[i] > w[q])
                q = i;
        }
        cout << w[p] + w[q] << endl;
    }
    return 0;
}

B. Prefix Removals

找到串的第一个后面没有这个字符的位置，向后输出即可。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        string str;
        cin >> str;
        for (int i = 0; i < str.size(); i++)
            if (str.find(str[i], i + 1) == string::npos)
            {
                cout << str.substr(i) << endl;
                break;
            }
    }
    return 0;
}

C. Alice and the Cake

一个数，每次将其分为 $\left \lfloor \frac w 2 \right \rfloor$ 和 $\left \lceil \frac w 2 \right \rceil$ 两个数，问当前序列是否可以通过一个数如此操作得到。

发现分后数的和一定不变，将序列中所有数加起来，按照这样操作，维护两个集合，一旦发现有一样的立刻抵消。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
bool check()
{
    int n;
    LL sum = 0;
    multiset<LL> A, B;
    cin >> n;
    for (int a; n; n--)
    {
        cin >> a;
        sum += a;
        A.insert(a);
    }
    B.insert(sum);
    while (!A.empty())
    {
        LL t = *B.begin();
        B.erase(B.lower_bound(t));
        if (A.count(t))
            A.erase(A.lower_bound(t));
        else
        {
            if (t == 1)
                return false;
            B.insert(t >> 1), B.insert(t - (t >> 1));
        }
    }
    return true;
}
int main()
{
    int T;
    cin >> T;
    while (T--)
        puts(check() ? "Yes" : "No");
    return 0;
}

D. Potion Brewing Class

给定一棵树，树上每个点有一个正整数权值，相邻两点的权值需要满足一定的比率关系，求权值和最小时权值和模 $998244353$ 的值。

考虑先构造一个一定合法的方案，将所有的比率乘起来作为根节点的值，那么所有数一定都是整数，这样可能不是最小值，而最小值一定是这个方案再除去所有数的 $gcd$ 。直接暴力求 $gcd$ 复杂度不对了，发现每次从父节点向子节点移动时，只会除去一个数乘上一个数，于是可以动态维护当前值和 $gcd$ 。具体地，将所有数质因数分解，记录每个质数的个数， $cur$ 构成当前的数，$ans$ 取历史最小值，最后 $ans$ 一定为最后的 $gcd$ 。

如果每次直接根号质因数分解，复杂度较大，考虑将每个数最小的质数因子筛出来，这样每次可以除以一个最小的质因数，保证了复杂度最坏为 $O(\log n)$ 。故可以在 $O(n \log n)$​ 时间内完成。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, mod = 998244353;
int inv[N];
int cnt, p[N], f[N];
int n, tot, ans[N], cur[N];
struct Edge
{
    int v, p, q;
};
vector<Edge> g[N];
void add(int x, int k)
{
    for (; x > 1; x /= f[x])
        cur[f[x]] += k, ans[f[x]] = min(ans[f[x]], cur[f[x]]);
}
void dfs(int x, int fa, int s)
{
    (tot += s) %= mod;
    for (Edge i : g[x])
        if (i.v != fa)
        {
            add(i.p, -1), add(i.q, 1);
            dfs(i.v, x, (LL)s * i.q % mod * inv[i.p] % mod);
            add(i.p, 1), add(i.q, -1);
        }
}
void init()
{
    inv[1] = 1;
    for (int i = 2; i < N; i++)
        inv[i] = -(LL)(mod / i) * inv[mod % i] % mod;
    for (int i = 2; i < N; i++)
    {
        if (!f[i])
            p[++cnt] = f[i] = i;
        for (int j = 1; j <= cnt && i * p[j] < N; j++)
        {
            f[i * p[j]] = p[j];
            if (i % p[j] == 0)
                break;
        }
    }
}
int binpow(int b, int k)
{
    int res = 1;
    while (k)
    {
        (k & 1) && (res = (LL)res * b % mod);
        b = (LL)b * b % mod;
        k >>= 1;
    }
    return res;
}
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int main()
{
    init();
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        tot = 0;
        for (int i = 1; i <= n; i++)
            g[i].clear();
        for (int i = 1; i <= n; i++)
            cur[i] = 0;
        int st = 1;
        for (int i = 1, a, b, c, d; i < n; i++)
        {
            cin >> a >> b >> c >> d;
            int e = gcd(c, d);
            c /= e, d /= e;
            g[a].push_back((Edge){b, c, d});
            g[b].push_back((Edge){a, d, c});
            add(c, 1), add(d, 1);
            st = (LL)st * c % mod * d % mod;
        }
        for (int i = 1; i <= n; i++)
            ans[i] = cur[i];
        dfs(1, 0, st);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= ans[i]; j++)
                tot = (LL)tot * inv[i] % mod;
        cout << (tot + mod) % mod << endl;
    }
    return 0;
}
相关文章