Reku
0%

Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2)

Posted on Edited on In Views: Valine:

A,B略

C. Fountains 一开始看错了题，还以为是什么很牛逼的背包题。 认真读了读题目，发现只需要两个喷泉，所以要么两个C、两个D、一个C一个D，用树状数组乱搞搞就行，很简单。

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
#include<bits/stdc++.h>
using namespace std;
class BITree{
public:
    static const long long SIZE = 100010, BIAS = 5;
    long long u[SIZE];
    void clear(){
        memset(u,0,sizeof(u));
    }
    void modify(long long x, long long v){
        for(x+=BIAS;x<SIZE;x+=x&-x) u[x]=max(v,u[x]);
    }
    long long getmax(long long x){
        long long s=0;
        for(x+=BIAS;x;x-=x&-x) s=max(s,u[x]);
        return s;
    }
} cc,dd;
int main()
{
	cc.clear();
	dd.clear();
	long long ans=0;
	long long mac=0;
	long long mad=0;
	long long n,c,d;
	cin>>n>>c>>d;
	for(int i=1;i<=n;i++)
	{
		long long x,y;
		char ch;
		cin>>x>>y>>ch;
		if(ch=='C')
		{
			if(y<=c){ mac=max(mac,x);
			long long p=cc.getmax(c-y);
			if(p&&x) ans=max(ans,p+x);
			cc.modify(y,x);}
		}
		else
		{
			if(y<=d) {mad=max(mad,x);
			long long p=dd.getmax(d-y);
			if(p&&x) ans=max(ans,p+x);
			dd.modify(y,x);}
		}
	}
	if(mac&&mad) ans=max(ans,mac+mad);
	cout<<ans<<endl;
	return 0;
}

D. Field expansion 题目可以转化为，给一列数字，找不相交两组数字相乘的结果分别大于A和B，使得用到的数字最少。 很容易发现，能用大的数字一定用大的。 因为A和B都不超过\(100000\)，所以用不超过\(34\)个数字一定可以找到一组合法解，那么显然就用最大的\(34\)个数字。 然后判断有没有合法解，就拆成两半，然后把所有解生成出来，一半枚举，另一半二分就可以了，蛮常见的处理方式。 要注意这个长方形是可以旋转的...因为没发现可以旋转，错了好多次QAQ

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
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
long long a,b,h,w,n;
long long e[100010]={};
long long x;
long long y;
bool cmp(long long x,long long y)
{
	return x>y;
}
bool pan(int t)
{
	int num1=0;
	int num2=0;
	long long p[2][30];
	long long ma=1ll;
	long long u=(2ll<<40);
	for(int i=1;i<=t/2;i++)
	{
		num1++;
		p[0][num1]=e[i];
		if(ma<u) ma*=e[i];
	}
	for(int i=1;i<=t-num1;i++)
	{
		num2++;
		p[1][num2]=e[i+num1];
		if(ma<u) ma*=e[i+num1];
	}
	if(ma<x*y) return 0;
	vector<long long> z1;
	vector<long long> z2;
	for(int i=1;i<=num1;i++)
	{
		int g=z1.size();
		z1.pb(p[0][i]);
		for(int j=0;j<g;j++)
		{
			if(z1[j]*p[0][i]<=100000) z1.pb(z1[j]*p[0][i]);
		}
	}
	for(int i=1;i<=num2;i++)
	{
		int g=z2.size();
		z2.pb(p[1][i]);
		for(int j=0;j<g;j++)
		{
			if(z2[j]*p[1][i]<=100000) z2.pb(z2[j]*p[1][i]);
		}
	}
	z1.pb(1);
	z2.pb(1);
	sort(z1.begin(),z1.end());
	sort(z2.begin(),z2.end());
	long long pma=222147483600ll;
	for(int i=0;i<z1.size();i++)
	{
		int l=0;
		int r=z2.size()-1;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(z1[i]*z2[mid]>=x) r=mid;
			else l=mid+1;
		}
		if(z1[i]*z2[l]>=x) pma=min(pma,z1[i]*z2[l]);
	}
	if((ma/pma)>=y) return 1;
	return 0;
}
int ans=-1;
void suan()
{
	x=(a/h)+!!(a%h);
	y=(b/w)+!!(b%w);
	//cout<<x<<" "<<y<<endl;
	if(x==1&&y==1)
	{
		cout<<0<<endl;
		exit(0);
	}
	sort(e+1,e+n+1,cmp);
	int l=1;
	int r=min(34ll,n);
	while(l<r)
	{
		int mid=(l+r)/2;
		if(pan(mid)) r=mid;
		else l=mid+1;
	}
	if(pan(l)!=0) 
	{
		if(ans==-1) ans=l;
		else ans=min(ans,l);
	}
}
int main()
{
	scanf("%lld%lld%lld%lld%lld",&a,&b,&h,&w,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&e[i]);
	}
	suan();
	swap(h,w);
	suan();
	cout<<ans<<endl;
	return 0;
}

