当前位置 : 主页 > 大数据 > 区块链 >

uoj 231 [IOI 2015] Teams - 贪心 - 可持久化线段树

来源:互联网 收集:自由互联 发布时间:2021-06-22
题目传送门 唯一的传送站 题目大意 一共有$n$个学生,以及$q$天需要安排任务。第$i$有$m_{i}$个任务,第$j$个任务必须由恰好$k_{i, j}$名学生去完成。第$i$名学生愿意参与一项需要人数恰

 

题目传送门

  唯一的传送站

题目大意

  一共有$n$个学生,以及$q$天需要安排任务。第$i$有$m_{i}$个任务,第$j$个任务必须由恰好$k_{i, j}$名学生去完成。第$i$名学生愿意参与一项需要人数恰好为$k$的任务当且仅当$A_i \leqslant k \leqslant B_i$。每个学生一天至多参与一项任务,也可以不参与任何任务。问每天是否存在分配方案。

  真想吐槽为什么有人把IOI的题出进省选模拟赛。(显然我是看了题解的)  

  好像网上这道题没啥题解,稍微写良心一点。(noi官网上有题解,只是应该默认看IOI题解的人都是佬,所以写得很精炼,嗯,应该没用错词。)

  先来说说34分做法。

  考虑将$k$从小到大排序,对于每个任务能选择的学生中,肯定希望先选择右端点较小的。因为如果它不选这个学生,那么后面的任务更难选择它了。

  然后就先对学生排一遍序,然后拿个堆就完事了。于是我们得到了34分的高分。

  怎么优化这个算法呢?

  考虑把学生看作二维平面内的点$(A, B)$,那么对于一个任务可以选择的学生是下图的阴影区域内的(包含边界):

  因为它要满足$A\leqslant k \wedge B\geqslant k$,将可行解画在二维平面上就是上面那样。

  根据上面的贪心策略就是先选择下面的点。注意到点的横坐标的多少在影响是否可选之后没有意义了。

  那么我们寻找一种比较舒服的取点的方式。假如我们在之前的取点过程中,不断将最后取的点的纵坐标为当前这个区域的上界。我们使得这些上界不断递减,例如:

  其中蓝色的部分是已经取走点的部分。然后如何实现这样的一个东西?

  考虑一级一级地向上取点,如果足够就把这一级的点全取走,合并上界。否则在主席树上求$k$大,找到新的上界加入栈。大概就是:

 

  其中红色部分是尝试取走的部分,黄色部分是在主席树上二分得到的东西。(其实这里省掉了一次尝试取走的过程)

  感觉思路还是挺简单的。我就说说我那丑陋的实现遇到的一大堆问题。

  1. 当上一次的上界比当前的$k$小时直接弹掉。
  2. 栈里不应有高度相同的上界。
  3. 上界中可能有多个点,可能包含未取的。

  于是便成功造就了我的码题1小时,调试3小时(果然我是个菜菜的NOIP选手)。

  另外说一下关于这道题的对拍。全随机很容易通过。

  钦定$B$的值可以得到一些不错的数据。

  然后我想了想,为什么转化到二维平面上就能实现优化。我觉得嘛,这东西有点像是二维偏序,在一维数组中自然不好处理,没有一种好的排序方式能够较好地处理。

  最后orz杜瑜皓题解上的dp做法。想到Hall定理,也想不到这种神奇的dp。

