〔NOIP2022模拟〕分！身！术！(踩大坑之三次优化QwQ)

发表于 更新于
模拟赛场寄大分,三次优化寄回家……

题面简述: 在序列内,区间最大值减最小值大于等于k为合法,寻找最小合法区间

不能泄题啊QwQ

  大佬: 一眼双指针+单调最队列

  我: 应该是线段树吧……QwQ

  于是我在考场上就打了线段树QwQ……最后只过了一个点改后才发现是我题意看错了……（我想呼死我自己…… 我把区间最大值看成区间和了QwQ(不过数据停挺水的,竟然还能过一个点……)

  考后改过来了,但是还是寄,过了5个,剩下的TLE

first🕋

  于是乎,既然是来枚举区间大小验证(我的做法),那么可以二分答案啊？

  很好……过了7个(但是还是寄啊QwQ)该T的还是TLE啊……

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
//check
inline bool check(int l, int r) {
    pair<int, int >temp = ask(1, 1, n, l, r);//返回pair,前max后min
    return (temp.first >= temp.second + k) ? 1 : 0;
}
.....//省略QwQ

//二分本体
if(check(1,n)){
    bool flag=0;
    int l=2,r=n-1,mid;
    while(l+1<=r){
        mid=(r+l)>>1;flag=0;
        for(int i=1;i+mid-1<=n;i++){
            if (check(1,1+mid-1)){
                r=mid;
                falg=1;
                break;
            }
        }
        if (!falg){
            l=mid+1;
        }
        printf("%d\n",l);
    }
}
else {puts("So Sad!");return 0;}

second🕋

  考虑到本体的性质,一个合法的区间内必然有一个小于等于当前区间大小的合法区间。 那么我们在下一次二分答案的时候就可以继续在上一次大于当前枚举区间大小合法的区间内找;

这里就先不展示code,因为我写寄了(1。没有找大于当前枚举区间的合法,而是直接在上一次合法区间找,2.我用的是vector,TLE,QwQ )

  不写了,线段树加二分加寻找合法区间,头都调炸了QwQ。还是乖乖用了单调队列

  但是没想到单调对了也寄了Σ(っ °Д °;)っ

thitd🕋

  这次寄了是因为我用来STL的deque,太慢了TLE了QwQ

可能是最后的数据太大(后来下下来发现有130多MB（；´д｀）ゞ),deque空间翻倍和其他操作太慢了,于是只能手打 QwQ(copy from ymj🤪)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct FUCK_DEQUE{
      int q[10000010];
  int head=0, tail=0;
  int pop_front() {
    head++;
    return q[head - 1];
  }
  int pop_back() {
    tail--;
    return q[tail + 1];
  }
  void push_front(int val) {
    head--;
    q[head] = val;
  }
  void push_back(int val) {
    q[tail] = val;
    tail++;
  }
  bool empty() { return head == tail; }
  int &front() { return q[head]; }
  int &back() { return q[tail - 1]; }
}maxn,minn;
//over

  然后就能开心的过了,嘿嘿

  最后引用某人的话(别听他瞎BB)

这个STL中看不中用啊

[cover:絵 画师:逢編いあむ] (画的戳中我的心窝了QwQ)

🍂全文完↩︎