头像

清风不是峰




离线:31分钟前


最近来访(232)
用户头像
h._
用户头像
e.Gravity
用户头像
望丶穿
用户头像
kzyz
用户头像
锦木千束
用户头像
hliatmy
用户头像
Acwing_ikun
用户头像
_C_
用户头像
实干者
用户头像
清风qwq
用户头像
恩泽之少
用户头像
微风入我怀
用户头像
..-
用户头像
lorendw7
用户头像
AᴄWing
用户头像
yxc的小迷妹
用户头像
陌丨落
用户头像
17637048556
用户头像
洛琪xii
用户头像
牧濑红莉栖


#847 div3
B:

题目:

现在有 n 个 六面骰子,都随机掷出,结果构成一个序列,给出这个序列所有元素的和, 还有去掉最高元素的和。

问你可能的序列是什么

思路:

可以得到最大值是多少,其他都至少为1,不超过最大值即可

代码

void solved()
{
    int n, m, s;
    cin >> n >> m >> s;

    int mxx  = m - s;

    ans[1] = mxx;

    s -= n - 1;

    for(int i = 2; i <= n; i++) ans[i] = 1;

    for(int i = 2; i <= n; i++)
    {

        if(s - (mxx - 1) >= 0)
        {
            s -= mxx - 1;
            ans[i] += mxx - 1;
        }else
        {
            ans[i] += s;
            break;
        }
    }

    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << endl;
}
C:

题目:

原本存在一个长度为 n 的序列,现在给出 n 个 序列, 分别对应去掉下标为 1 - n ,所剩下的序列。

思路:

观察规律,开头和结尾都是出现三次的数字,然后另一个数字就是下一个的数字。

代码

void solved()
{

    memset(cnt, 0, sizeof cnt);
    memset(w, 0, sizeof w);

    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n - 1; j++)
        {
            int x;
            cin >> x;
            cnt[j][x]++;
            if(!w[j][0]) w[j][0] = x;
            else
            {
                if(x != w[j][0]) w[j][1] = x;
            }
        }
    }

    int last = 0;

    for(int i = n - 1; i >= 1; i--)
    {

        if(i == n - 1)
        {
            if(cnt[i][w[i][0]] > cnt[i][w[i][1]]) ans[i + 1] = w[i][0], last = w[i][1];
            else ans[i + 1] = w[i][1], last = w[i][0];
            continue;
        }

        if(i == 1)
        {
            if(cnt[i][w[i][0]] > cnt[i][w[i][1]]) ans[i] = w[i][0], ans[i + 1] = w[i][1];
            else ans[i] = w[i][1], ans[i + 1] = w[i][0];
            continue;
        }

        if(w[i][0] == last)
        {
            ans[i + 1] = last;
            last = w[i][1];
        }else
        {
            ans[i + 1] = last;
            last = w[i][0];
        }

    }

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

    cout << endl;

}
D:

题目:

现在存在 n 个数,让你分成最小个数的组,使得组内都是连续的数字。

思路:

首先统计一下每个数字出现的个数。然后把所有数字排序。

排序后,可以看成几个块,块内都是连续的。

对于块内:

因为组内必须是连续的,所以因为块内个数是不同的,所以块内消耗后可能又导致不连续。

如果相邻两个数字的个数存在逆序,那么后面的数字因为个数小,会被先用完。这样中间连续会被断开。

例如连续的一组内个数分别为, 2 1 3 4, 存在逆序 2 1,1用完之后, 前面的 与 后面无法共组。

那么就要单独为一组,那么他们的差就是单独共组的,直到遇到不连续的,到下一个块了。

还要加上数字中最大个数

代码

void solved()
{
    map<int, int> hs;
    vector<int> a;

    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;

        if(!hs[x])
        {
            a.push_back(x);
        }
        hs[x]++;
    }

    sort(a.begin(), a.end());

    int mxx = hs[a[0]];
    int ans = 0;
    int len = a.size();

    for(int i = 1; i < len; i++)
    {
        int x = a[i];

        if(a[i] == a[i - 1] + 1)
        {
            if(hs[a[i - 1]] > hs[a[i]])
            {
                ans += (hs[a[i - 1]] - hs[a[i]]);
            }
            mxx = (hs[a[i]]);

        }else
        {
            ans += mxx;
            mxx = hs[a[i]];
        }

        mxx = max(mxx, hs[x]);
    }

    ans += mxx;

    cout << ans << endl;

}
E:

题目:略

思路:

对于当前给出的 x,a + b >> 为 x,那么意味着当存在一位 x 上为 1,下一位 a 和 b 对应位都应该为 1,这样可以进位到当前位置。

因为 a ^ b 为 x,

存在两种情况,

当位上位 1: 那么填 0 1 或者 1 0, 对于相加来说都一样,都归为 a 为 1, b 为 0

如果位上为 0, 那么填 11 或者 00。

参考上面,如果说当前位置为1, 需要下一位都是 11,但是如果下一位为 1,就矛盾了,输出 -1。

如果说当前位置为 0,就跳过,因为前一位已经决定了。

对于最后一位,如果是 1 因为不存在下一位,肯定不合法。

代码

void solved()
{
    int x;
    cin >> x;

    int a = 0, b = 0;

    if(x & 1)
    {
        cout << -1 << endl;
        return;
    }

    for(int i = 1; i <= 30; i++)
    {
        if(x >> i & 1)
        {
            if(x >> (i - 1) & 1)
            {
                cout << -1 <<endl;
                return;
            }
        }

        if(x >> i & 1)
        {
            a += 1 << i;
            a += 1 << (i - 1);
            b += 1 << (i - 1);
        }
    }

    cout << a << " " << b << endl;

}



第三场:
B:

题目:

现在有 n 块 1 * (k) 的砖头, k 的范围是 1 <= k <= (n + 1) / 2

问你能凑成最大边长的正方形是多少。

首先边长构成二段性质,小的边长大的边长肯定能凑成。

假设当前人让凑出 mid 边长的正方形。

我们优先用最长的凑,先凑出一个 mid * (k) 的长方形,防止里面。

然后再尽可能用 1 x (n + 1) / 2 的砖头填充,然后再用短的填充。

代码

bool check(int mid)
{
    int x = (n + 1) / 2;
    if(mid + (mid + x - 1) / x * (mid - x) > n) return true;
    else return false;

}

