C – The Number Of Good Substrings

这道题比较傻逼。

考虑记录上一个最近的\(1\)的位置\(nxt_i\)，然后显然的是：如果在\( O(n \log n) \)时间的扫描中扫描到\([l, r]\)大于当前区间，那么就考虑\(l\)左边是否有足够的零来补足长度。然后这道题就可以愉快的 AC 了。

// CF1217C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200;

int n, T, nxt[MAX_N];
char opt[MAX_N];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        int ans = 0;
        scanf("%s", opt);
        n = strlen(opt);
        for (int i = 0; i < n; i++)
            if (opt[i] == '1')
                nxt[i] = i;
            else
                nxt[i] = (i == 0 ? -1 : nxt[i - 1]);
        for (int r = 0; r < n; r++)
        {
            int number = 0;
            for (int l = r; l >= 0 && r - l < 20; l--)
            {
                if (opt[l] == '0')
                    continue;
                number |= 1 << (r - l);
                if (number <= r - (l == 0 ? -1 : nxt[l - 1]))
                    ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

D – Coloring Edges

有一个显然的结论：如果没有环，那么就直接只用一种颜色即可；如果环存在，那么就用两种颜色就行了。一开始把所有的环全部染黑，考虑在环结束的时候进行白色的染色即可，用类似 tarjan 的方法就行了。

// CF1217D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5050, MAX_E = 5050;

int head[MAX_N], current, n, m, stat[MAX_N], res[MAX_N];
bool cycle;

struct edge
{
    int to, id, nxt;
} edges[MAX_E];

void dfs(int u)
{
    stat[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (stat[edges[i].to] == 0)
            dfs(edges[i].to), res[edges[i].id] = 1;
        else if (stat[edges[i].to] == 2)
            res[edges[i].id] = 1;
        else
            res[edges[i].id] = 2, cycle = true;
    stat[u] = 2;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, src, dst; i <= m; i++)
    {
        scanf("%d%d", &src, &dst);
        edges[current].to = dst, edges[current].nxt = head[src];
        edges[current].id = i, head[src] = current++;
    }
    for (int i = 1; i <= n; i++)
        if (stat[i] == 0)
            dfs(i);
    printf("%d\n", cycle ? 2 : 1);
    for (int i = 1; i <= m; i++)
        printf("%d ", res[i]);
    return 0;
}

E – Sum Queries?

这道题大概可以猜到是用线段树进行维护。

我们其实只需要维护「坏的区间」：同位冲突的区间，然后记录每一位最小和次小的值（因为在后续的合并只会用到最小和次小的信息，这样是最优的）。线段树直接合并就行了，比较显然。

// CF1217E.cpp
#include <bits/stdc++.h>
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)
#define ll long long

using namespace std;

const ll MAX_N = 2e5 + 200, INF = 0x3f3f3f3f3f3f3f3f;

struct node
{
    ll digits[11][2];
} nodes[MAX_N << 2];

ll buf[11], n, m, ai[MAX_N];

void calc(ll x)
{
    for (int i = 0; i <= 10; i++)
        buf[i] = x % 10, x /= 10;
}

node merge(node ls, node rs)
{
    node res;
    for (int i = 0; i <= 10; i++)
        res.digits[i][0] = res.digits[i][1] = INF;
    for (int i = 0; i <= 10; i++)
    {
        res.digits[i][0] = min(ls.digits[i][0], rs.digits[i][0]);
        res.digits[i][1] = max(ls.digits[i][0], rs.digits[i][0]);
        res.digits[i][1] = min(res.digits[i][1], ls.digits[i][1]);
        res.digits[i][1] = min(res.digits[i][1], rs.digits[i][1]);
    }
    return res;
}

void build(int l, int r, int p)
{
    if (l == r)
    {
        calc(ai[l]);
        for (int i = 0; i <= 10; i++)
        {
            if (buf[i])
                nodes[p].digits[i][0] = ai[l];
            else
                nodes[p].digits[i][0] = INF;
            nodes[p].digits[i][1] = INF;
        }
        return;
    }
    build(l, mid, lson), build(mid + 1, r, rson);
    nodes[p] = merge(nodes[lson], nodes[rson]);
}

void update(ll pos, int l, int r, int p, ll val)
{
    if (l == r)
    {
        calc(val);
        for (int i = 0; i <= 10; i++)
        {
            if (buf[i])
                nodes[p].digits[i][0] = val;
            else
                nodes[p].digits[i][0] = INF;
            nodes[p].digits[i][1] = INF;
        }
        return;
    }
    if (pos <= mid)
        update(pos, l, mid, lson, val);
    else
        update(pos, mid + 1, r, rson, val);
    nodes[p] = merge(nodes[lson], nodes[rson]);
}

node query(ll ql, ll qr, ll l, ll r, ll p)
{
    if (ql <= l && r <= qr)
        return nodes[p];
    node res;
    for (int i = 0; i <= 10; i++)
        res.digits[i][0] = res.digits[i][1] = INF;
    if (ql <= mid)
        res = merge(res, query(ql, qr, l, mid, lson));
    if (mid < qr)
        res = merge(res, query(ql, qr, mid + 1, r, rson));
    return res;
}

int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ai[i]);
    build(1, n, 1);
    while (m--)
    {
        ll opt, l, r;
        scanf("%lld%lld%lld", &opt, &l, &r);
        if (opt == 1)
            update(l, 1, n, 1, r);
        else
        {
            node res = query(l, r, 1, n, 1);
            ll ans = INF;
            for (int i = 0; i <= 10; i++)
                ans = min(ans, res.digits[i][0] + res.digits[i][1]);
            if (ans >= INF)
                puts("-1");
            else
                printf("%lld\n", ans);
        }
    }
    return 0;
}