Znzryb's Blog
0%

Posted on Edited on

思路讲解

https://usaco.guide/plat/sweep-line?lang=cpp

主要参考了上面的题解。

这个分治法也比较玄学，就是先按照 x 排序，然后开始分治，从一对开始，逐渐变成两对，四对，八对，。。。

那么我们怎么样把两边的结果合并起来呢？这个就是分治的难点。

就是两边得到的答案，我们选一个较小值，然后把两边至少 x 满足这个值的点加入进来。

即

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ret=dfs(l,mid);
ret=min(ret,dfs(mid+1,r));
Real x=A[mid+1].x;
vector<Point> wp;
ROF(i,mid,l){
    Real d=abs(A[i].x-x);
    if(d*d<ret.d){
        wp.EB(A[i]);
    }else{
        break;
    }
}
FOR(i,mid+1,r){
    Real d=abs(A[i].x-x);
    if(d*d<ret.d){
        wp.EB(A[i]);
    }else{
        break;
    }
}

然后得到了 wp 数组，将其按照 y 排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Best mindis(vector<Point> &a,Best res){
    sort(all(a),[&](Point a,Point b){
        return a.y<b.y;
    });
    FOR(i,1,SZ(a)-1){  // 选一个点
		    // 向后扫描
        ROF(j,i-1,0){
            Point p=a[i],q=a[j];
            // 如果这个点的 y 已经不符合要求了，就直接开摆，后面的点y肯定更离谱
            if((p.y-q.y)*(p.y-q.y)>res.d){
                break;
            }
            Point v=p-q;
            res=min(res,{dot(v, v),p,q});
        }
    }
    return res;
}
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
struct Best{
    Real d;
    Point a,b;
    bool operator<(const Best &o)const{
        return d<o.d;
    }
};
Best mindis(vector<Point> &a,Best res){
    sort(all(a),[&](Point a,Point b){
        return a.y<b.y;
    });
    FOR(i,1,SZ(a)-1){
        ROF(j,i-1,0){
            Point p=a[i],q=a[j];
            if((p.y-q.y)*(p.y-q.y)>res.d){
                break;
            }
            Point v=p-q;
            res=min(res,{dot(v, v),p,q});
        }
    }
    return res;
}

Best dfs(int l,int r){
    if(l>=r) return {(ld)INF,A[l],A[l]}; 
    if(r-l==1){
        Point v=A[r]-A[l];
        return {dot(v,v),A[l],A[r]};
    }
    Best ret;
    int mid=r+l>>1;
    ret=dfs(l,mid);
    ret=min(ret,dfs(mid+1,r));
    Real x=A[mid+1].x;
    vector<Point> wp;
    ROF(i,mid,l){
        Real d=abs(A[i].x-x);
        if(d*d<ret.d){
            wp.EB(A[i]);
        }else{
            break;
        }
    }
    FOR(i,mid+1,r){
        Real d=abs(A[i].x-x);
        if(d*d<ret.d){
            wp.EB(A[i]);
        }else{
            break;
        }
    }
    return mindis(wp,ret);
}

AC代码

https://vjudge.net/solution/63334518

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

START202——Min-Max Deque

和该问题一样，直接解决这个问题比较难，我们可以解决一些更简单的问题。

比如说就是让果汁恰好为X？

那么考虑我们要选 i1,i2,...iki_1,i_2,...i_k 个，那么这些 i 要满足什么条件那？

这个问题其实也比较复杂，我们不妨只看 ...i1...i2......i_1...i_2... 这两个之间的情况。

我们发现，A[1]+⋯+A[i1]+⋯+A[i2−1]≥XA[1]+\cdots+A[i_1]+\cdots+A[i_2-1]≥X，是必要条件。

而且 A[i1+1]+⋯+A[i2−1]A[i_1+1]+\cdots+A[i_2-1] 的加多了的部分还可以回馈给 A[i2]A[i_2]

那么我们就会形成一种感觉，就是说前面的部分其实不重要，越少越好，后面的部分要越多越好，因为还可以回馈给下一个。（抱歉，官解也没有证明，所以说只能这样讲了）

当然，我们需要将这种思维拓展到每一个相邻元素之间，那么我们发现，前面一个元素的后面下面一个元素的前面，因此我们要恰好，就是需要删的元素不能多（这个还是很容易发现的）。

于是我们不难写出程序。

AC代码

https://www.codechef.com/viewsolution/1188472477

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

首先，做这道题目，需要有简单版的基础，简单版就是一个简单的贪心。以下是简单版的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
FOR(i,2,N){
    if(i&1){
        if(q.back()>=q.front()){
            q.EF(A[i]);
        }else{
            q.EB(A[i]);
            tr.update(i,i);
        }
    }else{
        if(q.back()<=q.front()){
            q.EF(A[i]);
        }else{
            q.EB(A[i]);
            tr.update(i,i);
        }
    }
}
ll ans=min(q.back(),q.front());

那复杂版就是多了一个在线修改+询问，一个询问就是把 A[p]:=xA[p]:=x，然后 naive 的想法就是再跑一遍简单版的程序，当然，不难发现，时间复杂度肯定有问题。

经过简单尝试，我们发现这个贪心算法不是很好优化，因此我们可以想办法改进一下我们的这个贪心做法。