void solved()
{
    cin >> n;

    if(n == 1)
    {
        cout << 1 << endl;
        return;
    }
    if(n == 2)
    {
        cout << -1 <<endl;
        return;
    }
    int  l = 2, r = n;


    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(check(mid)) r = mid - 1;
        else l = mid;
    }

    cout << l << endl;

}
C:

题目:

思路:

首先我们先打表前面的一些观察规律,不难发现每四个构成规律。

所以预处理出最初的 4, 5, 6 , 11, 因为 7 不存在。

根据 模 4 的取值进行往后添置四个数字即可。

代码

void solved()
{
    cin >> n;

    if(n <= 3 || (n == 7))
    {
        cout << -1 << endl;
        return;
    }

    vector<int>ans(n + 10);
    if(n % 4 == 0)
    {
        ans[1] = 3, ans[2] = 4, ans[3] = 1, ans[4] = 2;
        int now = 4;

        for(int i = 4; i <= n; i += 4)
        {

            now += 4;
            ans[i + 1] = now - 1;
            ans[i + 2] = now;
            ans[i + 3] = now - 3;
            ans[i + 4] = now - 2;
        }
    }else if(n % 4 == 1)
    {
        ans[1] = 4, ans[2] = 5, ans[3] = 1, ans[4] = 2, ans[5] = 3;

        int now = 5;

        for(int i = 5; i <= n; i += 4)
        {

            now += 4;
            ans[i + 1] = now - 1;
            ans[i + 2] = now;
            ans[i + 3] = now - 3;
            ans[i + 4] = now - 2;
        }
    }else if(n % 4 == 2)
    {
        int now = 6;
        ans[1] = 3, ans[2] = 5, ans[3] = 6, ans[4] = 1, ans[5] = 2, ans[6] = 4;

        for(int i = 6; i <= n; i += 4)
        {

            now += 4;
            ans[i + 1] = now - 1;
            ans[i + 2] = now;
            ans[i + 3] = now - 3;
            ans[i + 4] = now - 2;
        }
    }else if(n % 4 == 3)
    {
        ans[1] = 3, ans[2] = 4, ans[3] = 1, ans[4] = 6, ans[5] = 2, ans[6] = 8;
        ans[7] = 5, ans[8] = 10, ans[9] = 11, ans[10] = 7, ans[11] = 9;
        int now = 11;
        for(int i = 11; i <= n; i += 4)
        {

            now += 4;
            ans[i + 1] = now - 1;
            ans[i + 2] = now;
            ans[i + 3] = now - 3;
            ans[i + 4] = now - 2;
        }
    }

    for(int i = 1; i <= n; i++)
    {
        cout << ans[i] << " ";
    }
}
G:

题目:

思路:

DFS 搜索即可,不过需要注意的是题目的数据很大,需要使用快速幂

代码

long long qmi(long long a, long long b, int p)
{
    long long res = 1;
    while (b)
    {

        if (b & 1) res = (res % p) * (a % p) % p;

        a = (a % p) * (a % p) % p;
        b >>= 1;
    }

    return res;
}


void dfs(int u, int sum, int cnt)
{
    if(zm[u] == '=' )
    {
        if(sum != ans) return;

        int now = 0;
        cout <<sz[0];
        for(int i = 0; i < zm.size(); i++)
        {
            if(zm[i] != '?') cout << zm[i];
            else cout << ss[now++];
            cout <<sz[i + 1];

        }
        cout << endl;

        exit(0);
    }

    ss[cnt] = '-';
    dfs(u + 1, sum - sz[u + 1], cnt + 1);
            ss[cnt] = '+';
    dfs(u + 1, sum + sz[u + 1], cnt + 1);
            ss[cnt] = '#';

    if(sum > 0)
    dfs(u + 1, qmi(sum, sum, sz[u + 1]), cnt + 1);
}
void solved()
{

    cin >> s;

    int num = 0;

    for(int i = 0; i < s.size(); i++)
    {

        if(s[i] >= '0' && s[i] <= '9')
        {
            num += s[i] - '0';
            num *= 10;

            if(i == s.size() - 1)
            {
                sz.push_back(num / 10);
            }

        }else
        {
            sz.push_back(num / 10);
            num = 0;
            zm.push_back(s[i]);
        }
    }

    ans = sz[sz.size() - 1];


    dfs(0, sz[0], 0);
    cout << -1;


}



第二场:
C:

题目:

思路:

根据 A B 题可知,假如求 a的取值范围和 n - b 的取值范围的交集即可。

所以我们枚举 a 区间,去掉 a 区间对答案的影响,统计一下 交集区间内有多少个数字即可。

对于区间查询,用线段树维护数字的个数即可

代码

void push_up(int u)
{
    tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;
}

void push_down(int u)
{
    Node &root = tr[u], &le = tr[u <<1], &ri = tr[u << 1 | 1];

    if(root.lazy)
    {
        le.lazy += root.lazy;
        ri.lazy += root.lazy;
        le.cnt += (le.r - le.l + 1) * root.lazy;
        ri.cnt += (ri.r - ri.l + 1) * root.lazy;

        root.lazy = 0;
    }
}

void build(int u, int l, int r)
{
    if(l == r)
    {
        tr[u] = {l, r, 0};
        return;
    }

    tr[u] = {l, r};

    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

    push_up(u);
}

void modify(int u, int l, int r, int x)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].cnt += (tr[u].r - tr[u].l + 1) * x;
        tr[u].lazy += x;
        return;
    }

    push_down(u);

    int mid = tr[u].l + tr[u].r >> 1;

    if(l <= mid) modify(u << 1, l, r, x);
    if(r > mid) modify(u << 1 | 1, l, r, x);

    push_up(u);
}

LL query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].cnt;
    }

    push_down(u);
    int mid = tr[u].l + tr[u].r >> 1;

    LL ans = 0;

    if(l <= mid) ans = (ans + query(u << 1, l, r)) % MOD;
    if(r > mid) ans = (ans +query(u << 1 | 1, l, r)) % MOD;
    return ans % MOD;

}

vector<PII> qj;

