T1

这道题我直接切了

但是正解是(O(n)),我打的是(O(nlogn))

#include<cstdio>
#include<iostream>
#include<algorithm>
#define ri register int
#define Starseven main
#define mid (l+r>>1)
#define ls id<<1
#define rs id<<1|1
#define int long long
using namespace std;
const int N=5e5+20;
int read();
void write(int);
int n,t,mall,ans[N];

//----------------------------
struct node{
	int next,to,va;
}f[N];
int tail[N],k;

void Maketo(int from,int to,int va){
	f[++k].next=tail[from];tail[from]=k;f[k].to=to;f[k].va=va;
	return ;
}
//-----------------------------
//-----------------------------
bool can[N];
//-----------------------------

struct xyx{
	int deep,id,size,wson,dis,top,hsh;
}tr[N];
int cnt,sh[N];

void Dfs1(int x,int fa){
	tr[x].deep=tr[fa].deep+1;
	tr[x].size=1;
	for(ri i=tail[x];i;i=f[i].next){
		int y=f[i].to;if(y==fa) continue;
		tr[y].dis=tr[x].dis+f[i].va;
		Dfs1(y,x);
		if(!tr[x].wson||tr[tr[x].wson].size<tr[y].size) tr[x].wson=y;
		tr[x].size+=tr[y].size;
	}
	return ;
}

void Dfs2(int x,int to){
	tr[x].id=++cnt;tr[x].hsh=x;sh[cnt]=x;
	if(!tr[x].wson) return ;
	Dfs2(tr[x].wson,to);
	for(ri i=tail[x];i;i=f[i].next){
		int y=f[i].to;if(tr[y].id) continue;
		Dfs2(y,y);
	}	
}
//----------------------------

struct love{
	int va,lazy;
}tree[N<<2];

void Build_tree(int l,int r,int id){
	if(l==r){
		tree[id].va=tr[sh[l]].dis;
		return ;
	}
	Build_tree(l,mid,ls);Build_tree(mid+1,r,rs);
	return ;
}

void Pushdown(int id){
	tree[ls].lazy+=tree[id].lazy;
	tree[rs].lazy+=tree[id].lazy;
	tree[id].lazy=0;
	return ;
}

int Find(int l,int r,int loc,int id){
	if(l==r){
		tree[id].va=tree[id].va+tree[id].lazy;
		tree[id].lazy=0;
		return tree[id].va;
	}
	Pushdown(id);
	if(loc<=mid) return Find(l,mid,loc,ls);
	else return Find(mid+1,r,loc,rs);
}

void Change(int l,int r,int x,int y,int id,int k){
	if(x<=l&&y>=r){
		tree[id].lazy+=k;
		return ;
	} 
	Pushdown(id);
	if(x<=mid) Change(l,mid,x,y,ls,k);
	if(y>mid) Change(mid+1,r,x,y,rs,k);
}

//-------------------------

//-------------------------
bool cmp(const xyx &a,const xyx &b){
	return a.deep<b.deep;
}
//-------------------------

//-------------------------
void Solve(int from,int to){
	for(ri i=from;i<=to;i++){
		int gg=Find(1,n,tr[i].id,1);
		if(can[tr[i].hsh]){
			if(gg>mall+t*tr[i].deep){
				Change(1,n,tr[i].id,tr[i].id+tr[i].size-1,1,mall+t*tr[i].deep-gg);
				ans[tr[i].hsh]=mall+t*tr[i].deep;
			}
			else ans[tr[i].hsh]=gg;
		}
		else ans[tr[i].hsh]=gg;
	}
}

void Init(){
	freopen("climb1.in","r",stdin);
	freopen("climb.out","w",stdout);
}

signed Starseven(void){
//	Init();
	n=read(),t=read();
	for(ri i=2;i<=n;i++){
		int fa=read(),w=read(),judge=read();
		Maketo(fa,i,w);
		if(judge==1) can[i]=false;
		else can[i]=true;
	}
	Dfs1(1,0);Dfs2(1,1);
	Build_tree(1,n,1);
	sort(tr+1,tr+1+n,cmp);
	int st=1,head=1;
	mall=(-1)*t;
	while(head<=n){
		int judge=Find(1,n,tr[head].id,1)-t*tr[head].deep;
		mall=min(mall,judge);
		if(tr[head].deep==tr[head+1].deep) head++;
		else{
			Solve(st,head);
			st=head=head+1;
		}
	}
	for(ri i=1;i<=n;i++){
		write(ans[i]);puts("");
	}
	return 0;
}

int read(){
	char ch=getchar();
	int re=0,op=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') op=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		re=(re<<3)+(re<<1)+ch-'0';
		ch=getchar();
	}
	return re*op;
}

void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
	return ;
}

/*
4 3
1 7 1
1 5 0
2 1 0
*/

T2

题面.png

思路

看到题目中有最长时间可以猜测二分答案的思路。然后我们分析题目。

对于这种OI中的运动学题(~~手动滑稽~~)，我们不需要想的太复杂，只需要模拟判断

我们就根据上面的二分写下来代码：

const double eps=1e-12;
double l=1,r=maxn;
while(l+eps<r){
	double mid=(l+r)/2.0;//这里mid的含义是经过了mid时间
    if(Solve(mid)) r=mid;
    else l=mid;
}

然后判断的方法就是进行循环枚举经过时间后的位置，代码如下

for(int i=1;i<=n;i++)
	now[i]=loc[i]+v[i]*mid;

那我们怎么判断呢？

怎样会碰撞？

那就是(loc[i]<loc[j]),但是(now[i]>=now[j])

然后我们就可以去掉(k)个，然后怎么才能不碰撞？

当然是最后留下的序列是单调上升

所以就用(O(nlogn))的LIS来判断

代码如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
const int maxn=5e4+5;

pii vp[maxn];
double b[maxn],d[maxn];
int n,k;

template<typename T>
inline void read(T &x)
{
    char c;int f=1;
    while(!isdigit(c=getchar())) (c=='-')&&(f=-1);
    x=c^48;
    while(isdigit(c=getchar())) x=(x<<1)+(x<<3)+(c^48);
    x*=f;
}

int check(double ti)
{
    int nowans=0;
    for(int i=1;i<=n;++i)
        b[i]=1.0*vp[i].first+ti*vp[i].second;
    d[++nowans]=b[1];
    for(int i=2;i<=n;++i)
    {
        if(b[i]>d[nowans]) d[++nowans]=b[i];
        else d[lower_bound(d+1,d+nowans+1,b[i])-d]=b[i];
    }
    return nowans>=n-k;
}

int main()
{
    // freopen("B.in","r",stdin);
    // freopen("B.out","w",stdout);
    read(n);read(k);
    for(int i=1;i<=n;++i)
    {
        read(vp[i].first);read(vp[i].second);
    }
    sort(vp+1,vp+n+1);
    double l=0,r=2e6+5,mid;
    while(r-l>1e-10)
    {
        mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    if(l>2e6) puts("Forever");
    else printf("%.4lf
",l);
    return 0;
}

不会做

留坑代填