@[toc]

Codeforces Round #817 (Div. 4)题解

比赛地址： Codeforces Round #817 (Div. 4)
这次排名前一千了，有进步就行💪

A. Spell Check

题目

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

思路：字符串

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

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;
void solve()
{
    string a = "Timur";
    sort(all(a));
    int n;
    cin >> n;
    string s;
    cin >> s;
    sort(all(s));
    if (a == s)
        YES;
    else
        NO;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

B. Colourblindness

题目

给你两行长度相等的字符串，字符串只能由R、G、B组成。而且G和B被误认为是相同字母，问两个字符串是否相同。

思路

字符串

直接将所有的B转换为G即可

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;
void solve()
{
    int n;
    string a, b;
    cin >> n;
    cin >> a >> b;
    int ok = 1;
    for (int i = 0; i < n; i++)
    {
        int t = 0;
        if (a[i] == 'G' || a[i] == 'B')
            t++;
        if (b[i] == 'G' || b[i] == 'B')
            t++;
        if (t == 1)
            ok = 0;
    }
    if (ok)
        YES;
    else
        NO;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

C. Word Game

题目

有三个人，每个人都有n个字符串并且每个人的字符串都不相同。

如果一个字符串只在一个人那里出现，那么那个人加3分

如果一个字符串在两个人那里出现，那么那两人各加1分

如果一个字符串在三个人那里都出现了，那么就都不加分

思路

字符串+数据结构

我们要记录每个字符串在谁那里出现过，并且记录几次。

我们可以用map这个数据结构来实现。具体看代码。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;
int a[10];
void solve()
{
    mset(a, 0);
    int n;
    map<string, vector<int>> ma;
    cin >> n;
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            string s;
            cin >> s;
            ma[s].pb(i);
        }
    }
    for (auto x : ma)
    {
        vector<int> v = x.y;
        if (v.size() == 1)
        {
            a[v[0]] += 3;
        }
        else if (v.size() == 2)
        {
            a[v[0]]++;
            a[v[1]]++;
        }
    }
    cout << a[1] << " " << a[2] << " " << a[3] << endl;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

D. Line

题目

给你一个由L和R组成的字符串，如果某个位置上字符是L，那这个点可以贡献的价值为它左边有多少个字符，如果某个位置上字符是R，那这个点可以贡献的价值为它右边有多少个字符。问可以翻转k个字符（也可以不反转）的情况下这个字符串的最大价值和是多少？

思路

贪心

如果一个字符反转后的价值更大的话就记录下来，将所有记录下来的价值按从大到小排序，每次都先反转价值最大的那个。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;
char s[N];
int n;
void solve()
{
    cin >> n;
    scanf("%s", s + 1);
    vector<int> v;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == 'L')
        {
            if (n - i > i - 1)
            {
                v.pb(n - i - (i - 1));
            }
            ans += i - 1;
        }
        else
        {
            if (n - i < i - 1)
            {
                v.pb(-(n - i - (i - 1)));
            }
            ans += n - i;
        }
    }
    sort(v.begin(), v.end(), [](int x, int y)
         { return x > y; });
    for (int i = 1; i <= n; i++)
    {
        if (i <= v.size())
        {
            ans += v[i - 1];
        }
        cout << ans << " ";
    }
    cout << endl;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

E. Counting Rectangles

题目

给你很多个矩形，你有q此询问，每次询问会给你两个矩形的h和w，回答所有满足h1<h<h2 w1<w<w2的矩形的长乘宽之和。

思路：前缀和+差分

我们假设(h[i], w[i])标识一个矩形，在二维平面上如下图所示

