Codeforces-Round-895-Div-3

A. Two Vessels

题目翻译

你有两个装有水的容器。第一个容器含有$a$克水，第二个容器含有$b$克水。这两艘船都非常大，可以容纳任意数量的水。

您还有一个空杯子，最多可容纳$c$克水。

一次，您可以从任何容器中舀出多$c$克水，然后将其倒入另一个容器中。请注意，一次倒入的水的质量不必是整数。

使容器中水的质量相等所需的最少移动次数是多少？请注意，您无法执行除所描述的移动之外的任何操作。

思路

每次可以使得两个杯子的差距最多减少2*c,因此答案就是$\frac{abs(a-b)}{2c}$,向上取整

因为c++的/默认是下取整

$\frac{a}{b}$向上取整可以写成：$\frac{a+b-1}{b}$

或者使用ceil取整

或者使用 a/b+a%b!=0

代码

/**
 * PROBLEM_NAME:A. Two Vessels
 * ONLINE_JUDGE_NAME:Codeforces
 * Date:2023/9/7
 * Author:houyunfei
**/
#include 

#define int long long
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define IOS cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
#define cxk 1
#define debug(s, x) if (cxk) cout << "#debug:(" << s << ")=" << x << endl;
using namespace std;

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    int res = (abs(a - b) + 2 * c - 1) / (2 * c);
    cout << res << endl;
}

signed main() {
    IOS
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

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

B. The Corridor or There and Back Again

题目翻译

你正处在一条向右无限延伸的走廊里，分成了几个方形的房间。您从房间$1$开始，前往房间$k$，然后返回房间$1$。您可以选择$k$的值。移动到相邻的房间需要$1$秒。

另外，走廊里还有$n$个陷阱：第$i$个陷阱位于$d_i$房间，将在你进入房间**${\mathbf{d}}_{\mathbf{i}}$后$s_i$秒被激活。一旦陷阱被激活，你就无法进入或离开有该陷阱的房间。

可能的走廊以及通往房间$k$和返回的路径的示意图。

确定$k$的最大值，允许您从$1$房间移动到$k$房间，然后安全返回$1$房间。

例如，如果$n=1$和$d_1=2,s_1=2$，你可以前往$k=2$房间并安全返回（陷阱在$1+s_1=1+2=3$时刻激活，不能阻止你返回）。但如果你试图到达房间$k=3$，陷阱就会在$1+s_1=1+2=3$时刻激活，阻止你返回（你会在第二个$3$返回的路上尝试进入$2$房间，但激活的陷阱会阻止你）。 $k$任何更大的值也是不可行的。故答案为$k=2$。

思路

因为数据范围比较小，可以直接暴力枚举时间1-300,看是否合法，取合法的最大时间

代码

/**
 * PROBLEM_NAME:B. The Corridor or There and Back Again
 * ONLINE_JUDGE_NAME:Codeforces
 * Date:2023/9/7
 * Author:houyunfei
**/
#include 

#define int long long
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define IOS cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
#define cxk 1
#define debug(s, x) if (cxk) cout << "#debug:(" << s << ")=" << x << endl;
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1, x, y; i <= n; i++) {
        cin >> x >> y;
        a[i] = {x, y};
    }
    int mx = 0;
    for (int i = 1; i <= 300; i++) {
        bool ok = 1;
        for (int j = 1; j <= n; j++) {
            if ((i - a[j].first) * 2 >= a[j].second) {
                ok = 0;
                break;
            }
        }
        if (ok) {
            mx = max(mx, i);
        }
    }
    cout << mx << endl;
}

