当前位置： 首页 > news >正文

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

news 来源：原创 2024/5/3 21:50:07

文章目录

  • 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

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个数异或的结果就为x,那么就可以令最后两个数为a|b 和b,这样最后的结果就为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;
}

相关文章：

  • 【打工人摸鱼系列】python做皮卡丘桌宠，工作都有效率了呢
  • 手写模拟spring扫描底层实现
  • 照片拼图软件哪个好？快来看看这几个软件
  • 力扣打卡之合并两个有序数组
  • 通过划分法优化共识算法-“Scaling Replicated State Machines with Compartmentalization”详解
  • C#进阶04——委托和事件
  • MySQL数据库 增删查改案例讲解
  • 【面试入门必刷】算法入门-数据结构-栈（一）
  • 《论文复现》MOJITALK: Generating Emotional Responses at Scale 部分过程讲解
  • GBase 8s 安全性（6）- 备份与恢复
  • 【人工智能】神经网络八股扩展
  • 如何获取大数据行业高薪岗位offer？
  • mac mongodb6.0.1安装
  • Spring常见问题解决 - @EnableWebMvc 导致自定义序列化器失效
  • 深入理解JVM（一）JVM与Java体系结构
  • 【翻译】Mashape是如何管理15000个API和微服务的（三）
  • axios 和 cookie 的那些事
  • CentOS学习笔记 - 12. Nginx搭建Centos7.5远程repo
  • CSS 三角实现
  • iOS 系统授权开发
  • Javascripit类型转换比较那点事儿，双等号（==）
  • k8s 面向应用开发者的基础命令
  • leetcode386. Lexicographical Numbers
  • LintCode 31. partitionArray 数组划分
  • Storybook 5.0正式发布：有史以来变化最大的版本\n
  • Stream流与Lambda表达式（三） 静态工厂类Collectors
  • Sublime Text 2/3 绑定Eclipse快捷键
  • 关于Flux,Vuex,Redux的思考
  • 记录：CentOS7.2配置LNMP环境记录
  • 看域名解析域名安全对SEO的影响
  • 前端设计模式
  • 前嗅ForeSpider采集配置界面介绍
  • 让你的分享飞起来——极光推出社会化分享组件
  • 如何用Ubuntu和Xen来设置Kubernetes？
  • 微信端页面使用-webkit-box和绝对定位时，元素上移的问题
  • 一个完整Java Web项目背后的密码
  •  一套莫尔斯电报听写、翻译系统
  • 一文看透浏览器架构
  • 译有关态射的一切
  • 云大使推广中的常见热门问题
  • 走向全栈之MongoDB的使用
  • 长三角G60科创走廊智能驾驶产业联盟揭牌成立，近80家企业助力智能驾驶行业发展 ...
  • ​sqlite3 --- SQLite 数据库 DB-API 2.0 接口模块​
  • ​ssh-keyscan命令--Linux命令应用大词典729个命令解读
  • ​Z时代时尚SUV新宠：起亚赛图斯值不值得年轻人买？
  • ​二进制运算符：（与运算）、|（或运算）、~（取反运算）、^（异或运算）、位移运算符​
  • ​中南建设2022年半年报“韧”字当头，经营性现金流持续为正​
  • #Spring-boot高级
  • $L^p$ 调和函数恒为零
  • （6）设计一个TimeMap
  • （6）添加vue-cookie
  • （Oracle）SQL优化技巧（一）：分页查询
  • (ZT)薛涌：谈贫说富
  • （笔试题）分解质因式
  • （第27天）Oracle 数据泵转换分区表