通过上图我们可以发现，紫色那片区域的每个点都是满足条件的矩形。这样我们就只需要求紫色那片区域中所有矩形的价值之和即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e3 + 10, inf = 0x3f3f3f3f, mod = 998244353;
ll a[N][N];
ll b[N][N];
int n, q;
void solve()
{
    mset(a, 0);
    mset(b, 0);
    ll ans = 0;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        a[x][y] += x * y;
    }
    // 求二维前缀和
    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];
        }
    }
    while (q--)
    {
        int h1, w1, h2, w2;
        cin >> h1 >> w1 >> h2 >> w2;
        // 不能重叠，所以要小1
        h1++;
        w1++;
        h2--;
        w2--;
        ll ans = b[h2][w2] - b[h2][w1 - 1] - b[h1 - 1][w2] + b[h1 - 1][w1 - 1];
        cout << ans << endl;
    }
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

F. L-shapes

题目

思路

搜索

检查每个*是不是属于L型（满不满足条件1）
检查每个*周围八个方向上是否只有2个*（满不满足条件2）

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e2 + 10, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
char g[100][100];
int b[N][N]; // 记录每个*有没有被判断过
bool check(int x, int y)
{
    int sum = 0;
    for (int i = -1; i <= 1; i++)
        for (int j = -1; j <= 1; j++)
            if (g[x + i][y + j] == '*')
                sum++;
    return sum == 3;
}
bool get(int x, int y)
{
    b[x][y] = 1;
    int sum = 1;
    if (g[x + 1][y - 1] == '*')
    {
        b[x + 1][y - 1] = 1;
        sum++;
    }
    if (g[x + 1][y] == '*')
    {
        b[x + 1][y] = 1;
        sum++;
    }
    if (g[x][y + 1] == '*')
    {
        b[x][y + 1] = 1;
        sum++;
    }
    if (g[x + 1][y + 1] == '*')
    {
        b[x + 1][y + 1] = 1;
        sum++;
    }
    return sum == 3;
}
void solve()
{
    int ok = 1;
    mset(g, 'a');
    mset(b, 0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%s", g[i] + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (g[i][j] == '*' && b[i][j] == 0)
            {
                if (!get(i, j))
                    ok = 0;
            }
            if (g[i][j] == '*')
            {
                if (!check(i, j))
                    ok = 0;
            }
        }
    }
    if (ok)
        YES;
    else
        NO;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

G. Even-Odd XOR

题目

输出包含n个数的序列，每个数小于2^31，并且奇数项上的元素异或的结果和偶数项上的元素结果相同

思路：构造

奇数项和偶数项上异或的结果相同，那么整个序列的异或结果就为0
a | b | b | a = 0
每个数各不相同

由上面两个信息我们可以发现，我们只需要让前n-2个数随便填但不能相同，假设前n-2个数异或的结果就为b,那么就可以令最后两个数为a|b 和a,这样最后的结果就为0。

但是我们要特判一种情况就是b == 0 的时候，如果还按原来的方式的话后两个数就相同了。所以我们可以改变其中的一个数，使b != 0而且不能和其他数相同。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;
void solve()
{
    int n;
    cin >> n;
    vector<int> ans(n);
    int s = 0;
    for (int i = 0; i < n - 2; i++)
    {
        ans[i] = i;
        s ^= i;
    }
    if (s == 0)
    {
        ans[0] = (1 << 30) - 1;
        s = (1 << 30) - 1;
    }
    ans[n - 2] = (1 << 30) | s;
    ans[n - 1] = (1 << 30);
    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";
    cout << endl;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

【算法题解】Codeforces Round #817 (Div. 4)题解

Codeforces Round #817 (Div. 4)题解

A. Spell Check

B. Colourblindness

C. Word Game

D. Line

E. Counting Rectangles

F. L-shapes

G. Even-Odd XOR

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【算法题解】Codeforces Round #817 (Div. 4)题解

Codeforces Round #817 (Div. 4)题解

A. Spell Check

B. Colourblindness

C. Word Game

D. Line

E. Counting Rectangles

F. L-shapes

G. Even-Odd XOR

热门文章

最新文章

相关课程

相关电子书

相关实验场景