Codeforces Global Round 30 (Div. 1 + Div. 2)#

4题，Ranking 1.5k

A题#

只需要判断数组是否存在k,或者存在<k,也存在>k,做一下判断

1
void solve()
2
{
3
    int n;cin>>n;
4
    ve<int>a(n+1);
5
    for(int i=1;i<=n;i++) cin>>a[i];
6
    int x;cin>>x;
7
    int op=0,id1=0,id2=0;
8
    for(int i=1;i<=n;i++)
9
    {
10
        if(a[i]==x) op=1;
11
        if(a[i]>x) id1=1;
12
        if(a[i]<x) id2=1;
13
    }
14
    if(op||(id1&&id2))
15
    {
16
        cout<<"Yes\n";
17
    }
18
    else cout<<"No\n";
19
}

B题#

猜结论，猜测，出现的概率很大，对第i个位置，暴力向后跑100次

1
void solve()
2
{
3
    int n;cin>>n;
4
    ve<int>a(n+1);
5
    for(int i=1;i<=n;i++) cin>>a[i];
6
    ve<int>f;
7
    for(int i=1;i<=n;i++)
8
    {
9
        if(a[i]%2==0) f.push_back(a[i]);
10
    }
11
    if(f.size()>=2)
12
    {
13
        cout<<f[0]<<" "<<f[1]<<'\n';
14
        return ;
15
    }
16
    else
17
    {
18
        for(int i=1;i<=n;i++)
19
        {
20
            for(int j=i+1;j<=min(n,i+100);j++)
21
            {
22
                if((a[j]%a[i])%2==0)
23
                {
24
                    cout<<a[i]<<" "<<a[j]<<'\n';
25
                    return ;
26
                }
27
            }
28
        }
29
    }
30
    cout<<"-1\n";
31
}

C题#

做法比较麻烦。肯定有更简单的做法

对数组a扔到小顶堆。然后数组，b,c做按照b升序的排序。然后线段树维护数组c的区间最大值，以及最大值的下标，优先用数组a最小的，然后在数组b二分出a所能击败的位置id，查询区间[1,id]的最大值，更新小顶堆。随后修改击败位置的下标。

1
struct my_tree
2
{
3
    // 区间和
4
    #define kl (k<<1)
5
    #define kr (k<<1|1)
6

7
    struct node
8
    {
9
        int l, r, sum,id;
10
    };
11

12
    vector<node> tree;
13
    my_tree(int x)
14
    {
15
        tree = vector<node>(x*4+10);
16
    }
17

18
    void pushup(node& kk, const node& kkl, const node& kkr)
19
    {
20
        if(kkl.sum>kkr.sum) kk.sum=kkl.sum,kk.id=kkl.id;
21
        else kk.sum=kkr.sum,kk.id=kkr.id;
22
    }
23
    void pushup(int k)
24
    {
25
        pushup(tree[k], tree[kl], tree[kr]);
26
    }
27

28
    void build(int k, int l, int r, ve<int>& a)
29
    {
30
        tree[k]={l,r};
31
        if (l == r)
32
        {
33
            tree[k].sum = a[l];
34
            tree[k].id=l;
35
            return;
36
        }
37
        int mid = (l + r) >> 1;
38
        build(kl, l, mid, a);
39
        build(kr, mid + 1, r, a);
40
        pushup(k);
41
    }
42

43
    // 区间修改 // 区间替换
44
    void update(int k, int l, int r, int val)
45
    {
46
        if (tree[k].l >= l && tree[k].r <= r)
47
        {
48
            tree[k].sum = val;
49
            return;
50
        }
51
        int mid = (tree[k].l + tree[k].r) >> 1;
52
        if (l <= mid) update(kl, l, r, val);
53
        if (r > mid) update(kr, l, r, val);
54
        pushup(k);
55
    }
56

57
    node query(int k, int l, int r)
58
    {
59
        if (l <= tree[k].l && tree[k].r <= r) return tree[k];
60
        int mid = (tree[k].l + tree[k].r) >> 1;
61

62
        node kkl = {tree[k].l, mid,-1,-1};
63
        node kkr = {mid + 1, tree[k].r,-1,-1};
64
        node kk = {tree[k].l, tree[k].r,-1,-1};
65

66
        if (l <= mid) kkl = query(kl, l, r);
67
        if (r > mid) kkr = query(kr, l, r);
68
        pushup(kk, kkl, kkr);
69
        return kk;
70
    }
71
};
72
void solve()
73
{
74
    int n,m;cin>>n>>m;
75
    priority_queue<int,ve<int>,greater<>>pq;
76
    for(int i=1;i<=n;i++)
77
    {
78
        int x;cin>>x;
79
        pq.push(x);
80
    }
81
    ve<pii>a(m+1);
82
    for(int i=1;i<=m;i++) cin>>a[i].first;
83
    for(int i=1;i<=m;i++) cin>>a[i].second;
84
    function<bool(pii,pii)>cmp=[&](pii x,pii y)
85
    {
86
        if(x.first!=y.first) return x.first<y.first;
87
        return x.second>y.second;
88
    };
89
    sort(a.begin()+1,a.end(),cmp);
90
    ve<int>b(m+1),c(m+1);
91
    for(int i=1;i<=m;i++) b[i]=a[i].first,c[i]=a[i].second;
92
    my_tree te(m+1);
93
    te.build(1,1,m,c);//
94
    int ans=0;
95
    // for(int i=1;i<=m;i++) cout<<b[i]<<" \n"[i==m];
96
    // for(int i=1;i<=m;i++) cout<<c[i]<<" \n"[i==m];
97
    while(pq.size())
98
    {
99
        int x=pq.top();pq.pop();
100
        int id=upper_bound(b.begin()+1,b.end(),x)-b.begin();
101
        id--;
102
        if(id<=0) continue;
103
        auto [l,r,sum,ip]=te.query(1,1,id);
104
        // cout<<1<<" "<<id<<' '<<sum<<" "<<ip<<'\n';
105
        if(sum>0)
106
        {
107
            pq.push(max(x,sum));
108
        }
109
        if(sum>=0)
110
        {
111
            te.update(1,ip,ip,-1);
112
            ans++;//
113
        }
114
    }
115
    cout<<ans<<'\n';
116

117
}

