A、CCA的词典

因为我们可以随意交换相邻两个数，根据冒泡排序规则，所以我们可以得到由这些字母组成的任意字符串。
那么我们就对每行字符串进行字典序排序，再使用计数器计数即可。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 1e6 + 7;
ll n, m;
ll p[N];
void solve() {
    js;
    string s;
    map<string, int> mp;
    cin >> n;
    rep(i, 1, n) {
        cin >> s;
        sort(all(s));
        ++mp[s];
    }
    cin >> m;
    rep(i, 1, m) {
        cin >> s;
        sort(all(s));
        cout << mp[s] << endl;
    }
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

B、CCA的搬运

第一行两个整数分别是 $n,m\le2000$ 代表我们有 $n$ 个球 $m$ 次操作。

第二行输入 $n$ 个整数 $a_i\le100$ ，代表每个球的重量。

第三行输入 $m$ 个整数 $b_i\in[1,n]$ ，代表每次操作要把 $b_i$ 放在当前球堆的堆顶。

我们每次拿到堆顶的操作，花费的都是当前球上方全部小球重量和。现在要你求解如何安排起始顺序使得花费最小。

我们对于每个 $b_i$ 考虑从 $1$ 到 $n$ 来看，如果是第一次出现的 $b_i$ 那么它的上方一定会有之前出现过的全部不同数。例如 $b$ 数组为 $11223$ 这样的话遍历到 $b_i=3$ 的时候，在他上方一定会有 $1,2$ 两个小球，那么最优的解法一定是把 $3$ 号球放在 $1,2$ 球的下方。那么解法就出来了。

我们遍历全部的 $b_i$ 并且使用一个 $pair$ 统计第一次出现的 $b_i$ 他是什么小球以及对应价值。

接下来就对这样的初始 $pair$ 进行查找，模拟从顶向下的小球重量。并且每次遇到了对应小球，就把它换到最顶部。

struct Node {
    ll val;
    ll id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
}T[2007];
int top = 0;

const int N = 2000 + 7;
ll n, m;
ll a[N], b[N];
bool vis[N];
vector<int> st;

void solve() {
    n = read(), m = read();
    rep(i, 1, n)    a[i] = read();
    rep(i, 1, m) {
        b[i] = read();
        if (!vis[b[i]]) {
            T[++top] = { a[b[i]],b[i] }; // Node(val , id);
        }
        vis[b[i]] = 1;
    }
    ll ans = 0;
    rep(i, 1, m) {
        rep(j, 1, top) {
            if (T[j].id == b[i]) {
                Node tmp = T[j];
                repp(k, j, 2)   T[k] = T[k - 1];
                T[1] = tmp;
                break;
            }
            else ans += T[j].val;
        }
    }
    print(ans);
}

C、CCA的子树

首先把问题简化思考，如果给你的是一颗二叉树的话，你如何思考这个问题。

从根节点1出发，我们可以找到左边子树的最大值与右边子树的最大值，二者一定可以保证不存在公共的祖先，并且满足了找左右最大值的要求，我们如果找到了这样的两棵子树那么就把他们更新一下答案。

并且在左右子树中也同样是这样的问题，我们依次往下 $dfs$ 即可求解正确的答案。

现在仅仅是把树形结构从二叉树变化成了多叉树，那么同样的道理就是在多个儿子中间找到最大的两个儿子，如果只有一个儿子就不能更新答案。并且返回包含节点 $u$ 在内的最大子树点。

这里判断 $Error$ 只有单链一种情况，如果你把答案初始化到 $-10^9$ 代表无穷小的话，可能会出现这样的 $hack$ 数据把你卡掉，这道题目并没有考虑到。

3
1 -1000000000 -1000000000
1 2
1 3
-2000000000

const int N = 2e5 + 7;
const ll INF = 1e18;
ll n, m;
vector<int> edge[N];
ll a[N], ans = -INF;

int dfs(int u, int fa) {
    int max1 = 0, max2 = 0, x;
    for (auto& v : edge[u]) {  // 子树里面找最大的两个点
        if (v == fa)    continue;
        x = dfs(v, u);
        a[u] += a[v];   // 求解u以及它的子树和
        if (max1 == 0 or a[x] >= a[max1])    max2 = max1, max1 = x;
        else if (max2 == 0 or a[x] >= a[max2])    max2 = x;
    }
    if (max2 != 0)
        ans = max(ans, a[max1] + a[max2]);
    if (max1 == 0 or a[u] > a[max1])    max1 = u;
    return max1;
}

void solve() {
    n = read();
    rep(i, 1, n)    a[i] = read();
    int u, v;
    rep(i, 2, n) {
        u = read(), v = read();
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1, -1);
    if (ans == -INF) { puts("Error"); }
    else {
        print(ans);
    }
}

D、CCA的小球

我们要求解任意小球颜色都不同的方案数，那么我们就反向思考。

对于给定的 $n$ ，很显然全部的方案数就是 $n!$ 那么多种。

如果不存在任何一对相同的数，这就是最终答案。接下来如果存在一对相同的数的话。我们就要减掉这一对相同的数放在一起构造的答案数量。如果存在两对相同的数的话，我们就分别挑出一对相邻的减掉再加上两对同时相邻的答案，这样想先去就很容易想到容斥了。

对于每次我们让一对相邻方案数就是 $C^1_k$ ， $k$ 就是给出小球颜色中相同的颜色个数。

那么接下来就是捆绑之后顺序全排列。答案是 $(k-1)!$ ，但是这里我们还要注意一个点，对于相同的数来说颠倒前后两个数的顺序并没有贡献，所以之后的贡献还不能简单计算 $(k-1)!$ 还应该把相同数前后放在一起的情况除掉，那么答案就是 $\frac{(k-1)!}{2^{k-1}}$ ，理解就是除掉选择出来的那一对，其余对之间全排列计算贡献时出现前后的顺序不计。

接下来只要去枚举每次我们让几队相邻即可，因为涉及取模除法操作，并且发现每次就比前一次少除一个2，所以我们就干脆不在循环内部调用逆元了，再最终求解一次逆元即可。

const int N = 1e6 + 7;
ll n, m, k;
ll jc[N], inv[N];

ll C(int n, int m) {
    return jc[n] * inv[n - m] % MOD * inv[m] % MOD;
}

void solve() {
    jc[0] = 1;
    rep(i, 1, N - 1)    jc[i] = jc[i - 1] * i % MOD;
    inv[N - 1] = qpow(jc[N - 1], MOD - 2, MOD);
    repp(i, N - 2, 0)    inv[i] = inv[i + 1] * (i + 1) % MOD;
    n = read();
    unordered_map<int, int> mp;
    int x;
    rep(i, 1, n) {
        x = read();
        if (mp.count(x))    ++k;
        else mp[x] = 1;
    }
    //print(k);
    ll ans = jc[n], tmp = 1;
    rep(i, 1, k) {
        tmp = tmp * 2;
        if (tmp >= MOD)    tmp -= MOD;
        if (i & 1)
            ans -= C(k, i) * jc[n - i] % MOD * tmp % MOD;
        else
            ans += C(k, i) * jc[n - i] % MOD * tmp % MOD;
        ans = (ans + MOD) % MOD;
    }
    ans = ans * qpow(tmp, MOD - 2, MOD) % MOD;
    print(ans);
}

牛客练习赛78

A、CCA的词典

B、CCA的搬运

C、CCA的子树

D、CCA的小球