Daniel_yuan's Blog

芙卡米天下第一可爱 n(*≧▽≦*)n

0%

[NOI2019] 序列 题解

发表于 更新于
本文字数： 7.8k 阅读时长 ≈ 7 分钟

简单学习了模拟费用流之后一直有点迷糊，后来在交流中似乎悟到了些什么。

能推出这道题挺开心的，而且对模拟费用流有了更进一步的理解。

首先这个题目很容易建出费用流的图。

考虑每次增广都会新增一对 \(a,b\)，那么我们就需要起点向 \(\{a\}\) 连边，\(\{b\}\) 向终点连边，这样一条路径就一定会对应一对 \(a,b\)。

对于 \(K\) 个下标的限制，直接对起点拆点。

而对于至少的限制，我们把其转化成最多，即最多 \(K-L\) 对 \(c,d\) 不相同，这样也可以用一条流量为 \(K-L\) 的边表示。

而对于相同和不同的限制，如果相同那么显然可以直接流，即 \(a_i\) 向 \(b_i\) 连边。而如果不同，那么就需要通过上一行的边，所以建立两个辅助节点 \(L,R\)，\(L\) 向 \(R\) 连 \(K-L\) 的边，然后 \(\{a\}\) 向 \(L\) 连边，\(R\) 向 \(\{b\}\) 连边。

因为我们在增广的同时要保证最大，所以在所有起点向 \(\{a\}\) 的边上和 \(\{b\}\) 向终点的边上加上他们的权值的费用，其它边的费用为 \(0\)，这样就有了一个费用流的模型。

直接费用流肯定过不了，考虑模拟费用流。

我们可以发现一共有六种增广方式。 \[ \begin{aligned} &S \rightarrow A \rightarrow B \rightarrow T\\ &S \rightarrow A \rightarrow L \rightarrow R \rightarrow B \rightarrow T\\ &S \rightarrow A_1 \rightarrow L \rightarrow A_2 \rightarrow B_2 \rightarrow T\\ &S \rightarrow A_1 \rightarrow B_1 \rightarrow R \rightarrow B_2 \rightarrow T\\ &S \rightarrow A_1 \rightarrow L \rightarrow A_2 \rightarrow B_2 \rightarrow R \rightarrow B_3 \rightarrow T\\ &S \rightarrow A_1 \rightarrow B_1 \rightarrow R \rightarrow B_2 \rightarrow A_2 \rightarrow L \rightarrow A_3 \rightarrow B_3 \rightarrow T\\ \end{aligned} \] 在有下标的路径中，下标相同的点的位置相同。（如 \(A_1\) 和 \(B_1\) 的）

可以发现其中只有路径 \(2\) 会经过 \(L\rightarrow R\) 的边，所以我们可以先贪心把路径 \(2\) 走完，然后再增广 \(L\) 次。

考虑剩下的增广，设 \(P\) 为没选的点的集合，\(Q\) 为选了的点，且当前状态是用 \(L\rightarrow R\) 边形成的集合，\(O\) 为选了的点，且当前状态是用 \(A_i\rightarrow B_i\) 的边形成的集合。

那么对于剩下的五种路径，我们有以下限制： \[ \begin{aligned} A, B \in &P\\ \text{}\\ A_1, B_2 \in &P; &A_2 \in &Q\\ A_1, B_2 \in &P; &B_1 \in &Q\\ A_1, B_3 \in &P; &A_2, B_2 \in &Q\\ A_1, B_3 \in &P; &B_1, A_3 \in &Q; &A_2, B_2 \in O \end{aligned} \] 然后在增广完之后，上面的五条路径分别会出现这样的改变：

\(\text{insert } O\) \(\text{delete } O\) \(\text{insert } Q\) \(\text{delete } Q\) \(\text{insert }P\) \(\text{delete }P\)
\(\text{path 1}\) \(A,B\) \(A,B\)
\(\text{path 3}\) \(A_2,B_2\) \(A_1\) \(A_2\) \(A_1,B_2\)
\(\text{path 4}\) \(A_1,B_1\) \(B_2\) \(B_1\) \(A_1,B_2\)
\(\text{path 5}\) \(A_2,B_2\) \(A_2,B_2\) \(A_1,B_3\) \(A_1,B_3\)
\(\text{path 6}\) \(A_1,B_1,A_3,B_3\) \(A_2,B_2\) \(B_1,A_3\) \(A_2,B_2\) \(A_1,B_3\)

可以发现改变量并不多。

