AtCoder Beginner Contest 354

news/2024/6/20 15:55:16

A - Exponential Plant (abc354 A)

题目大意

某星球上的植物,初始高\(0\),然后每天依次增长 \(1,2,4,8,...\),问哪天就高过身高为\(h\)的高桥。

解题思路

因为是指数级别长高,枚举一下天数即可,由于\(h \leq 10^9\),因此天数不会超过 \(32\)天。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;int main(void) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int x;cin >> x;++x;int cnt = 0;while (x) {cnt++;x >>= 1;}cout << cnt << '\n';return 0;
}


B - AtCoder Janken 2 (abc354 B)

题目大意

给定\(n\)个人的名字和分数。

按名字字典序给他们排序。

然后设他们总分数为 \(sum\),则第 \(sum % n\)位为赢家。

问谁是赢家。

解题思路

按照题意,给名字排序,对分数求和,取个模后找到对应人的名字即为答案。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;int main(void) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;int sum = 0;vector<pair<string, int>> a(n);for (auto& i : a) {cin >> i.first >> i.second;sum += i.second;}vector<int> id(n);iota(id.begin(), id.end(), 0);sort(id.begin(), id.end(),[&](int i, int j) { return a[i].first < a[j].first; });int win = id[sum % n];cout << a[win].first << '\n';return 0;
}


C - AtCoder Magics (abc354 C)

题目大意

\(n\)个卡牌,有对应的强度\(a_i\)和花费 \(c_i\)

对于两个卡牌 \(i,j\),如果 \(a_i > a_j\)\(c_i < c_j\),则卡牌 \(j\)会被丢弃。

不断进行如上操作,问最终的牌是哪些。

解题思路

对每个卡牌的代价\(c\)从小到大排序,然后依次考虑当前卡牌\(j\)是否要丢弃。

因为是按顺序枚举 \(j\),则 \(i < j\)的卡牌都满足 \(c_i < c_j\),如果存在\(a_i > a_j\),则说明当前卡牌要丢弃。

因为是存在,所以我们维护 \(\max_{1 \leq i < j}(a_i)\),一个前缀的强度最大值,如果 \(max_a > a_j\),说明当前卡牌 \(j\)要丢弃,否则就不用丢弃。

把不需要丢弃的卡牌放到一个数组里,然后输出即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;int main(void) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;vector<array<int, 2>> a(n);for (auto& x : a)cin >> x[0] >> x[1];vector<int> id(n);iota(id.begin(), id.end(), 0);sort(id.begin(), id.end(), [&](int i, int j) { return a[i][1] < a[j][1]; });vector<int> ans;int maxx = 0;for (auto x : id) {if (a[x][0] < maxx)continue;ans.push_back(x);maxx = max(maxx, a[x][0]);}cout << ans.size() << '\n';sort(ans.begin(), ans.end());for (auto x : ans) {cout << x + 1 << " ";}cout << '\n';return 0;
}


D - AtCoder Wallpaper (abc354 D)

题目大意

给定一个如下定义的二维网格。

area

给定一个矩形区域,问该区域的黑色部分面积的两倍是多少。

解题思路

非常好的图,让我不知所措

定眼一看,发现只有本质不同的两类行(注意图里的水平线仅在\(y\)是偶数的行),每行的形状具有循环节,循环节长度为\(4\)

因此我们只需考虑考虑两行,最多长度为\(3\)的区域,其余的面积可以直接通过循环节算出来。

一个是偶数行(\(y = 0 \to 1\)),从 \((0,0)\)来往\(x\)正方向看, 循环节为\(4\)的黑色面积的两倍分别为 \(2, 1, 0, 1\)。奇数行则为\(1, 2, 1, 0\)

因此矩形区域\((a,b) -> (c,d)\) ,考虑\(a \to c\)的偶数行,可以计算出其黑色面积的大小,一个是循环节的大小 \(\lfloor \frac{c - a}{4} \rfloor \times (2 + 1 + 1)\),然后是多余的一小部份长度\((c - a) \% 4\),这个直接暴力计算即可。然后再\(\times\)偶数行的数量。

同理计算出奇数行的面积大小\(\times\)奇数行的数量,两者的和即为答案。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;int main(void) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int a, b, c, d;cin >> a >> b >> c >> d;array<array<int, 4>, 2> area{{{2, 1, 0, 1}, {1, 2, 1, 0}}};int sum = 4;auto solve = [&](int odd, int l, int r, int h) {LL ss = 1ll * (r - l) / 4 * sum * h;int cnt = (r - l) % 4;while (cnt--) {int left = ((l % 4) + 4) % 4;ss += 1ll * area[odd][left] * h;l++;}return ss;};int odd = (abs(b) % 2);LL one = solve(odd, a, c, (d - b + 1) / 2);LL two = solve(odd ^ 1, a, c, (d - b) / 2);cout << one + two << '\n';return 0;
}


