Codeforces Round 923(Div.3) A~G

A.Make it White (模拟)

题意：

给一个字符串 s s s，找出最左边的 B B B和最右边的 B B B，以这两个字母为左右端点的区间包含有多少个字母。

分析：

按照要求，遍历一遍字符串找到左右端点即可。

代码：

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int pos1 = 0, pos2 = n - 1;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'B') {
            pos1 = i;
            break;
        }
    }
    for (int i = n; i >= 0; i--) {
        if (s[i] == 'B') {
            pos2 = i;
            break;
        }
    }
    cout << max(0, pos2 - pos1 + 1) << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B.Following the String (贪心)

题意：

给出一个长度为 n n n的数组 a a a， a i a_i ai​表示 j < i j < i j<i的 s i = s j s_i=s_j si​=sj​出现的个数。询问是否存在字符串 s s s符合这个数组。

分析：

枚举 26 26 26个字母，每次贪心地放入字母即可。

代码：

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    string ans;
    vector<int> cnt(27, 0);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        for (int j = 0; j < 26; j++) {
            if (cnt[j] == x) {
                ++cnt[j];
                ans += char('a' + j);
                break;
            }
        }
    }
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C. Choose the Different Ones! (贪心)

题意：

给一个长度为 n n n的数组 a a a，一个长度为 m m m的数组 b b b，和一个偶数 k k k，询问能否从两个数组各取出 k / 2 k/2 k/2个数字，组成一个 1 − k 1-k 1−k的排列。

分析：

对于 1 − k 1-k 1−k的数字，如果只在 a , b a,b a,b中的一个数组中出现，那么就必须取，计算拿完这样的元素需要多少次，是否满足两个数组拿取的次数都满足小于等于 k / 2 k/2 k/2，其余元素随便取即可。

代码：

#include <bits/stdc++.h>

using namespace std;
map<int, int> map1, map2;

void solve() {
    int n, m, k, x;
    map1.clear();
    map2.clear();
    cin >> n >> m >> k;
    int cnt1 = k / 2, cnt2 = k / 2;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        map1[x]++;
    }
    for (int i = 1; i <= m; i++) {
        cin >> x;
        map2[x]++;
    }
    int flag = 0;
    for (int i = 1; i <= k; i++) {
        if (!map1.count(i) && !map2.count(i)) {
            flag = 1;
            break;
        } else if (map1.count(i) && !map2.count(i)) {
            cnt1--;
        } else if (map2.count(i) && !map1.count(i)) {
            cnt2--;
        }
    }
    if (cnt1 < 0 || cnt2 < 0 || flag)
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D.Find the Different Ones! (思维)

题意：

给一个长度为 n n n的数组 a a a， m m m次询问，每次询问给出一个区间 [ l , r ] [l,r] [l,r]，询问是否有 i , j i,j i,j满足以下条件：

  • l ≤ i , j ≤ r , a i ≠ a j l \le i,j\le r,a_i \neq a_j l≤i,j≤r,ai​=aj​

如果存在输出 i , j i,j i,j。

分析：

l e f t [ i ] left[i] left[i]维护 i i i左边第一个和自己不同的元素，每次询问判断是否 l e f t [ r ] < l left[r] < l left[r]<l 即可。

代码：

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2e5 + 5;
int a[MAXN], left1[MAXN];

void solve() {
    int n, q, l, r;
    cin >> n;
    left1[1] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 2; i <= n; i++) {
        if (a[i] != a[i - 1])
            left1[i] = i - 1;
        else
            left1[i] = left1[i - 1];
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> l >> r;
        if (left1[r] < l)
            cout << -1 << " " << -1 << endl;
        else
            cout << left1[r] << " " << r << endl;
    }
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E.Klever Permutation (思维)

题意：

给定两个整数 n , k n,k n,k，询问是否存在满足以下条件的合法排列：

  • 对所有满足 i + k − 1 ≤ n i+k-1 \le n i+k−1≤n的 i i i，每个区间 [ i − i + k − 1 ] [i-i+k-1] [i−i+k−1]的和中的最大值和最小值相差不超过 1 1 1。

分析：

设每个区间的和为 s [ i ] s[i] s[i]，那么需要构造成$s[i]-s[i-1]=1，s[i]-s[i]=-1 $交替这种形式。设前 4 4 4个元素为 a , b , c , d a,b,c,d a,b,c,d，那么可以想到如下构造： [ a , b , c , d , a + 1 , b − 1 , c + 1 , d − 1 , a + 2 , b − 2 , c + 2 , d − 2... ] [a,b,c,d,a+1,b-1,c+1,d-1,a+2,b-2,c+2,d-2...] [a,b,c,d,a+1,b−1,c+1,d−1,a+2,b−2,c+2,d−2...]即可。

