AI 助理
备案控制台
开发者社区 人工智能 文章 正文

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

2022-09-30 150
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【算法题解】Codeforces Round #817 (Div. 4)题解

@[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])标识一个矩形，在二维平面上如下图所示

image-20220831151312371

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

代码

#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

题目

image-20220831152611654

思路

搜索

  1. 检查每个*是不是属于L型（满不满足条件1）
  2. 检查每个*周围八个方向上是否只有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，并且奇数项上的元素异或的结果和偶数项上的元素结果相同

思路：构造

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

由上面两个信息我们可以发现，我们只需要让前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;
}
文章标签：
算法
游客472mxcrxda2he
目录
相关文章
HEX9CF
|
5月前
|
C++
【洛谷 P1923】【深基9.例4】求第 k 小的数 题解（nth_element）
该题目要求输入一个奇数个整数 $n$（$1 \le n &lt; 5000000$）和一个位置 $k$，在给定的 $n$ 个不超过 ${10}^9$ 的整数中找出第 $k$ 小的数。样例输入为 `5 1` 和 `4 3 2 1 5`，输出第 $1$ 小的数，即 `2`。解决方案使用 C++ 的 `nth_element` 函数来找到第 $k$ 小的数。
HEX9CF
38 0
加油，旭杏
|
5月前
|
算法
【牛客周赛Round 27】题目讲解
【牛客周赛Round 27】题目讲解
加油，旭杏
31 1
iamzfh
|
5月前
Codeforces Round #567 (Div. 2)D. Irrigation(思维+二分)
【6月更文挑战第11天】
iamzfh
27 0
平凡@之路
codeforces#754（div2)A~D题解
codeforces#754（div2)A~D题解
平凡@之路
47 0
dm2e66eopcgq6
|
人工智能 BI CDN
【Codeforces Round #835 (Div. 4)】A——G题解
笔记
dm2e66eopcgq6
96 0
dm2e66eopcgq6
|
人工智能
【Codeforces Round #849 (Div. 4)】A~G题解
笔记
dm2e66eopcgq6
94 0
Crane
Codeforces Round 859 (Div. 4)题解
Codeforces Round 859 (Div. 4)题解
Crane
100 0
游客472mxcrxda2he
|
人工智能 BI
Codeforces Round #805 (Div. 3) 题解
Codeforces Round #805 (Div. 3) 题解
游客472mxcrxda2he
162 0
Codeforces Round #805 (Div. 3) 题解
zzqwtc
|
人工智能 BI
CodeForces Round #713 (Div. 3) F - Education (贪心)
笔记
zzqwtc
100 0
LightOf
|
机器学习/深度学习 人工智能 BI
Codeforces Round #751 (Div. 2) D. Frog Traveler（bfs 优化）
Codeforces Round #751 (Div. 2) D. Frog Traveler（bfs 优化）
LightOf
134 0

热门文章

最新文章

  • 1
    为什么lisp这么强大的语言用的人这么少
  • 2
    数据库中的Schema和Database的区别
  • 3
    MAVEN简介之——settings.xml
  • 4
    小技巧 - 怎样屏蔽群消息（包括 @全体成员）？
  • 5
    深度 ｜ 大数据算法应用的测试发展之路
  • 6
    RDS for SQL server 空间问题排查汇总
  • 7
    JavaScript基本数据类型分析
  • 8
    日本将举办VR食品研讨会，用音效模拟食物入口的质感
  • 9
    df查询磁盘容量
  • 10
    谷歌搜搜不谋而合 “情境搜索”或成未来趋势
  • 1
    如何根据性能检测结果进行 CSS 优化？
    27
  • 2
    如何检测 CSS 性能瓶颈并进行优化？
    29
  • 3
    CSS优化技巧
    28
  • 4
    如何在 JavaScript 中访问和修改 CSS 变量？
    30
  • 5
    CSS 变量的作用域和 JavaScript 变量的作用域有什么不同？
    31
  • 6
    如何在 CSS 变量中使用函数？
    22
  • 7
    CSS 变量的作用域是什么？
    17
  • 8
    京东面试：亿级黑名单 如何设计？亿级查重 呢？（答案含：布隆过滤器、布谷鸟过滤器）
    24
  • 9
    android做中大型项目完美的架构模式是什么？是MVVM吗？如果不是，是什么？
    18
  • 10
    如何使用 JavaScript 动态修改 CSS 变量的值？
    11

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 相册服务中的故事生成算法介绍
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 神经网络概览及算法详解
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析

    • 相关电子书

    更多
  • 图解算法小抄
  • 超全算法笔试 模拟题精解合集
  • 超全算法笔试-模拟题精解合集

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月