这是本文档旧的修订版！

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

题意

给定 $[L,R]$，要求构造一张有向图，图中最多有 $32$ 个点。

使得所有边均从编号小的点指向编号大的点，且从点 $1$ 到图中编号最大的点的所有路径权值互异，且正好构成集合 $[L,R]$。

题解

先将 $[L,R]$ 转化为 $[0,R-L]$，再想一个 $[0,2^k-1]$ 的构造，最后再调整一下就可以得到答案。

查看代码

const int MAXN=33;
struct Edge{
	int u,v,w;
};
vector<Edge> Edges;
int v[MAXN];
int main()
{
	int L=read_int(),R=read_int(),pos=31;
	puts("YES");
	_rep(i,2,32)Edges.push_back(Edge{1,i,L});
	for(int i=31;i>1;i--)v[i]=1<<(31-i);
	R-=L;
	while(R){
		int offset=v[pos];
		_for(i,pos+1,32){
			if(R>=v[i]){
				R-=v[i];
				Edges.push_back(Edge{pos,i,offset-v[i]});
				offset+=v[i];
			}
		}
		if(R){
			R--;
			Edges.push_back(Edge{pos,32,offset});
		}
		pos--;
	}
	printf("%d %d\n",32,(int)Edges.size());
	_for(i,0,Edges.size())
	printf("%d %d %d\n",Edges[i].u,Edges[i].v,Edges[i].w);
	return 0;
}

CVBB ACM Team

目录

Codeforces Round #700 (Div. 1)

A. Searching Local Minimum

题意

题解

C. Continuous City

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

Codeforces Round #700 (Div. 1)

A. Searching Local Minimum

题意

题解

C. Continuous City

题意

题解

页面工具