A. 三途川的摆渡人（二）

思路

遍历字符串，每遍历到一个 ，答案加一。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 三途川的摆渡人（二）
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95928/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 = 5e4 + 5, M = 17;

void solve()
{
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for (char c : s) {
        ans += c == '0';
    }
    cout << ans;
}

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

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

B. 魔法之森的蘑菇（二）

思路

对 的数量做二维前缀和处理，然后枚举矩形的左上角和右下角。

查询枚举的矩形内是否有 ，如果存在，那么该矩形无法选择，否则可以选择，看其面积是否与之前记录的矩形面积更大，如果更大则把答案更新为当前枚举的矩形。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 魔法之森的蘑菇（二）
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95928/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 = 105, M = 17;

int n, m;
int s[N][N];
string g[N];

int qry(int x1, int y1, int x2, int y2)
{
    int res = s[x2][y2];
    if (y1)
        res -= s[x2][y1 - 1];
    if (x1)
        res -= s[x1 - 1][y2];
    if (x1 && y1)
        res += s[x1 - 1][y1 - 1];
    return res;
}

void solve()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> g[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            s[i][j] = g[i][j] == '*';
            if (i)
                s[i][j] += s[i - 1][j];
            if (j)
                s[i][j] += s[i][j - 1];
            if (i && j)
                s[i][j] -= s[i - 1][j - 1];
        }
    }
    int ma = 0;
    array<int, 4> ans;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int i1 = i; i1 < n; i1++) {
                for (int j1 = j; j1 < m; j1++) {
                    int v = qry(i, j, i1, j1);
                    if (!v) {
                        int w = (i1 - i + 1) * (j1 - j + 1);
                        if (w > ma) {
                            ma = w;
                            ans = { i, j, i1, j1 };
                        }
                    }
                }
            }
        }
    }
    for (int x : ans) {
        cout << x + 1 << ' ';
    }
}

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

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

C. 迷途之家的大贤者（二）

思路

如果同个数组内同个数的数量超过 ，那么必然要把这个数删到数量为 为止。

令 为把小红数组内的数都删到数量为 的必须总次数， 为把小紫数组内的数都删到数量为 的必须总次数。

比如小红的数组为 ，那么必须要删去 个 ， 个 ， 个 ，则 。

因为两人可以同时删，所以两个人可以同时删去必须删的数，两个人同时删，且把必须删去的数都删完的次数则为 。

如果其中一个人必须删的数比另外一个必须删的数少，那么她需要选择 个额外的数来同时删。

当两个人各自的数组内，里面的数都不重复，即数量都为 时，此时只会存在两个数组有相同一个数的情况。

比如，小红的数组为 ，小紫的数组为 ，两个数组有相同的 ，此时只需要删 次就可以，小红选择 删去，小紫选择 删去。

其实就是删去的时候，两个人同时删去一个不同的相同数字，这样就可以使得 个数字变成不存在相同的情况。因此，两个数组有 个相同的数，只需要删 次即可。

考虑到上面需要选择 个额外的数来同时删，所以一部分相同的数可以在这一步就删去了，所以需要删去的次数为 ，总的最小删除次数即为 。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 迷途之家的大贤者（二）
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95928/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 = 5e4 + 5, M = 17;

int n;
map<int, int> cnt[2], del[2];

void solve()
{
    cin >> n;
    for (int i = 0; i < 2; i++) {
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            cnt[i][x]++;
        }
    }
    int v[2] = { 0 };
    for (int i = 0; i < 2; i++) {
        for (auto& it : cnt[i]) {
            if (it.second >= 2) {
                v[i] += it.second - 1;
            }
            it.second = 1;
        }
    }
    int ans = max(v[0], v[1]);
    // cout << ans << '\n';
    int add = 0;
    int tmp = abs(v[0] - v[1]);
    for (auto it : cnt[0]) {
        int x = it.first;
        if (cnt[1].count(x)) {
            add++;
        }
    }
    add = max(0ll, (add - tmp + 1) / 2);
    ans += add;
    cout << ans;
}

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

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

D. 红魔馆的馆主（二）

思路

如果为 的倍数，那么必然要满足 为 的倍数。

通过这个性质，把 转换为 ，对于 来说，如果 为 的倍数，那么 则为满足乘积为 的一对。

显然，枚举 的复杂度为 ，是会超时的，考虑用前缀和配合上面 的思路进行优化。

因为 必然为 的因数，而 的因数只有 个，所以可以关于 的每个因数的数量做前缀和，当 时，那么该位置 的数量就为 。

