CodeForces Round #817 (div.4) A~F

A. Spell Check

题意：

有一个人名字叫 Timur，给你一个字符串，问你是不是字符串 “Timur” 的任何排列。

思路：

将 Timur 按照字符大小排序，再将所给的字符串排序，最后判断两个字符串是否相等即可。

代码如下：

#include 
#define ll long long
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--){
        string a = "Timur";
        sort(a.begin(), a.end());

        int n;
        cin >> n;
        string s;
        cin >> s;
        sort(s.begin(), s.end());

        if (a == s)
            cout << "YES" << endl;
        else
            cout << "NO" << 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

---

B. Colourblindness

题意：

给定两个长度相等的字符串，由 “R, G, B” 组成，但是 “G” 和 “B” 可以互相替换，即 “G” 和 “B” 可以看成同一字符，判断两个字符串是否相等。

思路：

依次遍历，当对应的字符不相等时，判断 “G” 与 “B” 是否一一对应。

代码如下：

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

int main()
{
    int t;
    cin >> t;
    while (t--){
        int n;
        cin >> n;
        string s1, s2;
        cin >> s1 >> s2;

        int flag = 0;
        for (int i = 0; i < n; i++){
            if (s1[i] == s2[i])
                continue;
            else if (s1[i] == 'G' && s2[i] == 'B')
                continue;
            else if (s1[i] == 'B' && s2[i] == 'G')
                continue;
            else {
                flag = 1;
                break;
            }
        }

        if (!flag) cout << "YES" << endl;
        else cout << "NO" << 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

---

C. Word Game

题意：

有三个人，每个人都有 n 个长度为 3 的字符串，且每个人的字符串都不相同。

如果一个字符串只有一个人有，那么这个人加 3 分；

如果一个字符串两个人有，那么这两个人都加 1 分；

如果一个字符串三个人都有，那么三个人都不加分。

思路：

首先将三个人全部的字符串都读入后，用 map 记录每个字符串出现的次数，再对每个人的字符串逐一判断即可。

代码如下：

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

void solve()
{
    vector<string> a, b, c;
    map<string, int> mp;

    int n;
    cin >> n;

    for (int i = 0; i < 3; i++){
        for (int j = 0; j < n; j++){
            string s;
            cin >> s;

            if (i == 0) a.push_back(s);
            if (i == 1) b.push_back(s);
            if (i == 2) c.push_back(s);

            mp[s]++;
        }
    }

    int cnt1 = 0, cnt2 = 0, cnt3 = 0;
    for (int i = 0; i < n; i++){
        if (mp[a[i]] == 1) cnt1 += 3;
        if (mp[a[i]] == 2) cnt1 += 1;
            
        if (mp[b[i]] == 1) cnt2 += 3;
        if (mp[b[i]] == 2) cnt2 += 1;
            
        if (mp[c[i]] == 1) cnt3 += 3;
        if (mp[c[i]] == 2) cnt3 += 1;
    }

    printf("%d %d %d\n", cnt1, cnt2, cnt3);
}

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
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

---

D.Line（贪心）

题意：

给定一个只由 L 和 R 组成的字符串，L 所能贡献的价值为其左边的字符个数，R 所能贡献的价值为其右边的字符个数。有 n 次互相翻转的机会，可以选择翻转或者不翻转，问这个字符串所能得到的最大价值和为多少。

思路：

贪心：要得到最大价值和，则必定字符串的左半边全为 R，右半边全为 L。

先计算初始字符串的价值和，再设置两个指针 i, j 从某一端开始向中间遍历，只要左边字符为 L 或者 右边字符为 R 时，就翻转一次，输出翻转后的价值和，再转向另一方向向中间继续遍历，如此循环直至全部遍历完即可。

代码如下：

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

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = ' ' + s;

    ll ans = 0;
    for (int i = 1; i <= n; i++){
        if (s[i] == 'L')
            ans += (i - 1);
        if (s[i] == 'R')
            ans += (n - i);
    }

    int i = 1, j = n;
    int f = 0; //标记
    int cnt = 0;
    while (i < j)
    {
        if (s[i] == 'L' && f == 0){
            ans += (n - i - (i - 1));
            i++;
            f = 1;
            cnt++;
            cout << ans << ' ';
        }
        else if (s[i] == 'R' && f == 0){
            i++;
            f = 1;
        }

        if (s[j] == 'R' && f == 1){
            ans += (j - 1 - (n - j));
            j--;
            f = 0;
            cnt++;
            cout << ans << ' ';
        }
        else if (s[j] == 'L' && f == 1){
            j--;
            f = 0;
        }
    }

    while (cnt < n){
        cnt++;
        cout << ans << ' ';
    }

    puts("");
}

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
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

---

E. Counting Rectangles（前缀和）

题意：

给定 n 个矩形的长和宽 h, w，询问 q 次，每次询问依次给出两个矩形的长和宽 h1, w1, h2, w2 ，求满足 h1 < h < w1 且 w1 < w < w2 的所有矩形的面积之和。

思路：

二维前缀和：先用一个二维数组依次累加存储前 i 个矩形的面积之和，所有满足 h1 < h < w1 且 w1 < w < w2 的矩形必定被存储在该二维数组的一段连续区间内，所以可以用二维前缀和预处理出每一段区间的面积之和，最后找到符合要求的区间即可。

代码如下：

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

ll a[N][N];
ll b[N][N];

void solve()
{
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    
    ll n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++){
        int h, w;
        cin >> h >> w;
        
        //原数组存储
        a[h][w] += h * w;
    }

    for (int i = 1; i <= 1000; i++){
        for (int j = 1; j <= 1000; j++){
            //二维前缀和预处理
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
        }
    }

    for (int i = 1; i <= q; i++){
        int h1, w1, h2, w2;
        cin >> h1 >> w1 >> h2 >> w2;

        ll ans = b[h2 - 1][w2 - 1] - b[h2 - 1][w1] - b[h1][w2 - 1] + b[h1][w1];
        cout << ans << 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
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

---

F. L-shapes

题意：

思路：

从上往下，从左往右逐个搜索：

先判断每个 * 是不是满足 L 形状；

再判断每个 * 周围八个方向是否只有两个 * 。

代码如下：

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

int n, m;
char mp[N][N]; 
int vis[N][N]; //标记数组

//判断是不是L
bool check(int x, int y)
{
    int sum = 0;
    for (int i = -1; i <= 1; i++){
        for (int j = -1; j <= 1; j++){
            if (mp[x + i][y + j] == '*')
                sum ++;
        }
    }

    if (sum == 3) 
        return true;
    return false;
}

//每个*周围最多有两个*
bool get(int x, int y)
{
    vis[x][y] = 1;
    int sum = 1; //自身为1

    //因为是从左上往右下搜索，所以要判断每个*的右下角四个方向是否是*
    if (mp[x][y + 1] == '*'){
        vis[x][y + 1] = 1;
        sum++;
    }
    if (mp[x + 1][y - 1] == '*'){
        vis[x + 1][y - 1] = 1;
        sum++;
    }
    if (mp[x + 1][y] == '*'){
        vis[x + 1][y] = 1;
        sum++;
    }
    if (mp[x + 1][y + 1] == '*'){
        vis[x + 1][y + 1] = 1;
        sum++;
    }

    if (sum == 3)
        return true;
    return false;
}

void solve()
{
    memset(mp, 'a', sizeof(mp));
    memset(vis, 0, sizeof(vis));

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%s", mp[i] + 1);

    int flag = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (mp[i][j] == '*' && vis[i][j] == 0){
                if (!get(i, j))
                    flag = 0;
            }

            if (mp[i][j] == '*'){
                if (!check(i, j))
                    flag = 0;
            }
        }
    }

    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << 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
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

---