alt

感觉难度不是很难的一场。

A. 排序危机(思维，模拟)

思路

问题本质就是从给出的字符串中挑出三种字符的子序列，然后按小写，数字，大写的顺序输出子序列，因此，可以从前往后遍历字符串，每遍历到一个字符就把它加入它所属的子序列的末尾，这样就保证了题目要求的“交换后同类字符的相对位置也是不变的”。

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

代码实现

// Problem: 排序危机
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95016/A
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e6 + 5;

void solve()
{
    int n;
    string s1, s2, s3, s;
    cin >> n >> s;

    for (int i = 0; i < n; i++) {
        if (islower(s[i]))
            s1 += s[i];
        else if (isupper(s[i]))
            s3 += s[i];
        else
            s2 += s[i];
    }
    cout << s1 << s2 << s3;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

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

B. 小歪商店故事：卷（简单数学）

思路

因为 $\frac{a_{max}}{b} < \frac{c}{d}$ ，所以 $a_{max} < \frac{b*c}{d}$ 。

因为 $a_{max}$ 是整数又满足上述性质，所以 $a_{max} = \lceil \frac{b*c}{d} \rceil - 1$ 。

复杂度

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$

代码实现

// Problem: 小歪商店故事：卷
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95016/B
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e6 + 5;

void solve()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int am = (b * c + d - 1) / d - 1;
    cout << a - am << ' ';
}

// a/b<c/d a<bc/d

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

C. 小苯的计算式（枚举）

思路

因为 $C$ 最大为 $2*10^5$ ，所以可以从 $0$ 到 $C$ 枚举 $A$ ，然后 $B=C-A$ ，再看对应的式子长度是否为 $n$ ，如果是的话那么当前符号条件的式子数量 $ans$ 就加一，最后 $ans$ 就是所求答案。

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$

代码实现

// Problem: 小苯的计算式
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95016/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e6 + 5;

