NOI2019 序列

link

题解

不考虑Ai,Bi的顺序,则相当于每次选出k个Pair(Ai,Bi),使得至少l个Ai=Bi

考虑费用流建图。

(文中a,b的边表示容量为a,费用为-b)

建S0,T0两个点,S向S0连k,0的边,T0向T连k,0的边。

S0向Ai连1,ai的边,Bi向T0连1,bi的边

Ai向Bi连1,0的边(表示两边都指定)

对于只指定一边的情况,建S1,T1表示只指定Bi,Ai的情况,S1向T1连k-l,0的边,Ai向S1连1,0的边,T1向Bi连1,0的边。

考虑怎么优化求费用流的过程,就是贪心模拟这一过程。

如果S1,T1的边还能有流量,则找一条S->S0->Max(ai)->S1->T1->Max(bi)->T0->T的增广路。

否则,增广路可能形如S->S0->Ai->Bi->T0->T,也可能形如S->S0->Ai->Bi->T1->Max(bi)->T0->T(Bi->T0的边已经满了),还可能形如S->S0->Max(ai)->S1->Ai->Bi->T0->T(S0->Ai的边已经满了)。

如果Ai->S1,T1->Bi都满了,那么就把Ai->S1->T1->Bi这条路径变成Ai->Bi。

用几个优先队列算一下每种情况就可以了

不过这样没法AC,只能84分(88?),要AC需要把只有删除的优先队列变成一次排序+删除标记。

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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
/*
Author: QAQ Automaton
Lang: C++
Prog: sequence.cpp
Mail: lk@qaq-am.com
Blog: https://www.qaq-am.com/
*/
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define int ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline bool read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;else if(c==EOF)return 0;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
return 1;
}

inline bool read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;else if(c==EOF)return 0;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
return 1;
}
inline bool read (char &x) {
x=gc();
return x!=EOF;
}
inline bool read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r')if(*x==EOF)return 0;
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
return 1;
}
template<typename A,typename ...B>
inline bool read(A &x,B &...y){
return read(x)&&read(y...);
}
// print a signed integer
inline bool write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
return 0;
}

inline bool write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
return 0;
}
inline bool write (char x) {
putc(x);
return 0;
}
inline bool write(const char *x){
while(*x){putc(*x);++x;}
return 0;
}
inline bool write(char *x){
while(*x){putc(*x);++x;}
return 0;
}
template<typename A,typename ...B>
inline bool write(A x,B ...y){
return write(x)||write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int a[200005],b[200005];
int inf;
struct _init_{
_init_(){
memset(&inf,0x3f,sizeof(inf));
}
};
_init_ __init__;
__gnu_pbds::priority_queue<pii> p2,p3;
__gnu_pbds::priority_queue<pii>::point_iterator i2[200005],i3[200005];
struct xqueue{
pii a[200005];
bool del[200005];
int it;
void erase(int x){
del[x]=1;
}
void init(int n){
for(int i=1;i<=n;++i)del[i]=0;
sort(a+1,a+n+1,dcmp<pii>);
it=1;
}
pii top(){
while(del[a[it].y])++it;
return a[it];
}
}p1,p4,p5;
int sx[200005],sy[200005];
int t;
void selectX(int x){
p4.erase(x);
if(!sy[x]){
p1.erase(x);
i3[x]=p3.push(make_pair(b[x],x));
}
else{
p2.erase(i2[x]);
--t;
}
sx[x]=1;
}
void selectY(int x){
p5.erase(x);
if(!sx[x]){
p1.erase(x);
i2[x]=p2.push(make_pair(a[x],x));
}
else{
p3.erase(i3[x]);
--t;
}
sy[x]=1;
}
void selectXY(int x){
sx[x]=sy[x]=1;
p1.erase(x);
p4.erase(x);
p5.erase(x);
}
signed main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
int T,n,k,l;
read(T);
for(;T;--T){
read(n,k,l);
l=k-l;
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1;i<=n;++i)read(b[i]);
for(int i=1;i<=n;++i)sx[i]=sy[i]=0;
p2.clear();
p3.clear();
for(int i=1;i<=n;++i){
p1.a[i]=(make_pair(a[i]+b[i],i));
p4.a[i]=(make_pair(a[i],i));
p5.a[i]=(make_pair(b[i],i));
}
p1.init(n);
p4.init(n);
p5.init(n);
int s=0;
t=0;
for(int i=1;i<=k;++i){
if(t<l){
++t;
s+=p4.top().x;
s+=p5.top().x;
selectX(p4.top().y);
selectY(p5.top().y);
}
else{
int a=p1.top().x,b=p2.empty()?-inf:(p2.top().x+p5.top().x),c=p3.empty()?-inf:(p3.top().x+p4.top().x);
if(a>b){
if(a>c){
selectXY(p1.top().y);
}
else{
++t;
selectY(p3.top().y);
selectX(p4.top().y);
}
}
else{
if(b>c){
++t;
selectX(p2.top().y);
selectY(p5.top().y);
}else{
++t;
selectY(p3.top().y);
selectX(p4.top().y);
}
}
s+=max(a,max(b,c));
}
}
write(s,'\n');
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×