Atcoder abc244

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
G(构造)Ex(计算几何,树状数组)

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

G - Construct Good Path

n点m边 简单无向连通图.

边长=点数

构造一条 长度小于4N的边, 让点i出现次数%2 == s[i]

范围

n 1e5

m 1e5

2s

1024mb

我的思路

说是图, 但是树也是图, 所以树应该也可以, 所以 先从图中随便提出个树再在树上做

显然树上有个不满足个数的方案

根到点再返回根, 这样走完所有再决定 根需要奇数次还是偶数次

但这样搞次数肯定超了

考虑树上两种,一个是成链,一个是分叉

链上 a-b-c-d-e-f-g-h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
abcdefgh
xxxxxxxx
      x
     x
      x
     x
    x  
   x
    x
   x
  x
 x
  x
 x
x

然后是分叉, 考虑分叉= 多个链合并起来, 主要关注一下合并处的奇偶

1
2
3
4
5
 a
 b
 c
d f 
e g

可以看成a b c d e 和 c f g 两条链

c的奇偶性 = 原来c的奇偶性 + 1(额外链数)

似乎就没了, 因为新增的链 对 链头的重复可以看成链尾上多一次,这样每个点次数不超过4, 最后判断根要奇还是偶即可

但是感觉好难写啊

题解

反复横跳!!!!

dfs(u):

u -> dfs(子节点1) -> u -> (如果字节点1不满足奇偶增加 (子节点1->u) ) -> dfs(子节点2) -> u -> (如果字节点1不满足奇偶增加 (子节点2->u) ) -> dfs(子节点3) -> u -> (如果字节点1不满足奇偶增加 (子节点3->u) ) ->

代码

https://atcoder.jp/contests/abc244/submissions/35031281

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
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<(int)n;i++)

int read(){int r;scanf("%d",&r);return r;}
std::vector<int> G[100010];
char s[100010];
bool vis[100010];
std::vector<int> ans;

void add(int u){
  ans.push_back(u);
  s[u]^=1;
}

void dfs(int v) {
  vis[v] = true;
  add(v);
  for(auto u : G[v]) if(!vis[u]) {
    dfs(u);
    add(v);
    if(s[u] == 1){
      add(u);
      add(v);
    }
  }
}

int main(void) {
  int n = read();
  int m = read();
  rep(i,1,m+1){
    int u = read();
    int v = read();
    G[u].push_back(v);
    G[v].push_back(u);
  }
  scanf("%s",s+1);
  rep(i,1,n+1) s[i] -= '0';

  dfs(1);
  // 处理根的奇偶
  printf("%d\n",(int)ans.size() - s[1]);
  rep(i,s[1],ans.size()) printf("%d ",ans[i]);
  printf("\n");
  return 0;
}

Ex - Linear Maximization

二维平面点集S, 初始空

q次操作

每次集合中增加点 (xi,yi), 然后查询S中最大的 (aix+biy)

范围

Q 2e5

xi,yi,ai,bi [-1e9,1e9]

5s

1024mb

我的思路

什么概念呢, ax+by 最大, 若 b>0, 就是 (a/b)x+y 最大

就是斜率(a/b) 的切线去切这个点, 所以需要维护的是一个所有点的凸包, 再根据斜率需求,决定在哪一段二分乱搞一下? set + lower_bound ?

1
2
3
4
5
6
7
   --
  /  \
 /    \
|      \
|      /
 \    /
  \__/

题解

这里用 inner product 来解释的, 就是 (A,B) 方向上最远的

如果所有点都不是动态加的,而是固定以后,来求q询问

可见最大值 一定在凸包顶点上, 可以考虑三分

如果点是动态加的

那么就是需要动态维护S的凸包

需要用平衡二叉搜索树, 比如 __gnu_pbds::tree 可以快速查询第n个是什么

但有不少语言并不像C++ 有这样的库

可以看成 区间查询, 也就是没有点插入, 而是每次查询一个点下标区间中的凸包的一个切线

而查询的区间, 可以划分成log级别个维护好的区间去做查询

代码

https://atcoder.jp/contests/abc244/submissions/35053588

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
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

