A

最小表示法字符串匹配

长得像的字母和数字被认为是一样的，问两个串是否相同。

比较简单的写法是类似最小表示法的思想。规定每一组相似字符，都变成其中某一个字符，然后看是否严格相等即可

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

	string s1, s2;
	cin >> s1 >> s2;
	for (auto &c : s1) {
		if (c == 'O') {
			c = '0';
		}
		if (c == 'l' || c == 'I') {
			c = '1';
		}
	}
	for (auto &c : s2) {
		if (c == 'O') {
			c = '0';
		}
		if (c == 'l' || c == 'I') {
			c = '1';
		}
	}
	if (s1 == s2) {
		cout << "yes\n";
	} else {
		cout << "no\n";
	}
}

B

数论思维 alt

实际上数列中初始只要有一个专一数，就可以，否则不可以。

尝试证明一下：首先是必要性，由于我们能执行的只有乘方和赋值操作，不能创造新的专一数，所以想要把专一数赋值给 $a_1$ ，必须开始就存在一个专一数；然后是充分性，如果开始 $a_1$ 就是专一数，那我们让后续操作不覆盖 $a_1$ 初始值即可，这是可以做到的，如果其它位置 $a_i$ 有专一数，可以在某一步让 $i=n^{'},j=1$ ，这样 $a_i$ 执行了 $a_1$ 次方，还是专一数，并且接下来把专一数赋值给 $a_1$ 了

至此充分必要都证明了。只需判断初始数列是否存在专一数即可，注意 $1$ 也是专一数，开始被这个坑了

void solve() {
    int n;
    cin >> n;
    vi a(n+1);
    rep(i,1,n){
        cin>>a[i];
    }
    rep(i, 1, n) {
        int x=a[i];
        map<int, int>mp;
        while (x != 1) {
            mp[minp[x]]++;
            x /= minp[x];
        }
        if (mp.size() == 1||a[i]==1) {
            cout << "yes\n";
            return;
        }
    }
    cout << "no\n";
}

C

字典序贪心构造 alt

注意是 $d$ 字典序最小，而不是构造出来的答案串字典序最小。字典序最小可以直接贪心，每一步都优先让当前位置最小，不考虑后面的。每一步只有 $0,1$ 两个选择，计算当前选哪个可以让 $d_i$ 更小，就选哪个。这种属于贪心构造，就一直贪，构造出来的就是最优的序列。

需要注意系数的下标是反的

void solve() {
    int n, a0, a1;
    cin >> n >> a0 >> a1;
 
    int c0 = 0, c1 = 0;
    string ans;
    while (n--) {
        if (abs(a1 * (c0 + 1) - a0 * c1) < abs(a1 * c0 - a0 * (c1 + 1))) {
            ans += '0';
            c0++;
        } else {
            ans += '1';
            c1++;
        }
    }
    cout << ans << '\n';
}

D

排序二分前缀和 alt

所有人两两计算心情的变化，规则如上。显然总数 $O(n^2)$ ，不能暴力。但对于每个人来说，他和其他所有人的贡献，存在一个阈值，大于阈值就是第二种情况，小于阈值就是第一种情况，只要找到阈值，就可以快速计算。

所以考虑枚举 $a_i$ ，然后找到第一个大于 $m-a_i$ 的位置，从这里到结束的人，对 $a_i$ 的贡献都是 $-a_j$ ，前缀和维护即可。在这前面的人，对 $a_i$ 的贡献都是 $a_i$ ，也可以 $O(1)$ 计算。

想要找到第一个大于 $m-a_i$ 的位置，考虑对所有人的 $a_i$ 排序，但还要对每个人分别回答，也就是需要知道排序后的数组内，当前这个人的初始序号，所以排序时把 $a_i$ 和序号绑在一起排序。

需要注意，可能不存在大于 $m-a_i$ 的人，以及自己和自己不会产生贡献，需要减掉

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

	vector<pii> a(n + 1);
	rep(i, 1, n) {
		int x;
		cin >> x;
		a[i] = {x, i};
	}
	sort(a.begin() + 1, a.end());
	vi s(n + 1);
	rep(i, 1, n) {
		s[i] = s[i - 1] + a[i].fi;
	}
	vi ans(n + 1);

	rep(i, 1, n) {
		int x = a[i].fi;
		int id = a[i].se;
		int p = upper_bound(a.begin() + 1, a.end(), make_pair(m - x, inf)) - a.begin();
		p--;
//		cout<<p<<' ';
		if (p <= n) {
			if (p >= i) {
				ans[id] = (p - 1) * x - (s[n] - s[p]);
			} else {
				ans[id] = p * x - (s[n] - s[p] - x);
			}
		} else {
			ans[id] = (p - 1) * x;
		}
	}

	rep(i, 1, n) {
		cout << ans[i] << ' ';
	}
	cout << '\n';

}

E

构造

非常奇妙的构造！