代码：

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2e5 + 5;
int ans[MAXN];

void solve() {
    int n, k;
    cin >> n >> k;
    int flag1 = 1, num = 1, now = 1;
    while (now <= k) {
        if (flag1) {
            for (int i = now; i <= n; i += k) {
                ans[i] = num;
                ++num;
            }
        } else {
            for (int i = now + ((n - now) / k) * k; i >= 1; i -= k) {
                ans[i] = num;
                ++num;
            }
        }
        flag1 ^= 1;
        ++now;
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F.Microcycle (图论)

题意：

给出一张 n n n个点， m m m条边的无向简单图，图不一定联通，在其中寻找包含最小边的环，输出最小边的边权和环上的所有节点。

分析：

从小到大枚举边权，用并查集判断两个点是否在一个集合内，如果在，证明找到了在环内的最小边，从这两个点中任选一点出发开始 b f s bfs bfs，搜索并记录路径即可。

代码：

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 5e5 + 5;
vector<int> g[MAXN];

struct Node {
    int w, u, v;

    friend bool operator<(const Node &a, const Node &b) {
        if (a.w != b.w)
            return a.w > b.w;
        return a.u < b.u;
    }
} edge[MAXN];

int fa[MAXN];

int get(int x) {
    if (fa[x] != x)
        fa[x] = get(fa[x]);
    return fa[x];
}

void solve() {
    int n, m;
    vector<int> ans;
    queue<int> q;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        g[i].clear();
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[i] = {w, u, v};
        g[u].push_back(v);
        g[v].push_back(u);
    }
    sort(edge + 1, edge + m + 1);
    int a, b, tmp = 1e9;
    for (int i = 1; i <= m; i++) {
        auto [w, u, v] = edge[i];
        int tmp1 = get(fa[u]);
        int tmp2 = get(fa[v]);
        if (tmp1 == tmp2 && w < tmp) {
            a = u, b = v;
            tmp = w;
        }
        fa[tmp1] = tmp2;
    }
    q.push(a);
    vector<int> Depth(n + 1, 0);
    while (q.size()) {
        auto u = q.front();
        q.pop();
        for (auto v: g[u]) {
            if (Depth[v])
                continue;
            if (u == a && v == b)
                continue;
            if (v == a)
                continue;
            Depth[v] = Depth[u] + 1;
            q.push(v);
        }
    }
    int dep = Depth[b], fr = b;
    while (dep) {
        ans.push_back(fr);
        for (auto v: g[fr]) {
            if (Depth[v] == dep - 1) {
                dep--;
                fr = v;
                break;
            }
        }
    }
    ans.push_back(a);
    cout << tmp << " " << ans.size() << endl;
    for (auto v: ans)
        cout << v << " ";
    cout << endl;
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

G.Paint Charges (dp)

题意：

给定 n n n个格子， a i a_i ai​表示这个格子可以使用的颜料数量。每次操作可以选定一个格子，并选择将 [ m a x ( i − a i + 1 , 1 ) , i ] [max(i-a_i+1,1),i] [max(i−ai​+1,1),i]或者 [ i , m i n ( i + a i − 1 , n ) ] [i,min(i+a_i-1,n)] [i,min(i+ai​−1,n)]的格子涂色，每个格子可以被涂色多次，询问将 [ 1 , n ] [1,n] [1,n]所有格子都涂上颜色的最少操作次数。

分析：

设 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示当使用前 i i i个元素，最左侧未填充位置是 j j j ，最右侧已填充位置是 k k k，所需要的最小操作数。有以下三种情况：

  • 不进行操作的状态转移： d p [ i ] [ j ] [ k ] = m i n ( d p [ i ] [ j ] [ k ] , d p [ i − 1 ] [ j ] [ k ] ) ; dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]); dp[i][j][k]=min(dp[i][j][k],dp[i−1][j][k]);

  • 向左填充的状态转移，需要根据 i , j , k , l i,j,k,l i,j,k,l大小进行讨论。

  • 向右填充的状态转移，需要根据 i , j , k , r i,j,k,r i,j,k,r大小进行讨论。

代码：

#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;
int a[105];
int dp[105][105][105];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 0; i <= n; i++) {
        for (int j = 1; j <= n + 1; j++) {
            for (int k = 0; k <= n; k++) {
                dp[i][j][k] = INF;
            }
        }
    }
    dp[0][1][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + 1; j++) {
            for (int k = 0; k <= n; k++) {
                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]);
                int l = max(i - a[i] + 1, 1);
                if (l <= j) {
                    int tmp1 = max(i, k);
                    dp[i][tmp1 + 1][tmp1] = min(dp[i][tmp1 + 1][tmp1], dp[i - 1][j][k] + 1);
                }
                int r = min(i + a[i] - 1, n);
                if (j < i) {
                    dp[i][j][max(k, r)] = min(dp[i][j][max(k, r)], dp[i - 1][j][k] + 1);
                } else {
                    int tmp1 = max(k, r);
                    dp[i][tmp1 + 1][tmp1] = min(dp[i][tmp1 + 1][tmp1], dp[i - 1][j][k] + 1);
                }
            }
        }
    }
    cout << dp[n][n + 1][n] << endl;
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/387408.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