E - Remove Pairs (abc354 E)

题目大意

给定\(n\)张卡牌,每张卡牌正反各写一个数字,高桥和青木玩游戏,每回合,一个人可拿走两张正面数字一样或反面数字一样的卡牌。不能操作者人输。

高桥先,问两者绝顶聪明的情况下,谁赢。

解题思路

朴素的博弈\(dp\)。由于 \(n \leq 18\),可以直接设 \(dp[i]\)表示现在还有的卡牌情况(一个二进制压缩状态)是\(i\)的情况下,先手是必赢还是必输。

要看其是必输还是必赢,则需要看后继状态是否存在必输态,如果存在必输态,则当前状态\(i\)可以通过对应的转移变成先手必输态 \(j\)(从当前态 \(i\)来看就是后手必输了),则说明当前状态 \(i\)是必赢,即 \(dp[i] = 1\),否则如果所有后继状态都是必赢态,则说明当前是必输态,即 \(dp[i] = 0\)

而后继状态就是当前状态可以做的决策的转移,即选择两张正面数字一样或反面数字一样的卡牌拿走。花\(O(n^2)\)枚举下选择的两张牌即可。

总的时间复杂度是 \(O(n^22^n)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;int main(void) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;vector<array<int, 2>> a(n);for (auto& x : a)cin >> x[0] >> x[1];int up = (1 << n);vector<int> dp(up, -1);dp[0] = 0;auto dfs = [&](auto dfs, int s) -> int {if (dp[s] != -1)return dp[s];int ok = 0;for (int i = 0; i < n; i++) {if ((~s >> i) & 1)continue;for (int j = i + 1; j < n; j++) {if ((~s >> j) & 1)continue;if (a[i][0] != a[j][0] && a[i][1] != a[j][1])continue;ok |= !dfs(dfs, s ^ (1 << i) ^ (1 << j));}}return dp[s] = ok;};int ok = dfs(dfs, up - 1);if (ok) {cout << "Takahashi" << '\n';} else {cout << "Aoki" << '\n';}return 0;
}


F - Useless for LIS (abc354 F)

题目大意

给定一个数组\(a\)

对于每个数字 \(a_i\),问在\(a\)的最长上升子序列中,\(a_i\)是否存在其中。

多组询问。

解题思路

首先肯定要求一遍最长上升子序列的长度,由于\(n \leq 2e5\),得用\(O(n \log n)\)的求法,假设我们求得的长度是\(LIS\)

考虑如何判断 \(a_i\)是否存在最长上升子序列中。

考虑最朴素的求上升子序列的求法,即 \(dp[i]\)表示前 \(i\)个数字,我选择第\(i\)个数字的最长上升子序列的长度,转移则枚举上一个数字是哪个。

如果\(a_i\)可以成为最长上升子序列中,那说明什么?

\(1 \to i\)中,选择 \(a_i\),得到最长上升序列长度 \(dp[i]\), 如果它可以成为最长上升子序列,则说明\(i \to n\)的最长上升子序列长度是 \(LIS - dp[i] + 1\)。这相当于从右往左考虑的最长下降子序列 \(dp_2[i] = LIS - dp[i] + 1\)

因此我们只需要求出从左到有的最长上升子序列长度\(dp[i]\)和从右往左的最长下降子序列长度 \(dp_2[i]\)。然后对于每个 \(a_i\),如果 满足 \(dp[i] + dp_2[i] - 1 == LIS\),则说明 \(a_i\)会存在 \(a\)的最长上升子序列中。

那现在的问题就是如何求\(dp\)\(dp2\),朴素的 \(dp\)的求法是 \(O(n^2)\),对于这里的 \(n \leq 2e5\)会超时。

考虑 \(O(n \log n)\)的求法,事实上可以从这还原出\(dp\)

\(len[i]\)表示最长上升子序列长度为 \(i\)的末尾数字(最大数字)的最小值。(和上面的区别相当于把 \(dp\)的值作为状态,条件变成了值),注意到 \(len\)是一个递增的数组,因此对于当前数字\(a_i\) ,可以二分找到它可以接在哪个数字\(a_j\)的后面,进而知道了当前的\(dp[i]\),然后更新 \(len\)数组。

