牛客练习赛111 题解

列竖式

对于每个 $AA$，考虑最低的第 $ii$ 位不为0的数 $XX$，$B=(10-X)\ast 10^{i}B\; =\; (10-X)*10^i$。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
    int x;
    cin >> x;
    int t =  1;

    while (x) {
        if (x % 10) {
            cout << (10 - x % 10)*t << '\n';
            return ;
        }

        t = t * 10;
        x /= 10;
    }

}
int main() {
    //  freopen("a.txt","r",stdin);
    int T = 1;
    cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

一次交换

考虑 $S_1[i]\mathrm{\ne }{S}_2[i]S\_1[i]\; \backslash neq\; S\_2[i]$的位置个数 $cntcnt$，

1)$cnt\ge 3cnt\backslash geq3$ 或 $cnt=1cnt=1$，无解

2)$cnt=2cnt=2$，交换着两个位置后不相等，无解。

3)$cnt=0cnt=0$，$S_{1}S\_1$ 不存在两个相同字符，无解。

否则，有解。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, M = 1e6 + 10;
char s1[N], s2[N];
int b[30];
void solve() {
    int n;
    cin >> n;
    cin >> s1 + 1;
    cin >> s2 + 1;
    int cnt = 0;
    multiset<char>st1, st2;

    for (int i = 1; i <= n; ++i) {
        b[s1[i] - 'a']++;
        st1.insert(s1[i]);
        st2.insert(s2[i]);

        if (s1[i] != s2[i]) {
            ++cnt;
        }
    }

    bool flg = 0;

    for (int i = 0; i < 26; ++i) {
        if (b[i] > 1)
            flg = 1;
    }

    if (st1 != st2) {
        puts("NO");
        return ;
    }

    if (cnt == 2 || cnt == 0 && flg) {
        puts("YES");
    } else
        puts("NO");

}
int main() {
    //  freopen("a.txt","r",stdin);
    int T = 1;

    //  cin>>T;
    while (T--) {
        solve();
    }

    return 0;
}

简单的数学题

显然 $kk$ 满足 $k⩽\lfloor \frac{m}{x}\rfloor k\; \backslash leqslant\; \backslash lfloor\; \backslash frac\{m\}\{x\}\; \backslash rfloor$时，$k⩽\lfloor \frac{m}{y}\rfloor k\; \backslash leqslant\; \backslash lfloor\; \backslash frac\{m\}\{y\}\; \backslash rfloor$。 $k>\lfloor \frac{m}{x}\rfloor k\; >\; \backslash lfloor\; \backslash frac\{m\}\{x\}\; \backslash rfloor$时，$k>\lfloor \frac{m}{y}\rfloor k\; >\; \backslash lfloor\; \backslash frac\{m\}\{y\}\; \backslash rfloor$。

则原问题要求有多少个 $yy$ 使得 $\lfloor \frac{m}{x}\rfloor =\lfloor \frac{m}{y}\rfloor \backslash lfloor\; \backslash frac\{m\}\{x\}\; \backslash rfloor\; =\; \backslash lfloor\; \backslash frac\{m\}\{y\}\; \backslash rfloor$，显然 $yy$ 存在于一个区间，可以二分得到大小。