我们发现比较难优化，是因为我们想通过一种方法直接在 O(log⁡n)O(\log n) 的时间复杂度内得到答案，这无疑有一定的难度。

那么，我们能不能在 O(log⁡n)O(\log n) 的时间复杂度内判断一个答案可不可行那？

这肯定是比之前的问题简单多了，但也没有那么简单。

假设答案为 XX，将原数组 AA 表示为 0101...0101... ，00 代表 <X<X，11 代表 ≥X≥X。
我们不难发现（在题设保证 N 为奇数的情况下）：

  1. 越后出现越重要。

  2. 1010110101 为相持阶段，得到的 BB 是 1111 类型，或维持原类型（即不能抵消 00）。

  3. 出现 1111 即使得 BB 变为 1111 类型（抵消一个 00）。

  4. 同理，出现 0000 即使得 BB 变为 0000 类型（抵消一个 11）。

那么通过上面发现的性质，那么我们其实就是要找到 1111 & 0000 的最靠右出现位置，这个可以使用二分答案+线段树二分 or 二分答案+二分+线段树解决。

具体来说是这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  auto check=[&](int mid){
      int pos00=tr.closer00(N,mid);
      int pos11=tr.closer11(N,mid);   // 使用线段树上二分实现
// pos00==-1 &&  pos11==-1 说明为1010结构，合法
      return pos11>=pos00;
  };
  auto cal=[&](){
      int l=1,r=N;
      while (l<r) {
          int mid=l+r+1>>1;
          if(check(mid)){
              l=mid;
          }else{
              r=mid-1;
          }
      }
      return l;
  };

代码：
https://www.codechef.com/viewsolution/1188151973

时间复杂度O(nlog⁡2n)O(n\log^2n)。

AC代码

https://www.codechef.com/viewsolution/1188151973

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

（现在看起来，这个题目有一点难了，超出了我的理解范围）

说实话，看这道题目，真一点思路都没有，连图都没有，我怎么动态规划？

那么一个联通块作为一个大块是非常难做的，那有没有可能分成好几个小块那？可以的兄弟，可以的，把 1 删除以后，就形成了一个个的小块。这些小块的访问顺序就是

A[li],A[li+1]…,A[ri]A[l_i],A[l_i+1]…,A[r_i]

注意到，我们可以要求这些小块互不连通，那你说联通的情况怎么办呢？怎么统计那？

image

哈哈，这就用到了一个小巧思，把这个看作为联向 1 的回边，这样我们就能保证小块之间不联通（指的是删除点 1 后）。

想到这个了，我们就会发现，在保持现有联通块及其访问顺序的情况下，哪些点可以连回 1 那？这个其实也很简单，大于 A[li]A[l_i] 即可。

然后题目说，我们现在已经成功的把一个大问题分解为小问题了，那不妨用 dp 继续。

Observe that we’ve really just broken the original problem down into smaller problems of the same nature - which naturally suggests dynamic programming.

呃，其实我觉得和分治思想差不多，就是继续把 A[li]A[l_i] 当根。

然后我们不难发现，这个重点就在于怎么样求这个块的划分方法那？

其实这个递推式子是不难的，是符合直觉的，但是确实比较难绷。

因为整了两个数组，dp（dp[i][j] 表示从 i 到 j 的答案） 和 split（split[i][j] 表示从 i 到 j 有多少种划分方法） 实际上是一个东西（忽略联向根的回边），就是有一个差一，即：

split[i+1][j]=dp[i][j]split[i+1][j]=dp[i][j]

那么我们怎么递推得到 splitsplit 那？其实也简单，不难发现（忽略联向根的回边）：

dp[L][R]=split[L+1][R]=∑x=L+1Rdp[L+1][x]⋅split[x+1][R]⋅[AL+1<Ax+1]（为真时是1，反之为0）dp[L][R]=split[L+1][R]=\sum^{R}_{x=L+1}dp[L+1][x]\cdot split[x+1][R]\cdot \\ [A_{L+1}<A_{x+1}]（为真时是1，反之为0）

这个式子看起来非常天外飞仙，其实很简单，就是把所有的分块都尝试一遍。

之所以分为两个，是为了避免差一错误。

你可能还会想，为什么一开始是 dp[L+1][x]dp[L+1][x] 那？首先不用 split 是为了避免 split[L+2][L+1]split[L+2][L+1] 这种诡异的情况出现，然后 A[L+1]A[L+1] 是一定要为根的，因此用dp[L+1][x]。

那为什么后面一个代码是 split[x+1][R]split[x+1][R] ，而不是 dp[x+1][R]dp[x+1][R] ？我也想了一会儿，不难发现 split[x+1][R]split[x+1][R] 可以保证 x+1 一定是根，但是不保证 x+2 一定是根，而采用 dp[x+1][R]dp[x+1][R] 会导致不仅 x+1 一定是根，x+2 也一定是根。

好，那么现在问题就来到了我们怎么样实现了。题解给了一种比较好的实现方法，就是先枚举长度，再枚举起始点，因为不难发现长的区间是从短的区间转移过来的。

我感觉题解给的式子有点麻烦了，而且有点奇怪。

AC代码

心路历程（WA，TLE，MLE……）