首页 > 其他分享 >题解:CF1349B Orac and Medians

题解:CF1349B Orac and Medians

时间:2024-07-22 19:28:45浏览次数:17  
标签:ch puts 相邻 int 题解 CF1349B read flag Orac

洛谷 | CF

刷一些 CF2000,进行一个录的记。

思路记录

  1. 首先观察到数列里的数不能凭空产生,所以初始序列必须含 \(k\)。
  2. 由于两个数的中位数是较小的那个,所以只要有一个与数列里的 \(k\) 相邻且比 \(k\) 大的数,就可以扩展到整个序列。
  3. 发现可以把第二条推广一下,不必要和 \(k\) 相邻,因为只要有两个相邻的比 \(k\) 大的数,就可以进行扩展到与 \(k\) 相邻。
  4. 问题就来到了如何产生一段长度大于 \(1\) 的比 \(k\) 大的数列。第三条是一种方法,还有一种就是两个大于 \(k\) 的数之间间隔一个任意数。(可以自己造几组样例手玩一下)

至此问题就得到了解决,一组数据时间复杂度 \(\mathcal{O(n)}\)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read();
int T;
int n,k,a[N];
int main()
{
	T=read();
	while(T--)
	{
		bool flag=0;
		n=read();k=read();
		for(int i=1;i<=n;i++) a[i]=read();
		if(n==1&&a[1]==k) {puts("yes");continue;}
		for(int i=1;i<=n;i++) if(a[i]==k) flag=1;
		if(!flag) {puts("no");continue;}
		else flag=0;
		for(int i=2;i<=n;i++)
		{
			if(a[i-1]>=k&&a[i]>=k) {puts("yes"),flag=1;break;}
		} 
		if(!flag)
		for(int i=2;i<n;i++)
		{
			if(a[i-1]>=k&&a[i+1]>=k) {puts("yes"),flag=1;break;}
		}
		if(!flag) puts("no");
	}
	return 0;
}

inline int read()
{
	int x=0,f=1;
	char ch;
	ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')
	{
		x=(x<<1)+(x<<3)+(ch&15);
		ch=getchar();
	}
    return x*f;
}


标签:ch,puts,相邻,int,题解,CF1349B,read,flag,Orac
From: https://www.cnblogs.com/yzxgg/p/18316743

相关文章

  • Linux-shell脚本链接Oracle执行查询
    #!/bin/bash#zkm2024-07-22Linux脚本链接Oracle数据库,用户判断sftp、ftp生成文件目录是否为空,若为空则短信表插入一条数据,用于短信提醒。#注意:#1、当前服务器需要安装Oracle客户端#2、sqlplus验证连接Oracle正常#当前时间date_time=`date+"%Y%m%d%H%M"`#输出时间echo"开......
  • Oracle 到 MySQL 函数替换方案汇总
    常用函数和语法转换  NVL函数Oracle语法:NVL(COUNT(*),0)MySQL语法:IFNULL(COUNT(*),0) 转字符串 Oracle语法:to_char(字段)MySQL语法:CONVERT(字段,CHAR) Rownum递增 Oracle语法:SELECTrownumnumFROMSYS_ENUMMySQL语法:SELECT(@i:=@i......
  • SLF4J: Class path contains multiple SLF4J bindings 问题解决
    背景:springboot项目名称test,在使用slf4j后,服务启动报错 报错信息:SLF4J:ClasspathcontainsmultipleSLF4Jbindings.SLF4J:Foundbindingin[jar:file:/D:/Program%20Files/Java/.m2/repository/ch/qos/logback/logback-classic/1.2.7/logback-classic-1.2.7.jar!/or......
  • [CEOI2018] Lottery 题解
    前言题目链接:洛谷。题意简述给出序列\(a_1\ldotsa_n\)和常数\(l\leqn\),定义:\[\operatorname{dis}(i,j)=\sum_{k=0}^{l-1}[a_{i+k}\neqa_{j+k}]\qquad(i,j\in[1,n-l+1])\]每次询问一个\(k\),求对于所有\(i\in[1,n-l+1]\),求\(\sum......
  • [COCI2015-2016#1] RELATIVNOST 题解
    前言题目链接:洛谷。这道题有很多做法,但是模拟赛寄了,故记之。题意简述给你两个长为\(n\)的序列\(A\)和\(B\),和一个常数\(c\leq20\),有\(q\)次修改。每次修改后求:\[\large\sum_{S\subseteq\lbracei\rbrace_{i=1}^{n}\land|S|\geqc}\prod_{x\inS......
  • [ARC176E] Max Vector 题解
    题目链接点击打开链接题目解法这个题的一个转化很关键:把一次操作\(j\)等价看作必须满足\((\forall_{1\lei\len}X_i\gea_{j,i})|(\forall_{1\lei\len}Y_i\gea_{j,i})=1\)正确性是显然的另外的一个关键思路是网络流有了上面的转化,我们考虑切糕模型(其实接下来都好想......
  • 题解 B3694 数列离散化
    link简而言之,离散化就是把一个数列转化为由小到大的排名来缩小范围。离散化需要这个题不用数字本身。举个例子:-200244879914993235793离散化后就是:15243\(-2002\)最小,所以它对应\(1\)\(448799\)最大,所以它对应\(5\)实现考虑如何实现。首先由于离散化前后......
  • 【Web】ImaginaryCTF 2024 部分题解
    目录journalcrystalsP2CreadmeTheAmazingRacejournal简单的assert命令拼接payload:?file=test','..')===true||system("echo`tac/flag-cARdaInFg6dD10uWQQgm.txt`")||strpos('testcrystalsdocker-compose.yml里让服务报错读到泄露的hos......
  • 题解:牛客周赛 Round 52 A
    A两数之和时间限制:C/C++1秒,其他语言2秒空间限制:C/C++262144K,其他语言524288KSpecialJudge,64bitIOFormat:%lld题目描述对于给定的正整数\(z\),你需要寻找两个不同的正整数\(x\)和\(y\),使得\(x+y=z\)成立。如果不存在这样的\(x\)和\(y\),你只需要输出NO。......
  • ABC363 DEF 题解
    ABC363DEF题解前情提要:赛时过了ABCE。D-PalindromicNumber题目链接其实赛时已经看出了一些性质,但没想完做法,赛后看题解才发现这么简单/fn首先,为了方便,我们不把\(0\)视作回文数(因此需要特判一下\(n=1\)的情况)。下面要证明:\(d\)位回文数有\(10^{\left\lfloor\f......