2019.10.26【NOIP提高組】模拟 A 組

T1：比賽的時候我以為想到了正解，但是調了很長時間之後我發現了錯誤。正解和我的方法還是有很大差别的。

正解如下：首先貪心算出ans。然後我們從前往後枚舉b的每一位放什麼。

對于第i位，我們把剩下沒有用過的b分成兩部分——小于等于a[i]的和大于a[i]的。那麼我們就可以二分兩次來求b[i]了。易證b的合法性在兩部分之中是有單調性的。至于判定，我們可以在二分除了mid之後再O(n)貪心做一遍剩下的數，求出第i為放mid的答案。

T2：這題我比賽時想到了正解，但是沒時間打了。

二分答案，然後我們發現剩下的就是一個掃描線問題。

具體操作不好講，還是看代碼吧：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define MAXN 50010
#define pi M_PI
using namespace std;

struct point
{
	double x;
	double y;
	ll rank;
	double v;
};
point a[MAXN];
struct sor
{
	double v;
	ll num;
};
sor b[MAXN];
ll f[MAXN],n;
double ans,k,w;
const double L=0.000000001;
int game1(const sor &a,const sor &b)
{
	if(a.v<b.v)return 1;
	else return 0;
}
int game2(const point &a,const point &b)
{
	if(a.v*w-b.v*w<0)return 1;
	if(a.v*w-b.v*w>0)return 0;
	if(a.y>b.y)return 1;
	else return 0;
}
ll sum(ll x)
{
	ll i=x,s=0;
	while(i>=1){s+=f[i];i=i-(i&(-i));}
	return s;
}
ll change(ll x)
{
	ll i=x;
	while(i<=n){f[i]++;i=i+(i&(-i));}
}
double find(ll num)
{
	ll i,j,s;
	double l,r;
	l=0;r=pi;
	while(l<=r)
	{
		k=(l+r)/2;w=tan(k);
		for(i=1;i<=n;i++)a[i].v=a[i].y-w*a[i].x;
		sort(a+1,a+n+1,game2);
		memset(f,0,sizeof(f));
		s=0;
		for(i=1;i<=n;i++)
		{
			s=s+sum(n)-sum(a[i].rank-1);
			change(a[i].rank);
		}
		if(s<=num-1)ans=k,l=k+L;
		else r=k-L;
	}
	return ans;
}
int main()
{
//freopen("line.in","r",stdin);
//freopen("line.out","w",stdout);
ll i,j,w=0;
scanf("%lld",&n);
for(i=1;i<=n;i++)scanf("%lf %lf",&a[i].x,&a[i].y);
for(i=1;i<=n;i++)b[i].v=a[i].y,b[i].num=i;
sort(b+1,b+n+1,game1);
for(i=1;i<=n;i++)
{
	if(b[i].v!=b[i-1].v||i==1)w++;
	a[b[i].num].rank=w;
}
if((n*(n-1)/2)%2==1)printf("%.10lf",find(n*(n-1)/2/2+1));
else printf("%.10lf",(find(n*(n-1)/2/2)+find(n*(n-1)/2/2+1))/2);
}
           

T3：首先假設我們已經建完圖了，那麼設g[i]表示有多少個j滿足j>i且i、j有連邊，那麼

。這是因為在i後面與i有連邊的所有點必定構成一個完全圖，是以這個完全圖中的點兩兩的顔色肯定是不同的，而i有與它們都有連邊，是以i就隻剩下了(n-g[i])中選擇。所有i的方案乘起來就是答案了。

那麼現在的問題就是求g，這裡有一個簡單的方法：

從前往後掃，對于每個點維護一棵線段樹，然後把i的線段樹合并到i後面與i最近的有連邊的點，這樣我們就可以在O(nlogn)的複雜度内構完圖。實作時可以線段樹合并，也可以set+啟發式合并（set維護每一個點連向的點）。