Code

  1 /**
  2  * uoj
  3  * Problem#231
  4  * Accepted
  5  * Time: 12591ms
  6  * Memory: 304020k
  7  */
  8 #include <bits/stdc++.h>
  9 #include "teams.h"
 10 using namespace std;
 11 typedef bool boolean;
 12 
 13 const int N = 5e5 + 5;
 14 
 15 typedef class SegTreeNode {
 16     public:
 17         int s, id;
 18         SegTreeNode *l, *r;
 19 
 20         SegTreeNode():s(0), l(NULL), r(NULL) {    }
 21         SegTreeNode(int id, SegTreeNode* nul):s(0), id(id), l(nul), r(nul) {    }
 22 
 23         inline void pushUp() {
 24             s = l->s + r->s;
 25         }
 26 }SegTreeNode;
 27 
 28 #define Limit 4000000
 29 
 30 SegTreeNode pool[Limit];
 31 SegTreeNode *top = pool;
 32 SegTreeNode null(-1, &null);
 33 
 34 SegTreeNode* newnode(int id) {
 35     if (top - pool >= Limit)
 36         return new SegTreeNode(id, &null);
 37     top->id = id;
 38     return top++;
 39 }
 40 
 41 typedef class ChairTree {
 42     public:
 43         int n;
 44         SegTreeNode** rts;
 45         
 46         ChairTree() {    }
 47         ChairTree(int n):n(n) {
 48             rts = new SegTreeNode*[(n + 1)];
 49             for (int i = 0; i <= n; i++)
 50                 rts[i] = &null;
 51         }
 52 
 53         void update(SegTreeNode*& op, SegTreeNode*& p, int l, int r, int idx, int id) {
 54             if (!p || p->id != id)
 55                 p = newnode(id), p->s = op->s, p->l = op->l, p->r = op->r;
 56             if (l == r) {
 57                 p->s++;
 58                 return;
 59             }
 60             int mid = (l + r) >> 1;
 61             if (idx <= mid)
 62                 update(op->l, p->l, l, mid, idx, id);
 63             else
 64                 update(op->r, p->r, mid + 1, r, idx, id);
 65             p->pushUp();
 66         }
 67 
 68         int query(SegTreeNode*& p, int l, int r, int ql, int qr) {
 69             if (l == ql && r == qr)
 70                 return p->s;
 71             int mid = (l + r) >> 1;
 72             if (qr <= mid)
 73                 return query(p->l, l, mid, ql, qr);
 74             if (ql > mid)
 75                 return query(p->r, mid + 1, r, ql, qr);
 76             return query(p->l, l, mid, ql, mid) + query(p->r, mid + 1, r, mid + 1, qr);
 77         }
 78 
 79         int query(SegTreeNode*& ap, SegTreeNode*& rp, int l, int r, int k) {
 80             if (k > ap->s - rp->s)
 81                 return -1;
 82             if (l == r)
 83                 return l;
 84             int ls = ap->l->s - rp->l->s, mid = (l + r) >> 1;
 85             if (ls >= k)
 86                 return query(ap->l, rp->l, l, mid, k);
 87             return query(ap->r, rp->r, mid + 1, r, k - ls);
 88         }
 89 
 90         void update(int nv, int idx) {
 91             update(rts[nv - 1], rts[nv], 1, n, idx, nv);
 92         }
 93 
 94         int query(int vl, int vr, int l, int r) {
 95             if (l > r)    return 0;
 96             return query(rts[vr], 1, n, l, r) - query(rts[vl], 1, n, l, r);
 97         }
 98 
 99         int query(int vl, int vr, int k) {
100             return query(rts[vr], rts[vl], 1, n, k);
101         }
102 }ChairTree;
103 
104 int n;
105 vector<int> *g;
106 ChairTree ct;
107 
108 void init(int n, int* A, int* B) {
109     ::n = n;
110     g = new vector<int>[(n + 1)];
111     ct = ChairTree(n);
112     for (int i = 0; i < n; i++)
113         g[A[i]].push_back(B[i]);
114     for (int i = 1; i <= n; i++) {
115         for (int j = 0; j < (signed) g[i].size(); j++)
116             ct.update(i, g[i][j]);
117         if (!g[i].size())
118             ct.rts[i] = ct.rts[i - 1];
119     }
120 }
121 
122 typedef class Data {
123     public:
124         int p, h, r;
125 
126         Data(int p = 0, int h = 0, int r = 0):p(p), h(h), r(r) {    }
127 }Data;
128 
129 Data st[N];
130 
131 int can(int m, int* K) {
132     int tp = -1;
133     sort(K, K + m);
134     st[++tp] = Data(0, n, 0);
135     for (int i = 0; i < m; i++) {
136         while (tp && st[tp].h < K[i])
137             tp--;
138         int finded = ct.query(st[tp].p, K[i], K[i], K[i]), used = 0;
139         while (tp && st[tp].h == K[i])
140             finded += ct.query(st[tp - 1].p, st[tp].p, K[i], K[i]) - st[tp].r, used += st[tp].r, tp--;
141         if (finded >= K[i]) {
142             st[++tp] = Data(K[i], K[i], K[i] + used);
143             continue;            
144         }
145         int nf = finded, h = K[i];
146 //        cerr << i << " Init " << nf << " " << h << " " << tp << endl; 
147         while (nf < K[i]) {
148             nf = nf + ct.query(st[tp].p, K[i], h + 1, st[tp].h);
149             if (nf >= K[i]) {
150                 int k = K[i] - finded + ct.query(st[tp].p, K[i], 1, h);
151 //                cerr << k << endl;
152                 h = ct.query(st[tp].p, K[i], k);
153                 int r = k - ct.query(st[tp].p, K[i], 1, h - 1);
154 //                cerr << r << endl;
155                 while (st[tp].h == h)
156                     r += st[tp].r, tp--;
157                 st[++tp] = Data(K[i], h, r);
158 //                cerr << "New data added " << K[i] << " " << h << " " << r << endl;
159                 assert(st[tp].h <= n);
160                 break;
161             }
162             h = st[tp].h, finded = nf;
163 //            cerr << i << " Rect " << nf << " " << h << " " << tp << endl; 
164             nf = nf + ct.query(st[tp - 1].p, st[tp].p, h, h) - st[tp].r;
165             tp--;
166             if (nf >= K[i]) {
167                 int r = K[i] - finded + ct.query(st[tp + 1].p, K[i], h, h) + st[tp + 1].r;
168                 while (st[tp].h == h)
169                     r += st[tp].r, tp--;
170                 st[++tp] = Data(K[i], h, r);
171 //                cerr << "New data added " << K[i] << " " << h << " " << r << endl;
172                 assert(st[tp].h <= n);
173             } else if (tp == -1 && nf < K[i])
174                 return 0;
175             finded = nf;
176 //            cerr << i << " Rest " << nf << " " << h << " " << tp << endl; 
177         }
178     }
179     return 1;
180 }
网友评论