USACO 2024年1月铜组 MAJORITY OPINION(思维 模拟)

2024-02-21 23:44

本文主要是介绍USACO 2024年1月铜组 MAJORITY OPINION(思维 模拟),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第一题:MAJORITY OPINION

标签:思维、模拟

题意:给定一个长度为 n n n的序列 a a a,操作:若区间 [ i , j ] [i,j] [i,j]内某个数字 k k k出现的次数 大于区间长度的一半,可以将区间内的所有数都换成这个数 k k k。经过多次操作之后,让区间 [ 1 , n ] [1,n] [1,n]内都为同一个数,输出所有可能的数(按照数字递增的顺序),若没有输出 − 1 -1 1。( 1 < = n < = 1 0 5 , 1 < = a i < = n 1<=n<=10^5,1<=a_i<=n 1<=n<=105,1<=ai<=n

题解:连续两个相同的数,不管是往前还是往后一个,都可以把加进来的数变成区间内的这个数。
比如 x y y z x\ y \ y \ z x y y z可以往前把 x x x变成 y y y,往后把 z z z变成 y y y,那其实再往前或者再往后 可以把所有数都变成 y y y
除此之外,还有 y x y y \ x\ y y x y的情况也是满足条件的,先把中间的这个 x x x变成 y y y,然后也可以把所有数都变成 y y y

最终就变成了求第 i i i数和 i − 1 i-1 i1个数或者第 i − 2 i-2 i2个数 是否相同,相同的话,就可以去作为我们的答案,当然可能有重复的情况,所以要去重输出。
代码

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int t, n, a[N], res[N];int main() {cin >> t;while (t--) {cin >> n;int c = 0;for (int i = 1; i <= n; i++) {cin >> a[i];if (i >= 2 && a[i] == a[i - 1]) res[++c] = a[i];else if (i >= 3 && a[i] == a[i - 2]) res[++c] = a[i];}sort(res + 1, res + 1 + c);c = unique(res + 1, res + 1 + c) - res - 1;if (c == 0) cout << -1 << endl;else {for (int i = 1; i < c; i++) {cout << res[i] << " ";}cout << res[c] << endl;}}return 0;
}

这篇关于USACO 2024年1月铜组 MAJORITY OPINION(思维 模拟)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

高效录音转文字:2024年四大工具精选!

在快节奏的工作生活中,能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候,一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具! 365在线转文字 直达链接:https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

usaco 1.3 Calf Flac(暴搜)

思路是暴搜。 需要注意的地方是输入的方法,以及输出时的换行。 代码: /*ID: who jayLANG: C++TASK: calfflac*/#include<stdio.h>#include<string.h>#include<math.h>int main(){freopen("calfflac.in","r",stdin);freopen("calfflac.ou

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

usaco 1.2 Palindromic Squares(进制转化)

考察进制转化 注意一些细节就可以了 直接上代码: /*ID: who jayLANG: C++TASK: palsquare*/#include<stdio.h>int x[20],xlen,y[20],ylen,B;void change(int n){int m;m=n;xlen=0;while(m){x[++xlen]=m%B;m/=B;}m=n*n;ylen=0;whi

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (