Codeforces Round 907 (Div. 2)ABCF

A. Sorting with Twos

题意：给你一个数组\(a_1,a_2,...,a_n\),你可以进行以下操作：

• 选择一个非负整数\(m\)，并且\(2^m\le n\)
• 把\(1\le i \le 2^m\)的元素\(a_i\)减一

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

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

// 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

题意：给你一个长度为\(n\)的数组\(a\)，和\(q\)个次修改。

对于第\(i\)次修改，我们把所有能整除\(2^{x_i}\)次方的数加上\(2_{x_i-1}\),其中\((x_i\le30)\).问最终的数组是什么样的。

思路：一个数一定可以写成\(t\times 2^a\)，如果\(a\ge x\)那么可以被整除。考虑\(2^a+2^{x-1} = 2^{x-1}\times(2^{a-(x-1)}+1)\)

其中：\(2^{a-(x-1)}+1\)是奇数，那么之后不可能在被\(2\)的幂次减小。那么我们可操作序列一定的一个单调递减序列。

因为\(x_i\le30\)，那么最多操作\(30\)次，直接暴力即可。

// 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

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

• 第一种：选择一个山洞(至少有一个活着的怪兽)，我们杀死他。组合技+1
• 第二种：使用组合技，当山洞里面怪兽数论\(\ge x\)，那么当前山洞怪兽数直接\(-x\)，组合技\(x\)置为0.

思路：排序+贪心+双指针

因为一定是用小的累计，去大的里面用组合技是优的。注意特判\(l=r\)的情况。

// 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

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

\(q\) 次操作：

• \(1\ \ x\) ，在 \(s\) 下挂一个节点，编号为 \(sz+1\) ，初始权值为 \(0\) 。

• \(2\ \ x\ v\) ，将当前 \(x\) 子树中节点的权值加上 \(v\) 。

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

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

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

// 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;
}

本栏目推荐文章
• NSSCTF Round#16 Basic WriteUp
• Hey left 1 Codeforces Round 918 (Div. 4)
• vue3 获取循环的div的总宽度
• CodeForces 1312G Autocompletion
• Educational Codeforces Round 152 (Rated for Div. 2)
• codeforces 918 div4
• div滚动加载数据
• CF Beta Round 93-D.Fibonacci Sums-齐肯多夫分解、DP
• CodeForces 1329D Dreamoon Likes Strings
• CodeForces 1237H Balanced Reversals

Codeforces Round ABCF 907 Divcodeforces round 907 div codeforces round abcf 907 codeforces round 911 div codeforces round 864 div codeforces round 887 div codeforces round 863 div codeforces round 913 div codeforces round 915 div codeforces round 917 div codeforces round 912 div