signed main() {
    IOS
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

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

C. Non-coprime Split

题目翻译

给你两个整数$l\le r$。你需要找到正整数$a$和$b$，使得同时满足以下条件：

• $l\le a+b\le r$
• $\gcd (a,b)\ne 1$

或报告它们不存在。

$\gcd (a,b)$表示数字$a$和$b$的【最大公约数】(https://en.wikipedia.org/wiki/Greatest_common_divisor)。例如$\gcd (6,9)=3$、$\gcd (8,9)=1$、$\gcd (4,2)=2$。

思路

如果l=r,那么就看l是不是素数，如果是素数就无解，否则可以找到一个因子x,另一个数为l-x,而$\frac{l-x}{x}=\frac{l}{x}-1$,因此$gcd(x,l-x)!=1$

如果l!=r：

• r为奇数，此时r-1>=l ,并且r-1一定为偶数，因此可以构造 (2,r-1-2), 他们的gcd=2;
• r为偶数，可以直接构造(2,r-2),gcd=2;

此外，还需要特判一些误解的情况。

代码

/**
 * PROBLEM_NAME:C. Non-coprime Split
 * ONLINE_JUDGE_NAME:Codeforces
 * Date:2023/9/7
 * Author:houyunfei
**/
#include 

#define int long long
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define IOS cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
#define cxk 1
#define debug(s, x) if (cxk) cout << "#debug:(" << s << ")=" << x << endl;
using namespace std;
//13 14 15 16 17
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void solve() {
    int l, r;
    cin >> l >> r;
    if (l == 1 && r <= 3) {
        cout << -1 << endl;
        return;
    }
    if (l == 2 && r <= 3) {
        cout << -1 << endl;
        return;
    }
    if (l != r) {
        if (r & 1) {
            cout << 2 << " " << r - 1 - 2 << endl;
        } else {
            cout << 2 << " " << r - 2 << endl;
        }
    } else {
        for (int i = 2; i * i <= l; i++) {
            if (l % i == 0) {
                cout << i << " " << l - i << endl;
                return;
            }
        }
        cout << -1 << endl;
    }
}

signed main() {
    IOS
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

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

D. Plus Minus Permutation

题目翻译

给你$3$个整数——$n$、$x$、$y$。我们将排列的分数${}^{†}$ $p_1,\dots ,p_n$称为以下值：

$
(p_{1 \cdot x} + p_{2 \cdot x} + \ldots + p_{\lfloor \frac{n}{x} \rfloor \cdot x}) - (p_{1 \cdot y} + p_{2 \cdot y} + \ldots + p_{\lfloor \frac{n}{y} \rfloor \cdot y})
$

换句话说，排列的得分是所有指数$i$能被$x$整除的$p_i$之和，减去所有指数$i$能被$y$整除的$p_i$之和。

你需要在长度$n$的所有排列中找到最大可能的分数。

例如，如果$n=7$、$x=2$、$y=3$，则通过排列$[2,\underline{6},\underline{1},\underline{7},5,\underline{\underline{4}},3]$获得最高分数，并且等于$(6+7+4)-(1+4)=17-5=12$。

${}^{†}$长度$n$的排列是由$n$个从$1$到$n$的不同整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$是排列，但$[1,2,2]$不是排列（数字$2$在数组中出现两次），$[1,3,4]$也不是排列（$n=3$，但数组包含$4$） 】）。

思路

看n里面有几个x的倍数，有几个y的倍数，有几个lcm(x,y)的倍数，

答案应该是x倍数上面的数-y倍数上面的数，lcm(x,y)上面的数不记录答案，因为是一个减去一个加回来

设$x1=n/x,y1=n/y,t=n/(lcm(x,y))$

我们应该贪心的把x倍数上面的数从大到小放，把y倍数上面的数从小到大放。

n范围比较大，可以使用等差数列求和公式计算。

$S_n=\frac{n\ast (a_1+a_n)}{2}$

代码

/**
 * PROBLEM_NAME:D. Plus Minus Permutation
 * ONLINE_JUDGE_NAME:Codeforces
 * Date:2023/9/7
 * Author:houyunfei
**/
#include 

#define int long long
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define IOS cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
#define cxk 1
#define debug(s, x) if (cxk) cout << "#debug:(" << s << ")=" << x << endl;
using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    int t = lcm(x, y);
    int x1 = n / x - n / t;
    int y1 = n / y - n / t;
    int res = 0;
    res += x1 * (n + n - x1 + 1) / 2;
    res -= y1 * (1 + y1) / 2;
    cout << res << endl;
}

signed main() {
    IOS
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}
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

E. Data Structures Fan

题目翻译

给你一个整数数组$a_1,a_2,\dots ,a_n$，以及一个由$n$个字符组成的二进制字符串${}^{†}$ $s$。

Augustin 是数据结构的忠实粉丝。因此，他要求你实现一个可以回答$q$查询的数据结构。有两种类型的查询：

• “1$l$ $r$”（$1\le l\le r\le n$）— 将$l\le i\le r$中的每个字符$s_i$替换为其相反字符。即，将$\text{0}$全部替换为$\text{1}$，将$\text{1}$全部替换为$\text{0}$。
• “2 $g$” ( g ∈ { 0 , 1 } g \in \{0, 1\} g∈{0,1}) — 计算所有索引$i$的数字$a_i$的按位异或 的值】 这样$s_i=g$。请注意，空数集的$\mathrm{XOR}$被认为等于$0$。

请帮助奥古斯丁回答所有问题！

例如，如果$n=4$、$a=[1,2,3,6]$、$s=\text{1001}$，请考虑以下一系列查询：

1.“2$0$”——我们对索引$i$感兴趣，其中$s_i=0$，从$s=1001$开始，这些是索引$2$和$3$，所以查询的答案将是$a_2\oplus a_3=2\oplus 3=1$。
2.“1$1$ $3$”——我们需要将字符$s_1,s_2,s_3$替换为其反义词，因此在查询$s=1001$之前，在查询之后：$s=0111$。
3.“2$1$”——我们对索引$i$感兴趣，其中$s_i=1$，从$s=0111$开始，这些是索引$2$，$3$和$4$，所以答案为查询结果为$a_2\oplus a_3\oplus a_4=2\oplus 3\oplus 6=7$。
4.“1$2$ $4$”—$s=0111$ $\to$ $s=0000$。
5. “2$1$”—$s=0000$，没有带有$s_i=1$的索引，因此由于空数集的$\mathrm{XOR}$被认为等于$0$，所以该查询的答案是$0$。

${}^{†}$二进制字符串是只包含字符$\text{0}$或$\text{1}$的字符串。

思路

异或的性质:

• x^x=0

可以使用两个变量zero,one 来记录整个字符串中1上面权值异或的答案，0上面权值异或的答案。

• 对于1操作：
  • 将整个字符串翻转，那么对于zero来说，他应该先去掉这个区间中0上权值的异或和(设为x)，再异或上这个区间中1上权值的异或和(设为y), 去掉x可以使用zero^x,因为zero=x^t(其中t为除去这个区间的其他0上权值异或和),这样zero^x=t^x^x=t,再异或上y可以使用zero^y,因此总的操作其实就是zero^x^y=zero^sum,其中sum为这个区间所有权值的异或和
• 对于2操作，直接输出对应的1和0即可。

快速求区间的异或可以使用类似于前缀和思想。

代码

/**
 * PROBLEM_NAME:E. Data Structures Fan
 * ONLINE_JUDGE_NAME:Codeforces
 * Date:2023/9/7
 * Author:houyunfei
**/
#include 

#define int long long
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define IOS cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
#define cxk 1
#define debug(s, x) if (cxk) cout << "#debug:(" << s << ")=" << x << endl;
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    string s;
    cin >> s;
    s = " " + s;
    cin >> q;
    vector<int> s1(n + 1);
    int x = 0, y = 0; //x-0 y-1
    for (int i = 1; i <= n; i++) {
        s1[i] = s1[i - 1] ^ a[i];
        if (s[i] == '1') {
            y ^= a[i];
        } else {
            x ^= a[i];
        }
    }
    while (q--) {
        int op, l, r;
        cin >> op;
        if (op == 2) {
            cin >> l;
            if (l == 0) {
                cout << x << " ";
            } else {
                cout << y << " ";
            }
        } else {
            cin >> l >> r;
            x ^= s1[r] ^ s1[l - 1];
            y ^= s1[r] ^ s1[l - 1];
        }
    }
    cout << endl;
}
    int q;

signed main() {
    IOS
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

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

F. Selling a Menagerie

题目翻译

您是一个动物园的主人，该动物园由$n$只动物组成，编号从$1$到$n$。然而，维护动物园的费用相当昂贵，所以你决定卖掉它！

众所周知，每种动物都害怕另一种动物。更准确地说，动物$i$害怕动物$a_i$（$a_i\ne i$）。另外，每只动物的成本是已知的，对于动物$i$来说，它等于$c_i$。

您将按固定顺序出售所有动物。正式来说，你需要选择一些排列${}^{†}$ $p_1,p_2,\dots ,p_n$，先卖动物$p_1$，然后卖动物$p_2$，依此类推，最后卖动物$p_n$。

当你出售动物$i$时，有两种可能的结果：

• 如果动物$a_i$在动物$i$之前**被出售，您将因出售动物$i$而收到$c_i$钱。
• 如果动物$a_i$在动物$i$之前未出售，您将因出售动物$i$而收到$2\cdot c_i$钱。 （令人惊讶的是，目前害怕的动物更有价值）。

您的任务是选择出售动物的顺序，以使总利润最大化。

例如，如果$a=[3,4,4,1,3]$、$c=[3,4,5,6,7]$，并且您选择的排列是$[4,2,5,1,3]$，则：

• 第一个被出售的动物是动物$4$。动物$a_4=1$之前没有被出售过，所以你会因为出售它而收到$2\cdot c_4=12$钱。
• 第二个出售的动物是动物$2$。动物$a_2=4$之前已被出售，因此您可以通过出售它获得$c_2=4$的钱。
• 第三个出售的动物是动物$5$。动物$a_5=3$之前没有出售过，所以出售它你会收到$2\cdot c_5=14$钱。
• 第四个出售的动物是动物$1$。动物$a_1=3$之前没有出售过，所以出售它你会收到$2\cdot c_1=6$钱。
• 第五个出售的动物是动物$3$。动物$a_3=4$之前已被出售，因此您可以通过出售它获得$c_3=5$的钱。

通过这种排列选择，您的总利润是$12+4+14+6+5=41$。请注意，在本例中，$41$不是最大可能利润。

${}^{†}$长度$n$的排列是由$n$个从$1$到$n$的不同整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$是一个排列，但$[1,2,2]$不是一个排列（$2$在数组中出现了两次），$[1,3,4]$也不是一个排列（$n=3$，但$4$出现在数组中）大批）。

思路

根据输入数据，可以从i向a[i]连一条单向边，w[i]为点权，此时可以发现先拿i就可以获得两倍的贡献。因此可以记录每个点的入度，然后按照拓扑排序的方式，先拿入度为0的点，这些点拿了贡献就是两倍，

拿完之后剩下的就是一些环了，环与环之间不会相连，因为一个点最多有一个出边。

对于一个环，显然需要拿出一个点，这个点的代价为1倍，这样其他点点代价可以做到两倍，因此只需要找到这个环里面权值最低点哪个点，最后拿这个点，就可以做到贡献最大化。

代码

/**
 * PROBLEM_NAME:F. Selling a Menagerie
 * ONLINE_JUDGE_NAME:Codeforces
 * Date:2023/9/7
 * Author:houyunfei
**/
#include 

#define int long long
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define IOS cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
#define cxk 1
#define debug(s, x) if (cxk) cout << "#debug:(" << s << ")=" << x << endl;
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> w(n + 1), a(n + 1), d(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        d[a[i]]++;
    }
    for (int i = 1; i <= n; i++) cin >> w[i];
    queue<int> q;
    vector<bool> st(n + 1);
    for (int i = 1; i <= n; i++) {
        if (d[i] == 0) q.push(i);
    }
    vector<int> res;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        st[x] = true;
        res.push_back(x);
        if (--d[a[x]] == 0) q.push(a[x]);
    }
    //剩下的都是环了
    for (int i = 1; i <= n; i++) {
        if (st[i])continue;
        int x = i;
        vector<int> t;
        while (!st[x]) {
            st[x] = true;
            t.push_back(x);
            x = a[x];
        }
        int pos = 0; //权值最小的点的位置
        for (int j = 0; j < t.size(); j++) {
            if (w[t[j]] < w[t[pos]]) pos = j;
        }
        for (int j = 0; j < t.size(); j++) {
            pos++;
            if (pos == t.size())pos = 0;
            res.push_back(t[pos]);
        }
    }
    for (const auto &item: res) {
        cout << item << " ";
    }
    cout << endl;

}

