AtCoder Beginner Contest 352 A~E(F更新中...)

2024-05-05 12:36

本文主要是介绍AtCoder Beginner Contest 352 A~E(F更新中...),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A. AtCoder Line(判断)

题意

N N N个车站,列车的运行有两种方向,即 1 → n 1 \rightarrow n 1n n → 1 n \rightarrow 1 n1两种。

问,从 x x x点到 y y y点,仅乘坐一次列车,是否会经过站点 z z z

分析

判断 z z z点是否出现在 x x x点到达 y y y点的路线中即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;void solve() {int n, x, y, z;cin >> n >> x >> y >> z;if (x > y) {if (z >= y && z <= x) {cout << "Yes" << endl;} else {cout << "No" << endl;}} else {if (z <= y && z >= x) {cout << "Yes" << endl;} else {cout << "No" << endl;}}
}int main() {solve();return 0;
}

B.Typing(字符串匹配)

题意

有两个字符串,一个想要打出的字符串S,一个是实际打出字符串T,请你输出当前字符串T中正确字符所在的下标。

分析

进行双指针进行字符串匹配,每次匹配上后输出下标即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;void solve() {string s, t;cin >> s >> t;int len_s = s.size(), len_t = t.size();for (int i = 0, j = 0; i < len_t; i++) {if (s[j] != t[i]) {} else {cout << i + 1 << ' ';j++;}}
}int main() {solve();return 0;
}

C. Standing On The Shoulders(枚举)

题意

n n n个人,每个人有一个肩膀的高度以及头顶的高度。

你可以任意重排这 n n n个人,排序完成后,第一个人将站在地面上,后面的每一个人均站在前一个人的肩膀上,问,最优方案下,最高的人的头顶距离地面的最高高度是多少?

分析

观察发现,前 n − 1 n - 1 n1个人对最后高度的贡献只有他的肩膀高度,而最后一个人对最后高度的贡献只有他的头顶高度,因此,可以先统计所有人的肩膀高度之和,然后依次枚举每个人作为最后一个人的高度即可(即肩膀高度之和减去当前人的肩膀高度再加上头部高度)。

代码

#include<bits/stdc++.h>using namespace std;
typedef long long ll;struct Node {ll x, y;
} a[200005];void solve() {int n;cin >> n;ll sum = 0;for (int i = 0; i < n; i++) {cin >> a[i].x >> a[i].y;sum += a[i].x;}ll ans = 0;for (int i = 0; i < n; i++) {ans = max(ans, sum - a[i].x + a[i].y);}cout << ans << endl;
}int main() {solve();return 0;
}

D. Permutation Subsequence(滑动窗口+set)

题意

给出一个包含 1 ∼ n 1 \sim n 1n的一个排列,当你从这个排列中取出其中 k k k个数字,如果这 k k k个数字满足以下条件,那么就是一个好的序列:

  • 取出的数字下标分别为 i 1 , i 2 , … , i k i_1, i_2, \ldots, i_k i1,i2,,ik,且 i i < i 2 < … < i k i_i < i_2 < \ldots < i_k ii<i2<<ik

  • 将取出的 k k k个数字进行排序后,第一个数字为 a a a,后面的数字依次为 a + 1 , a + 2 , a + 3 , … , a + k − 1 a + 1, a + 2, a + 3, \ldots, a + k - 1 a+1,a+2,a+3,,a+k1

请你求出所有好的序列中, i k − i 1 i_k - i_1 iki1的最小值。

分析

不难想到,所有好的序列必然是将原数组排序,任取其中连续的 k k k个数字,那么难点就在于快速得到每一段区间对应的数字原本下标的最大最小值(数组同时记录数字以及数字开始时的下标)。

如果掌握线段树等计算区间极值的算法,就可以直接枚举区间计算答案。

以下给出一个特殊做法,固定一个长度为 k k k的窗口,并使用两个set维护区间内的数字所在的原下标,两个set一个从小到大排序,一个从大到小排序。这样,每次移动完窗口后,只需要取出两个set的第一个元素,就能知道区间内数字原本下标的最大最小值,每次更新区间的时间复杂度为 O ( l o g n ) O(logn) O(logn)

这样,记录所有窗口中的最大下标减最小下标的最小值即可。

Hint

可以通过 ∗ ( s e t . b e g i n ( ) ) *(set.begin()) (set.begin())获取set中的第一个元素

代码