void solve()
{
    int n, c;
    cin >> n >> c;

    int ans = 0;
    int m = to_string(c).size();
    for (int a = 0; a <= c; a++) {
        string sa = to_string(a);
        string sb = to_string(c - a);
        if (sa.size() + sb.size() + m + 2 == n)
            ans++;
    }
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

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

D. K（构造，思维）

思路

如果有 $k$ 个极大不同区间，那么极大不同区间的最大长度为 $n-k 1$ 。

当 $n-k 1 <0$ 时，极大不同区间长度为负数，这是不可能的，因此当 $k>n$ 时无解。

对于有解的情况，不妨让极大不同区间长度为 $n-k 1$ ，这样的话，对于一个极大不同区间 $[l,r]$ ，它的下一个极大不同区间就是 $[l 1,r 1]$ ，区间中元素的变化就是丢弃了 $a_l$ ，增加了 $a_{r 1}$ 。

如果 $a_l \ne a_{r 1}$ ，那么区间 $[l,r 1]$ 将会可能是更大的极大不同区间，这样就发生冲突了，所以要令 $a_{r 1} = a_l$ 。

因此，令 $m = n-k 1$ ，如果 $i \le m$ ， $a_i = i$ ，（第一个极大不同区间设置为 $1,2,...m$ ），否则 $a_i =a_{i-m}$ 。

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

代码实现

// Problem: K
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95016/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e6 + 5;

int n, k, a[N];

void solve()
{
    cin >> n >> k;
    if (k > n) {
        cout << "NO";
    } else {
        cout << "YES\n";
        int m = n - k + 1;
        for (int i = 1; i <= n; i++) {
            if (i <= m)
                a[i] = i;
            else
                a[i] = a[i - m];
            cout << a[i] << ' ';
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

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

// k > n 无解
// 区间数量为k，区间长度最大为 n-k+1

E. 小苯的区间选数（枚举，贪心）

思路

因为 $sum$ 是在 $[l_1,r_1]$ 和 $[l_2,r_2]$ 中选一个数相加得到的，所以 $sum \in [l_1 l_2,r_1 r_2]$ 。

令 $L = l_1 l_2,R = r_1 r_2$ 。如果 $x<R$ ，那么 $x$ 从 $R$ 的最高位向下若干位会与 $R$ 相同，然后在第一个不同的位置上， $x$ 对应位置上的数字小于 $R$ 对应位置上的数字。

如果 $x$ 与 $R$ 第一个不同的位置为 $p$ ，那么 $p$ 之后的位置可以都放 $9$ ，使得数位和尽可能大。

因为数位不会很多，所以可以从高到低枚举第一个不同的位置，若当前枚举到位置 $i$ ， $R$ 从最高位到第 $i 1$ 位构成的数字位 $now$ ， $now$ 的数位和为 $sum$ ，如果 $R_i \ne 0$ ，那么此时数位和最大的 $x = now*10^{i 1} (R_i-1)*10^i (10^i -1)$ ，对应的数位和为 $sum R_i-1 i*9$ 。（这里数位 $i$ 是从 $0$ 开始计算的，数位 $i$ 为从低到高第 $i 1$ 个位置）。

如果 $x \ge L$ ，那么就将 $sum R_i-1 i*9$ 与当前记录的最大数位和 $ans$ 比较保留最大值。

还有一种 $x=R$ 的情况，可以初始化的时候把 $ans$ 置为 $R$ 的数位和，这样 $R$ 的数位和也参与进了比较中。

复杂度

时间复杂度 $O(\log R)$ ，空间复杂度 $O(\log R)$

代码实现

// Problem: 小苯的区间选数
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95016/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e6 + 5;

int pre[N];
// pre[i] = 10^i

void init()
{
    pre[0] = 1;
    for (int i = 1; i <= 18; i++) {
        pre[i] = pre[i - 1] * 10;
    }
}

// 分解出 x 每个数位上的数字
vector<int> div(int x)
{
    vector<int> res;
    while (x) {
        res.push_back(x % 10);
        x /= 10;
    }
    return res;
}

void solve()
{
    int l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;

    int l = l1 + l2, r = r1 + r2;

    vector<int> nums = div(r);

    int ans = 0, now = 0, sum = 0;
    int n = nums.size();
    for (int x : nums)
        ans += x;
    for (int i = n - 1; i >= 0; i--) {
        if (nums[i]) {
            int val = (now * 10 + nums[i] - 1) * pre[i] + pre[i] - 1;
            if (val >= l)
                ans = max(sum + nums[i] - 1 + i * 9, ans);
        }
        now = now * 10 + nums[i];
        sum += nums[i];
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    init();

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

F. 小Z的树迁移（预处理，离线，树上启发式合并）

思路

令 $pre_u$ 为从根节点 $1$ 到节点 $u$ 路径上边的权值和， $dep_u$ 为节点 $u$ 的深度。

如果 $u$ 为 $v$ 的父节点， $w$ 为边 $(u,v)$ 的权值，则 $pre_v = pre_u w$ 。其实 $dep_v$ 和 $pre_v$ 本质上是一样的， $dep_v$ 相当与 $w=1$ 的情况， $dep_v = dep_u = 1$ 。

如果节点 $u$ 向下移动 $d$ 次移动到 $v$ ， $v$ 的深度 $dep_v$ 显然为 $dep_u d$ ，从 $u$ 到 $v$ 路径上的权值和为 $pre_v - pre_u$ 。（类似前缀和）。

对于每个查询，其实就是在以 $u$ 为根的子树中，找到满足深度为 $dep_u d$ 的节点 $v$ ，对应的 $pre_v - pre_u$ 的最大值，因为 $pre_u$ 是确定的，所以是要找 $pre_v$ 的最大值。

当搜索完以 $u$ 为根的子树后，可以得到该子树内所有不同深度对应的最大的 $pre_v$ 。举个例子，子树中深度为 $d$ 的所有节点为 $v_1,v_2$ ，可以得到子树中深度为 $d$ 的 $pre_v$ 的最大值为 $max(pre_{v_1},pre_{v_2})$ 。

在回溯到 $u$ 的父节点 $fu$ 时，可以把在搜索完以 $u$ 子树后，得到该子树内所有不同深度对应的最大的 $pre_v$ 传递上去。

如果 $fu$ 恰好要进行深度为 $dep_{fu} d$ 的查询，就可以从 $u$ 传递上来的信息中看有没有深度为 $dep_{fu} d$ 对应的 $pre_v$ 最大值。

如果因为 $fu$ 会有多个子节点 $u$ ，所以可能存在有多个子树中深度为 $dep_{fu} d$ 对应的 $pre_v$ 最大值，应该取其中的最大值。

换句话说，对于每个节点 $u$ ，要维护一个二元组集合 $val_u$ ，其中的元素为 $(深度，u 子树中该深度对应的 pre_v 最大值)$ 。

当搜索完 $u$ 的子节点 $v$ ，就将 $u$ 和 $v$ 的集合进行合并，合并时，若两个元素的深度相同，保留对应 $pre_v$ 最大值的最大的元素，最后 $u$ 的集合中元素就代表着以 $u$ 为根的子树内某种深度对应的 $pre_v$ 最大值，就可以进行关于 $u$ 的查询。

为确保合并时的复杂度不会过高，采用启发式合并，就是每次都是将小集合合并入大集合，换句话说，就是每次遍历小集合，将遍历到的元素加入大集合。

因为是将小集合合并入大集合，相当与小集合的大小翻倍了，因为集合最后的大小为 $n$ ，所以原先小集合的部分被遍历次数最多就是 $\log n$ ，共有 $n$ 个元素，所以这样合并的最坏复杂度为 $O(n \log n)$ 。

复杂度

时间复杂度 $O(n \log n q)$ ，空间复杂度 $O(n \log n q)$

代码实现

// Problem: 小Z的树迁移
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95016/F
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e5 + 5;

int n, m, idx;
int ans[N], dep[N], pre[N];
vector<array<int, 2>> h[N], qry[N];

int p[N];
unordered_map<int, int> val[N];

int find(int x)
{
    return p[x] != x ? p[x] = find(p[x]) : x;
}

void merge(int u, int v)
{
    u = find(u), v = find(v);
    if (u != v) {
        if (val[u].size() > val[v].size())
            swap(u, v);
        // 小集合val[u] 合并入大集合val[v]
        for (auto it : val[u]) {
            int x = it.first, y = it.second;
            val[v][x] = max(val[v][x], y);
        }
        p[u] = v;
    }
}

void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    for (auto it : h[u]) {
        int v = it[0], w = it[1];
        if (v == fa)
            continue;
        pre[v] = pre[u] + w;
        dfs(v, u);
        merge(u, v);
    }
    int pu = find(u);
    val[pu][dep[u]] = pre[u];
    // 以u为根的子树只有u深度为dep[u]，直接赋值即可
    for (auto it : qry[u]) {
        int ds = dep[u] + it[0], id = it[1];
        if (!val[pu].count(ds)) {
            ans[id] = -1;
            // 若没有对应深度则无解
        } else {
            ans[id] = val[pu][ds] - pre[u];
        }
    }
}

void solve()
{
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        h[u].push_back({ v, w });
        h[v].push_back({ u, w });
    }
    for (int i = 1; i <= n; i++) {
        p[i] = i;
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int u, d;
        cin >> u >> d;
        qry[u].push_back({ d, i });
    }
    dfs(1, 0);
    for (int i = 1; i <= m; i++)
        cout << ans[i] << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

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

题解 | #牛客周赛 Round 67#

A. 排序危机(思维，模拟)

思路

复杂度

代码实现

B. 小歪商店故事：卷（简单数学）

思路

复杂度

代码实现

C. 小苯的计算式（枚举）

思路

复杂度

代码实现

D. K（构造，思维）

思路

复杂度

代码实现

E. 小苯的区间选数（枚举，贪心）

思路

复杂度

代码实现

F. 小Z的树迁移（预处理，离线，树上启发式合并）

思路

复杂度

代码实现