用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:contest:cf_700_div._1

这是本文档旧的修订版!


Codeforces Round #700 (Div. 1)

A. Searching Local Minimum

题意

给定一个 $1\sim n$ 的排列,最多允许 $100$ 次询问,每次可以询问指定位置的值。

要求找到一个 $i$ 满足 $a_i\lt a_{i-1}$ 且 $a_i\lt a_{i+1}$,假定 $a_0=a_{n+1}=\infty$。

题解

维护区间 $[l,r]$,满足 $a_l\lt a_{l-1},a_r\lt a_{r+1}$。于是当 $l=r$ 时答案位置确定。

接下来二分区间,如果 $a_m\lt a_{m+1}$,则将 $r$ 修改为 $m$,否则将 $l$ 修改为 $m$。于是可以使用 $\log n$ 次询问得到答案。

$ps.$ 比赛时乱搞了一个单测试点正确率为 $95\text{%}$ 的随机算法,我当时脑子指定是有什么问题。

查看代码

查看代码

int n;
int query(int pos){
	if(pos==n+1)
	return n+1;
	else{
		printf("? %d\n",pos);
		fflush(stdout);
		return read_int();
	}
}
void ans(int pos){
	printf("! %d\n",pos);
	fflush(stdout);
}
int main()
{
	n=read_int();
	int lef=1,rig=n,mid;
	while(lef<rig){
		mid=lef+rig>>1;
		if(query(mid)<query(mid+1))
		rig=mid;
		else
		lef=mid+1;
	}
	ans(lef);
	return 0;
}

C. Continuous City

题意

题解

查看代码

查看代码

 
2020-2021/teams/legal_string/jxm2001/contest/cf_700_div._1.1612855635.txt.gz · 最后更改: 2021/02/09 15:27 由 jxm2001