CodeForces Round #535 (div.3) A~D

A. Two distinct points

题意：

给定两个区间，左右端点分别为 l₁, r₁, l₂, r₂，找到不同的 a ，b 两数，使得 l₁ <= a <= r₁ ，l₂ <= b <= r₂ .

思路：

直接取区间的右端点，如果右端点相同，那么将第二个右端点的位置减一即可。

代码如下：

#include 
using namespace std;

void solve()
{
    int l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;

    cout << r1 << ' ';
    if (r1 == r2)
        cout << r2 - 1 << endl;
    else 
        cout << r2 << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        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

---

B. Divisors of Two Integers

题意：

给定一个长度为 n 的数组，其中每个数都是 x 或 y 的约数，这些数里面包括 1 以及 x 和 y 其本身，并且如果某个数出现了两次，那就代表这个数既是 x 的约数，也是 y 的约数。
要求找到 x 和 y。

思路：

首先，数组中一定有 x 和 y 这两个数，可以将数组从小到大排序，最大的那个数即为 x 和 y 其中的一个，我们可以将其赋值给 x 。

接着再找出只为 x 的约数，将其排除掉；
如果某个数不是 x 的约数，且其值是其他的数里面最大的，因为 一个数的约数除了它本身外一定都比它小，既然数组中包含它本身，那么剩下的最大的数就是 y 。

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 130;

int a[N]; //原数组
int b[N]; //标记

int main()
{
    int n;
    cin >> n;

    ll x = 1, y = 1;
    int cnt = 0;
    int mx = 0;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, a + n);

    x = a[n - 1]; //设定x为最大数

    for (int i = 0; i < n - 1; i++){
        if (x % a[i] == 0 && a[i] != a[i + 1]){
            b[i] = 1; //标记排除掉不符合条件的数
        }
    }

    for (int i = n - 2; i >= 0; i--){
        if (b[i] == 0){
            y = a[i]; //y为剩下的最大的数
            break;
        }
    }

    cout << x << ' ' << y << endl;

    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

---

C. Nice Garland

题意：

给定一个只包含 'R', 'G', 'B' 的字符串，对字符串进行操作，每次操作可以将一个字符替换为其他任意字符，要求操作后的字符串每隔 3 个距离的字符都相等。例如 RGBRGBRGB .

思路：

因为字符串只包含 3 种字符，就会导致如果这个的字符串的长度大于等于 3 时，一定是 RGB 这三个字符的某一种排列的循环，那么 RGB 一共有 6 种排列方式，将其预先存储在 str[] 中。

然后挨个枚举每一种排列去和字符串进行匹配，找出让字符串为 3 字符循环的最小消耗即可，中间使用变量 k 来记录是哪一种排列方式让消耗最小，然后最后输出他的循环节即可。

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 2e5 + 10;

char str[10][5] = {"RGB", "RBG", "GBR", "GRB", "BRG", "BGR"};

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;

    if (n == 1){
        puts("0");
        cout << s << endl;
    }
    else {
        int res = 1e8;
        int k;
        for (int i = 0; i < 6; i++) //挨个枚举每一种排列
        {
            int cnt = 0;
            for (int j = 0; j < n; j++){
                if (s[j] != str[i][j % 3])
                    cnt++;
            }

            if (cnt < res){
                res = cnt;
                k = i; //记录是哪一种排列
            }
        }

        cout << res << endl;
        for (int i = 0; i < n; i++){
            cout << str[k][i % 3];
        }
        cout << endl;
    }

    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

---

D. Diverse Garland

题意：

与上题类似，给定一个只包含 'R', 'G', 'B' 的字符串，对字符串进行操作，每次操作可以将一个字符替换为其他任意字符。要求目标字符串中任何两个相邻的字符都是不同的，求最小操作次数。

思路：

同样与上题差不多的思路，先将三个字符存入 str[] 中，然后遍历字符串，如果某个字符与前一字符相同，就将其替换成另一字符，如果替换后的字符与后一字符相同，再将其替换，记为一次操作。最后输出操作数和修改后的字符串即可。

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 2e5 + 10;

char str[5] = {'R', 'G', 'B'};

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;

    int cnt = 0;
    for (int i = 1; i < n; i++){
        for (int j = 0; j < 3; j++){
            if (s[i] == str[j] && s[i - 1] == str[j]) //先比较前一字符
            {
                cnt++;
                s[i] = str[(j + 1) % 3];
                if (s[i] == s[i + 1]) //再比较后一字符
                    s[i] = str[(j + 2) % 3];
            }
        }
    }

    cout << cnt << endl;
    for (int i = 0; i < n; i++)
        cout << s[i];
    cout << endl;

    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

---