或者直接用数论分块的结论，区间为$[\lfloor \frac{m}{\lfloor \frac{m}{x}+1\rfloor }\rfloor +1,\lfloor \frac{m}{\lfloor \frac{m}{x}\rfloor }\rfloor ][\backslash lfloor\; \backslash frac\{m\}\{\backslash lfloor\; \backslash frac\{m\}\{x\}+1\; \backslash rfloor\}\; \backslash rfloor+1,\backslash lfloor\; \backslash frac\{m\}\{\backslash lfloor\; \backslash frac\{m\}\{x\}\; \backslash rfloor\}\; \backslash rfloor]$，$ans=\lfloor \frac{m}{\lfloor \frac{m}{x}\rfloor }\rfloor ]-\lfloor \frac{m}{\lfloor \frac{m}{x}+1\rfloor }\rfloor ans=\backslash lfloor\; \backslash frac\{m\}\{\backslash lfloor\; \backslash frac\{m\}\{x\}\; \backslash rfloor\}\; \backslash rfloor]-\backslash lfloor\; \backslash frac\{m\}\{\backslash lfloor\; \backslash frac\{m\}\{x\}+1\; \backslash rfloor\}\; \backslash rfloor$。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, M = 1e9;
void solve() {
    int m, x;
    cin >> m >> x;
    int L, R;
    int l = x, r = m;

    while (l < r) {
        int mid = (l + r + 1) >> 1;

        if (m / mid == m / x)
            l = mid;
        else
            r = mid - 1;
    }

    R = l;
    l = 1, r = x;

    while (l < r) {
        int mid = (l + r) >> 1;

        if (m / mid == m / x)
            r = mid;
        else
            l = mid + 1;
    }

    L = l;
    cout << R - L + 1 << '\n';
}
int main() {
    //  freopen("a.txt","r",stdin);
    int T = 1;
    cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

青蛙兔子的约会

设青蛙走了 $xx$ 步，兔子走了 $yy$ 步，则青蛙和兔子相遇满足 $ax+by=nax+by=n$ 。首先判断有解情况即 $gcd(a,b)\mathrm{\mid }ngcd(a,b)|n$ 。利用扩展欧几里得算法可以求出$x=x0+b\mathrm{/}d\times kx=x0+b/d\; \backslash times\; k$ ，令 $p=b\mathrm{/}dp=b/d$

则原问题让我们求 $L⩽x0+p\times k⩽RL\; \backslash leqslant\; x0+p\; \backslash times\; k\; \backslash leqslant\; R$是否有解，则令$l=\lceil \frac{L-x0}{p}\rceil l=\backslash lceil\; \backslash frac\{L\; -x0\}\{p\}\; \backslash rceil$, $r=\lfloor \frac{R-x0}{p}\rfloor r=\backslash lfloor\; \backslash frac\{R\; -x0\}\{p\}\; \backslash rfloor$

若 $l>rl>r$ 无解，否则有解。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 1e9;

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

void solve() {
    int a, b, n, L, R;
    cin >> a >> b >> n >> L >> R;

    int x, y;
    int d = exgcd(a, b, x, y);

    if (n % d != 0) {
        puts("NO");
        return ;
    }

    int p = b / d;
    x = (LL)x * n / d % p;
    x = (x % p + p) % p;

    int l, r;

    if (L - x < 0)
        l = 0;
    else
        l = (L - x + p - 1) / p;

    if (R - x < 0)
        r = -1;
    else
        r = (R - x) / p;

    if (l > r)
        puts("NO");
    else
        puts("YES");
}
int main() {
    //  freopen("a.txt","r",stdin);

    int T = 1;
    cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

树上游戏

考虑Bob赢的情况需要同时满足以下两种情况

1）割边得到子树的叶子节点先手赢的个数应该等于总共的叶子节点赢的个数，否则Alice能通过除子树外的节点赢。

2）然后考虑子树内，是否无法先手获胜，由于每次割一条边 $u,vu,v$，只改变先手从 $v,fa(v)v,fa(v)$ 作为起点是否获胜的状态，则可以推得整个子树的状态。

考虑 $dp(u,s1,s2)(s1,s2=0\mathrm{/}1)dp(u,s1,s2)\; (s1,s2\; =\; 0/1)$， 表示先手从 $uu$ 开始是否获胜 $s_{1}s\_1$ ,先手从 $fa(u)fa(u)$ 开始是否获胜为$s_2,us\_2,\; u$ 节点子树下叶子节点是否存在先手必胜。

假设 $a[v]=3a[v]\; =\; 3$，则 $u,fa(u)u,fa(u)$ 只要存在一个点先手从该节点输的，则在 $vv$ 这个节点先手必胜即 $dp(u,s1,s2)\mathrm{\mid }=dp(v,(!s1)\mathrm{\mid }\mathrm{\mid }(!s2),s1)dp(u,s1,s2)\; \backslash \; |=\backslash \; dp(v,(!s1)\; ||\; (!s2),s1)$。

$a[v]=1,2a[v]\; =\; 1,2$ 同理可知。

对于叶子节点 $dp(u,s1,s2)=s1dp(u,s1,s2)\; =\; s1$。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MX = 1e5;
const int N = 5e5 + 10, M = 1e6 + 10;
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int f[N][2][2], g[N], sz[N], a[N], u[N], v[N], dep[N];
int tot = 0;
void dfs1(int u, int f1, int f2) {
    if (f1 >= 1 && a[u] == 1)
        g[u] |= (!g[f1]);

    if (f2 >= 1 && a[u] == 2)
        g[u] |= (!g[f2]);

    if (f1 >= 1 && a[u] == 3)
        g[u] |= (!g[f1]);

    if (f2 >= 1 && a[u] == 3)
        g[u] |= (!g[f2]);

    bool flg = 1;

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];

        if (j == f1)
            continue;

        dep[j] = dep[u] + 1;
        flg = 0;
        dfs1(j, u, f1);
        sz[u] += sz[j];
    }

    if (flg) {
        if (g[u])
            sz[u] = g[u];

        tot += g[u];
    }
}
void dfs2(int u, int fa) {
    bool flg = 1;

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];

        if (j == fa)
            continue;

        flg = 0;
        dfs2(j, u);

        for (int s1 = 0; s1 < 2; ++s1) {
            for (int s2 = 0; s2 < 2; ++s2) {
                if (a[j] == 1)
                    f[u][s1][s2] |= f[j][!s1][s1];

                if (a[j] == 2)
                    f[u][s1][s2] |= f[j][!s2][s1];

                if (a[j] == 3)
                    f[u][s1][s2] |= f[j][(!s1) || (!s2)][s1];
            }
        }
    }

    if (flg) {
        for (int s1 = 0; s1 < 2; ++s1) {
            for (int s2 = 0; s2 < 2; ++s2) {
                f[u][s1][s2] = s1;
            }
        }
    }
}
void solve() {
    int n;
    cin >> n;
    memset(h, -1, sizeof h);

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

    for (int i = 1; i <= n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        u[i] = a, v[i] = b;
        add(a, b);
        add(b, a);
    }

    dfs1(1, 0, -1);
    dfs2(1, 0);

    for (int i = 1; i <= n - 1; ++i) {
        int a = u[i], b = v[i];

        if (dep[a] > dep[b]) {
            swap(a, b);
        }

        if (sz[b] == tot && !f[b][0][1]) {
            puts("Bob");
        } else
            puts("Alice");
    }
}
int main() {
    //  freopen("a.txt","r",stdin);
    int T = 1;

    //  cin>>T;
    while (T--) {
        solve();
    }

    return 0;
}

