Codeforces Round 870 (Div. 2)【A、B、C、D】

news/2024/10/30 15:34:10/

文章目录

  • A. Trust Nobody(暴力)
  • B. Lunatic Never Content(数学)
  • C. Dreaming of Freedom(数学、暴力)
  • D. Running Miles(前缀、后缀)

传送门

A. Trust Nobody(暴力)

题意:给出n个人的陈述,每个人陈述至少有ai个人说谎,让你求出可能是说谎人数。
思路:(废话,可以不看,本来我考虑一种贪心的方法,假定xxx说的是真的,然后检验,发现wa2),我们可以观察到n很小,我们只需枚举说谎的情况即可,然后统计说谎人数是否符合,时间复杂度为n2,这题卡了很多人,主要还是思维定势,其实没什么难的。

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
using namespace std;
const int N = 105;
int a[N];
void solve() {int n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 0; i <= n; i++) {int cnt = 0;for (int j = 1; j <= n; j++) cnt += (i < a[j]);if (i == cnt) {cout << i << '\n';return;}}cout << -1 << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}

B. Lunatic Never Content(数学)

题意:给你一个数组,让你找到一个最大的模数x,对每一个数取模x,使得这个数组具有回文特性,找不到就输出0。
思路:首先什么时候没有最大的x,如果说已经符合回文特性的话,就可以取无穷大。如果不符合回文特性的话。我们考虑每一对对称不同的数。
推导:此处al为对称轴左侧,ar为对称轴有侧的数,r为余数,k1,k2为整数,x是模数。
a l ≡ r ( m o d x ) a_l\equiv r(mod~x) alr(mod x)
a r ≡ r ( m o d x ) a_r\equiv r(mod~x) arr(mod x)
a l = k 1 x + r a_l=k_1x+r al=k1x+r
a r = k 2 x + r a_r=k_2x+r ar=k2x+r
a l − a r = ( k 1 − k 2 ) x a_l-a_r=(k_1-k_2)x alar=(k1k2)x
x ∣ a l − a r x|a_l-a_r xalar
x是每对不同的差的因子,所以直接求最大公约数即可。

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
using namespace std;
const int N = 1e5 + 5;
int a[N];
void solve() {int n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];int gcd = 0;int l = 1, r = n;while (l < r) {if (a[l] != a[r]) {int d = abs(a[l] - a[r]);if (d) {if (!gcd) gcd = d;else gcd = __gcd(gcd, d); }}l++;r--;}cout << gcd << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}

C. Dreaming of Freedom(数学、暴力)

题意:n个人每人投一票,给m个算法,每次保留票数最多的算法,判断能否保证最后必定留下一个算法。
思路:总票数不变都是n,如果说当前剩下x种算法, n % x != 0 的话,说明至少会有一种算法会被淘汰,可以继续减少,如果说 n % x == 0,可以把票数平均分配,这样就全部保留了。我们考虑最坏的情况,(投票人故意每次投 n / x ,剩下一个 n % x,一个个淘汰),就必须保证,n 不会被 2~m的数整除。我们考虑根号分治,枚举因子。时间复杂度为tsqrt(n)。其实就是找到最小的质因子。

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
using namespace std;
const int N = 1e5 + 5;
void solve() {int n, m;cin >> n >> m;for (int i = 2; i * i <= n; i++) {if (n % i == 0 && i <= m) {cout << "NO\n";return;}}if (n <= m && n > 1) {cout << "NO\n";return;}cout << "YES\n";
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}

D. Running Miles(前缀、后缀)

题意:给出一个数组,你可以选取一个长度大于等于3的区间,value为区间内三个最大的值减去(r-l)。
关键:首先左右两端必定是最大的值中的两个。
证明:如果说左右区间两端不是最大值的两个,我们覆盖的区间更大,那么我们可以减去这两个最大的值外的值,增量不变,但是 r- l变小了,总的值更大了。
思路:上面可以表示为,value=a[l]+a[mid]+a[r]-r+l=a[mid]+a[r]-r+a[l]+l。只需预处理一下mid右侧的a[r]-r的情况,mid左侧a[l]+l的情况

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
using namespace std;
const int N = 1e5 + 5;
int l[N], r[N], a[N];
void solve() {int n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];l[1] = a[1] + 1;r[n] = a[n] - n;for (int i = 2; i <= n; i++) l[i] = max(l[i - 1], a[i] + i);for (int i = n - 1; i >= 1; i--) r[i] = max(r[i + 1], a[i] - i);int ans = -inf;for (int i = 2; i < n; i++) {ans = max(ans, a[i] + l[i - 1] + r[i + 1]);}cout << ans << '\n'; 
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}

http://www.ppmy.cn/news/62589.html

相关文章

【2023】华为OD机试真题全语言-题目0234-字符串重新排列

题目0234-字符串重新排列 题目描述 给定一个字符串s,s包括以空格分隔的若干个单词,请对s进行如下处理后输出: 单词内部调整:对每个单词字母重新按字典序排序单词间顺序调整: 统计每个单词出现的次数,并按次数降序排列次数相同,按单词长度升序排列次数和单词长度均相同…

防御DDoS袭击的高防服务器该如何选择?来看这7点

防御DDoS袭击的高防服务器该如何选择&#xff1f;互联网发展势头迅猛&#xff0c;但也催生了一些黑色利益链&#xff0c;那就是网络袭击&#xff0c;其中又以DDoS袭击最为普遍&#xff0c;也是最让运维人员头疼的袭击类型之一。如今的DDoS袭击动辄几十上百G的流量&#xff0c;普…

Figma转换为sketch,分享这3款工具

在我们的设计工作中&#xff0c;我们经常会遇到各种各样的设计文件相互转换的问题。 你经常为此头疼吗&#xff1f;当你遇到Figma转换Sketch文件的问题时&#xff0c;你是如何解决的&#xff1f;Figma转换Sketch文件有工具吗&#xff1f; 根据众多设计师的经验&#xff0c;本…

一次SQL的完整处理流程

流程&#xff1a; 1. 客户端到连接器是通过TCP/IP SSL通信协议连接的&#xff0c; 2.连接器验证MySQL权限信息是否正常&#xff0c;连接量是否正常&#xff0c;长时间没有连接服务器会自动断开等等 &#xff1b; 3. 然后到解析器&#xff0c;通过客户端发过来的sql进行语法解析…

PAT A1032 Sharing

1032 Sharing 分数 25 作者 CHEN, Yue 单位 浙江大学 To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, l…

Alertmanager集群搭建【共享配置文件docker版】

# 当集群中的Alertmanager节点不在一台主机时,通常需要使用--cluster.advertise-address参数指定当前节点所在网络地址 #共享alertmanager.yml配置文件,可以挂载到同一个目录下 version: "3" services: alertmanager1: image: prom/alertmanager:latest …

【Redis】概述与安装

概述 Redis 是什么&#xff1f; Redis&#xff08;Remote Dictionary Server )&#xff0c;即远程字典服务&#xff1b; 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库&#xff0c;并提供多种语言的 API。 Redis 会周期性的把…

ADRV9002官方例程开发过程中遇到的问题

开发环境&#xff1a;Vivado2021.2 HDL版本&#xff1a;hdl_2021_r2 GitHub - analogdevicesinc/hdl at hdl_2021_r2 no-OS版本&#xff1a;no_OS-2021_R2 GitHub - analogdevicesinc/no-OS at 2021_R2 &#xff08;PS&#xff1a;也可以用Vivado2019.1开发&#xff0c…