CF1237

Posted on | Edited on | Views:

$Global\ Round\ 5$

A Balanced Rating Changes

只需要保证向上取整的次数和向下取整的次数相同就可以了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
int n,t=0,sum=0;
int trans(double x,bool f)
{
	int k=x<0?-1:1;
	f^=(x<0);
	x=fabs(x);
	return (f?k*floor(x):k*ceil(x));
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		int x=read();
		if(x%2==0)
		{
			printf("%d\n",x>>1);
			continue;
		}
		if(t)
		{
			printf("%d\n",trans((double)(x)/2.0,0));
			--t;
		}
		else
		{
			printf("%d\n",trans((double)(x)/2.0,1));
			++t;
		}
	}
	return 0;
}

B Balanced Tunnel

按照进入的顺序依次遍历,判断一下有没有先进入的车在它之后出去.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int n,a[MAXN],pos[MAXN];
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=n;++i)
	{
		int x=read();
		pos[x]=i;
	}
	int mx=0,ans=0;
	for(int i=1;i<=n;++i)
	{
		int x=a[i];
		if(mx>pos[x])
			++ans;
		mx=max(mx,pos[x]);
	}
	cout<<ans<<endl;
	return 0;
}

C Balanced Removals

把所有点以 $x,y,z$ 坐标分别为第一,二,三关键字排序.

构造方案时,对于 $x$ 坐标相同的一段,递归进去通过比较 $y,z$ ,将它们删到只剩一个点或者没有点.

于是剩下所有点的 $x$ 都互不相同,从前往后,相邻的作为一对删掉即可. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=5e4+10;
struct node
{
	int v[3],id;
	bool operator < (const node &rhs) const
	{
		for(int i=0;i<3;++i)
			if(v[i]!=rhs.v[i])
				return v[i]<rhs.v[i];
		return false;
	}
}p[MAXN];
int solve(int L,int R,int k)
{
	if(L==R)
		return p[L].id;
	int head=L,cur=0;
	for(int i=L;i<=R+1;++i)
	{
		if(i==R+1 || p[i].v[k]!=p[head].v[k])
		{
			int x=solve(head,i-1,k+1);
			if(x && !cur)
				cur=x;
			else if(x && cur)
			{
				printf("%d %d\n",cur,x);
				cur=0;
			}
			head=i;
		}
	}
	return cur;
}
int main()
{
	int n=read();
	for(int i=1;i<=n;++i)
	{
		p[i].id=i;
		for(int j=0;j<3;++j)
			p[i].v[j]=read();
	}
	sort(p+1,p+1+n);
	solve(1,n,0);
	return 0;
}

D Balanced Playlist

可以将链复制两份,接在后面.

复制两份而不是一份,是为了方便判断答案为无穷大的情况.

只考虑这 $3n$ 个点,若某个点答案 $>2n$ ,则实际答案一定为无穷大,否则就是该答案.

考虑第 $i$ 个点对前面哪些点有贡献,这可以在线段树上二分出来,还要和所有前缀的限制取 $\max$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=3e5+10;
int n,m,a[MAXN];
struct Segtree
{
	int mx[MAXN<<2];
#define root mx[o]
#define lson mx[o<<1]
#define rson mx[o<<1|1]
	void pushup(int o)
	{
		root=max(lson,rson);	
	}
	void BuildTree(int o,int l,int r)
	{
		if(l==r)
			return (void)(root=a[l]);
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
		pushup(o);
	}
	int query(int o,int l,int r,int L,int R)
	{
		if(L<=l && r<=R)
			return root;
		int mid=(l+r)>>1;
		int res=0;
		if(L<=mid)
			res=max(res,query(o<<1,l,mid,L,R));
		if(R>mid)
			res=max(res,query(o<<1|1,mid+1,r,L,R));
		return res;
	}
}T;
#define lowbit(x) x&(-x)
int bit[MAXN];
void add(int x,int c)
{
	for(;x<=n;x+=lowbit(x))
		bit[x]+=c;
}
int sum(int x)
{
	int s=0;
	for(;x;x-=lowbit(x))
		s+=bit[x];
	return s;
}
int main()
{
	m=n=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=n+1;i<=2*n;++i)
		a[i]=a[i-n];
	for(int i=2*n+1;i<=3*n;++i)
		a[i]=a[i-n];
	n*=3;
	T.BuildTree(1,1,n);
	int lst=0;
	for(int i=1;i<=n;++i)
	{
		int L=1,R=i,pos;
		while(L<=R)
		{
			int mid=(L+R)>>1;
			int mx=T.query(1,1,n,mid,i);
			if(2*a[i]>=mx)
				R=mid-1,pos=mid;
			else
				L=mid+1;
		}
		pos=max(pos,lst);
		add(pos,1);
		add(i+1,-1);
		lst=pos;
	}
	for(int i=1;i<=m;++i)
	{
		int ans=sum(i);
		if(ans>2*m)
			ans=-1;
		printf("%d ",ans);
	}
	puts("");
	return 0;
}

E Balanced Binary Search Trees

F Balanced Domino Placements

G Balanced Distribution

H Balanced Reversals