乱七八糟的小题

Posted on | In

记录脑筋急转弯

习惯

链式前向星需要memset head数组

记得特判

20校赛前一天的三角形

https://codeforces.com/contest/1355/problem/C

给三段区间，要求找出能构成三角形的向量的数目。乍一看要画图用线性规划……好麻烦就没写出来，出题人给的是另一种思路：想办法算出对于每个s（a+b<=s<=b+c），有多少对（x，y）的和等于s。这样一来我们就可以枚举z边，然后把当前和大于z的xy取法数目加在答案上。

第一步是个区间加，即对于所有x，把[x+b,x+c]这一段取法值加一，因为是离线的就不用线段树了，在区间首尾打标记然后维护当前点的取法即可，遍历一遍就赋值好了。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=1e6+2;
ll ways[maxn];
int main(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans=0;
    for(int i=a;i<=b;i++){
        ways[i+b]+=1;
        ways[i+c+1]-=1;
    }
    ll tmp=0;
    for(int i=a+b;i<=b+c+1;i++){
        tmp+=ways[i];
        ways[i]=tmp;
    }
    assert(tmp==0);
    for(int i=b+c;i>c;i--){
        tmp+=ways[i];
        if(i<=d+1)
            ans+=tmp;
    }
    cout<<ans<<endl;
}

最大区间和beta

我们知道单纯求最大区间和可以用dp，在线性时间搞出来。这道题https://codeforces.com/contest/1359/problem/D要求我们求 减去区间最大值后的区间和 的最大值，增加了难度。

首先，我们可以用单调栈求出，对于每个点i，向左向右最远走到哪里可以不遇到比自己大的，这样我们可以确定下来点i可选的有效区间范围（即a[i]在这个范围中是最大值）。接下来我们只需要在这个区间中选择一个包含i的区间，可以用线段树维护前缀和的最大和最小值。在i左侧找到前缀和最小值，在i右侧找前缀和最大值，两者相减就是整体区间的最大值了。相减时还需要排除右边<=左边的情况。

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
#define lson (o<<1)
#define rson (o<<1|1)
#define inf 0x3f3f3f3f
const int maxn=1e5+2;

int n,a[maxn],sum[maxn];
int mn[maxn<<2],mx[maxn<<2];

void build(int o,int l,int r){
    if(l==r){
        mn[o]=mx[o]=sum[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    mn[o]=min(mn[lson],mn[rson]);
    mx[o]=max(mx[lson],mx[rson]);
}

int qu_mn(int o,int l,int r,int L,int R){
    if(l>=L&&r<=R){
        return mn[o];
    }
    int mid=(l+r)>>1;
    int res=inf;
    if(L<=mid){
        res=min(res,qu_mn(lson,l,mid,L,R));
    }
    if(R>mid){
        res=min(res,qu_mn(rson,mid+1,r,L,R));
    }
    return res;
}

int qu_mx(int o,int l,int r,int L,int R){
    if(l>=L&&r<=R){
        return mx[o];
    }
    int mid=(l+r)>>1;
    int res=-inf;
    if(L<=mid){
        res=max(res,qu_mx(lson,l,mid,L,R));
    }
    if(R>mid){
        res=max(res,qu_mx(rson,mid+1,r,L,R));
    }
    return res;
}

int l[maxn],r[maxn];    //记录每个点向左右走到哪为止不会遇到比自己大的,用单调栈求出
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sum[0]=0;
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    stack<int> stk;
    for(int i=1;i<=n;i++){
        while(stk.size()&&a[stk.top()]<=a[i])
            stk.pop();
        if(stk.size()){
            l[i]=stk.top()+1;
        }else{
            l[i]=0;
        }
        stk.push(i);
    }
    while(stk.size()){
        stk.pop();
    }
    for(int i=n;i;i--){
        while(stk.size()&&a[stk.top()]<=a[i])
            stk.pop();
        if(stk.size()){
            r[i]=stk.top()-1;
        }else{
            r[i]=n;
        }
        stk.push(i);
    }
    build(1,0,n);
    int ans=0;
    for(int mnn,mxx,i=1;i<=n;i++){
        mnn=qu_mn(1,0,n,l[i],i);
        mxx=qu_mx(1,0,n,i,r[i]);
        if(mxx<=mnn)
            continue;
        ans=max(ans,mxx-mnn-a[i]);
    }
    cout<<ans<<endl;
}

数列翻转一下，再做dp

https://codeforces.com/contest/1366/problem/E

将当前要在a中找到的、每个subarray中的合法最小值称作目标数字。

直接从头开始线性遍历的话会遇到一个问题，就是你无法确定每个subarray中哪个数字是一定要选的，在存在连续一段目标数字的时候。而如果你把ab数组翻转一下，就会发现，遇到的第一个目标数字一定要选，如果不选的话，上一个subarray的最小值就会是它了。

并查集の新体验

https://codeforces.com/contest/1370/problem/E

分析题意得出，要做的就是求去重后的序列能拆分成多少个0101串（或1010），因为这样的串是可以一次处理完。

首先用序列自动机搞出来nxt数组，表示i及之后第一个0（1）元素的位置。然后从前向后贪心地选0101就行，有个问题就是选过的要标记vis，然后如果在找下一个元素时发现选过了，就要沿着nxt一直向下去找，这显然是n平方的。所以我们用了带路径压缩的并查集来处理。fa就表明，当当前元素不可用的时候，下一个要找谁。

https://codeforces.com/contest/1370/submission/84587433

路径压缩

1
2
3
int find(int x){
    return (fa[x]==x?x:fa[x]=find(fa[x]));
}