526互联

Educational Codeforces Round 150 (Rated for Div. 2)

发布时间 2023-10-19 00:07:17作者: gan_coder

A题直接拆成 1 1 n-2
<=4时bob，否则alice

B题直接模拟一下就行

C题开始想复杂了，我们直接枚举是哪个字符转成哪个字符即可，如果是变大，一定是放在最左，如果是变小，一定是放在最右，爆算即可。

D题，显然N^2dp，但是还是想错一些细节，假设按右端点排序后，当前考虑第i个区间，假设我们让它跟前面第j个区间匹配，那么前面区间的右端点都必须小于min(lj,li)，开始就是没考虑到要小于lj。

设pi记录i右边第一个跟i没有交集的区间是哪个。

那么就从min(p[i],p[j])这些点转移过来即可。

维护一下前缀min即可，因为这个前缀min可以拆开维护。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N=1e6+5;
const ll mo=998244353;
const int inf=1<<30;
struct node{
	int l,r;
};
node a[N];
int f[N],n,g[N],p[N],mn;
bool cmp(node a,node b){
	return a.r<b.r;
}
bool pd(int a,int b,int c,int d){
	return ((c<=a && b<=d) || (a<=c && d<=b) || (a<=c && c<=b) || (c<=a && a<=d));
}
int main()
{ 
//	freopen("data.in","r",stdin);	
//	freopen("data.out","w",stdout);
	
	int T;
	scanf("%d",&T);
	while (T--){
		
		scanf("%d",&n);
		fo(i,1,n) {
			scanf("%d %d",&a[i].l, &a[i].r);
		}
		sort(a+1,a+n+1,cmp);
		
//		fo(i,1,n) printf("%d %d\n",a[i].l ,a[i].r);
	
		fo(i,0,n) f[i]=inf,g[i]=inf;
		
		f[0]=0;
		a[0].r=-1;
		
		g[0]=0;
		
		fo(i,1,n) {
			fd(j,i-1,0) {
				if (a[j].r <a[i].l) {
					p[i]=j; break;
				}
			}
			
			fd(j,i-1,0) {
				if (a[j].r >=a[i].l) {
					mn=min(p[j], p[i]);
					
					f[i]=min(f[i], g[mn]+i-2);
				}
			}
			
			g[i]=min(g[i-1], f[i]-i);
		}

		int ans=inf;
		fo(i,0,n) ans=min(ans, f[i]+n-i);
		printf("%d\n",ans);
		
	}
	
	return 0;
}