Atcoder abc304

發表於 更新於 分類於 ， Disqus： 文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘
G(二分,xor),Ex(拓扑排序)

https://atcoder.jp/contests/abc304/tasks

G - Max of Medians

给长2n的数组A,让元素配成n对，每对做xor得到长n的序列B

求 max(sorted(B)[n/2+1])

n 1e5

ai [0,2^30]

5s

1024mb

我的思路

xor + max 常见思路从高位向低位贪心,

对于第b位

min(count 0, count 1) 就是能构成1 的方案数

如果 min >= n/2 +1, 那么 就是 从 b位是0和是1的分成两组，其中各选出一个，还需要对低位进行处理啊

如果 min < n/2+1, 那么就是b位无法成为1,那么0和1分成两组，这两组内部选两个排序

这两个都并不好处理，因为第n/2+1大在这过程中不光没有消掉，而且还会增加维度

题解

二分

定义4个函数(序列中每个至多被选一次)

f(C,x) = k : C序列最多能找k个对，让每对的xor 大于等于x

g(C,D,x) = k :最多能找k个对(Ci,Dj)，让每对的xor 大于等于x

$f_d(C,x) = f(C \mod 2^{d+1},x \mod 2^{d+1})$

$g_d(C,D,x) = g(C \mod 2^{d+1},D \mod 2^{d+1},x \mod 2^{d+1})$

题目就是要找$f_{29}(A,x) = f(A,x) \ge \lfloor \frac{N+1}{2}\rfloor$

如果能计算$f$,则可以二分$x$

计算$f_d(C,x)$, 不妨假设$C_i,x \in [0,2^{d+1})$

令$C^{(0)},C^{(1)}$分别表示$C$中$2^d$位为0和1的子序列

  • $f_{-1}(C,x)=\lfloor \frac{|C|}{2}\rfloor$
  • 如果$x$的$2^d$位是0
    • 那么 $C^{(0)}$和$C^{(1)}$中各选一个配对 总会大于$x$
    • 那么不能配对的部分能否超过 $\lfloor \frac{||C^{(0)}|-|C^{(1)}||}{2}\rfloor$个
    • 也就是 $f_d(C,x) = \min(|C^{(0)}|,|C^{(1)}|) + \min( \lfloor \frac{||C^{(0)}|-|C^{(1)}||}{2}\rfloor, f_{d-1}(C^{(多)},x))$
  • 如果$x$的$2^d$位是1
    • $C^{(0)}$和$C^{(1)}$内部的xor总是 小于 x
    • $f_d(C,x) = g_{d-1}(C^{(0)},C^{(1)},x)$

计算$g_d(C,D,x)$, 同样不妨设$C_i,D_i,x\in [0,2^{d+1})$

  • $g_{-1}(C,D,x) = \min(|C|,|D|)$
  • 如果$x$的$2^d$位是0
    • 和上面原理一样， 配0/1始终大于x
    • $|C^{(0)}|\le|D^{(1)}|$ 且 $|C^{(1)}|\le|D^{(0)}|$, $g_d(C,D,x) = |C^{(0)}|+|C^{(1)}|$
    • $|C^{(0)}|\le|D^{(1)}|$ 且 $|C^{(1)}| > |D^{(0)}|$, $g_d(C,D,x) = |C^{(0)}|+|D^{(0)}|+\min(|C^{(1)}|-|D^{(0)}|,|D^{(1)}|-|C^{(0)}|,g_{d-1}(C^{(1)},D^{(1)},x))$, 和上面原理一样，如果先配0/1,那么 就是 剩余C1和D1,所以看C1和D1最多能配多少个
    • 对称同理
  • 如果$x$的$2^d$位是1
    • $g_d(C,D,x) = g_{d-1}(C^{(0)},D^{(1)},x)+g_{d-1}(C^{(1)},D^{(0)},x)$

代码

https://atcoder.jp/contests/abc304/submissions/42873766

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;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
tuple<int,vector<int>,int,vector<int> > _(const vector<int>&a,int d){
  vector ret(2,vector<int>{});
  for(auto o:a) ret[(o>>d)&1].push_back(o);
  return {ret[0].size(),ret[0],ret[1].size(),ret[1]};
}
int g(const vector<int>&C,const vector<int>&D,int x,int d){
  if(d==-1) return min(C.size(),D.size());
  if(C.size() == 0 or D.size() == 0) return 0; // cut
  auto [szC0,C0,szC1,C1] = _(C,d);
  auto [szD0,D0,szD1,D1] = _(D,d);
  if((x>>d)&1){
    return g(C0,D1,x,d-1) + g(C1,D0,x,d-1);
  }else{
    if(szC0 <= szD1 and szC1 <= szD0) return szC0 + szC1;
    if(szC0 >= szD1 and szC1 >= szD0) return szD0 + szD1;
    if(szC0 <= szD1 and szC1 >= szD0) {
      return szC0 + szD0 + min({szD1-szC0,szC1-szD0,g(D1,C1,x,d-1)});
    }else{
      return szC1 + szD1 + min({szD0-szC1,szC0-szD1,g(D0,C0,x,d-1)});
    }
  }
}
int f(const vector<int>&C,int x,int d){
  if(d == -1) return C.size()/2;
  if(C.size() == 0) return 0;
  auto [szC0,C0,szC1,C1] = _(C,d);
  if((x>>d)&1){
    return g(C0,C1,x,d-1);
  }else{ // = 0
    if(szC0 <= szC1) return szC0 + min((szC1-szC0)/2,f(C1,x,d-1));
    else             return szC1 + min((szC0-szC1)/2,f(C0,x,d-1));
  }
}
int main() {
  int n=read();
  vector<int> a(2 * n);
  rep(i,0,2*n) a[i]=read();
  int l = 0; // ok
  int r = 1 << 30; // not ok
  while(r-l > 1){
    int mid=(l+r)/2;
    (f(a,mid,30) >= (n+1)/2 ? l : r) = mid;
  }
  printf("%d\n",l);
  return 0;
}