signed main() {
    IOS
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}
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

G. Replace With Product

题目翻译

给定一个数组$a$，其中$n$个正整数。您需要恰好执行一次以下操作：

• 选择$2$个整数$l$和$r$（$1\le l\le r\le n$），并将子数组$a[l\dots r]$替换为单个元素：子数组$(a_l\cdot \dots \cdot a_r)$中所有元素的乘积。

例如，如果对数组$[5,4,3,2,1]$进行参数$l=2,r=4$的运算，则数组将变为$[5,24,1]$。

您的任务是在应用此操作后最大化数组的总和。找到应用此操作的最佳子数组。

思路

显然，如果区间的两边都是1，这些1一定不会选。

可以先找到区间[l,r],区间l的左边都是1，区间r的右边都是1，l和r都不等于1

对于一个区间来说，如果这个区间中元素的乘积大于1e9了，那么我们就会选择将整个区间进行合并，因为对于端点都是>=2的数，显然乘上这些数获得的贡献远比加上这些数获得的贡献大。

如果区间的乘积<1e9,那么说明不会有超过30个数大于1，因此可以记录这些>1的数的位置，然后暴力枚举两个数进行合并，看哪种方案获得的贡献最大，此时不会爆int。

代码

/**
 * PROBLEM_NAME:G. Replace With Product
 * ONLINE_JUDGE_NAME:Codeforces
 * Date:2023/9/7
 * Author:houyunfei
**/
#include 