void solved()
{
    cin >> n >> m;

    int mxx = 0;

    for(int i = 0; i < m; i++)
    {
        PII x;
        cin >> x.first >> x.second;
        qj.push_back(x);
        mxx = max(mxx, x.second);
    }

    build(1, 1, mxx);

    for(int i = 0; i < m; i++)
    {
        int l = qj[i].first, r = qj[i].second;
        modify(1, l, r, 1);
    }

    LL ans = 0;

    for(int i = 0; i < m; i++)
    {
        int l = qj[i].first, r = qj[i].second;
        modify(1, l, r, -1);


        int ri = n - l;
        int le = n - r;

        le = max(le, 1);
        ri = min(ri, mxx);

        LL sum = query(1, le, ri) % MOD;

        ans = (ans + sum) % MOD;

        modify(1, l, r, 1);
    }

    cout << ans << endl;
}

D:

题目:

思路:

不难发现,每次取子树意味着每个点获得的次数跟他的深度有关。

所以按照深度依次放球即可。

代码

void dfs(int u, int fa, int de)
{
    dep[u] = de;

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u, de + 1);
    }
}

void solved()
{
    memset(h, -1, sizeof h);

    cin >> n;


    for(int i = 2; i <= n; i++)
    {
        int x;
        cin >> x;
        add(x, i), add(i, x);
    }

    for(int i = 1; i <= n; i++)
        cin >> w[i];

    dfs(1, -1, 1);


    sort(dep + 1, dep + 1 + n, greater<int>());
    sort(w + 1, w + 1 + n, greater<int>());

    int ans = 0;

    for(int i = 1; i <= n; i++)
    {
        ans += w[i] * dep[i];
    }

    cout << ans <<endl;
}
F:

题目:

存在一个起点和终点和一些怪兽,问你能从起点走到终点的所有路径走过点的个数。

思路:

因为是统计走过点的个数,所以必须既能从起点走到终点又能从终点走到起点。

一次bfs来思考,发现并不容易维护出走到终点的路径上的点。

所以我们通过两次bfs,一次从起点,一次从终点。如果说一个点被走过两次,

意味着这个点既能走到终点又能走到起点。

代码

void bfs(PII u, bool st[N][5], int dx[2], int dy[2])
{
    queue<PII> q;
    q.push(u);

    while(q.size())
    {
        auto top = q.front();
        q.pop();

        int x = top.first, y = top.second;

        for(int i = 0; i < 2; i++)
        {
            int zx = x + dx[i], zy = y + dy[i];
            if(zx < 1 || zx > n || zy < 1 || zy > 3) continue;
            if(st[zx][zy] || g[zx][zy])continue;
            st[zx][zy] = true;

            q.push({zx, zy});

        }

    }
}

void solved()
{

    cin >> n >> k;

    for(int i = 1; i <= n; i++) for(int j = 1; j <= 3; j++) st1[i][j] = st2[i][j] = g[i][j] = 0;

    for(int i = 0; i < k; i++)
    {
        int x, y;
        cin >> x >> y;
        if(!g[x][y]) g[x][y] = true;
        else g[x][y] = false;
    }

    st1[1][1] = true;
    bfs({1, 1}, st1, dx1, dy1);
    st2[n][3] = true;
    bfs({n, 3}, st2, dx2, dy2);

    int ans = 0;


    if(!st1[n][3])
    {
        cout << 0 << endl;
        return;
    }
    for(int i = 1; i <= n;i ++)
    {
        for(int j = 1; j <= 3; j++)
        {
            if(st1[i][j] && st2[i][j]) ans++;
        }
    }

    cout << max(0, ans - 1) << endl;
}
H

题目:

注意不一定连续

思路:

方法1:

按照题目那样构造数字,首先找到最少个子序列并且值最大的情况。

比他更多子序列值不变,考虑子序列个数变少的情况。

如果子序列变少,那么肯定要融合两个子序列,贪心的来说,融合子序列值最少的两个子序列。

所以从最少个数依次往后融合即可。

每次减少的贡献为,前一个对答案的贡献,和融合后对当前子序列减少的贡献。

方法2:

对于每一个数字单独自考贡献,因为数字之间互不影响,1怎么放跟1的贡献有关,与其他数字无关。

假设 k 个子序列,如果 1 的个数有 s 个。

如果 s <= k, 那么我们每个序列放一个,贡献就是 s,如果 s > k, 那么肯定有多余的,那么我们都放在一个序列力。

贡献就是 k - 1

那么我们维护所有数字出现的个数,因为 k 越大,越能放置更多的数字,所以维护一个指针来找到 <=k 的最大

个数,这样前面的都贡献都是出现的个数,后面的都是k - 1

需要注意的是输出很多回车,’\n’ 优于 endl

法1代码

void solved()
{

    memset(cnt, 0, sizeof cnt);
    memset(cf, 0, sizeof cf);

    cin >> n;
    int mxx = 0;

    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        cnt[a[i]] ++;
        mxx = max(mxx, cnt[a[i]]);

    }

    for(int i = 1; i <= 100000; i++)
    {
        if(cnt[i])
        {
            cf[1]++;
            cf[cnt[i] + 1]--;
        }
    }

    for(int i = 1; i <= mxx; i++) cf[i] += cf[i - 1], g[i] = cf[i];
    sort(cf + 1, cf + mxx, greater<int>());


    int res = 0;


    for(int i = 1; i <= mxx; i++)
        res += cf[i];


    for(int i = mxx; i <= n; i++) ans[i] = res;


    for(int i = mxx - 1; i >= 1; i --)
    {
        res -= cf[i + 1];
        res -= g[i + 1];
        g[i] = g[i] - cf[i + 1];
        ans[i] = res;
    }

    for(int i = 1; i <= n; i++) cout << ans[i] << '\n';


}

法 2 代码

void solved()
{
    memset(cnt, 0, sizeof cnt);
    cin >> n;
    int mxx = 0;

    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        cnt[a[i]] ++;
    }

    vector<int>num;
    for(int i = 1; i <= 100000; i++) if(cnt[i]) num.push_back(cnt[i]);
    int len = num.size();
    sort(num.begin(), num.end());

    int now = 0;
    int lsum = 0;

    for(int i = 1; i <= n; i++)
    {
        while(now != len && num[now] <= i)
        {
            lsum += num[now];
            now++;
        }

        cout << lsum + (len - now) * (i - 1) << '\n';
    }
}

J:

题目:

思路:

不难发现,对于每一对数字即存在负数,也能通过题目给的两个式子做正数贡献。

所以都按照整数统计答案即可

代码

void solved()
{
    int n;
    cin >> n;
    int sum = 0;

    for(int i = 0; i < n; i++) cin >> a[i], sum += abs(a[i]);

    int ans = 0;

    for(int i = 0; i < n; i++)
    {
        ans += sum + n * abs(a[i]);
    }

    cout << ans << endl;


}
L:

题目:

思路:

题目中存在 四个变量。简单来说可以枚举其他三个变量,然后求另一个变量的个数。

三个变量的复杂度明显超时,所以我们最多枚举两个变量。

如果枚举两个变量,肯定是枚举 x 和 k,因为 i 和 j 是乘法,枚举一个必须枚举另一个。

然后我们必须知道对应 ai * aj 出现的次数,所以我们可以通过预处理来 再次枚举两个变量来预处理出余数。

需要注意的是题目要求 i j k 互不相等,我们预处理时预处理全部的对数。在统计 x 和 k 的时候,没有处理 i 和 j k 有没有相等。

所以我们维护一个二维变量为,每个下标出现的次数。这样统计答案的时候减去 i 和 j 中出现 k 的次数。

代码

void solved()
{
    scanf("%lld%lld", &n, &p);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]), a[i] %= p;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
    {
        if(i == j) continue;

        cnt1[a[i] * a[j] % p]++;
        cnt2[i][a[i] * a[j] % p] ++;
        cnt2[j][a[i] * a[j] % p] ++;
    }


    for(int i = 0; i < p; i++)
    {
        int ans = 0;

        for(int j = 1; j <= n; j++)
        {
            int x = (i - a[j] + p) % p;
            ans += cnt1[x] - cnt2[j][x];
        }

        printf("%lld ", ans);
    }

    printf("\n");


}




第一场

https://ac.nowcoder.com/acm/contest/46800#question

A:

题目:

按照 ABABABABAB, 来点球,问你在第几球结束比赛,或者没有分出胜负。

思路:

如果胜场少的一方后面都赢了,还是无法胜场大于另一方,那么已经结束比赛。

否则到最后都没分出胜负

代码

void solved()
{
    cin >> s + 1;

    int A, B;
    A = B = 0;

    bool flag = false;

    for(int i = 1; i <= 10; i++)
    {
        if(i % 2 != 0 && s[i] == '1')
            A++;

        if(i % 2 == 0 && s[i] == '1')
            B++;

        if(A > B)
        {
            if(A > B + (10 - i) / 2 + (i % 2))
            {
                flag = true;
                cout << i << endl;
                return;
            }
        }

        if(B > A)
        {
            if(B > A + (10 - i) / 2)
            {
                flag = true;
                cout << i << endl;
                return;
            }
        }
    }

    if(!flag)
    {
        cout << -1 <<endl;
    }
}
C:

题目:

思路:

不难发现,对于所有引用量 > 0, 的文章,都各自找一人发表,这样是最多的情况。

代码

void solved()
{
    int n;
    cin >> n;
    int ans = 0;

    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        if(a[i]) ans++;
    }

    cout <<ans <<  endl;
}
F:

题目:

现在存在一些树,存在一些点上有炸弹,我们找到一组方案 S T, S 为终点 T 为七点,使得我们必须经过有炸弹的点。

思路:

题目只要求方案数,所以只需要判断是否炸弹都在一个连通块内,或者不存在炸弹。

因为炸弹可以随便放,所以个数不影响答案。

对于炸弹所在连通块的数量 > 1, 那么无论如何也不能找到一个路径使得都经过。

如果数量 == 1, 那么连通块内任意两个点都可以,为连通块内点的数量 ^ 2

如果数量 == 0, 那么任意连通块都可,任意连通块参考上面

代码

void solved()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i++) p[i] = i, cnt[i] = 1;


    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        int pa = find(a), pb = find(b);
        if(pa != pb)
        {
            p[pa] = pb;
            cnt[pb] += cnt[pa];
        }
    }

    int p = 0;
    int ans = 0;
    int ans2 = 0;

    for(int i = 1; i <= n; i++)
    {
        int x, px;
        cin >> x;

        if(x)
        {
            px = find(i);
            if(!bom[px])
            {
                p++;
                ans += cnt[px] * cnt[px];
                bom[px] = true;
            }
        }
        if(i == find(i)) ans2 += cnt[i] * cnt[i];
    }


    if(!p)
    {
        cout << ans2 << endl;
    }else if(p == 1) cout << ans <<endl;
    else cout << 0 << endl;

}

G:

题目:

思路:

不难发现是区间操作,由此想到线段树,但是因为根号操作不满足线段树内合并,所以只能单点操作。

但是单点操作时间复杂度是不够的。

对于根号操作,我们打表发现,所有的数字都会归于一个数字,所以有很多操作是多余的,如果说当前操作的

数字已经归于终点,那么没必要操作了。

代码

int f(int x)
{
    return round(10 * sqrt(x));
}

void push_up(int u)
{
    tr[u].sum = tr[u << 1]. sum + tr[u << 1 | 1].sum;
    tr[u].flag = tr[u << 1].flag & tr[u << 1 | 1].flag;
}


void build(int u, int l, int r)
{
    if(l == r)
    {
        tr[u] = {l, r, a[l], 0, 0};
        return;
    }

    tr[u] = {l, r};
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

    push_up(u);
}

void modify(int u, int l, int r, int k)
{
    int lr = (tr[u].r - tr[u].l + 1);
    if(tr[u].flag) return;

    if(tr[u].l == tr[u].r)
    {

        for(int i = 0; i < k; i++)
        {
            int last = tr[u].sum;
            tr[u].sum = f(tr[u].sum);
            if(last == tr[u].sum)
            {
                tr[u].flag = true;
                break;
            }
        }
    }else
    {
        int mid = tr[u].r + tr[u].l >> 1;

        if(mid >= l) modify(u << 1, l, r, k);
        if(r > mid) modify(u << 1 | 1, l, r, k);
        push_up(u);
    }
}




void solved()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];

    build(1, 1, n);


    for(int i = 0; i < m; i++)
    {
        int op, l, r, k;
        cin >> op;

        if(op == 1)
        {
            cin >> l >> r >> k;
            modify(1, l, r, k);
        }else
        {
            cout << tr[1].sum << endl;
        }
    }
}

H:

题目:

思路:

因为题目保证了拼图是完好的,所以最终都会一个凸出对于一个凹下去。

所以我们统计目前给出的拼图的 凸凹个数,然后差来找到对应成本

代码

void solved()
{
    cin >> n;

    int p1 = 0, p2 = 0;

    for(int i = 0; i < n * n - 1; i++)
    {
        cin >> ss[i];

        int np1 = 0, np2 = 0;

        for(int j = 0; j < 4; j++)
        {
            if(ss[i][j] == '1') p1++;
            else if(ss[i][j] == '2')p2++;
        }
    }

    cout <<  p1 - p2 + 10<< endl;

}
K:

题目:

思路:

首先我们优先考虑最多放置1的,满足 0 个坏区间。

发现 1 0 0 1 0 0 1,这样放置是边界 0 个坏区间,然后接下来放一定会出现坏区间。

那么我们贪心的来说接下来肯定是连续放置1,尽可能在一个区间内。

因为后面可能出现 1 00 1 0,而前面的 1 0 0,已经固定,所以我们从后面开始放。

然后统计坏区间即可

代码

void solved()
{
    int n, m;
    cin >> n >> m;

    string s = "";

    if((n - 1) / 3 + 1 >= m)
    {
        cout << 0 << endl;
        return;
    }

    for(int i = 0; i < n; i++)
        s += '0';

    int sum = 2;
    int pos = 0 ;

    for(int i = 0; i < n; i++)
    {
        sum++;
        if(sum == 3) s[i] = '1', sum = 0, pos++;
        if(pos == m) 
            break;
    }


    sum = 0;

    for(int i = n  - 1; i >= 0; i--)
    {
        if(sum + pos == m) break;

        if(s[i] == '0') 
        {
            s[i] = '1';
            sum++;
        }
    }


    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(i + 2 == n) break;

        int sum = 0;
        for(int j = i; j < i + 3; j++)
        {
            if(s[j] == '1') sum++;
        }

        if(sum >= 2)
        {
            ans++;
        }
    }

    cout << ans << endl;
}

代码

void solved()
{
    int n, m;
    cin >> n >> m;

    string s = "";

    for(int i = 0; i < n; i++)
        s += '0';

    int sum = 2;
    int pos = 0 ;

    for(int i = 0; i < n; i++)
    {
        sum++;
        if(sum == 3) s[i] = '1', sum = 0, pos++;
        if(pos == m) 
            break;
    }


    sum = 0;

    for(int i = n  - 1; i >= 0; i--)
    {
        if(sum + pos == m) break;

        if(s[i] == '0') 
        {
            s[i] = '1';
            sum++;
        }
    }


    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(i + 2 == n) break;

        int sum = 0;
        for(int j = i; j < i + 3; j++)
        {
            if(s[j] == '1') sum++;
        }

        if(sum >= 2)
        {
            ans++;
        }
    }

    cout << ans << endl;
}
M:

题目:

思路:

不难发现,每一个前面的送出多少仙贝都影响后面,所以思考 dp。

状态表示:f[i][j] 表示已经给了 i个人,还剩下 j 个仙贝。

状态转移

首先枚举 i j,其次要枚举当前第 i 个人要给多少仙贝。

所以 f[i][j] = max(f[i][j], f[i - 1][j + k] + (k) / (j + k));

最后统计答案,看看给了 n 个人,剩下多少个仙贝的好感度最多。。

代码

void solved()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j >= 0; j--)
        {            
            for(int k = 0; k <= m; k++)
            {
                if(j + k <= m)
                f[i][j] = max(f[i][j], f[i - 1][j + k] + (k * 1.0 /(j + k)));
            }
        }
    }

    long double ans = 0;

    for(int i = 0; i <= m; i++) ans = max(ans, f[n][i]);

    printf("%.8llf",ans);
}



#843 div2

https://codeforces.com/contest/1775

A2:

题目

给出一个字符串只包含AB,让你拆分成三个非空子串,a.b.c,满足两个条件其中一个

1.a <=b , c <= b

2.b <= a, b <= c

A,数据范围小,统一看B做法

思路:

观察条件发现关键在中间那个子串,所以我们设法去构造中间那个。所以中间那个不能包含两边边界的字母。

假设除了边界存在一个 a, 那么我只选择中间的 ‘a’, 这样满足最小,即使其他地方出现了 ‘aa’, 但符合 a <= aa ab

如果不存在,那么除了除了边界,中间全是 b,那么直接取中间所有毫无疑问是最大字典序。

代码

void solved()
{
    string s;
    cin >> s;

    int pos = -1;

    for(int i = 0; i < s.size(); i++)
    {
        if(s[i] == 'a' && i != 0 && i != s.size() - 1)
        {
            pos = i;
            break;
        }
    }

    if(pos != -1)
    {
        for(int i = 0; i < pos; i++) cout << s[i]; cout << " a " << " ";
        for(int i = pos + 1; i < s.size(); i++) cout << s[i];
        cout << endl;
    }else
    {
        cout << s[0] << " ";
        for(int i = 1; i < s.size() - 1; i++) cout << s[i];
        cout << " " << s[s.size() - 1];
        cout << endl;
    }
}
B:

题目:

给出一个序列,问你能不能找到一个两个子序列 a,b ,使得 a 中所有的数字取或,b中所有数字取或,使得 两个数字相等。

思路:

题目 给出了每个 a[i] 二进制形式。

假设两个子序列就差一个元素,并且他们 f 都相同,说明相差的这个元素的所有位置上的1,其他元素都是存在的。

那么就成立,否则,就必须包含都包含这个元素。假设全部元素都有自己独特的 1, 那么肯定是构不成的。

代码

void solved()
{
    map<int,int>cnt;

    int n;
    cin >>  n;
    int mxx = 0;
    for(int i = 0; i < n; i++)
    {
        int k;
        cin >> k;
        w[i].clear();
        for(int j = 0; j < k; j++)
        {
            int x;
            cin >> x;
            w[i].push_back(x);
            cnt[x]++;
        }
    }

    for(int i = 0; i < n; i++)
    {
        bool flag = false;

        for(int j = 0; j < w[i].size(); j++)
        {
            int x = w[i][j];

            if(cnt[x] == 1)
            {
                flag = true;
            }
        }

        if(!flag)
        {
            cout << "YES" << endl;
            return ;
        }
    }


    cout << "NO" << endl;


}
C:

题目:

给出两个数字 n 和 x, 问你能不能找到合法的最小 m 使得 n & (n + 1).. m == x

思路:

首先拆成二进制来思考,我们对比 n 和 x,分出来其中的情况,来构造 m。

对于相同位置上

1.n - 0, x - 1

这种情况一定不会出现,因为是&运算,意味着存在一个 0,就一直为0,所以输出- 1

2.n - 0, x - 0

这种情况对于中间的数字来说,是 1 是 0, 都不影响

3.n - 1, x - 1

这种情况来说,我们要求 n - m 中对应位置上不允许出现 0

4.n - 1, x - 0,

那么我们要求,n - m 对应位置上需要 >= 1 个 0

因为 n - m 是逐渐增加 1, 这就意味着,在二进制中逐渐进位。

1,2 两种情况不需要特别考虑但对于 3, 4 有特别要求。

对于 3 来说,对应位上不能出现0,那么意味着 n - m 中到这位不能存在进位,因为进位意味着从 1 变为0

对 4 来说,我们需要从 n - m 中,这位进位,这样至少满足一个 0。

对于进位来说,意味着我们的终点 m,对应于 n 中,一个位置上的数字从 0 变为 1,代表它后面的数字都进位了。

从 0 变1,那么肯定是 0 - 0,我们可1, 可0,这时候需要一个变为1 来进位,因为 m 尽可能的小,所以需要找到最小的 0 - 0 位

这样假设说 1 - 0 不能出现在 1 - 1, 的前面,这样对于两个要求都冲突。

并且我们要变 0 为 1, 的位置也不能出现在 11 的前面,不然同样进位与 1 1 冲突

代码

void solved()
{
    int n, m;
    cin >> n >> m;

    vector<int> wn, wm;

    int n1  = n, m1 = m;

    if(n1 == 0) wn.push_back(0);
    if(m1 == 0) wm.push_back(0);

    while(n1) wn.push_back(n1 % 2), n1 /= 2;
    while(m1) wm.push_back(m1 % 2), m1 /= 2;

    if(wm.size() > wn.size())
    {
        cout << -1 << endl;
        return;
    }

    int ln = wn.size(), lm = wm.size();

    for(int i = 0; i < ln - lm;i ++)
    {
        wm.push_back(0);
    }

    int ans = 0;
    bool flag = false;
    int pos00 = wm.size();
    bool h10 = false;
    bool h00 = false;
    int pos11 = 1e9;

    for(int i = wn.size() - 1; i >= 0; i--)
    {
        if(wn[i] == 0 && wm[i] == 1)
        {
            cout << -1 << endl;
            return;
        }

        if(wn[i] == 1 && wm[i] == 0)
        {
            h10 = true;

            if(!h00)
            {
                h00 = true;
                ans += 1ll << (pos00);

                if(pos00 >= pos11)
                {
                    cout << -1 << endl;
                    return;
                }
            }
        }

        if(wn[i] == 0 && wm[i] == 0)
        {
            pos00 = i;
        }

        if(wn[i] == 1 && wm[i] == 1)
        {
            if(h10)
            {
                cout << -1 << endl;
                return;
            }

            pos11 = i;

            ans += 1ll << i;

        }
    }

    cout << ans << endl;
}
D:

题目:

现在存在 n 个数字,如果说两个数字的 gcd 不等于 1, 那么这个数字存在一条为 1 的边。

给出一个起点和终点,问你两个数字的最短代价。

思路:

首先肯定不能两两数字建边,肯定会MLE。

所以我们记录每个数字的质因子,让每个数字和他们的质因子建边。

找每个数的质因子,我们通过欧拉筛来找到最小质因子,然后找到所有质因子。

让两两数字通过质因子来可以相互到达。 设质因子为虚拟点。

这样我们通过质因子为桥,大大缩短边的个数,边为 2* n, 否则为n ^ 2

然后 01 bfs

代码

int bfs()
{
    deque<int>q;
    q.push_back(start);

    memset(dist, 0x3f,sizeof dist), memset(vis, 0, sizeof vis);
    dist[start] = 0;

    while(q.size())
    {
        int top = q.front();
        q.pop_front();
        if(vis[top]) continue;
        vis[top] = true;

        for(int i = h[top]; i != -1; i = ne[i])
        {
            int j = e[i];
            int ww = w[i];

            if(ww == 0)
            {
                if(dist[j] > dist[top])
                {
                    dist[j] = dist[top];
                    pre[j] = top;
                    q.push_front(j);
                }
            }else
            {
                if(dist[j] > dist[top] + 1)
                {
                    dist[j] = dist[top] + 1;
                    pre[j] = top;
                    q.push_back(j);
                }
            }

        }
    }

    if(dist[edd] >= 0x3f3f3f3f / 2) return -1;
    return dist[edd];
}

void solved()
{
    idx = 0;
    cin >> n;
    memset(h, -1, sizeof h);


    int mxx = 0;
    for(int i = 1; i <= n; i++) cin >> a[i], mxx = max(mxx, a[i]);
    cin >> start >> edd;

    map<PII, int> mp;


    if(start == edd)
    {
        cout << 1 << endl;
        cout << edd <<endl;
        return;
    }

    if(a[start] == a[edd])
    {
        if(a[start] == 1)
        {
            cout << -1 << endl;
            return;
        }

        cout << 2 << endl;
        cout << start << " " << edd << endl;
        return;

    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = a[i]; j >= 2; j /= st[j])
        {

            if(mp[{i, st[j]}]) continue;

            add(st[j] + n, i, 1);
            add(i, st[j] + n, 0);

            mp[{i, st[j]}] = 1;
        }
    }


    int ans = bfs();


    if(ans == -1)
    {
        cout << -1 << endl;
    }else
    {

        vector<int>res;
        int now = edd;

        while(now != start)
        {
            if(now <= n) res.push_back(now);
            now = pre[now];
        }

        res.push_back(start);
        cout << res.size() << endl;
        for(int i = res.size() - 1; i >= 0; i--) cout << res[i] << " ";
        cout << endl;

    }
}



对区间进行开平方,不符合懒标记的要求,不能从大区间分道小区间。
所以只能单调修改。
但是因为修改的时候是开平方,开平方超过10次,就变为1,再开也相同。
所以遇到区间内都是1的情况,我们不用开,直接return,这样可以节省大部分时间

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;

struct Node
{
    int l, r;
    LL sum;
}tr[N * 4];

int n, m;
LL a[N];

