Educational Codeforces Round 92

比赛链接

D. Segment Intersections

题意

给定两种线段 $[l_a,r_a],[l_b,r_b]$ ，每种线段有 $n$ 条，记为 $a_1,a_2\cdots a_n$ 和 $b_1,b_2\cdots b_n$。

每次操作可以任选一条线段 $[l,r]$，将其变换成 $[l-1,r]$ 或 $[l,r+1]$。

要求输出最小操作步数，使得 $\sum_{i=1}^n f(a_i,b_i)\ge k$，其中 $f(a,b)$ 表示线段 $a,b$ 相交部分长度。

题解 1

暴力枚举 $i$，只考虑前 $i$ 对线段求出最小答案，时间复杂度 $O(n)$。

查看代码

int main()
{
	int t=read_int();
	while(t--){
		LL n=read_int(),k=read_int(),l1=read_int(),r1=read_int(),l2=read_int(),r2=read_int(),ans=1e10;
		LL tot=max(r1,r2)-min(l1,l2),d=max(l1,l2)-min(r1,r2);
		_rep(i,1,n){
			if(tot*i>=k)
			ans=min(ans,d*i+k);
			else
			ans=min(ans,(tot+d)*i+(k-tot*i)*2);
		}
		ans=max(ans,0LL);
		enter(ans);
	}
	return 0;
}

题解 2

分类讨论，时间复杂度 $O(1)$。

查看代码

int main()
{
	int t=read_int();
	while(t--){
		LL n=read_int(),k=read_int(),l1=read_int(),r1=read_int(),l2=read_int(),r2=read_int();
		if(l1>l2)
		swap(l1,l2),swap(r1,r2);
		if(r1>=r2){
			k-=n*(r2-l2);
			r1-=(r2-l2);
			r2=l2;
			swap(r1,r2);
		}
		else if(r1>=l2){
			k-=n*(r1-l2);
			swap(r1,l2);
			r2-=l2-r1;
			l2=r1;
		}
		if(k<=0){
			puts("0");
			continue;
		}
		int cost=2*(l2-r1),d=l2-r1,len1=r1-l1,len2=r2-l2;
		if(len1+len2+d==0){
			enter(k*2);
			continue;
		}
		if(k>=n*(len1+len2+d)){
			k-=n*(len1+len2+d);
			enter(n*(len1+len2+cost)+2*k);
			continue;
		}
		int ks=k/(len1+len2+d);
		k%=(len1+len2+d);
		if(ks>0)
		enter(ks*(len1+len2+cost)+min(2*k,d+k));
		else
		enter(d+k);
	}
	return 0;
}

E. Calendar Ambiguity

题意

求满足同余方程 $xd+y\equiv yd+x\pmod w$，其中 $1\le x,y\le n$。

题解

移项，得 $d(x-y)\equiv 0\pmod w$，记 $w'=\frac w{(w,d)}$，于是问题等价于 $w'\mid (x-y)$。

考虑枚举 $(x-y)=iw'$，于是满足条件的解个数为 $$\sum_{i=1}^{\lfloor\frac n{w'}\rfloor}n-iw'=n\lfloor\frac n{w'}\rfloor-\frac {\lfloor\frac n{w'}\rfloor(1+\lfloor\frac n{w'}\rfloor)}2\lfloor\frac n{w'}\rfloor w$$

时间复杂度 $O(\log(\min(w,d)))$。

查看代码

int main()
{
	int t=read_int();
	while(t--){
		int m=read_int(),d=read_int(),w=read_int(),n,k;
		w/=__gcd(w,d-1);
		n=min(m,d),k=n/w;
		enter(1LL*n*k-1LL*(1+k)*k*w/2);
	}
	return 0;
}

CVBB ACM Team

目录

Educational Codeforces Round 92

D. Segment Intersections

题意

题解 1

题解 2

E. Calendar Ambiguity

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

Educational Codeforces Round 92

D. Segment Intersections

题意

题解 1

题解 2

E. Calendar Ambiguity

题意

题解

页面工具