TCP高频知识点

TCP高频知识点

本篇文章主要讲述一下在面试过程中TCP的高频知识点 1.TCP三次握手流程图: 客户端发送一个SYN&#xff08;同步&#xff09;报文段给服务器&#xff0c;选择一个初始序列号&#xff0c;并设置SYN标志位为1。服务器接收到客户端的SYN报文段后&#xff0c;回复一个ACK&#xff08…
阅读更多...
AI短视频一键换脸小程序源码/带流量主

AI短视频一键换脸小程序源码/带流量主

微信云开发AI一键视频换脸小程序源码是由极客二改后发布的&#xff0c;小程序增加了广告控制&#xff0c;插屏广告&#xff0c;激励广告和原生广告&#xff0c;由于采用了微信云开发没有后台&#xff0c;所以不需要域名和服务器也可以正常搭建使用&#xff0c;所有的配置都可以…
阅读更多...
面试技术栈 —— 2024网易雷火暑期实习真题

面试技术栈 —— 2024网易雷火暑期实习真题

面试技术栈 —— 2024网易雷火暑期实习真题 1. 最长递增子序列。2. 集中限流和单机限流你觉得哪个好&#xff1f;3. redis部署服务器配置&#xff0c;为什么不用哨兵&#xff1f;4. 讲讲分布式session的原理。5. 数据库&#xff1a;表数据量大了&#xff0c;如何分表&#xff1…
阅读更多...
FT2232调试记录（1）

FT2232调试记录（1）

FT2232调试记录&#xff08;1&#xff09; FT2232调试记录&#xff08;2&#xff09; FT2232调试记录&#xff08;3&#xff09; &#xff08;1&#xff09;FT2232简介&#xff1a; FT2232是一种通用的USB转串口芯片&#xff0c;用于在计算机和外部设备之间建立通信连接。它…
阅读更多...
Hive的相关概念——架构、数据存储、读写文件机制

Hive的相关概念——架构、数据存储、读写文件机制

目录 一、架构及组件介绍 1.1 Hive整体架构 1.2 Hive组件 1.3 Hive数据模型&#xff08;Data Model&#xff09; 1.3.1 Databases 1.3.2 Tables 1.3.3 Partitions 1.3.4 Buckets 二、Hive读写文件机制 2.1 SerDe 作用 2.2 Hive读写文件流程 2.2.1 读取文件的过程 …
阅读更多...
VS Code主题设置（美化VS Code）（主题+背景+图标+特效+字体）

VS Code主题设置（美化VS Code）（主题+背景+图标+特效+字体）

目录 切换整体主题&#xff08;整体主题&#xff09; 切换文件图标主题 设置VS Code背景图案 字体特效 连击特效 字体设置 主题的具体效果放在了文章末尾&#xff0c;这篇文章后续也会进行更新 ————————————————————————————…
阅读更多...
探讨深度学习

探讨深度学习

深度学习 深度学习概述进展崛起框架 主页传送门&#xff1a;&#x1f4c0; 传送 深度学习 概述 深度学习是机器学习领域的一个分支&#xff0c;它是一种基于人工神经网络的学习方法&#xff0c;旨在让 计算机模仿人类大脑的神经结构和学习方式&#xff0c;从大量数据中学习并…
阅读更多...
主板指示灯亮着，电脑却无法开机怎么办？这里提供几个解决方法

主板指示灯亮着，电脑却无法开机怎么办？这里提供几个解决方法

如果你的电脑无法开机，但主板指示灯亮着，最可能的原因可能是机箱上的电源按钮有故障。或者，连接按钮和主板电源开关头的接线坏了。在这种情况下，你仍然可以启动电脑。 但是，如果备用启动方法失败，你可能正在处理有故障的硬件部件。但是，你可以查找POST代码或将零件与备…
阅读更多...
MATLAB实现朴素贝叶斯分类

MATLAB实现朴素贝叶斯分类

朴素贝叶斯&#xff08;Naive Bayes&#xff09;是一种基于贝叶斯定理的分类算法&#xff0c;它假设特征之间相互独立&#xff0c;从而简化了计算复杂性。该算法常用于文本分类、垃圾邮件过滤、情感分析等应用场景。 MATLAB实现鸢尾花数据集分类代码如下&#xff1a; clear lo…
阅读更多...
Web基础01-HTML+CSS

Web基础01-HTML+CSS

