测试

• 晚上考试,是 \(SCOI\ 2016\ Day\ 2\) 的题目.

妖怪

• 由于之前在洛谷上用三分水过去了,就很 \(naive\) 地打了一个三分就跑了.获得 \(10\) 分好成绩.
• 记 \(x=atk,y=dnf,k=\frac b a\) ,推下式子,有 \(strength(a,b)=x+y+x*k+y*\frac 1 k\).
• 注意到有一个我忘了的结论和这个形式很相似:过定点 \((x,y)\) ,斜率为 \(k\) 的直线在 \(x,y\) 轴上的截距之和为 \(x+y-x*k-y*\frac 1 k\).
• 于是改一下定义,记 \(k=-\frac b a<0\) ,则 \(strength(a,b)\) 即为截距之和.那么对于一个确定的斜率 \(k\) ,使得截距之和最大的那个点一定在凸包上.
• 于是先求一个凸包,再对凸包上每个点求一次可取的最小值即得答案.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

inline int read()

{

	int out=0,fh=1;

	char jp=getchar();

	while ((jp>'9'||jp<'0')&&jp!='-')

		jp=getchar();

	if (jp=='-')

		fh=-1,jp=getchar();

	while (jp>='0'&&jp<='9')

		out=out*10+jp-'0',jp=getchar();

	return out*fh;

}

const int MAXN=1e6+10;

int n;

int atk[MAXN],dnf[MAXN];

const double eps=1e-8;

struct v2{

	double x,y;

	v2(double x=0,double y=0):x(x),y(y){}

	v2 operator + (const v2 &rhs) const

		{

			return v2(x+rhs.x,y+rhs.y);

		}

	v2 operator - (const v2 &rhs) const

		{

			return v2(x-rhs.x,y-rhs.y);

		}

	inline double operator * (const v2 &rhs) const

		{

			return x*rhs.y-y*rhs.x;

		}

	double angle()

		{

			return atan2(y,x);

		}

	bool operator < (const v2 &rhs) const

		{

			return x==rhs.x?y<rhs.y:x<rhs.x;

		}

	v2 operator ^ (const double &lambda) const

		{

			return v2(x*lambda,y*lambda);

		}

	double slop()

		{

			return y/x;

		}

};

double calc(double k,v2 p)

{

	return p.x+p.y-k*p.x-p.y/k;

}

v2 p[MAXN],stk[MAXN],origin;

int tp=0;

int cmp(v2 a,v2 b)

{

	double a1=(a-origin).angle();

	double a2=(b-origin).angle();

	return a1==a2?a.x<b.x:a1<a2;

}

void ConvexHull()

{

	sort(p+1,p+1+n);

	for(int i=n;i>=1;--i)

		{

			while(tp>=2 && (stk[tp]-stk[tp-1])*(p[i]-stk[tp])<=0)

				--tp;

			stk[++tp]=p[i];

		}

}

int main()

{

//	freopen("monster.in","r",stdin);

//	freopen("monster.out","w",stdout);

	n=read();

	for(int i=1; i<=n; ++i)

		{

			atk[i]=read(),dnf[i]=read();

			p[i]=v2(dnf[i],atk[i]);

		}

	ConvexHull();

	double ans=2e9;

	for(int i=1;i<=tp;++i)

		{

			double k1=(i==tp?0:(stk[i]-stk[i+1]).slop());

			double k2=(i==1?-2e9:(stk[i]-stk[i-1]).slop());

			double k=-sqrt(1.0*stk[i].y/stk[i].x);

			if(k1>=k && k>=k2)

				ans=min(ans,calc(k,stk[i]));

			if(i!=tp && stk[i].y>stk[i+1].y)

				break;

			if(i!=tp)

				ans=min(ans,calc(k1,stk[i]));

		}

	printf("%.4lf\n",ans);

	return 0;

}

美味

• 这题之前写过虽然写得很丑,用主席树搞一搞即可,应该是相对最简单的.

围棋

• 考场上妄图用一些奇奇怪怪的 \(kmp\ +​\)容斥乱搞,无果,寻病终,获得 \(10​\) 分好成绩.