HGOI7.13集训题解_∴。w。1i!↓lp h

题解

今天是可怕的一天。因为今天是lzy4896s大佬出题（博客传送门）。没错他是一个恶魔！！！（CF红名大佬）。所以又是打暴力的一天orz

以下为原创题。若有路人经过，可以看看博取一笑

---

第一题——特殊消消看（game）

【题目描述】

• 给你一个十分长的字符串，其中相邻存在互不相同的字符，则相邻的字符就会被删去，之后的字符则补上位置。每次删去所有互相不同的字符，问需要几次才能不消除。

---

• 这道题暴力链表模拟可以打80分。
• 我链表$O(n)$算法打炸了只有40分。
• 错误算法是，每次相消的字符串的前后字符相连。而重新判断新的互不相同的字符进入队列。每个字符只会被在重判时扫到，所以是$O(n)$

• 但重新进入队列时，如何取舍成了问题。判断下一个字符是否和当前字符相同。如果相同，则可以把自己之前的字符串处理掉进入队列，但是如果下一个字符是上一步就被处理掉的，那么当下一个字符所在的处理串的末尾的字符链接到的应该是上一串的头。这样子就出现了重复处理的混乱。无法解决。

• 正确解法是：将连续的字符压缩成单元，每次暴力维护单元的两端。如果单元长度为0，则合并左右两端。

• 复杂度考虑：由于每次扫描字符至少-1，所以扫描次数不会超过字符数的。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAXN 1000010
void fff(){
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
}
char s[MAXN];
vector <pair<int,char> > lis;//记录所在字符和字符数量
vector <pair<int,char> > merge(vector<pair<int,char> > lis){//合并两端的单元
    vector<pair<int,char> > res;
    for (int i=0;i<lis.size();){
        int j=i,sz=0;
        while (j< lis.size()&&lis[j].second==lis[i].second)
            sz+= lis[j].first,++j;
        res.push_back(make_pair(sz,lis[i].second));
        i=j;
    }
    return res;
}  
int main(){
    fff();
    int len;
    scanf("%d",&len);
    scanf("%s",s);
    for (int i=0;i<len;){
         int j=i;
         while (j<len&&s[j]==s[i]) j++;
         lis.push_back(make_pair(j-i,s[i]));
         i=j;
    }
    int ans=0;
    while(true){
        bool flag=false;
        vector<pair<int,char> > tmp;
        for (int i=0;i<lis.size();i++){
            int t=0;
            if(i&&lis[i-1].second!=lis[i].second) ++t;
            if(i+1<lis.size()&&lis[i+1].second!=lis[i].second) ++t;
            if(t) flag=true;
            if(lis[i].first-t>0) tmp.push_back(make_pair(lis[i].first-t,lis[i].second));
        }
        lis=merge(tmp);
        if(!flag) break;
        ans++;
    }
    cout<<ans;
}
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

---

第二题——最大最小（maxmin）

【题目描述】

• 给出序列。并给出多组查询$[l,r]$，求有多少连续的字数组的最大值和最小值的差值在$[l,r]$范围之间。
• 查询次数为q，序列长度为n。保证$qn\leq2*10^6,n\leq5*10^5$

---

