竞赛讨论区 > 牛客练习赛111 题解
头像
wanghai673
发布于 2023-05-05 21:58
+ 关注

牛客练习赛111 题解

列竖式

对于每个 AA,考虑最低的第 ii 位不为0的数 XXB=(10X)10iB = (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;
}

一次交换

考虑 S1[i]S2[i]S_1[i] \neq S_2[i]的位置个数 cntcnt

1)cnt3cnt\geq3cnt=1cnt=1,无解

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

3)cnt=0cnt=0S1S_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 满足 kmxk \leqslant \lfloor \frac{m}{x} \rfloor时,kmyk \leqslant \lfloor \frac{m}{y} \rfloork>mxk > \lfloor \frac{m}{x} \rfloor时,k>myk > \lfloor \frac{m}{y} \rfloor

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

或者直接用数论分块的结论,区间为[mmx+1+1,mmx][\lfloor \frac{m}{\lfloor \frac{m}{x}+1 \rfloor} \rfloor+1,\lfloor \frac{m}{\lfloor \frac{m}{x} \rfloor} \rfloor]ans=mmx]mmx+1ans=\lfloor \frac{m}{\lfloor \frac{m}{x} \rfloor} \rfloor]-\lfloor \frac{m}{\lfloor \frac{m}{x}+1 \rfloor} \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)ngcd(a,b)|n 。利用扩展欧几里得算法可以求出x=x0+b/d×k x=x0+b/d \times k ,令 p=b/dp=b/d

则原问题让我们求 Lx0+p×kRL \leqslant x0+p \times k \leqslant R是否有解,则令l=Lx0pl=\lceil \frac{L -x0}{p} \rceil, r=Rx0pr=\lfloor \frac{R -x0}{p} \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/1)dp(u,s1,s2) (s1,s2 = 0/1) , 表示先手从 uu 开始是否获胜 s1s_1 ,先手从 fa(u)fa(u) 开始是否获胜为s2,u s_2, u 节点子树下叶子节点是否存在先手必胜。

假设 a[v]=3a[v] = 3 ,则 u,fa(u)u,fa(u) 只要存在一个点先手从该节点输的,则在 vv 这个节点先手必胜即 dp(u,s1,s2) = dp(v,(!s1)(!s2),s1)dp(u,s1,s2) \ |=\ 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 移出左边界的最小操作为 区间内左边cntcntxx 的下标和 减去 左边界左边 cntcnt 个非 xx 的下标和。右边同理。

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

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

总复杂度为 O(nlog2n)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;
}

全部评论

(4) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