void push_up(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r)
{
    if(l == r)
    {
        tr[u] = {l, r, a[l]};
        return;
    }

    tr[u] = {l, r};


    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

    push_up(u);
}

void modify(int u, int l, int r)
{


    if(tr[u].r - tr[u].l + 1 == tr[u].sum) 
    {
        return;
    }

    // cout << tr[u].l << " " << tr[u].r << endl;

    if(tr[u].l == tr[u].r && tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum = sqrt(tr[u].sum);
        return;
    }

    int mid = tr[u].l + tr[u].r >> 1;

    if(mid >= l) modify(u << 1, l, r);
    if(r > mid) modify(u << 1 | 1, l, r);

    push_up(u);
}

LL query(int u, int l, int r)
{

    // cout << tr[u].l << " " <<tr[u].r << endl;

    if(tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].sum;
    }

    LL ans = 0;
    int mid = tr[u].l + tr[u].r >> 1;

    if(l <= mid) ans += query(u << 1, l, r);
    if(r > mid) ans += query(u << 1 | 1, l, r);

    return ans;
}

int main()
{
    ios::sync_with_stdio(false);

    int T = 1;

    while(cin >> n)
    {
        cout << "Case #" << T ++ << ":" <<endl;

        for(int i = 1; i <= n; i++) cin >> a[i];

        build(1, 1, n);


        cin >> m;
        for(int i = 0; i < m; i++)
        {
            LL op, l, r;
            cin >> op >> l >> r;

            if(l > r) swap(l, r);
            if(op == 0)
            {
                modify(1, l, r);
            }
            else
            {
                cout << query(1, l, r) << endl;
            }
        }
        cout << endl;
    }

}



活动打卡代码 AcWing 4343. 数颜色

线段树。
因为题目是数线段的个数,不是端点,可能出现端点不同,但是线段是一个。
将 tr[i] 表示 i - i + 1, 为 col 颜色

#include<bits/stdc++.h>
using namespace std;
const int N = 80000 + 10;
int n;

struct Node
{
    int l, r;
    int col;
    int lazy;
}tr[N * 4];

void push_down(int u)
{
    Node &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];

    if(root.lazy != -1)
    {
        l.col = r.col = root.lazy;
        l.lazy = r.lazy = root.lazy;
        root.lazy = -1;
    }
}

void build(int u, int l, int r)
{
    if(l == r)
    {
        tr[u] = {l, r, -1, -1};
        return;
    }

    tr[u] = {l, r, -1, -1};

    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}



void modify(int u, int l, int r, int w)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].col = w;
        tr[u].lazy = w;
        return;
    }else
    {
        push_down(u);

        int mid = tr[u].l + tr[u].r >> 1;

        if(l <= mid) modify(u << 1, l, r, w);
        if(r > mid) modify(u << 1 | 1, l, r, w);
    }


}

int query(int u, int l, int r)
{
    if(tr[u].l == tr[u].r)
    {
        return tr[u].col;
    }

    push_down(u);

    int mid = tr[u].l + tr[u].r >> 1;

    if(l <= mid) return query(u << 1, l, r);
    if(r > mid) return query(u << 1 | 1, l, r);

    return -1;
}

int main()
{
    while(cin >> n)
    {
        build(1, 1, 80001);

        map<int, int> sum;

        int mxx = 0;

        for(int i = 0; i < n; i++)
        {
            int w, l, r;
            cin >> l >> r >> w;
            l++, r++;

            mxx = max(mxx, r);
            modify(1, l, r - 1, w);
        }

        int col =  query(1, 1, 1);

        if(col != -1)
        sum[col]++;

        for(int i = 1; i < mxx; i++)
        {
            int x = query(1, i, i);
            if(x != col && x != -1) sum[x]++, col = x;
        }

        for(auto x : sum)
        {
            cout << x.first << " " << x.second << endl;
        }

        cout << endl;

    }


    return 0;
}



Hello 2023

https://codeforces.com/contest/1779

A:

题目:给出一个字符串,只包含 L, R, L 表示从 1- l -1, 都被照亮, R 表示 从 R + 1 - n 都被照亮。

先问你只能改变一次,交换相邻两项,问你能不能使得所有的字符串被照亮

思路:

如果存在一个 R的位置小于 L 的位置,或者存在连续的 LR,我们交换一次。

代码

void solved()
{
    cin  >> n;
    string s;
    cin >> s;

    bool flag = false;

    bool pl, pr;
    pl = pr = false;

    for(int i = 0; i < n; i++)
    {
        if(pr == true && pl == false && s[i] == 'L')
        {
            cout << 0 << endl;
            flag = true;
            return;
        }

        if(s[i] == 'L') pl = true;
        else pr = true;
    }

    for(int i = 0; i < n - 1; i++)
    {

        if(s[i] == 'L' && s[i + 1] == 'R')
        {
            cout << i  + 1 << endl;
            flag = true;
            return;
        }
    }

    if(flag == false)
    {
        cout << -1 << endl;
    }

}
B:

题目:

请你找出一个数组满足,任意相邻两项的和等于全部数字的和。

思路:

不难发现对于偶数个数,直接取全部相邻两个是相反数即可。

对于奇数

我们把等式表示出来

a1 + a2 = a1 + a2 + a3 +.... an

0 = a3 + … an;

因为相邻两项必须是相反数。 我们把小于 0 移等号右边, 大于0 等号左面

a3 + a5 +.. a n-1 = a4 + a6 + .. an

两边元素个数不同,再次转移等式

a3 = (a4 - a5) + (a6- a7) + (an - 1 - an)

因为任意相邻两项都是相等的。

所以 a3 = (a4 - a3) * (n / 2 - 1)

任意相邻两项随便取一个数字 取 1 好计算,

所以a3 = n / 2 - 1, a4 = a3 + 1

但是我们发现对于 n == 3的情况时候 带入 3/ 2 -1 为0, 不符合题目要求,所以不存在

代码

void solved()
{
    cin >> n;

    if(n == 3)
    {
        cout << "NO" << endl;
        return;
    }

    cout << "YES" <<endl;

    if(n % 2 == 0)
    {
        for(int i = 1; i <= n; i++)
        {
            if(i % 2 != 0)
            cout << 1 << " ";
            else cout << -1 << " ";
        }

        cout << endl;
    }else
    {
        int x =  n / 2 - 1;
        int y = - x - 1;

        for(int i = 1; i <= n; i++)
        {
            if(i & 1) cout << x <<" ";
            else cout << y << " ";
        }

        cout << endl;

    }
}