令 为前 个数中， 的数量，。

美丽度可以表示为 。( 满足 为 的倍数且 为 的因子)

这样就算出没进行操作的美丽度了，那进行一次操作的美丽度怎么算呢？

可以枚举对哪个元素加一，然后减去该元素原先对美丽度的贡献 。( 为当前枚举的下标，这里相比与上面增加了 ，是因为要考虑下标 之后可以与 进行配对的 数量。），增加元素加一后对美丽度的贡献，和原先的贡献计算方式一样，这样就得到了对下标为 的元素加一后的美丽度。

取所有情况下美丽度的最大值即为答案。

复杂度

时间复杂度 ， 为 的因子数。

空间复杂度

代码实现

// Problem: 红魔馆的馆主（二）
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95928/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 = 4e5 + 5, M = 500;

int n;
int a[N];
unordered_map<int, int> f[N];

vector<int> pre;

void init()
{
    for (int i = 1; i <= 495; i++) {
        if (495 % i == 0)
            pre.push_back(i);
    }
}

void solve()
{
    cin >> n;
    int R = 495;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        int g = __gcd(a[i], R);
        for (int j : pre) {
            f[i][j] += f[i - 1][j];
            if (j * g % R == 0) {
                sum += f[i][j];
            }
        }
        f[i][g]++;
    }
    int ans = sum;
    for (int i = 1; i <= n; i++) {
        int add = 0;
        int g = __gcd(a[i], R);
        int g1 = __gcd(a[i] + 1, R);
        for (int j : pre) {
            if (j * g % R == 0) {
                add -= f[i - 1][j];
                add -= f[n][j] - f[i][j];
            }
            if (j * g1 % R == 0) {
                add += f[i - 1][j];
                add += f[n][j] - f[i][j];
            }
        }
        ans = max(ans, sum + add);
    }
    cout << ans;
}

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

    init();

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

E. 博丽神社的巫女（二）

思路

进行操作后有 中情况，相当与第 组中有 个数。

数组中操作后所有的元素和等于 ，相当与每组数种都必须选出一个数，使得和恰好为 。

通过上面分析得到，这实际上是个分组背包问题。

令 为在前 组数中是否可以凑出 ， 表示可以， 表示不能。

若第 组数中选出了 ，且 ，说明前 组中能凑出 ，那么 可以被凑出，。

题目还要求求一个具体方案，只需要在计算时记录前驱状态即可，具体的说就是如果 是通过 得到的，那么记录下 的前驱状态为 ,同时记录下得到操作 的操作次数，然后从末尾状态 向前回溯即可。

复杂度

时间复杂度 ， 空间复杂度

代码实现

// Problem: 博丽神社的巫女（二）
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95928/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 = 1e5 + 5, M = 105;

int n, m = 1e5;
int f[M][N], pre[M][N], g[M][N];

void solve()
{
    cin >> n;
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        int cnt = 0;
        do {
            for (int j = x; j <= m; j++) {
                if (f[i - 1][j - x]) {
                    f[i][j] = 1;
                    pre[i][j] = j - x;
                    g[i][j] = cnt;
                }
            }
            x /= 2;
            cnt++;
        } while (x);
    }
    if (!f[n][m]) {
        cout << "-1";
    } else {
        vector<int> ans;
        for (int i = n; i >= 1; i--) {
            ans.push_back(g[i][m]);
            m = pre[i][m];
        }
        for (int i = n - 1; i >= 0; i--) {
            cout << ans[i] << ' ';
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

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

F. 雾之湖的冰精（三）

代码实现

// Problem: 雾之湖的冰精（三）
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95928/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, M = 10;

int n;
int ans;
int a[N];
int f[N][M];
vector<int> h[N];

void dfs(int u, int fa)
{
    int pre[M] = { 0 };
    for (int v : h[u]) {
        if (v == fa)
            continue;
        dfs(v, u);
        for (int i = 0; i + a[u] <= 9; i++) {
            for (int j = 0; i + j + a[u] <= 9; j++) {
                ans += pre[i] * f[v][j];
            }
        }
        for (int i = 0; i + a[u] < M; i++) {
            ans += f[v][i];
            f[u][i + a[u]] += f[v][i];
        }
        for (int i = 0; i < M; i++) {
            pre[i] += f[v][i];
        }
    }
    f[u][a[u]]++;
    // cout << u << ' ' << ans << '\n';
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        h[u].push_back(v);
        h[v].push_back(u);
    }
    dfs(1, 0);
    cout << ans;
}

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

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