那么我们用 \(5\) 个可删堆，分别维护：\(A,B\) 都在 \(P\) 的和的最大值，\(A\) 在 \(P\) 的最大值，\(B\) 在 \(P\) 的最大值，\(A\) 在 \(P\) 且 \(B\) 在 \(Q\) 的最大的 \(A\) 的权值，\(A\) 在 \(Q\) 且 \(B\) 在 \(P\) 的最大的 \(B\) 的权值。并同时维护 \(A,B\) 都在 \(Q\)，\(A,B\) 都在 \(O\) 的对数，就可以通过这五个可删堆的拼凑，得到上述五条路径的最大值，修改的时候由于修改量很少，暴力更新可删堆即可。

总复杂度 \(O(\sum n\log \max\{n\})\)。

贴个代码

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
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define RI register int
typedef long long LL;

#define FILEIO(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);

using namespace std;

namespace IO {
  char buf[1000000], *p1 = buf, *p2 = buf;
  inline char gc() {
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
    return p1 == p2 ? EOF : *(p1++);
  }
  template <class T> inline void read(T &n) {
    n = 0; RI ch = gc(), f;
    while ((ch < '0' || ch > '9') && ch != '-') ch = gc();
    f = (ch == '-' ? ch = gc(), -1 : 1);
    while (ch >= '0' && ch <= '9') n = n * 10 + (ch ^ 48), ch = gc();
    n *= f;
  }
  char Of[105], *O1 = Of, *O2 = Of;
  template <class T> inline void print(T n, char ch = '\n') {
    if (n < 0) putchar('-'), n = -n;
    if (n == 0) putchar('0');
    while (n) *(O1++) = (n % 10) ^ 48, n /= 10;
    while (O1 != O2) putchar(*(--O1));
    putchar(ch);
  }
}

using IO :: read;
using IO :: print;

int const MAXN = 2e5 + 5;
struct Node {
  int v, id;
  bool operator < (const Node &A) const {
    return v ^ A.v ? v < A.v : id < A.id;
  }
  bool operator == (const Node &A) const {
    return v == A.v && id == A.id;
  }
} a[MAXN], b[MAXN];
struct ErasableHeap {
  priority_queue <Node> I, O;
  inline void flush() { while (!O.empty() && I.top() == O.top()) I.pop(), O.pop(); }
  inline void clear() { while (!I.empty()) I.pop();    while (!O.empty()) O.pop(); }
  inline void insert(Node x) { I.push(x); }
  inline void erase(Node x)  { O.push(x); }
  inline bool empty() { flush(); return I.empty(); }
  inline Node top()   { flush(); return I.top();   }
} q1, q2, q3, q4, q5;
// Max AB in P; Max A in P; Max B in P; Max A in P and B in Q; Max A in Q and B in P;
int visa[MAXN], visb[MAXN];
int stkQ[MAXN], stkO[MAXN];
// 0 : in P; 1 : in Q; 2 : in O
int cntO, cntQ;

void DeleteAll(int x) {
  if (visa[x] == 0 && visb[x] == 0) q1.erase((Node){a[x].v + b[x].v, x});
  if (visa[x] == 0)                 q2.erase(a[x]);
  if (visb[x] == 0)                 q3.erase(b[x]);
  if (visa[x] == 0 && visb[x] == 1) q4.erase(a[x]);
  if (visa[x] == 1 && visb[x] == 0) q5.erase(b[x]);
  if (visa[x] == 1 && visb[x] == 1) --cntQ;
  if (visa[x] == 2 && visb[x] == 2) --cntO;
}
void InsertAll(int x) {
  if (visa[x] == 0 && visb[x] == 0) q1.insert((Node){a[x].v + b[x].v, x});
  if (visa[x] == 0)                 q2.insert(a[x]);
  if (visb[x] == 0)                 q3.insert(b[x]);
  if (visa[x] == 0 && visb[x] == 1) q4.insert(a[x]);
  if (visa[x] == 1 && visb[x] == 0) q5.insert(b[x]);
  if (visa[x] == 1 && visb[x] == 1) stkQ[++cntQ] = x;
  if (visa[x] == 2 && visb[x] == 2) stkO[++cntO] = x;
}
void PushInQ(int *vis, int x) {
  DeleteAll(x);
  vis[x] = 1;
  InsertAll(x);
}
void PushInO(int x) {
  DeleteAll(x);
  visa[x] = visb[x] = 2;
  InsertAll(x);
}

