【NOIP2018模拟賽2018.10.22】cards

題目

題解

– 這道題隻有特判呢

對于前8個點，發現隻要x從小到大排好序，就是求y的lca，用樹樁數組優化一下就好了

對于後2個點，隻要pi<=pj，我們就連一條有向邊，最後跑最長路就好

代碼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1e6+5;

int m;
int x[MAXN],y[MAXN],z[MAXN];
bool flag;
int g[1005][1005];
int du[MAXN],d[MAXN];
int a[MAXN];
int c[MAXN];

bool small(int a,int b){
	if(x[a]<=x[b]&&y[a]<=y[b]&&z[a]<=z[b])
		return 1;
	return 0;
}

void topsort(){
	queue<int>q;
	for(int i=1;i<=m;i++)
		if(!du[i]){
			q.push(i);
			d[i]=1;
		}
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=1;i<=m;i++)
			if(g[x][i]){
				g[x][i]=0;
				d[i]=max(d[i],d[x]+1);
				du[i]--;
				if(!du[i])
					q.push(i);
			}
	}
}

bool comp(const int &a,const int &b){
	if(x[a]==x[b])
		return y[a]<y[b];
	return x[a]<x[b];
}

int ask(int x){
	int ans=0;
	for(x;x;x-=x&-x)
		ans=max(ans,c[x]);
	return ans+1;
}

void add(int x,int v){
	for(x;x<=MAXN;x+=x&-x)
		c[x]=max(c[x],v);
}

int main(){
	cin>>m;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x[i],&y[i],&z[i]);
		if(!y[i]){
			cout<<m;
			return 0;
		}
		if(z[i])
			flag=1;
		a[i]=i;
	}
	if(flag){
		for(int i=1;i<=m;i++)
			for(int j=1;j<=m;j++)
				if(i!=j&&small(j,i)){
					g[j][i]=1;
					du[i]++;
				}
		topsort();
		int ans=0;
		for(int i=1;i<=m;i++)
			ans=max(ans,d[i]);
		cout<<ans;
	}
	else{
		sort(a+1,a+1+m,comp);
		for(int i=1;i<=m;i++){
			int x=a[i];
			d[x]=ask(y[x]);
			add(y[x],d[x]);
		}
		int ans=0;
		for(int i=1;i<=m;i++)
			ans=max(ans,d[i]);
		cout<<ans;
	}
	return 0;
}