本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-11 22:48:58

题外话

赛时 C 题先是被卡了 40min，然后感觉没希望滚去做 E，然后没做出来，又跳回 C，又思考了 10min，找不出错，随手输入了一组数据结果 Successful hack，然后我对着这组 hack 数据改，最终将其 AC。此时还剩下 7min，去看了下 D，看上去很简单的样子，可是没时间做了。赛后把 D 题切了

又掉了大分

A

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	int a[3][3];
	int r,c;
	void main()
	{
		cin>>r>>c;
		cin>>a[1][1]>>a[1][2];
		cin>>a[2][1]>>a[2][2];
		cout<<a[r][c];
	}
}
int main()
{
	Main::main();
	return 0;
}

B

对于每个人，$O(k)$ 计算照亮他的最小光照半径，记为 $p_i$。
答案就 $p$ 数组的最大值

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const int maxn=1005;
	int a[maxn];
	ll x[maxn],y[maxn];
	map<int,bool> im;
	double problem[maxn];
	int n,k;
	double dis(ll x,ll y,ll x2,ll y2)
	{
		double c1=double(x-x2);
		double c2=double(y-y2);
		return sqrt(c1*c1+c2*c2);
	}
	void main()
	{
		cin>>n>>k;
		for(int i=1;i<=k;i++)
		{
			cin>>a[i];
			im[a[i]]=1;
		}
		for(int i=1;i<=n;i++)
		{
			cin>>x[i]>>y[i];
			problem[i]=1e9;	
		}
		double ans=0.0;
		for(int i=1;i<=k;i++)
		{
			double col=0;
			problem[a[i]]=0;
			for(int j=1;j<=n;j++)
			{
				if(im[j])continue;
				problem[j]=min(problem[j],dis(x[j],y[j],x[a[i]],y[a[i]]));
			}
		}
		for(int i=1;i<=n;i++)
		{
			ans=max(ans,problem[i]);
		}
		printf("%.10lf",ans);
	}
}
int main()
{
	Main::main();
	return 0;
}

C

这道题需要分成 $d \ge 0$ 和 $d \le 0$ 两种情况讨论

• $d \ge 0$
  考虑一下极端情况，$x$ 可能会超出数列的最大元素或小于数列的最小元素，此时要进行特判
  普通情况下（$x$ 处于数列的最大元素与最小元素之间），那就计算出 $x$ 与其在数列中的最接近的元素的差的绝对值
• $d \le 0$
  总体思路和 $d \ge 0$ 的情况一样，不过计算最大元素和最小元素的部分要改变。

代码（赛时的代码不是给人看的，格式化了一下）：

#include <bits\/stdc++.h>
using namespace std;
namespace Main {
	typedef __int128 ll;
	void main() {
		long long x,a,d,n;
		cin>>x>>a>>d>>n;
		if(d>=0) {
			ll imax=a+ll(n-1)*(ll)d;
			\/\/-----------极端情况---------- 
			if(x<=a) {
				cout<<(long long)(a-x);
				return;
			}
			if(x>=imax) {
				cout<<(long long)(x-imax);
				return;
			}
			\/\/-----------蒲通的情况------------- 
			ll ans1=(x-a)%d;\/\/靠左 
			ll ans2=abs(d-(x-a)%d);\/\/靠右 
			cout<<(long long)(min(ans1,ans2));
		} else {\/\/d<0
			ll imin=a+ll(n-1)*(ll)d;
			if(x>=a) {
				cout<<(long long)(x-a);
				return;
			}
			if(x<=imin) {
				cout<<(long long)(imin-x);
				return;
			}
			ll ans1=abs((x-a)%d);
			ll ans2=abs(abs(d)-abs((x-a)%d));
			cout<<(long long)(min(ans1,ans2));
		}
	}
}
int main() {
	Main::main();
	return 0;
}

D

这道题看完了之后，肯定感觉：“要是所有的元素全都大于等于 $x_i$ 或者全都小于 $x_i$ 就好了”
为了创建这种条件，考虑将它们分成两组，一组全部大于等于 $x_i$，一组全部小于 $x_i$。 现在的瓶颈就在于如何快速分开。显然如果暴力分的话是 $O(n)$ 的，乘上 $q$ 就爆了。
但是如果预先排一下序，那么每次询问就能以 $O(logn)$ 的复杂度找到分割点。 然后这道题就做出来了

代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const int maxn=2e5+5;
	int n,q;
	ll a[maxn];
	ll qzh[maxn];
	void main()
	{
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			qzh[i]=qzh[i-1]+a[i];
		}
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++)
		{
			qzh[i]=qzh[i-1]+a[i];
		}
		ll xi;
		for(int i=1;i<=q;i++)
		{
			scanf("%lld",&xi);
			int pos=lower_bound(a+1,a+n+1,xi)-a;
			if(pos==-1)
			{
				ll ans=(xi*n)-qzh[n];
				printf("%lld\n",ans);
				continue;
			}
			ll ans=0;
			ans+=xi*(pos-1)-qzh[pos-1];
			ans+=(qzh[n]-qzh[pos-1])-xi*(n-pos+1);
			printf("%lld\n",ans);
		}
	} 
}
int main()
{
	Main::main();
	return 0;	
}