2018.10.22 练习赛 分治专练

T1 防线

题解：

拿到这道题,题目中提出奇数的个数少于等于一个(没有奇数就无解),我们可以很容易的利用好一个性质:一串偶数加上一个奇数必定是一个奇数;

我们二分一个奇数的位置,\(O(N)\)求前缀和,如果这个位置之前的和为奇数,那么我们将右边界左移,否则左边界右移;

\(code\):

#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#define lowbit(x) (x&-x)
#define ll long long
#define ld double
#define fuck puts("There's no weakness.")
#define mod 998244353 
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=x*10+tt-'0';
    if(flag) x=-x;
}

const int maxn=1000001<<1;
struct node{
	int x,y,w;
	inline node(int a=0,int b=0,int c=0)
	{x=a,y=b;w=c;}
}a[maxn];

int n,t,l=1,r;
bool ok(int x)
{
	int tot=0;
	for(int i=1;i<=n;i++)
	if(a[i].x<=x) tot+=((min(a[i].y,x)-a[i].x)/a[i].w)+1;
	return tot&1;
}

int cal(int x)
{
	int tot=0;
	for(int i=1;i<=n;i++)
	tot+=(a[i].x<=x&&a[i].y>=x&&(x-a[i].x)%a[i].w==0);
	return tot;
}

int main()
{
	//freopen("defend.in","r",stdin);
	//freopen("defend.out","w",stdout);
	read(t);
	while(t--)
	{
		read(n);
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++)
		{
			int x,y,z;
			read(x),read(y),read(z);
			a[i]=node(x,y,z);
			r=max(r,y);
		}
		bool flag=0;int ans=0;l=1;
		while(l<=r)
		{
			int mid=l+r>>1;
			if(ok(mid)){ans=mid,r=mid-1,flag=1;}
			else l=mid+1;
		}
		if(flag) printf("%d %d\n",ans,cal(ans));
		else fuck;
	}
	return 0;
}

T2 航运调度

题解：

显然两点之间的距离\(dis(t)\)是一个关于时间t二次函数开方,对于所有的点对所组成的二次函数,我们每个图像都有一个极值,这些极值所组成的函数依旧是一个单峰函数,否则这道题就多解了,三分一个时间,\(O(N^2)\)验证即可;

\(code:\)

#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#define lowbit(x) (x&-x)
#define ll long long
#define ld double
#define fuck puts("There's no weakness.")
#define mod 998244353 
#define eps 1e-7
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=x*10+tt-'0';
    if(flag) x=-x;
}

const int maxn=302;
struct node{
	ld x,y,a,b;
	inline node(ld t1=0,ld t2=0,ld t3=0,ld t4=0)
	{x=t1,y=t2,a=t3,b=t4;}
}a[maxn];

int n;
bool same(ld a,ld b){return fabs(a-b)<=eps;}
ld pow_(ld a)
{return a*a;}

ld cal(int i,int j,ld t)
{
	ld a1=a[i].a,b1=a[i].b,x1=a[i].x,y1=a[i].y;
	ld a2=a[j].a,b2=a[j].b,x2=a[j].x,y2=a[j].y;
	ld nowx1=a1*t+x1,nowy1=b1*t+y1;
	ld nowx2=a2*t+x2,nowy2=b2*t+y2;
	return pow_(nowx1-nowx2)+pow_(nowy1-nowy2);
}

ld fx(ld t)
{
	ld ans=0;
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
	ans=max(ans,cal(i,j,t));
	return sqrt(ans);
}

int main()
{
	//freopen("dis.in","r",stdin);
	//freopen("dis.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++)
	{
		ld x,y,aa,bb;
		read(x),read(y),read(aa),read(bb);
		a[i]=node(x,y,aa,bb);
	}
	ld l=0.0,r=1e9*1.0,lmid,rmid;
	while(!same(l,r))
	{
		lmid=l+(r-l)/3;
		rmid=r-(r-l)/3;
		if(fx(lmid)<=fx(rmid)) r=rmid;
		else l=lmid;
	}
	printf("%.2lf %.2lf",r,fx(r));
	return 0;
}

T3 分形之城

题解：

之前一直做不来这种题,这次下决心将它弄懂之后有一定的感悟\(,,,\)

对于这类分形递归的题,我们可以根据点数较少的图,找当前图点与上一张图的点之间的关系,找出的关系只要是一定程度上合理的,那么它必定对我们的每次递归都会成立;

设定一下递归边界即可;

\(code:\)

#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#define lowbit(x) (x&-x)
#define ll long long
#define ld double
#define fuck puts("There's no weakness.")
#define mod 998244353 
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=x*10+tt-'0';
    if(flag) x=-x;
}

ll a[32],cnt[32];
ld pow_(ld a){return a*a;}
void dfs(ll n,ll id,ld &x,ld &y)
{
    if(n==1)
    {
        if(id==1) x=1,y=1;
        if(id==2) x=1,y=3;
        if(id==3) x=3,y=3;
        if(id==4) x=3,y=1;
        return;
    }
    ld tx,ty;
    int flag=(id-1)/cnt[n]+1;
    if(flag==1)
	{
		dfs(n-1,id,tx,ty);
		x=ty,y=tx;
	}
	if(flag==2)
	{
		dfs(n-1,id-cnt[n],tx,ty);
		x=tx,y=a[n-1]+ty;
	}
    if(flag==3)
	{
		dfs(n-1,id-(cnt[n]<<1),tx,ty);
		x=a[n-1]+tx,y=a[n-1]+ty;
	}
    if(flag==4)
	{
		dfs(n-1,id-cnt[n]*3,tx,ty);
		x=a[n]-ty,y=a[n-1]-tx;
	}
}

ld cal(ld x1,ld y1,ld x2,ld y2)
{
    return sqrt(pow_(x1-x2)+pow_(y1-y2))*5;
}

ll n,aa,bb,t;
int main()
{
    read(t);a[1]=4,cnt[1]=1;
    for(int i=2;i<=31;i++)
    a[i]=a[i-1]<<1,cnt[i]=cnt[i-1]<<2;
    
    while(t--)
    {
        ld x1,x2,y1,y2;
        read(n),read(aa),read(bb);
		dfs(n,aa,x1,y1);
        dfs(n,bb,x2,y2);
        printf("%.0lf\n",cal(x1,y1,x2,y2));
    }
}
比赛杂项题解练习赛二分分形图分治

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

牛客练习赛91（并查集+二维偏序+二分）

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

数据结构与算法之PHP查找算法（二分查找）

二分查找模板（准确找定值）

浅谈二分的边界问题

P7715 「EZEC-10」Shape 题解

Proguard混淆之后行数LineNumber对不上问题解决

标签