一个更简单的做法，可以对c == 0的放到一个集合中，然后先去操作>0的，优先选择b小的，在现有的可重集合二分查找第一个可以击败b的，去更新最后在对c==0的数组做操作。这样可以简化一下线段树的码量

1
void solve()
2
{
3
    int n,m;cin>>n>>m;
4
    ve<int>a(n+1),b(m+1),c(m+1);
5
    int cnt0=0,cnt1=0;
6
    for(int i=1;i<=n;i++) cin>>a[i];
7
    for(int i=1;i<=m;i++) cin>>b[i];
8
    for(int i=1;i<=m;i++) cin>>c[i];
9
    ve<int>id0,id1;
10
    for(int i=1;i<=m;i++)
11
    {
12
        if(c[i]==0) id0.push_back(i);
13
        else id1.push_back(i);
14
    }
15
    auto cmp=[&](int l,int r)->bool
16
    {
17
        if(b[l]!=b[r]) return b[l]<b[r];
18
        return l<r;
19
    };
20
    sort(id0.begin(),id0.end(),cmp);
21
    sort(id1.begin(),id1.end(),cmp);
22
    multiset<int>se;
23
    for(int i=1;i<=n;i++) se.insert(a[i]);
24
    int ans=0;
25
    for(int k=0;k<id1.size();k++)
26
    {
27
        int i=id1[k];//优先拿出较小的b。
28
        auto it=se.lower_bound(b[i]);//找第一个大于等于他的a
29
        if(it==se.end()) break;
30
        int x=*it;//
31
        se.erase(it);
32
        x=max(x,c[i]);
33
        se.insert(x);
34
        ans++;
35
    }
36
    // for(auto x:se) cout<<x<<" ";
37
    // cout<<'\n';
38
    // cout<<ans<<'\n';
39
    for(auto i:id0)
40
    {
41
        auto it=se.lower_bound(b[i]);
42
        if(it==se.end()) break;
43
        se.erase(it);
44
        ans++;
45
    }
46
    cout<<ans<<'\n';
47

48
}

D题#

s^’[i]=s[i-1] || s^’[i]=s[i] 得到i位置一定由<i前面的位置更新，所以优先从后向前去考虑满足第i个位置前提下，如何满足<i的位置，如果第下标l<=i位置满足s[l]=t[i],这样i位置可以由l位置更新得到，此时记录[l,i]区间，对于i-1,的更新一定由<l的位置得到。

处理好每一个s[i]满足等于t[i]由l位置更新。这个操作可以nlogn的做法得到。整个s => s^’ => t的操作次数就是 $max_{i=1}^{n}$ (i-l)

1
void solve()
2
{
3
    int n,k;cin>>n>>k;
4
    ve<ve<int>>MP(27);
5
    string s,t;cin>>s>>t;
6
    for(int i=0;i<n;i++) MP[s[i]-'a'].push_back(i);
7
    ve<pii>f;
8
    int ls=n-1;
9
    for(int i=n-1;i>=0;i--)
10
    {
11
        if(MP[t[i]-'a'].size()==0)
12
        {
13
            cout<<-1<<'\n';
14
            return ;
15
        }
16
        int id=upper_bound(MP[t[i]-'a'].begin(),MP[t[i]-'a'].end(),min(i,ls))-MP[t[i]-'a'].begin();
17
        id--;
18
        if(id<0)
19
        {
20
            cout<<-1<<'\n';
21
            return ;
22
        }
23

24
        id=MP[t[i]-'a'][id];//值
25
        ls=min(ls,id);
26
        if(id<i) f.push_back({id,i});//id--->i;
27
    }
28
    int cha=0;
29
    for(int i=0;i<f.size();i++)
30
    {
31
        auto [l2,r2]=f[i];
32
        // cout<<l2<<" "<<r2<<'\n';
33
        cha=max(r2-l2,cha);
34
    }
35
    if(cha>k)
36
    {
37
        cout<<-1<<'\n';
38
        return ;
39
    }
40
    cout<<cha<<'\n';
41
    while(f.size())
42
    {
43
        ve<pii>h;
44
        for(auto [l,r]:f)
45
        {
46
            // cout<<l<<" "<<l+1<<"\n";
47
            // swap(s[l],s[l+1]);
48
            s[l+1]=s[l];
49
            l++;
50
            if(l<r) h.push_back({l,r});
51
        }
52
        cout<<s<<'\n';
53
        f=h;
54
        // ends;
55
    }
56
    // ends;
57
}

E题#

没看，并查集，重构树，最近公共祖先

待施工