Ex - Constrained Topological Sort

n点,m边(si,ti)有向图(无自环无重边),

是否存在1~n的排列P满足

  • $P_{s_i} < P_{t_i},i=1\cdots M$
  • $P_i\in[L_i,R_i], i = 1\cdots N$

如果存在，输出一个合法的P

n 2e5

m 4e5

3s

1024mb

我的思路

题如其名，如果没有LR的限制，就是一个拓扑排序，因为每个有向边在排列中的意义就是排列中顺序

或者说给图染色1~n,每个颜色出现一次，然后有向边决定了 si的染色小于ti, 而如果成环必不可能

所以就一定是无环做拓扑

而怎么做呢

没有限制就是,初始cur=1, 每次选入度为0的赋予当前cur,然后cur++,删除这个点更新入度

有限制以后，首先想到的是贪心

每次选择入度为0,且当前r限制最小的进行赋值

然而可能出现情况是 u-> v,而u的R很大，但是v的R很小，从而u迟迟没有被删除，导致v过期

想法还是根据拓扑，传递L和R

R[u] = min(R[v])-1, 对于所有 u->v

L[v] = min(L[u])+1, 对于所有 u->v

这样同样会有问题

u->v1->w, u->v2->w 限制上看可能不会冲突，但是可能v1,v2都占用了同一个

而这个虽然没有证明，但是感觉上是可以从实际赋值的过程中 触发冲突?

但是问题是，有没有一种可能，有方案，但是因为赋值顺序的问题产生了“冲突”

显然也是存在的

1[1,3] - 2[2,4]

1[1,3] - 3[2,4]

1[1,3] - 4[2,4]

5[1,5]

但是注意到，这里1[1,3]的R比5[1,5]的R小，而这个小换句话说，如果1是非1不可

那么 让它非1不可的链接的内容一定是把[2,r[1]]的都填完了

证明不了

题解

我的想法是对的,就是传递l,r加上拓扑贪心min r

证明:

假设当前点A[l,r0],B[l,r1], r0 < r1

而B选l有一个合法方案, 此时A选择的是x

显然对于小于l的不影响，而交换 A选l和B选x,显然l < x <= r0 < r1

但是x可能比B的后继节点大

注意到因为经过了传递r,所以B的后继节点的r一定大于r1, 所以B的后继节点C若选最小赋值的y < x, 则交换x,y

1
2
3
4
5
6
A: [l..........r0]
        x0
             x1 
B: [l..............r1]
C:     [...y.............], B后继实际选择的最小的C
D:       [..z..............], C后继实际选择的最小的D

A-x,B-l,C-y (B->min(C))

变为

A-l,B-x,C-y (B->min(C)), (y>x或不存在后继) 或 A-l,B-y,C-x (B->min(C)), (y<x)

而这里C可能也有后继，但是正如和B的交换一样，如果C的后继有冲突，则说明C和C的后继也可以发生交换,有限次交换，可以得到一个同样合法的

所以这样也会有方案，

所以就是 拓扑+传递+贪心就没了

这里甚至不需要 -1,直接min r都够了

代码

https://atcoder.jp/contests/abc304/submissions/42874951

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
template<class T>using minPQ=priority_queue<T,vector<T>,greater<T> >;
ll read(){ll r;scanf("%lld",&r);return r;}
int l[200010];
int r[200010];
vector<int>g[200010];
void dfs(int u){
  static bool vis[200010];
  vis[u] = 1;
  for(auto&v:g[u]){
    if(!vis[v]) dfs(v);
    r[u]=min(r[u],r[v]);
  }
}
int main(){
  int n=read();
  int m=read();
  vector<int>d(n+1);
  rep(i,0,m) {
    int u=read();
    int v=read();
    g[u].push_back(v);
    d[v]++;
  }
  rep(i,1,n+1) {
    l[i]=read();
    r[i]=read();
  }
  rep(i,1,n+1) dfs(i);
  minPQ<pair<int,int> > pq; // 度为0 且 l <= cur
  vector<vector<int> > l2u(n+1);
  rep(i,1,n+1) if(!d[i]) l2u[l[i]].push_back(i);
  vector<int> ans(n+1);
  rep(i,1,n+1) {
    for(auto&j:l2u[i])pq.push({r[j],j});
    if(pq.empty()) return printf("No\n")*0;
    auto [w,u]=pq.top();
    pq.pop();
    if(w<i) return printf("No\n")*0;
    ans[u]=i;
    for(auto&v:g[u]){
      if(--d[v] == 0){
        if(l[v] > i) l2u[l[v]].push_back(v);
        else pq.push({r[v],v});
      }
    }
  }
  printf("Yes\n");
  rep(i,1,n+1) printf("%d ",ans[i]);
  return 0;
}

总结

G

还是完全不会二分， 不过也是第一次见到 xor+max 配合二分的，印象中之前做了不少xor+max配合的都是从高位向下贪心， 这里应该也不完全是max,是相当于第k大了

然后 操作上 还是 从高位向低位 分解,后面的推理拆解很自然， 所以核心感觉在想到，啊可以“二分”

Ex

怎么说呢，就是那种有“不会一下证明的正确想法”，对于算法比赛来说是AC的，但是数学性上是不对的

参考

官方题解