代码中求 \(dp2\)是将 \(a\)左右翻转然后全部取相反数,就相当于再求一个从左到右的最长上升子序列了。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;const int inf = 1e9 + 7;int main(void) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--) {int n;cin >> n;vector<int> a(n);for (auto& x : a)cin >> x;int LIS = 0;auto solve = [&](vector<int>& a) -> vector<int> {vector<int> dp(n + 1, inf), len(n, 1);dp[0] = -inf;for (int i = 0; i < n; ++i) {int pos = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();len[i] = pos;dp[pos] = min(dp[pos], a[i]);LIS = max(LIS, pos);}return len;};auto l = solve(a);reverse(a.begin(), a.end());for (auto& i : a)i *= -1;auto r = solve(a);reverse(r.begin(), r.end());vector<int> ans;for (int i = 0; i < n; ++i) {if (l[i] + r[i] - 1 == LIS)ans.push_back(i + 1);}cout << ans.size() << '\n';for (auto x : ans)cout << x << ' ';cout << '\n';}return 0;
}


G - Select Strings (abc354 G)

题目大意

给定\(n\)个字符串。字符串有价值。

选定一些字符串,使得字符串俩俩之间不存在子串的关系,最大化价值。

解题思路

首先可以花\(O(\max(n^2, (\sum |s|)^2))\) 求出俩俩字符串之间的不可选择关系。

剩下的问题就是有一个图,点有点权,点之间的连边表示不能同时选。然后选些点,点权值最大。

感觉很像一个最小割

神奇的代码



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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

相关文章

鸿蒙HarmonyOS实战-Stage模型(开发卡片页面)

🚀一、开发卡片页面 HarmonyOS元服务卡片页面(Metaservice Card Page)是指在HarmonyOS系统中,用于展示元服务的页面界面。元服务是指一组提供特定功能或服务的组件,例如天气服务、音乐播放服务等。元服务卡片页面可以显示元服务的相关信息和操作选项,用户可以通过点击卡…

连接池设计与实现一——以Golang Http1.1为例

0. 前言 连接池是一个非常重要的开发思想,如http client会构建连接池复用底层TCP连接,使用database/sql的使用也会有连接池的配置。那么代码底层是如何实现连接池的呢?这篇文档将以Golang语言为基础,分析http1.1连接池底层实现 ★ 注意:我们仅仅关注连接池设计思想、以及关…

Spring 面向切面编程AOP 详细讲解

1. Spring 面向切面编程AOP 详细讲解 @目录1. Spring 面向切面编程AOP 详细讲解每博一文案2. AOP介绍说明2.1 AOP的七大术语2.2 AOP 当中的 切点表达式3. 使用Spring 对 AOP 的实现使用3.1 准备工作3.2 Spring 基于AspectJ的AOP注解式开发3.2.1 实现步骤3.2.2 各个通知类型的说…

vulnhub - NYX: 1

标准攻击链vulnhub - NYX: 1 描述 这是一个简单的盒子,非常基本的东西。 它是基于vmware的,我不知道它是否可以在VB上运行,如果你愿意的话可以测试一下。 /home/$user/user.txt 和 /root/root.txt 下有 2 个标志。 信息收集 NYX靶ip:192.168.157.159 nmap -sT -sV -sC -O -p…

Vue3学习之项目工程初步了解

1.介绍项目工程,如在vscode中下图

因更懂你而更热爱,智慧PC助力当代每一位“霞客”行

“大丈夫当朝碧海而暮苍梧”,从小就立志游历天下的徐霞客,自公元1613年5月19日这天开始了一生的披荆斩棘。三十年时间素履而往,所有足迹凝练出了一本《徐霞客游记》,在地理学、地质学、文学、历史学中都占有重要一席。因热爱而出发,如果他生在当下,一定是中国最大的旅游博…

Pyqt6PySide6 事件与事件的处理函数

什么是事件? 事件是程序收到外界的输入,处于某种状态时自动发送的信号。事件有固定的类型,每种类型有自己的处理函数,用户只要重写这些函数,即可达到特定的目的。通过事件可以用一个控件监测另外一个控件,并可过滤被监测控件发出的事件。 事件的类型与处理函数 事件的概念…

C语言编程题练习 (从初识到入门再到进阶)修正版

C语言编程题练习 📔(从初识到入门再到进阶) 小飞机 🛬#include<stdio.h>int main() {printf(" ** \n");printf(" ** \n");printf("***************\n");printf("***************\n");printf("…