问一个大小确定的地图，给出一个地雷布置方案，使得数字格恰好 $k$ 个。一个核心观察是，如果地图上每个格子，都是地雷或数字的话，那么我们把一个数字位置改成地雷，数字格恰好减少一个。如果我么没有保证每个格子都是地雷或数字，把一个数字变成地雷，虽然直接损失了一个数字，但是可能会让原本没有数字和地雷的格子，变成数字，对数字的影响是复杂的。但是如果我们保证了，每个格子都是数字或地雷，就只会损失这一个数字，其他格都不会改变。

那么基于此，我们想使得数字格 $k$ 个，可以先让所有格都是数字或地雷，并且最大化数字，如果此时数字个数不小于 $k$ ，每次把一个数字变成地雷，减少数字直到等于 $k$ ，否则，由于我们已经最大化数字个数了，不可能再增加，无解。

于是问题只剩下，让每个格子都是数字或地雷，并且数字个数最大化，如何构造。让所有格子都是地雷或数字是简单的，因为可以多放地雷，让地雷的影响范围覆盖整个地图即可。问题是如何让数字个数最大化，那就要尽可能让地雷少放，让地雷的影响范围最大化，最优方案其实就是尽可能让每个地雷，都管一个 $3×3$ 的区域，让不同地雷的影响范围无重叠。那么也就是模三余二的位置要放地雷，特殊情况是， $n$ 模三余一，那么剩下的这一行也要放一个地雷，虽然这样地雷的影响范围就有重叠了，但如果不放的话，最后一行就没有数字了，这就是这种情况下的最优， $m$ 模三余一也同理。

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
 
    vvi a(n + 1, vi(m + 1));
    int cnt = n * m;
    rep(i, 1, n) {
        rep(j, 1, m) {
            if (i % 3 == 2 || i == n && n % 3 == 1) {
                if (j % 3 == 2 || j == m && m % 3 == 1) {
                    a[i][j] = 1;
                    cnt--;
                }
            }
        }
    }
    if (cnt < k) {
        cout << -1 << '\n';
    } else {
        rep(i, 1, n) {
            rep(j, 1, m) {
                if (!a[i][j] && cnt > k) {
                    a[i][j] = 1;
                    cnt--;
                }
            }
        }
 
        rep(i, 1, n) {
            rep(j, 1, m) {
                cout << a[i][j];
            }
            cout << '\n';
        }
    }
}

F

计数

给每个人涂色， $a_i$ 表示有 $a_i$ 个人的颜色和他相同。问 $m$ 种颜色，涂色方案数有多少？

首先一个 $a_i$ 的出现次数，一定要是 $a_i$ 的倍数，因为每一组都是 $a_i$ 个人，可能有多组，所以如果不满足这一点，无解。接下来，对于每一个 $a_i$ ，假设出现 $x$ 次，说明有 $x/a_{i}$ 组颜色不同的人，这样我们可以计算一共有多少组不同颜色，如果颜色数大于 $m$ ，也无解。

接下来都有解，计算方案。对于有 $x$ 次出现的 $a_i$ ，要把这 $x$ 人分成 $y=x/a_i$ 个 $a_{i}$ 的组，这是经典问题，这里考虑的是组合数，不是排列数的话，方案数是 $x!/a_i!a_i!...a_i!y!$ ，也就是先全排列，然后让每个组内的不同排列，都是视为同一种，因为我们认为组内元素是无差别的，最后再除以组之间的排列，因为我们这里求的是组合。这里其实也等价于代码内的实现， $C(x,a_i)C(x-a_i,a_i)C(x-2a_i,a_i)...C(a_i,a_i)/y!$ ，这样选出来的也是排列数，需要除掉组之间的排列

不同 $a_i$ 之间是独立的，方案数相乘，就得到了划分组的所有组合，再假设有 $cnt$ 组，从 $m$ 个颜色里选 $cnt$ 个颜色，给这些组染色，并且染色方案可以随意排列，所以是 $A_m^{cnt}$

int cal(int n, int k) {
    int res = 1;
    for (int i = n; i >= n - k + 1; i--) {
        res = res * i % M1;
    }
    return res;
}
void solve() {
    int n, m;
    cin >> n >> m;
 
    map<int, int>mp;
    int ans = 1;
    rep(i, 1, n) {
        int x;
        cin >> x;
        mp[x]++;
    }
 
    int cnt = 0;
    for (auto [k, v] : mp) {
        if (v % k) {
            cout << 0 << '\n';
            return;
        }
        for (int i = v; i > 0; i -= k) {
            ans = ans * C(i, k) % M1;
        }
        int f = v / k;
        cnt += f;
 
        rep(i, 1, f) {
            ans = ans * inv(i, M1) % M1;
        }
    }
    if (cnt > m) {
        cout << 0 << '\n';
        return;
    }
    ans = ans * cal(m, cnt) % M1;
    cout << ans << '\n';
 
}

小白128 构造|组合数学

A

B

C

D

E

F