#define int long long
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define IOS cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
#define cxk 1
#define debug(s, x) if (cxk) cout << "#debug:(" << s << ")=" << x << endl;
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = n;
    while (l <= n && a[l] == 1) l++;
    while (r >= 1 && a[r] == 1) r--;
    if (l >= r) {
        cout << "1 1\n";
        return;
    }

    int mul = 1;
    for (int i = l; i <= r; i++) {
        mul *= a[i];
        if (mul > 1e9) {
            cout << l << " " << r << endl;
            return;
        }
    }

    int t = 0;
    vector<int> pos;
    for (int i = l; i <= r; i++) {
        if (a[i] > 1) {
            t++;
            pos.push_back(i);
        }
    }
    if (t >= 30) {
        cout << l << " " << r << endl;
        return;
    }
    vector<int> s(n + 1), sum(n + 1);
    s[0] = 1;
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] * a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    int x = l, y = l;
    int mx = sum[n];
    for (int i = 0; i < pos.size(); i++) {
        for (int j = i + 1; j < pos.size(); j++) {
            t = s[pos[j]] / s[pos[i] - 1] + sum[n] - (sum[pos[j]] - sum[pos[i] - 1]);
            if (t > mx) mx = t, x = pos[i], y = pos[j];
        }
    }
    cout << x << " " << y << endl;
}

signed main() {
    IOS
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}
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