#include<bits/stdc++.h>using namespace std;
typedef long long ll;struct Node{ll a, id;
}a[200005];ll n, k;set<int, greater<int> > st1;
set<int, less<int> > st2;void solve() {cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i].a;a[i].id = i;}int ans = INT_MAX;sort(a + 1, a + n + 1, [&](Node o, Node o1) {if (o.a != o1.a) return o.a < o1.a;return o.id < o1.id;});for (int i = 1; i <= k; i++) {st1.insert(a[i].id);st2.insert(a[i].id);}ans = *(st1.begin()) - *(st2.begin());for (int i = k + 1; i <= n; i++) {st1.erase((a[i - k].id));st1.insert(a[i].id);st2.erase((a[i - k].id));st2.insert(a[i].id);ans = min(ans, *(st1.begin()) - *(st2.begin()));}cout << ans << endl;
}int main() {solve();return 0;
}

E.Clique Connect(并查集)

题意

给出一个包含 n n n个点的图,你将会对这个图进行以下操作 M M M次:

  • 给出一个集合 S S S,以及一个费用 C C C,将所有属于集合中的点两两建边,所有边的边权均为 C C C.

完成操作后,问,这个图上的最小生成树的权值是多少?

分析

本题是并查集模板题。

由于每次对一个集合中建的边权都是相同的,那么不需要记录所有的边,只要要保证这个集合中的点连通即可,这里选择将每个点与集合中前一个点建边。

然后就是经典的Kruscal算法,将所有边按边权排序,然后按边权从小到达遍历边,并使用并查集进行维护,当两个点不在同一个集合中时,就在这两个点之间建边,并记录费用以及连的边数。

结束操作后,如果没有连上 n − 1 n - 1 n1条边,就说明不存在最小生成树,输出-1。否则,输出记录的费用。

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;struct Node{ll u, v, cost;friend bool operator < (const Node &o1, const Node &o2) {return o1.cost < o2.cost;}
}num[400005];ll n, m, cnt, ans, sum, f[400005];int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);
}void merge(Node node) {int fu = find(node.u);int fv = find(node.v);if (fu != fv) {f[fu] = fv;ans += node.cost;sum++;}
}int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int k, c;cin >> k >> c;int pre = -1;for (int j = 1; j <= k; j++) {int a;cin >> a;if (j > 1) {num[cnt++] = Node{pre, a, c};}pre = a;}}sort(num, num + cnt);for (int i = 1; i <= n; i++) f[i] = i;for (int i = 0; i < cnt; i++) {merge(num[i]);}if (sum != n - 1) {cout << -1 << endl;} else {cout << ans << endl;}return 0;
}

F.Estimate Order

更新中…

赛后交流

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

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

这篇关于AtCoder Beginner Contest 352 A~E(F更新中...)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/961733

相关文章

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

一文详解SQL Server如何跟踪自动统计信息更新

《一文详解SQLServer如何跟踪自动统计信息更新》SQLServer数据库中,我们都清楚统计信息对于优化器来说非常重要,所以本文就来和大家简单聊一聊SQLServer如何跟踪自动统计信息更新吧... SQL Server数据库中,我们都清楚统计信息对于优化器来说非常重要。一般情况下,我们会开启"自动更新

Redis缓存问题与缓存更新机制详解

《Redis缓存问题与缓存更新机制详解》本文主要介绍了缓存问题及其解决方案,包括缓存穿透、缓存击穿、缓存雪崩等问题的成因以及相应的预防和解决方法,同时,还详细探讨了缓存更新机制,包括不同情况下的缓存更... 目录一、缓存问题1.1 缓存穿透1.1.1 问题来源1.1.2 解决方案1.2 缓存击穿1.2.1

Linux Mint Xia 22.1重磅发布: 重要更新一览

《LinuxMintXia22.1重磅发布:重要更新一览》Beta版LinuxMint“Xia”22.1发布,新版本基于Ubuntu24.04,内核版本为Linux6.8,这... linux Mint 22.1「Xia」正式发布啦!这次更新带来了诸多优化和改进,进一步巩固了 Mint 在 Linux 桌面

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R

Ubuntu 24.04 LTS怎么关闭 Ubuntu Pro 更新提示弹窗?

《Ubuntu24.04LTS怎么关闭UbuntuPro更新提示弹窗?》Ubuntu每次开机都会弹窗提示安全更新,设置里最多只能取消自动下载,自动更新,但无法做到直接让自动更新的弹窗不出现,... 如果你正在使用 Ubuntu 24.04 LTS,可能会注意到——在使用「软件更新器」或运行 APT 命令时,

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :