Codeforces Round 907 (Div. 2)ABCF

Nannan Lv5
  2024-09-24 22:31 2024-09-24 22:31 Created   2024-09-30 20:01:31 2024-09-30 20:01:31 Updated      

Codeforces Round 907 (Div. 2) ABCF

A. Sorting with Twos

题意：给你一个数组,你可以进行以下操作：

  • 选择一个非负整数，并且
  • 把的元素减一

问：你能通过上述操作使得数组单调不减吗？

思路：对于不满足单调不减的位置，我们看他是不是的幂次的位置，如果不是那就不行。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N];
set<ll>mi;
void init(ll n)
{
    ll t = 1;
    for(int i = 0;i <= n; i++)
        mi.insert(t),t*=2;
}
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    init(1010);
    while(t--)
    {
        int n; cin>>n;
        for(int i = 1;i <= n; i++)
            cin>>a[i];
        bool ok = true;
        for(int i = 1;i < n; i++)
        {
            if(a[i]>a[i+1])
            {
                if(mi.find(i)==mi.end())
                {
                    ok = false;
                    break;
                }
            }
        }
        if(ok)
            cout<<"YES\n";
        else cout<<"NO\n";
    }


    return 0;
}

B. Deja Vu

题意：给你一个长度为的数组，和个次修改。

对于第次修改，我们把所有能整除次方的数加上,其中.问最终的数组是什么样的。

思路：一个数一定可以写成，如果那么可以被整除。考虑

其中：是奇数，那么之后不可能在被的幂次减小。那么我们可操作序列一定的一个单调递减序列。

因为，那么最多操作次，直接暴力即可。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int n,q; cin>>n>>q;
        for(int i = 1;i <= n; i++)
            cin>>a[i];

        int k = 100;
        while(q--)
        {
            int x; cin>>x;
            if(x>=k)continue;
            for(int i = 1;i <= n; i++)if(a[i]%(1<<x)==0){
                a[i]+=(1<<(x-1));
            }
            k = x;
        }

        for(int i = 1;i <= n; i++)
            cout<<a[i]<<" ";
        cout<<"\n";

    }
    return 0;
}

C. Smilo and Monsters

题意：有个山洞，每个山洞有只怪兽。现在要杀掉全部的怪兽。你有2种技能：

  • 第一种：选择一个山洞(至少有一个活着的怪兽)，我们杀死他。组合技+1
  • 第二种：使用组合技，当山洞里面怪兽数论，那么当前山洞怪兽数直接，组合技置为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
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
97
98
99
100
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        for(int i = 1;i <= n; i++)
            cin>>a[i];
        sort(a+1,a+1+n);
        ll ans = 0,x = 0;
        int l = 1,r = n;
        while(l<=r)
        {
           //cout<<"l = "<<l<<" r = "<<r<<"\n";
            if(l==r)
            {
                /*
                    d = a[l]-x

                    a[l] = 6, x = 2
                    d = 4
                    ans += d/2+1

                    a[l] = 6,x = 3
                    d = 3
                    ans += d/2 
                */
                if((a[l]-x)&1)
                {
                    ans+=(a[l]-x)/2;
                    if(x+(a[l]-x)/2>0)ans++;
                    ans++;
                }
                else
                {
                    ans+=(a[l]-x)/2+1;
                }
                break;
            }
            if(x<a[r])
            {
                int d = a[r]-x;
                //cout<<"d = "<<d<<"\n";
                if(a[l]<d)
                {
                    x += a[l];
                    ans += a[l];
                    a[l] = 0;
                    l++;
                }
                else if(a[l]==d)
                {
                    x += a[l];
                    ans += a[l];
                    a[l] = 0,a[r] = 0;
                    ans += 1,x = 0;
                    r--,l++;
                }
                else if(a[l]>d)
                {
                    a[l]-=d;
                    x += d;
                    ans += d;
                   // cout<<"d = "<<d<<"\n";
                    a[r] = 0;
                    r--,ans += 1,x = 0;
                }
            }
            else
            {
                x -= a[r];
                a[r] = 0;
                ans += 1;
                r--;
            }   
        }
        cout<<ans<<"\n";
    }


    return 0;
}
/*
13
17
13
5
10
12
14
*/