C:

题目:

现在存在一个数组a,给出一个 m。

存在一个操作可以选择任意一个 i

将 ai = -ai

我们定义 s 数组为前缀和数组,问你最小操作次数满足 s[i] >= s[m] i 是任意下标

思路:

毫无疑问 m 将整个数组分为三部分。

为 m - 1 和 m + 1 和 m。

1.对于 m来说,要满足 sm是最小值,那么 m 必须 <= 0, 否则,再 s[m - 1] + a[m] > s[m]

前提是 m > 1, 所以对 m 的情况特判一下。

2.对于 1 - m -1 来说,题目给出的不等式变换一下 0 >= ak + 1.... + a[m - 1]

所以我们要满足 1- m - 1的后缀必须小于 0

3.对于 m + 1 - n 来说 am + 1… a[k] >= 0, 满足 m + 1 - k 的前缀 >= 0

对于 2 3 两种情况,如果说存在一个 s[i],不满足不等式,那么我们就通过操作来满足。

例如情况 3,出现不满足,那么我们需要让 s[i] 变大,贪心的来说找到 s[i] 的前缀中,最小的那个数字,通过变换来增大 s[i]

直到满足条件。 所以我们通过堆来维护最大值,取堆顶找到最大值。

情况 2 同理

代码

void solved()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >> a[i];


    priority_queue<int> q;
    int sum, ans = 0;

    if(n == 1)
    {
        cout << 0 << endl;
        return ;
    }

    if(a[m] > 0 && m > 1) ans++, a[m] *= -1;
    sum += a[m];

    for(int i = m - 1; i >= 2; i --)
    {
        sum += a[i];
        q.push(a[i]);

        while(sum > 0)
        {
            int x = q.top();
            q.pop();
            x*=-1;
            sum += 2 * x;
            ans++;
        }
    }

    sum  = 0;

    priority_queue<int, vector<int>, greater<int>> q2;

    for(int i = m + 1; i <= n; i++)
    {
        sum += a[i];
        q2.push(a[i]);

        while(sum < 0)
        {
            int x= q2.top();
            q2.pop();
            x*=-1;
            sum += 2 * x;
            ans++;
        }
    }

    cout << ans << endl;

}

D:

题目:

现在存在两个数组a, b,存在一些工具。我们要通过工具使得 a 变为 b。

工具存在一个值 x, x 能够把任意范围的值都变为 min(a[i], x)

现在问你能不能成功

思路:

因为工具是把长的变成短的。 如果说 a 数组对应于 b 数组的值,存在 a[i] < b[i]

那么我们不可能成功

所以考虑最优解,对应一个工具 x,我们尽可能的包括 b[i] == x

假如 b[l] == b[r], 那么我们最多用两个工具,最少用一个。

如果用一个,那么 b[l] ~ b[r] 中的最大值必须 < x

这样保证用完之后不会影响其他 bi 的操作,否则 bi > x, 如果用了之后 b变小,那么无论用什么工具都无法变回来。

所以我们找到每个数字找到所有的下标,看看相邻两个数字能不能共用一个工具,或者相邻三个等等。

所以需要在找到区间的最大值,那么需要数据结构来维护。

维护最值可以用 ST 表和 线段树。

代码

void init()
{
    for(int j = 0; j < M; j++)
    {
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            if(!j) f[i][j] = b[i];
            else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
}

int query(int l, int r)
{
    int len = r - l + 1;

    int k = log(len) / log(2);

    return(max(f[l][k], f[r - (1 << k) + 1][k]));
}


void solved()
{
    cnt.clear();


    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    cin>> m;
    for(int i = 1; i <= m; i++) cin >> w[i], cnt[w[i]]++;




    for(int i = 1; i <= n; i++)
    {
        if(a[i] < b[i])
        {
            cout << "NO" << endl;
            return;
        }
    }

    init();
    map<int, vector<int>>hs;

    for(int i = 1; i <= n; i++) if(b[i] != a[i])hs[b[i]].push_back(i);

    for(auto x : hs)
    {
        int now = x.first;
        vector<int> pos = x.second;

        int ans = 1;

        int l, r;
        if(pos.size() != 1)
            l = pos[0], r = pos[1];
        for(int i = 0; i < pos.size() - 1; i++)
        {
            r = pos[i + 1];

            if(query(l, r) > now)
                l = pos[i + 1], ans++;
        }

        if(cnt[now] < ans)
        {

            cout << "NO" << endl;
            return;
        }

    }

    cout << "YES" << endl;



}


活动打卡代码 AcWing 1273. 天才的记忆

参考区间dp
求区间最值

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 18;

int n, m;
int f[N][M];
int a[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int j = 0; j < M; j++)
    {
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            if(!j) f[i][j] = a[i];
            else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }

    cin >> m;

    for(int i = 0; i < m; i++)
    {
        int l, r;
        cin >> l >> r;
        int len = r - l + 1;

        int k = log(len) / log(2);

        cout << max(f[l][k], f[r - (1 << k) + 1][k]) << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1285. 单词

因为我们的队列存的从第一层到最后一层,所以我们从最后一层开始遍历,这样可以让长度小的字符串。
在大的出现过的直接递推得到。

#include<bits/stdc++.h>
using namespace std;

const int N = 1000010;
int tr[N][26], idx;
int id[210], f[N];
char str[N];
int q[N], ne[N];
int n;

void insert(int x)
{
    int p = 0;

    for(int i = 0; str[i]; i++)
    {
        int t = str[i] - 'a';

        if(!tr[p][t]) tr[p][t] = ++ idx;
        p = tr[p][t];

        f[p]++;
    }

    id[x] = p;
}

void build()
{
    int hh = 0, tt = -1;

    for(int i = 0; i < 26; i++) if(tr[0][i]) q[++tt] = tr[0][i];


    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = 0; i < 26; i++)
        {
            int j = tr[t][i];

            if(!j) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[j] = tr[ne[t]][i];
                q[++tt] = j;
            }
        }
    }
}


int main()
{
    cin >> n;

    for(int i = 1; i <= n; i++) cin >> str, insert(i);     

    build();

    for(int i = idx - 1; i >= 0; i--) f[ne[q[i]]] += f[q[i]];

    for(int i = 1; i <= n; i++) cout << f[id[i]] << endl;
}