using Point = std::pair<ll, ll>;
const ll INF = 0x3f3f3f3f3f3f3f3f;
Point sub(Point a,Point b){ // return a-b
  return {a.first-b.first,a.second-b.second};
}

ll cross(Point a, Point b, Point c){ // (a-b) x (c-b)
  auto [x0,y0] = sub(a,b);
  auto [x1,y1] = sub(c,b);
  return x1*y0 -x0*y1;
}

struct ConvexHull{
  std::vector<Point> lower;
  std::vector<Point> upper;
  ConvexHull(Point p): lower{p}, upper{p}{}
  ConvexHull(const ConvexHull& a, const ConvexHull& b){ // 两个凸包合并
    {
      std::vector<Point> v; // 逆时针弧 下凸
      std::merge(a.lower.begin(), a.lower.end(), b.lower.begin(), b.lower.end(), back_inserter(v)); // 本身a,b下标有序, merge 会按pair的比较的排序
      for(Point p : v){
        while(lower.size() >= 2 && cross(lower.rbegin()[1], lower.back(), p) <= 0) lower.pop_back();
        lower.push_back(p);
      }
    }
    {
      std::vector<Point> v; // 顺时针弧 上凸
      std::merge(a.upper.begin(), a.upper.end(), b.upper.begin(), b.upper.end(), back_inserter(v)); // 本身a,b下标有序, merge 会按pair的比较的排序
      for(Point p : v){
        while(upper.size() >= 2 && cross(upper.rbegin()[1], upper.back(), p) >= 0) upper.pop_back();
        upper.push_back(p);
      }
    }
  }
  ll get(ll A, ll B) const { // 凸包中 求 Ax+By 的最大值,  B > 0, max(a/bx+y) 顺时针 上凸, B < 0 min(a/bx+y) 逆时针下凸
    auto& s = B < 0 ? lower : upper;
    auto f = [&](ll i){ return A * s[i].first + B * s[i].second; };
    ll l = 0;
    ll r = s.size() - 1;
    while(r-l >= 3){ // 3分
      ll x1 = (2*l+r)/3;
      ll x2 = (l+2*r)/3;
      ll f1 = f(x1);
      ll f2 = f(x2);
      if(f1 < f2) l = x1;
      else r = x2;
    }
    ll ans = -INF;
    rep(i,l,r+1) ans = std::max(ans, f(i));
    return ans;
  }
};
int main(){
  ll Q = read(); // 2e5
  std::vector<ConvexHull> S;
  rep(i,1,Q+1){
    ll X = read();
    ll Y = read(); // + (X,Y)
    ll A = read(); //
    ll B = read(); // 查询(A,B)
    S.emplace_back(std::pair{X, Y});
    // 最低位 2的幂次 次处理, 其实就是树状数组的想法, 每个位置表示 二进制最低位对应的一断内容,现在直接收集起来
    for(int j = i; j%2==0; j/=2){
      S.rbegin()[1] = ConvexHull(S.rbegin()[1], S.back());
      S.pop_back();
    }
    ll ans = -INF;
    for(auto& s : S) ans = std::max(ans, s.get(A, B));
    printf("%lld\n",ans);
  }
}

总结

G

不会编码.. 不会构造

Ex

计算几何没几个会的, 感觉核心问题还是计算集合没写熟悉吧

哦 原来维护这样的凸包不用去分什么 分割点或者上下部分

而是直接一个vector维护 一圈凹,一个vector维护一圈凸

然后两个合并的时候, 就是 先拼起来, 然后凹与凹合并, 凸与凸合并, 也没有去维护头部与后续的关系, 就是虽然每个都不严格, 但是它们的最优 = 所求的最优,

然后因为本身凸包就可能达到n个点, 所以依靠的是树状数组的思想而不是凸包本身,来让复杂度 是 n log n 级别,

一个更复杂的题 洛谷 P3309 SDOI2014

动态插入点,

强制在线 动态询问 区间下标[l..r]中的点,中给定斜率下最大值

参考

官方题解

pbds(平板电视)

1
2
3
4
#include<bits/extc++.h>
using namespace __gnu_pbds;


https://en.cppreference.com/w/cpp/iterator/back_inserter