这题很简单，处理一下前缀和就完事儿，没什么好说的。当时就做出了这个题 🙁
code
B. parcel
这题还是很有意思的，正式赛没做出来，其实第一问暴力很容易求，不过 作为一名 ACMer，有一种惯性会忽略掉这种方式…，下次一定要补上了。
题解可以参考官方题解
我这里就是将题解翻译一下，同时总结一下学到东西。
分析
首先对于每一个没有 deliver 的位置，我们可以先求出它的最短距离。这个可以将整个地图看成一个 graph，然后，任意两个deliver之间的距离为 0，然后将 所有deliver 看做图上的一个节点，其他的点与点之间的距离为 曼哈顿距离，那么只需要对图做一个 bfs 就行了，这就是answer中说的 muti-source bfs，其实感觉与bfs 并没有什么区别。
然后对于答案来说我们可以二分枚举，将优化问题转化为 满足性问题。
也就是说 对于一个固定的 $K$, 我们判断，是否可以找到一个点使得，所有点到delivers的距离不会超过 $K$.
判断这个是很容易的。
这里涉及到一个 曼哈顿距离 到 切比雪夫距离 的转化
关于曼哈顿距离与切比雪夫距离的转化，推荐参考 SGColin’s Space
有了这个我们就可以得到，答案分析中的结果
dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))
那么固定一个点 ($x_2$,$y_2$) 我们只需要求出 $min (x_i+y_i),max (x_i+y_i),min (x_i-y_i),max (x_i - y_i), i in dist(i)>K$
这个复杂度是 $O(RC)$ 的
加上二分的复杂度
$O(RClog(R+C))$
code
C. contention
这题非常有意思，官方给的编程实在太麻烦，太难懂了，毕竟一个笔试题又不是算法竞赛，居然搞出 interval tree 这种东西实在是太可怕了，正式赛只有两人做出来，我参考了第一人的做法Mahmoudian。
分析
首先我们可以观察到，对于一个 booking 来说，如果它放在最后，那么它能确定的seat 数目一定是固定的，与前面 booking 的顺序无关。
同时我们 可以证明这样一个贪心的做法一定是正确的:
倒着确定booking 的顺序，每次取能booking 到的seat 最多的去掉，然后在剩余集合中如法炮制
伪代码
S : booking_set
for i =0 : q
book_j = argmax(number_of_seat(S))
S = S/{book_j}
可以证明这个做法一定是正确的。
证明
设这样做不是最优的，也就是说 存在一种顺序 $p_1 dots p_q, numberOfSeat(p_q)<numberOfSeat(p_j)$ 比 $p_j$ 放在最后更优。我们总是可以将 $p_j$ 放在最后使得其不弱于序列$P_i$,即 构造顺序 $p_1,dots ,p_{j-1},p_{j+1},dots ,p_q,p_j$ 称为序列2
首先， $ans1<=number1(p_q),ans2<=number2(p_j),number1(p_j)>=number2(p_j)>=number1(p_q)ge ans1$ 因此 在序列 1中 $p_j$ 不是瓶颈。同时 $number2(p_i)ge number1(p_i),forall ineq j$ (因为遮挡少了 $p_j$)
ok。这就引出了一个朴素的算法，就是伪代码的做法，不过我们需要确定的是booking 放在最后能够book到多少seat。 这个可以用扫描线 $O(Q)$ 做出来，只有 $Q$ 条线段。
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define INF64 0x3f3f3f3f3f3f3f3f
#define ms(x,v) memset(x,(v),sizeof(x))
typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TIII;
typedef pair<PII,int> PIII;
const int MAXN = 1e6+10;
int del(map<PII,int>& seg){
int last = 0;
for(auto it = seg.begin(); it != seg.end();){
auto now = it;
const int st = now -> first.first;
const int ed = -now -> first.second;
int& val = now ->second=0;
if(ed <= last){
++it;
continue;
};
if(last<st)last = st;
auto jt = ++it;
assert(now != it);
assert(last < ed);
assert(last >=st);
int sweep_right = last;
for(;jt != seg.end() ; ++jt){
const int l = jt ->first.first;
const int r = - jt ->first.second;
if(sweep_right >=ed || l >= ed)break;
if(r <= sweep_right)continue;
if(l > sweep_right)val+= l - sweep_right;
sweep_right = r;
}
if(sweep_right < ed) val += ed - sweep_right;
// for next
last = max(ed,last);
}
// del max one
PIII p = *seg.begin();
for(auto it :seg){
if(it.second > p.second)p = it;
}
// cout << p.first.first << " " << p.first.second << " " << p.second<<"n";
seg.erase(p.first);
return p.second;
}
int solve(){
int n,q;
cin >> n >> q;
map<PII,int>seg;
int ans =n+1;
for(int i=0; i<q ; ++i){
int l,r;
cin >> l>>r;
seg.insert({{--l,-r},0});
}
if(seg.size() < q)return 0;
while(!seg.empty() && ans!=0){
ans = min(ans,del(seg));
}
return ans;
}
int main(){
ios :: sync_with_stdio(0);
cin.tie(0);
std::cout.precision(8);
std::cout.setf( std::ios::fixed, std:: ios::floatfield );
TIII t;
int T;
cin >> T;
// cout << "T = " << T << "n";
for(int t =1 ; t <= T; ++t){
auto ans = solve();
cout << "Case #"<<t<<": "<<ans<<"n";
}
return 0;
}
O(Qlog N) 版本
当然这样做无法通过大数据，这里我参考了 rank1 的做法，没有采用interval tree 的做法，而是用了二分。
和 $B$ 题一样，我们将问题转化为: 给定一个 $k$ 能否找到一种方式使得答案 大于等于 $k$。
参考上面的一些结论，很容易得到这样一个想法:
对于每一个 booking 来说，我们可以在满足能够让其book到的seat 大于等于 $k$ 的情况下将其尽可能的往后放。
具体可参见 code
code
reference
版权声明
本作品为作者原创文章，采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
作者: taotao
转载请保留此版权声明，并注明出处
近期评论