A.小红的对错判断

思路

直接把字符串的字母都转小写，然后判断是否为 即可。

复杂度

时间复杂度为 ， 为输入的字符串

代码实现

// Problem: 小红的对错判断
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/92662/A
// Memory Limit: 524288 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()
{
    string s;
    cin >> s;
    for (char& c : s) {
        c = tolower(c);
    }
    // cout << s << '\n';
    if (s == "yes")
        cout << "accept";
    else
        cout << "wrong answer";
}

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/92662/B
// Memory Limit: 524288 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 x;
    cin >> x;
    cout << x << '\n';
    for (int i = x; i > 1; i--) {
        int xi = x, cnt = 0;
        while (xi % i == 0) {
            cnt++;
            xi /= i;
        }
        if (cnt && xi == 1) {
            cout << "=" << i << "^" << cnt << '\n';
        }
    }
    if (x == 1) {
        cout << "=1^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/92662/C
// Memory Limit: 524288 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;
    cin >> n;
    int cur = 0;
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cur += cnt[x]++;
        cout << cur << ' ';
    }
}

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/92662/D
// Memory Limit: 524288 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 x = a + d;
    int y = b + c;
    int z = min(x, y);
    cout << (z % 2 ? "kou" : "yukari") << '\n';
}

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

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

F.小红的树上路径查询（easy）

思路

查询路径的两个端点分别为 ，以查询路径的一个端点 为根，进行 ，如果搜到 则可以从 回溯到根节点，从而找到路径上的所有点。

以路径上的点为起点进行 ，即可搜出到其他点的最短路径。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 小红的树上路径查询（easy）
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/92662/F
// Memory Limit: 524288 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, q;
int dis[N];
vector<int> h[N];

vector<int> path;

int dfs(int u, int fa, int y)
{
    if (u == y) {
        path.push_back(u);
        return 1;
    }
    for (int v : h[u]) {
        if (v == fa)
            continue;
        if (dfs(v, u, y)) {
            path.push_back(u);
            return 1;
        }
    }
    return 0;
}

void solve(int x, int y)
{
    dfs(x, 0, y);
    memset(dis, -1, sizeof(dis));
    queue<int> q;
    for (int u : path) {
        q.push(u);
        dis[u] = 0;
    }
    int ans = 0;
    while (q.size()) {
        int u = q.front();
        q.pop();
        ans += dis[u];
        for (int v : h[u]) {
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    cout<<ans;
}

void solve()
{
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        h[u].push_back(v);
        h[v].push_back(u);
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        solve(x, y);
    }
}

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

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

G.小红的树上路径查询（hard）

思路

版本有 次查询，按 版本的思路，复杂度为 ，显然会超时。

令节点 为整个树的根节点， 为以 为根节点， 到子树内的所有点的最短路径之和，实际上就是以 为根，子树内的所有点的深度和。

可以发现，对于节点 ，如果节点 为它的子节点， 到 子树内所有点的最短路径之和，实际上就是 到 子树内的所有点的最短路径之和，然后每个点都加一（增加 到 的边），因此，若 为以 为根的子树的节点数，。

像上图这样的树，如果查询路径为从 到 ，路径上的点为 ，可以发现，最短路径和可以表示为 ，一个节点的贡献不一定直接就是 ，如果该节点有子节点在路径上，则需要减去子节点对应的子树部分的贡献，对式子化简后可以得到 ，因此，到查询路径 的最短路之和为 。

其实就是 ( 为路径上的点，且不是 ，但这还不是答案，因为上面的情况为 为整颗树的根节点的情况，如果 不是整颗树的根节点，还有除了以 为根的子树外的部分要求，但是这部分距离路径上最近的节点就是 ，综合一下， 就变成了要求所有点到 的最短路径之和，这可以用换根 求出。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 小红的树上路径查询（easy）
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/92662/F
// Memory Limit: 524288 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 = 19;

int n, q;
int f[N], sz[N], dep[N], sum[N], par[N][M];
vector<int> h[N];

void dfs(int u, int fa)
{
    sz[u] = 1;
    dep[u] = dep[fa] + 1;
    for (int v : h[u]) {
        if (v == fa)
            continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

void dfs1(int u, int fa)
{
    par[u][0] = fa;
    for (int i = 1; i < M; i++) {
        par[u][i] = par[par[u][i - 1]][i - 1];
    }
    sum[u] = sum[fa] + sz[u];
    for (int v : h[u]) {
        if (v != fa) {
            dfs1(v, u);
            f[u] += f[v] + sz[v];
        }
    }
}

void dfs2(int u, int fa)
{
    for (int v : h[u]) {
        if (v != fa) {
            f[v] = f[u] + n - 2 * sz[v];
            dfs2(v, u);
        }
    }
}

int lca(int a, int b)
{
    if (dep[a] > dep[b])
        swap(a, b);
    for (int i = M - 1; i >= 0; i--) {
        int bi = par[b][i];
        if (dep[bi] >= dep[a])
            b = bi;
    }
    if (a == b)
        return a;
    for (int i = M - 1; i >= 0; i--) {
        int ai = par[a][i];
        int bi = par[b][i];
        if (ai != bi)
            a = ai, b = bi;
    }
    return par[a][0];
}

void solve()
{
    cin >> n >> q;
    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);
    dfs1(1, 0);
    dfs2(1, 0);
    while (q--) {
        int x, y;
        cin >> x >> y;
        int z = lca(x, y);
        int ans = f[z] - (sum[x] + sum[y] - 2 * sum[z]);
        cout << ans << '\n';
    }
}

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

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