Educational Codeforces Round 61

Educational Codeforces Round 61

今早刚刚说我适合打pikmike出的EDU

然后我就挂了

A

不管

B

不管

C

这道题到快结束了才调出来

大概就是(n^2)枚举不选的区间

然后随便搞搞？

大体就是维护一下区间(1)的个数和(2)的个数

判断枚举的区间有没有交集

这个的答案就是并集1的个数和交集2的个数

用总的减去更新就好了

另外如果一个区间被另外一个区间完全包含

那么这个区间肯定是没用的

特判一下就好了

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 5005;
struct node{
	int xi;
	int yi;	
}a[N],b[N];
int n,q;
int sum[N];
int num2[N];
int num1[N];
bool book[N];
int tot;
int ans;
int cnt;
inline bool cmp(node x,node y){
	if(x.xi != y.xi)
	return x.xi < y.xi;
	return x.yi < y.yi;	
}
inline int read(){
	int v = 0,c = 1;char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') c = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		v = v * 10 + ch - 48;
		ch = getchar();
	}
	return v * c;
}
inline bool jiao(int x,int y){
	return a[x].yi >= a[y].xi;
}
int main(){
	n = read(),q = read();
	for(int i = 1;i <= q;++i){
		a[i].xi = read();
		a[i].yi = read();
	}
	sort(a + 1,a + q + 1,cmp);
	for(int i = 1;i <= q;++i){
		bool flag = 0;
		for(int j = 1;j <= q;++j){
			if(j == i || book[j]) continue;
			if(a[j].xi <= a[i].xi && a[j].yi >= a[i].yi) flag = 1;
		}
		if(!flag) b[++cnt] = a[i];
		else book[i] = 1;
	}
	sort(b + 1,b + cnt + 1,cmp);
	for(int i = 1;i <= cnt;++i){
		for(int j = b[i].xi;j <= b[i].yi;++j) sum[j]++; 
	} 
	for(int i = 1;i <= n;++i){
		num1[i] = num1[i - 1] + (sum[i] == 1);
		num2[i] = num2[i - 1] + (sum[i] == 2);
		if(sum[i]) tot++;
	}
	if(cnt <= q - 2){printf("%d
",tot);return 0;}
	if(cnt == q - 1){
		for(int i = 1;i <= cnt;++i){
			ans = max(ans,tot - (num1[b[i].yi] - num1[b[i].xi - 1]));
		}
		cout << ans;
		return 0;
	}
	for(int i = 1;i <= cnt;++i){
		for(int j = i + 1;j <= cnt;++j){
			int x = i,y = j;
			if(jiao(x,y)){
				ans = max(ans,tot - (num2[b[x].yi] - num2[b[y].xi - 1])
				 - (num1[b[y].yi] - num1[b[x].xi - 1]));	
			}
			else{
				ans = max(ans,tot - (num1[b[y].yi] - num1[b[y].xi - 1]) - (num1[b[x].yi] - num1[b[x].xi - 1]));	
			}
		}
	}
	cout << ans;
	return 0;
}

D

很明显,答案具有可二分性

我们二分答案之后,实质上就变成了一个贪心

维护一个堆

我们枚举时间轴

然后每次弹出需要充电的时间轴最靠前的元素，每次给他充电

这样时间复杂度为(O(n + k)*log(ans)*log(n))

我凭着这个算法成功卡进了最劣解第一名

这种算法可能有点卡常

我们优化一下

发现堆得本质是为了取出当前时间最靠前的

而时间这个东西又是单调不降的

我们就可以开vector来维护

同时对于时间维护一个指针,表示当前时间点

顺着指针扫就好了

每次从vector里面搞出来一个,然后把他放在应该在的位置

这样时间复杂度就变成了

(O((n + k)log(ans)))

就不会被卡常了

只放一下两个log的代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 3e5 + 3;
LL a[N],b[N];
LL c[N];
LL n,m,k;
struct node{
	LL rest;
	int id;
	LL outt;
	LL intt;
};
bool operator < (node x,node y){
	return x.outt > y.outt;
}
inline LL read(){
	LL v = 0,c = 1;char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') c = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		v = v * 10 + ch - 48;
		ch = getchar();
	}
	return v * c;
}
inline bool check(LL mid){
	priority_queue <node> q;
	for(int i = 1;i <= n;++i) q.push((node){a[i] - b[i] * c[i],i,c[i],0});
	for(int i = 1;i < k;++i){
		node x = q.top();int id = x.id;q.pop();	
		if(x.outt > k) break;
		if(x.outt < i) return 0;
		if(x.rest + mid + (x.outt - i) * b[id] < 0) return 0;
		LL re = x.rest + mid + (x.outt - i) * b[id];
		LL cc = re / b[id] + 1;
		q.push((node){re - cc * b[id],id,cc + i,i});
	}
	if(n == 1){
		if(q.top().outt < k) return 0;
		if(q.top().outt > k) return 1;
		if(q.top().rest + mid < 0) return 0;	
	}
	else{
		if(q.top().outt < k) return 0;	
		if(q.top().outt > k) return 1;
		if(q.top().rest + mid < 0) return 0;
		q.pop();
		if(q.top().outt <= k) return 0;
	}
	return 1;
}
int main(){
	
	n = read(),k = read() - 1;
	for(int i = 1;i <= n;++i) a[i] = read();
	for(int i = 1;i <= n;++i){
		b[i] = read();
		c[i] = a[i] / b[i] + 1;
	}
	sort(c + 1,c + n + 1);
	for(int i = 1;i <= n;++i){
		if(c[i] < i){
			printf("-1
");
			return 0;
		}
	}
	LL l = 0,r = 1e13,ans;
	for(int i = 1;i <= n;++i) c[i] = a[i] / b[i] + 1; 
	while(l <= r){
		LL mid = (l + r) >> 1;
		if(check(mid)) r = mid - 1,ans = mid;
		else l = mid + 1;
	}
	printf("%lld
",ans);
	return 0;
}

F

区间DP

我们设(f_{l,r})表示吧([l,r])这个区间全部删完的最小次数

对于(s[l])我们考虑是把他和区间内的某个一起删还是单独删

[dp_{l , r} = min(dp_{l + 1,r} + 1,min_{l<i <= r,s[i] == s[l]}dp_{l,i - 1} + dp_{i,j}) ]

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 505;
int f[N][N];
int n;
char s[N];
inline int read(){
	int v = 0,c = 1;char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') c = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		v = v * 10 + ch - 48;
		ch = getchar();
	}
	return v * c;
}
int main(){
	memset(f,0x3f,sizeof(f));
	n = read();
	scanf("%s",s + 1);
	for(int i = 1;i <= n;++i){
		f[i][i] = 1;
		f[i][i - 1] = 0;
	}
	f[n + 1][n] = 0;
	for(int len = 2;len <= n;++len){
		for(int i = 1;i <= n;++i){
			int j = i + len - 1;
			if(j > n) continue;
			f[i][j] = min(f[i][j],1 + f[i + 1][j]);
			for(int h = i + 1;h <= j;++h) 
			if(s[i] == s[h]) f[i][j] = min(f[i][j],f[i + 1][h - 1] + f[h][j]);
		}
	}
	cout << f[1][n];
	return 0;
}