摆书

对于每个区间 $[l,r][l,r]$ 内的 $xx$，容易知道一定是左边一部分 $xx$ 移动到左边界外，右边一部分 $xx$ 移动到右边界外。

枚举左边有多少个 $xx$ 移动到左边界外，记作 $cntcnt$。则将 $xx$ 移出左边界的最小操作为 区间内左边$cntcnt$个 $xx$ 的下标和 减去 左边界左边 $cntcnt$ 个非 $xx$ 的下标和。右边同理。

观察发现 $cntcnt$ ，在取值范围内为单峰函数，之后可以利用整数三分，找到 $cntcnt$ 取何值时，答案最小。

在三分过程中，需要快速求出 $cntcnt$ 个左边界左边不是 $xx$ 的下标和，这里可以利用直接开 $nn$ 个 $vectorvector$ 在，对每个 $vectorvector$ 排序后，就可以二分出 $cntcnt$ 个左边界左边不是 $xx$ 的下标和。右边同理。

总复杂度为 $O(nlo{g}^{2}n)O(nlog^2n)$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 1e15;
const int N = 1e5 + 10;
int a[N], L, R, x, c1, c2, cnt, t1, t2;
vector<int>v[N];
vector<LL>s[N];
LL pre[N];
LL getl(int cnt) {
    auto &vec = v[x];
    int id = lower_bound(vec.begin(), vec.end(), L) - vec.begin();
    cnt += vec[id] - L;
    int l = 1, r = id;

    while (l < r) {
        int mid = (l + r) >> 1;

        if (vec[id] - vec[mid] - (id - mid) <= cnt)
            r = mid;
        else
            l = mid + 1;
    }

    int t = vec[l] - (cnt - (vec[id] - vec[l] - (id - l)));
    return pre[L - 1] - pre[t - 1] - (s[x][id - 1] - s[x][l - 1]);
}
LL getr(int cnt) {
    auto &vec = v[x];
    int id = upper_bound(vec.begin(), vec.end(), R) - vec.begin() - 1;
    cnt += R - vec[id];
    int l = id, r = vec.size() - 1;

    while (l < r) {
        int mid = (l + r + 1) >> 1;

        if (vec[mid] - vec[id] - (mid - id) <= cnt)
            l = mid;
        else
            r = mid - 1;
    }

    int t = vec[l] + (cnt - (vec[l] - vec[id] - (l - id)));
    return pre[t] - pre[R] - (s[x][l] - s[x][id]);
}
LL query(int mid) {
    LL s1 = s[x][t1 + mid] - s[x][t1];
    LL s2 = s[x][t1 + cnt] - s[x][t1 + mid];
    return s1 - getl(mid) + getr(cnt - mid) - s2;
}
int n, m;
void solve() {
    //  int n ,m ;
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        v[i].push_back(0);

    for (int i = 1; i <= n; ++i)
        cin >> a[i], v[a[i]].push_back(i), pre[i] = pre[i - 1] + i;

    for (int i = 1; i <= n; ++i) {
        int m = v[i].size() - 1;
        s[i].resize(m + 2);
        sort(v[i].begin(), v[i].end());

        for (int j = 1; j <= m; ++j) {
            s[i][j] = v[i][j] + s[i][j - 1];
        }
    }

    for (int i = 1; i <= m; ++i) {
        cin >> L >> R >> x;
        cnt = upper_bound(v[x].begin(), v[x].end(), R) - lower_bound(v[x].begin(), v[x].end(), L);
        t1 = upper_bound(v[x].begin(), v[x].end(), L - 1) - lower_bound(v[x].begin(), v[x].end(), 1);
        t2 = upper_bound(v[x].begin(), v[x].end(), n) - lower_bound(v[x].begin(), v[x].end(), R + 1);
        c1 = L - 1 - t1;
        c2 = n - R - t2;

        int l = max(0, cnt - c2), r = min(cnt, c1);

        if (!cnt) {
            puts("0");
            continue;
        }

        if (l > r) {
            puts("-1");
            continue ;
        }

        while (l < r) {
            int mid1 = (l + r) >> 1, mid2 = mid1 + 1;

            if (query(mid1) < query(mid2))
                r = mid1;
            else
                l = mid2;
        }

        LL ans = query(l);
        cout << ans << '\n';
    }
}
int main() {

    int T = 1;

    //  cin>>T;
    while (T--) {
        solve();
    }

    return 0;
}