int main() {

  int T; read(T);
  while (T--) {
    int n, K, L; read(n), read(K), read(L);
    int res = K - L;
    for (RI i = 1; i <= n; ++i)
      read(a[i].v), a[i].id = i;
    for (RI i = 1; i <= n; ++i)
      read(b[i].v), b[i].id = i;

    for (RI i = 1; i <= n; ++i)
      visa[i] = visb[i] = 0;
    cntO = 0, cntQ = 0;
    q1.clear(); q2.clear(); q3.clear(); q4.clear(); q5.clear();

    sort(a + 1, a + 1 + n, [](Node x, Node y){ return x.v > y.v; });
    sort(b + 1, b + 1 + n, [](Node x, Node y){ return x.v > y.v; });  
    LL ans = 0;
    for (RI i = 1; i <= res; ++i) {
      ans += a[i].v, visa[a[i].id] = 1;
      ans += b[i].v, visb[b[i].id] = 1;
    }
    sort(a + 1, a + 1 + n, [](Node x, Node y){ return x.id < y.id; });
    sort(b + 1, b + 1 + n, [](Node x, Node y){ return x.id < y.id; });
    for (RI i = 1; i <= n; ++i) InsertAll(i);

    int tmp = L;
    while (L--) {
      LL val1 = q1.top().v;
      LL val2 = !q2.empty() && !q5.empty() ? q2.top().v + q5.top().v : -0x7f7f7f7f7f7f7f7f;
      LL val3 = !q3.empty() && !q4.empty() ? q3.top().v + q4.top().v : -0x7f7f7f7f7f7f7f7f;
      LL val4 = cntQ && !q2.empty() && !q3.empty() ? q2.top().v + q3.top().v : -0x7f7f7f7f7f7f7f7f;
      LL val5 = cntO && !q4.empty() && !q5.empty() ? q4.top().v + q5.top().v : -0x7f7f7f7f7f7f7f7f;
      if (val1 > val2 && val1 > val3 && val1 > val4 && val1 > val5) {
        ans += val1;
        PushInO(q1.top().id);
      }
      else if (val2 > val3 && val2 > val4 && val2 > val5) {
        ans += val2;
        int tmp = q5.top().id;
        PushInQ(visa, q2.top().id);
        PushInO(tmp);
      }
      else if (val3 > val4 && val3 > val5) {
        ans += val3;
        int tmp = q4.top().id;
        PushInQ(visb, q3.top().id);
        PushInO(tmp);
      }
      else if (val4 > val5) {
        ans += val4;
        int t1 = q2.top().id, t2 = q3.top().id;
        PushInO(stkQ[cntQ]);
        PushInQ(visa, t1);
        PushInQ(visb, t2);
      }
      else {
        ans += val5;
        int t1 = q4.top().id, t2 = q5.top().id, t3 = stkO[cntO];
        PushInQ(visa, t3), PushInQ(visb, t3);
        PushInO(t1);
        PushInO(t2);
      }
    }
    print(ans);
  }

/*

S -> A -> B -> T
S -> A -> L -> R -> B -> T
S -> A1 -> L -> A2 -> B2 -> T
S -> A1 -> B1 -> R -> B2 -> T
S -> A1 -> L -> A2 -> B2 -> R -> B3 -> T
S -> A1 -> B1 -> R -> B2 -> A2 -> L -> A3 -> B3 -> T

First, use all of the path 2
Then, expand rest times

Let P is a set of the nodes not be chosen, Q is a set of the nodes be chosen into LR, Otherwise is O.
path 1 : A, B   in P                            O : A, B   insert
path 3 : A1, B2 in P; A2     in Q               O : A2, B2 insert                         Q : A2 delete,     A1     insert
path 4 : A1, B2 in P; B1     in Q               O : A1, B1 insert                         Q : B1 delete,     B2     insert
path 5 : A1, B3 in P; A2, B2 in Q               O : A2, B2 insert                         Q : A2, B2 delete, A1, B3 insert
path 6 : A1, B3 in P; B1, A3 in Q; A2, B2 in O  O : A2, B2 delete, A1, B1, A3, B3 insert  Q : B1, A3 delete, A2, B2 insert

*/

  cerr << (double)(clock()) / CLOCKS_PER_SEC << " ms " << endl;

  return 0;
}

// created by Daniel yuan
/*
     ________
    /        \
   / /      \ \
  / /        \ \
  \            /
   \  ______  /
    \________/
*/

最后再来个总结：

模拟费用流究其根本是先建图，然后再分析图进行贪心模拟。