E. Aquarium decoration 把所有的物品分为四份：A和B都喜欢的，A喜欢的，B喜欢的，A和B都不喜欢的。 然后枚举第一部分找多少个，用两个树状数组加速剩下三部分的计算就好了。我的做法是一个树状数组处理前缀个数，然后另一个处理前缀和，到时候二分就可以了。 写错了好多次...码力好差...

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int n,m,k;
long long c[200010]={};
bool a[200010]={};
bool b[200010]={};
long long qhb[200010]={};
long long qhb1[200010]={};
long long qhb2[200010]={};
vector<long long> bb;
vector<long long> b1;
vector<long long> b2;
vector<long long> b3;
struct pp
{
	long long s;
	int a;
	int b;
} e[200010];
bool cmp(pp x,pp y)
{
	return x.s<y.s;
}
class BITree{
public:
    static const int SIZE = 400010, BIAS = 5;
    long long u[SIZE];
    void clear(){
        memset(u,0,sizeof(u));
    }
    void modify(int x, long long v){
        for(x+=BIAS;x<SIZE;x+=x&-x) u[x]+=v;
    }
    long long getsum(int x){
        long long s=0;
        for(x+=BIAS;x;x-=x&-x) s+=u[x];
        return s;
    }
} bh,qh;
int ne;
int na[200010]={};
int nb[200010]={};
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&c[i]);
	}
	int x;
	scanf("%d",&x);
	for(int i=1;i<=x;i++)
	{
		int o;
		scanf("%d",&o);
		a[o]=1;
	}
	scanf("%d",&x);
	for(int i=1;i<=x;i++)
	{
		int o;
		scanf("%d",&o);
		b[o]=1;
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]&&b[i]) bb.pb(c[i]);
		else if(a[i]) b1.pb(c[i]);
		else if(b[i]) b2.pb(c[i]);
		else b3.pb(c[i]);
	}
	sort(bb.begin(),bb.end());
	sort(b1.begin(),b1.end());
	sort(b2.begin(),b2.end());
	sort(b3.begin(),b3.end());
	for(int i=0;i<bb.size();i++)
	{
		if(i==0) qhb[i]=bb[i];
		else qhb[i]=qhb[i-1]+bb[i];
	}
	ne=0;
	for(int i=0;i<b1.size();i++)
	{
		if(i==0) qhb1[i]=b1[i];
		else qhb1[i]=qhb1[i-1]+b1[i];
		ne++;
		e[ne].s=b1[i];
		e[ne].a=i;
		e[ne].b=-1;
	}
	for(int i=0;i<b2.size();i++)
	{
		if(i==0) qhb2[i]=b2[i];
		else qhb2[i]=qhb2[i-1]+b2[i];
		ne++;
		e[ne].s=b2[i];
		e[ne].a=-1;
		e[ne].b=i;
	}
	for(int i=0;i<b3.size();i++)
	{
		ne++;
		e[ne].s=b3[i];
		e[ne].a=-1;
		e[ne].b=-1;
	}
	sort(e+1,e+ne+1,cmp);
	bh.clear(); qh.clear();
	for(int i=1;i<=ne;i++)
	{
		bh.modify(i,1);
		qh.modify(i,e[i].s);
		if(e[i].a!=-1) na[e[i].a]=i;
		if(e[i].b!=-1) nb[e[i].b]=i;
	}
	long long ans=-1;
	bool bj=0;
	for(int i=bb.size()-1;i>=0;i--)
	{
		if((i+1)>m) continue;
		long long mans=0;
		if((i+1)>=k)
		{
			if((m-i-1)>ne) break;
			mans+=qhb[i];
			mans+=qh.getsum(m-i-1);
			if(ans==-1) ans=mans;
			else ans=min(ans,mans);
		}
		else
		{
			int w=k-i-1;
			int u=m-i-1-2*w;
			if(u<0) break;
			if(w>(int)b1.size()||w>(int)b2.size()) break;
			if(i==bb.size()-1)
			{
				for(int j=0;j<w-1;j++)
				{
					bh.modify(na[j],-1);
					bh.modify(nb[j],-1);
					qh.modify(na[j],-b1[j]);
					qh.modify(nb[j],-b2[j]);
				}
			}
			w--;
			mans+=qhb[i];
			mans+=qhb1[w];
			mans+=qhb2[w];
			bh.modify(na[w],-1);
			bh.modify(nb[w],-1);
			qh.modify(na[w],-b1[w]);
			qh.modify(nb[w],-b2[w]);
			if(u!=0)
			{
				int l=1;
				int r=ne;
				while(l<r)
				{
					int mid=(l+r)/2;
					if(bh.getsum(mid)>=u) r=mid;
					else l=mid+1;
				}
				if(bh.getsum(l)==u) mans+=qh.getsum(l);
				else break;
			}
			if(ans==-1) ans=mans;
			else ans=min(ans,mans);
		}
		if(i==0) bj=1;
	}
	if(bb.size()==0) bj=1;
	if(bj&&2*k<=m&&k<=b1.size()&&k<=b2.size())
	{
		int w=k;
		long long mans=0;
		w--;
		mans+=qhb1[w];
		mans+=qhb2[w];
		bh.modify(na[w],-1);
		bh.modify(nb[w],-1);
		qh.modify(na[w],-b1[w]);
		qh.modify(nb[w],-b2[w]);
		int u=m-2*k;
		if(u!=0)
		{
			int l=1;
			int r=ne;
			while(l<r)
			{
				int mid=(l+r)/2;
				if(bh.getsum(mid)>=u) r=mid;
				else l=mid+1;
			}
			if(bh.getsum(l)==u) mans+=qh.getsum(l);
			else
			{
				mans=ans;
			}
		}
		if(ans==-1) ans=mans;
		else ans=min(ans,mans);
	}
	cout<<ans<<endl;
	return 0;
}