• 没错！
• 就是这道恶魔题！
• 我暴力只打了60分！
• 他自己的数据可以卡掉自己的标准程序！
• 他连位运算和st算法的log的常数都要卡！
• 他是不是一个恶魔！！！！！
• 我人生第一次遇见一个信奥的标准答案！！！！
• 大家记住这个恶魔！！！！！！！
• 好接下来讲这个正解。
• 正解利用了数学上的最大值和最小值的单调性。
• 先将问题转化为（$\leq high$的答案数）-（<script type="math/tex" id="MathJax-Element-15">< low</script>的答案数），就是说求出有多少个字数组的和$\leq$一个定值。
• 由于最大值和最小值只差有单调性（最大值只会越来越大或者相等，最小值只会越来越小或相等，那么最大值最小值只差也只会单调递增）。
• 则可以枚举起点来求出每一个为起点的合法子区间的个数。减减加加就出来了。
• 最大值和最小值用st维护。但查询的时候需要预先处理长度数组和log2的常数。 由于这个数据真的非常的极限（由此我们可以看出lzw是个大魔王）

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#define LL long long 
using namespace std;
void fff(){
    freopen("maxmin.in","r",stdin);
    freopen("maxmin.out","w",stdout);
}
const int MAXN=500100;
int n,q,h;
int a[MAXN],bin[MAXN];
int mx[MAXN][20],mi[MAXN][20],lg[MAXN],ans1[MAXN],ans2[MAXN];
void st(){
    for (int i=1;i<=n;i++){
        mx[i][0]=a[i];
        mi[i][0]=a[i];
    }
    for (int j=1;j<20;j++){
        for (int i=1;i+(1<<j)-1<=n;i++){
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
            mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(int x,int y){
    if(x>y) swap(x,y);
    int k=(double)log(y-x+1)/log(2.0);
    return (max(mx[x][k],mx[y-(1<<k)+1][k])-min(mi[x][k],mi[y-(1<<k)+1][k]));
}
LL Solve(int low,int high){
    LL res=0;
    for (int i=1,r=1;i<=n;i++){
        while (r+1<=n&&query(i,r+1)<low) r++;
        ans1[i]=r;
    }
    for (int i=1,r=1;i<=n;i++){
        while (r+1<=n&&query(i,r+1)<=high) r++;
        ans2[i]=r;
    }
    for (int i=1;i<=n;i++) if(ans1[i]<=ans2[i]) res+=ans2[i]-ans1[i];
    return res;
}
int main(){
    fff();
    for (int i=1,h=2;h<MAXN;h<<=1,i++) lg[i];
    for (int i=1;i<MAXN;i++) if(!lg[i]) lg[i]=lg[i-1];
    bin[0]=1;for (int i=1;i<20;i++) bin[i]=bin[i-1]<<1;
    scanf("%d%d",&n,&q);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    st();
    for (int i=1;i<=q;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%lld\n",Solve(l,r));
    }
    return 0;
}
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

---

第三题——平均数（mean）

【题目描述】

• 给出一个长度为N的正整数的数组求有多少个子区间的平均数大于等于K。（是的这就是原题，lzw4896s懒得打题面了）

---

• 这道题也是神仙解法。我暴力还是只拿了50分（前50%的数据真的很水）
• 正确解法是巧妙运用树状数组和离散化。
• 先把每一个数都-k，这样子就是求得有多少个数和是>=0
• 那利用离散化之后树状数组求和就可以得出了。
• 以上是lzw大佬给出的题解…虽然我觉得概括的很到位..也确实没什么好添加的了。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
#define LL long long
using namespace std;
void fff(){
    freopen("mean.in","r",stdin);
    freopen("mean.out","w",stdout);
}
const int MAXN=200100;
int n,cnt,k;
map<LL,int> mp;
inline int Lowbit(int x){
    return x&(-x);
}
int a[MAXN],c[MAXN];
LL t[MAXN],b[MAXN],ans=0,sum[MAXN]; 
void Insert(int x){
    while (x<=cnt){
        c[x]++;
        x+=Lowbit(x);
    }
}
int Sum(int x){
    int res=0;
    while (x){
        res+=c[x];
        x-=Lowbit(x);//这个都是树状数组的常规操作了，单点更新，区间求和
    }
    return res;
}
int main(){
    fff();
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for (int i=0;i<=n;i++) t[i]=sum[i]-1LL*k*i,b[i]=t[i];//每个数都进行一次前缀和减去的操作
    sort(b,b+n+1);//离散化的操作
    for (int i=0;i<=n;i++) if(!mp[b[i]]) mp[b[i]]=++cnt;//离散化之后的排序标记
    for (int i=0;i<=n;i++) t[i]=mp[t[i]];//建立映射

    for (int i=0;i<=n;i++){
        ans+=Sum(t[i]);//求和。
        Insert(t[i]);//插入
    }
    cout<<ans;
    return 0;
}
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