F. A Growing Tree

题意：给定一棵树，初始只含一个节点，编号为 ，初始权值为 ，设树的大小为 。

次操作：

  • ，在 下挂一个节点，编号为 ，初始权值为 。

  • ，将当前 子树中节点的权值加上 。

求所有操作完成后每个节点的点权。

思路：离线+倒序++dfs序+树状数组

对于子树的操作很容易想到转为序然后区间操作。但是考虑到是动态生成的树，那咋办捏？我们考虑离线倒着做。我们先建立出最终的树，然后对于加一个点的操作，我们就记录这个点的答案，因为这就是它的最终答案，在此之前它还不存在，那么操作也没有影响。所以我们只需要正常加就好，因为是倒着的，之前的也不会影响之后的。记得最后算1(root)的答案。

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e5 + 10;
ll  w[N];
vector<int> e[N];
int n, root, q;
int tot, l[N], r[N], tid[N], top[N], bs[N], sz[N], f[N], dep[N];

void dfs1(int u, int fa)
{
    sz[u] = 1;
    dep[u] = dep[fa] + 1;
    bs[u] = -1;
    f[u] = fa;
    for(auto v : e[u])
    {
        if(v == fa) continue;
        dfs1(v, u);
        sz[u] +=sz[v];
        if(bs[u] == -1 || sz[v] > sz[bs[u]])
            bs[u] = v;
    }
}

void dfs2(int u,int t)
{
    l[u] = ++tot;
    tid[tot] = u;
    top[u] = t;
    if(bs[u] != -1)
        dfs2(bs[u], t);
    for(auto v : e[u])
    {
        if(v == bs[u] || v == f[u])    continue;
        dfs2(v, v);
    }
    r[u] = tot;
}

template<class T>
struct BIT {
    T c[N];
    int size;
    void init()
    {
        for(int i = 0;i <= size; i++)
            c[i] = 0;
    }
    void resize(int s) { size = s;}
    T query(int x) { // 1 ... x
        assert(x <= size);
        T s = 0;
        for (; x; x -= x & (-x)) {
        s += c[x];
    }
     return s;
    }

    void modify(int x, T s) { // a[x] += s
        assert(x != 0);
        for (; x <= size; x += x & (-x)) {
            c[x] += s;
        }
    } 

     void change(int l, int r, ll val) {
        modify(l, val);
        modify(r + 1, -val); 
    }
};

BIT<ll>tr;


void solve()
{
    tot = 0;
    vector<array<int,3>>evt;
    cin>>q;
    for(int i = 1;i <= q; i++)
        e[i].clear();
    int n = 1;
    for(int i = 1;i <= q; i++)
    {
        int op; cin>>op;
        if(op==1)
        {
            int u; cin>>u;
            e[u].push_back(n+1);
            e[n+1].push_back(u);
            n++;
            evt.push_back({op,u,n});
        }else{
            int u,x; cin>>u>>x;
            evt.push_back({op,u,x});
        }
    }
    tr.init();
    tr.resize(n+10);
    root = 1;
    dfs1(root, 0);
    dfs2(root, root);

    reverse(evt.begin(),evt.end());
    int sz = n;
    //新增一个节点，我们查询它的值就是它最终的了，因为再往前他不存在
    for(auto [op,u,x] : evt)
    {
        if(op==1)
            w[x] = tr.query(l[x]);
        else
            tr.change(l[u],r[u],x);
    }
    w[1] = tr.query(l[1]);
    for(int i = 1;i <= n; i++)
        cout<<w[i]<<" ";
    cout<<"\n";
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        solve();
    }


    return 0;
}

  • Title: Codeforces Round 907 (Div. 2)ABCF
  • Author: Nannan
  • Created at : 2024-09-24 22:31:00
  • Updated at : 2024-09-30 20:01:31
  • Link: https://redefine.ohevan.com/2024/09/24/Codeforces Round 907 (Div. 2)ABCF/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
Codeforces Round 907 (Div. 2)ABCF
  1. Codeforces Round 907 (Div. 2) ABCF
    1. A. Sorting with Twos
    2. B. Deja Vu
    3. C. Smilo and Monsters
    4. F. A Growing Tree