目录 一、HTML 1.概述 2.html结构解析 3.HTML标签分类 4.HTML标签关系 5.HTML空元素 6.HTML属性 7.常用标签 &#xff08;1&#xff09;HTML标签 &#xff08;2&#xff09;标题标签 &#xff08;3&#xff09;换/折行标签 &#xff08;4&#xff09;段落标签 &am…
阅读更多...
相机图像质量研究(12)常见问题总结：光学结构对成像的影响--炫光

相机图像质量研究(12)常见问题总结：光学结构对成像的影响--炫光

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…
阅读更多...
blender在几何节点中的这些变换中的旋转，其实可以是两种旋转顺序

blender在几何节点中的这些变换中的旋转，其实可以是两种旋转顺序

看似xyz的旋转角度&#xff0c;但如果按照欧拉角来谈它的旋转&#xff0c;就大有学问了。 我们知道&#xff0c;在blender中有局部旋转和全局旋转。但其实这两者在某种情况下可以等价。 那就是&#xff0c;如果参照全局坐标系&#xff0c;按xyz的顺序进行欧拉旋转&#xff0c;…
阅读更多...
宝宝起名神器小程序源码/支持多种流量主模式

宝宝起名神器小程序源码/支持多种流量主模式

还不知道怎么给虎宝宝取名字么&#xff1f;那么这款小程序源码就可以帮到你了&#xff0c;这款小程序支持输入姓氏自动起名。 不满意还可以点击换一换来找到满意的&#xff0c;支持起两个字或者三个字的名字。另外也给该款小程序添加了几个流量主位置&#xff01;&#xff01;…
阅读更多...
【Java】零基础蓝桥杯算法学习——二分查找

【Java】零基础蓝桥杯算法学习——二分查找

算法模板一: // 数组arr的区间[0,left-1]满足arr[i]<k,[left,n-1]满足arr[i]>k;Scanner scan new Scanner(System.in);int[] arr {1,2,3,4,5};int left 0,right arr.length-1;int k scan.nextInt();while(left<right) {//leftright时退出循环int mid (leftrigh…
阅读更多...
Python爬虫——解析库安装（1）

Python爬虫——解析库安装（1）

目录 1.lxml安装2.Beautiful Soup安装3.pyquery 的安装 我创建了一个社区&#xff0c;欢迎大家一起学习交流。社区名称&#xff1a;Spider学习交流 注&#xff1a;该系列教程已经默认用户安装了Pycharm和Anaconda&#xff0c;未安装的可以参考我之前的博客有将如何安装。同时默…
阅读更多...
吃瓜 - 春山学

吃瓜 - 春山学

2024年春晚看似一个贵州献上的歌舞节目《上春山》&#xff08;白敬亭、魏大勋、魏晨合唱&#xff09;引发网络破案&#xff1a;白敬亭有没有抢C位和故意换衣服&#xff1f;网上的“白敬亭春晚走位风波”不断升级&#xff0c;喂到嘴里的瓜不吃也不行啊。 三人都是明侦的元老嘉…
阅读更多...
【OrangePi Zero2 智能家居】智能家居项目的软件实现

【OrangePi Zero2 智能家居】智能家居项目的软件实现

一、项目整体设计 二、项目代码的前期准备 三、实现语音监听接口 四、实现socket监听接口 五、实现烟雾报警监听接口 六、实现设备节点代码 七、实现接收消息处理接口 一、项目整体设计 整体的软件框架大致如下&#xff1a; 整个项目开启4个监听线程&#xff0c; 分别是&…
阅读更多...
DFM-无监督图像匹配

DFM-无监督图像匹配

DFM&#xff1a;A Performance Baseline for Deep Feature Matching&#xff08;深度特征匹配的性能基准&#xff09; 2021.06.14 摘要 提出了一种新的图像匹配方法&#xff0c;利用现成的深度神经网络提取的学习特征来获得良好的图像匹配效果。该方法使用预训练的VGG结构作为…
阅读更多...
一周学会Django5 Python Web开发-项目配置settings.py文件-基本配置

一周学会Django5 Python Web开发-项目配置settings.py文件-基本配置

锋哥原创的Python Web开发 Django5视频教程&#xff1a; 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计17条视频&#xff0c;包括&#xff1a;2024版 Django5 Python we…
阅读更多...
AJAXJSON入门篇

AJAXJSON入门篇

AJAX&JSON 概念&#xff1a;AJAX(Asynchronous JavaScript And XML):异步的JavaScript和XML AJAX作用&#xff1a; 与服务器进行数据交换&#xff1a;通过AJAX可以给服务器发送请求&#xff0c;并获取服务器响应的数据 使用了AJAX和服务器进行通信&#xff0c;就可以使用H…
阅读更多...
最新文章

Copyright @ 2022~2023