以下几道题是最近遇到的比较巧妙的题目，有时需要一点思维上的灵光一闪。
D - Send More Money
题目链接： D - Send More Money
题意：
给定三个字符串，将每个字符映射成数字，判断前两个字符串表示的数相加是否能得到第三个字符串，要求字符和数字必须一一对应。
解题思路：
首先数字最多只有 $10$ 个，因此如果字符总数大于 $10$ ，显然不存在答案。
剩下的情况，每个字符和数字一一对应，最多只有 $10!$ 种情况，数据范围很小，暴力是可以承受得住的， 但实现方面其实还是有点考验能力。
可以将所有字符放到一个数组里，用哈希表将字符和下标映射起来，然后枚举数字 $[0,9]$ 的全排列，将字符对应下标的数字取出即可。
注意事项：
要特判有前导零的情况。
代码如下：
#include <map>
#include <vector>
#include <cstring>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
vector<string> s(3);
for (auto &u : s) cin >> u;
vector<char> b;
for (auto &u : s)
for (auto &c : u)
b.emplace_back(c);
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
// 字符数大于 10
if ((int)b.size() > 10)
{
cout << "UNSOLVABLE\n";
return 0;
}
vector<int> num(10);
iota(num.begin(), num.end(), 0);
map<char, int> mp;
for (int i = 0; i < (int)b.size(); i ++ ) mp[b[i]] = i;
do
{
vector<string> c = s;
for (auto &u : c)
for (auto &v : u)
v = (char)(num[mp[v]] + '0');
// 特判前导零
if (c[0][0] == '0' || c[1][0] == '0' || c[2][0] == '0') continue;
vector<long long> a(3);
for (int i = 0; i < 3; i ++ ) a[i] = stol(c[i]);
if (a[0] && a[1] && a[2] && a[0] + a[1] == a[2])
{
for (auto &u : a)
cout << u << '\n';
return 0;
}
} while (next_permutation(num.begin(), num.end()));
cout << "UNSOLVABLE\n";
return 0;
}
D - Anything Goes to Zero
题目链接： D - Anything Goes to Zero
题意：
给定一个 $n$ ，将它变成对它的二进制表示中 $1$ 的个数取模的结果，直到它变成 $0$ ，操作次数为 $f(n)$ 。现在给定一个 $X$ ，分别求出对它二进制表示的每一位取反后需要的操作次数。
解题思路：
这个题目描述有点绕，但分析之后可以发现，对某一位取反后，第一次操作时模数只有两种可能，即 $one+1$ 或 $one-1$ ，其中 $one$ 为二进制表示中 $1$ 的个数，整个二进制表示不超过 $2\times 10^5$ ，说明第一次操作后的结果也不会超过 $2\times 10^5$ 。
进一步观察，某个不超过 $2\times 10^5$ 的数，对它进行题目所述的操作，直到变成 $0$ ，其实次数很少，直接暴力做就行。
对于第 $i$ 位来说，如果它取反后变成 $1$ ，那么就会为整体加上 $2^{n-i-1}$ ，然后对 $one+1$ 取模；如果它取反后变成 $0$ ，那么就会为整体减去 $2^{n-i-1}$ ，然后对 $one-1(one>1)$ 取模。
因此可以预处理一下 $X$ 对 $one+1$ 和 $one-1(one>1)$ 取模的结果，然后枚举每个位置，处理以下这个位取反后对 $X$ 的影响，得到第一次操作后的结果，然后暴力做即可。
注意事项：
要注意 $X$ 的二进制表示只有一个 $1$ 的情况，否则可能出现除以 $0$ 的错误。
结果记得加上第一次操作。
代码如下：
#include <iostream>
using namespace std;
int qp(int a, int b, int mod)
{
int res = 1;
while (b)
{
if (b & 1) res = (long long)res * a % mod;
a = (long long)a * a % mod;
b >>= 1;
}
return res;
}
int work(int x)
{
int res = 0;
while (x)
{
int cnt = __builtin_popcount(x);
x %= cnt;
res ++ ;
}
return res;
}
int main()
{
int n;
string s;
cin >> n >> s;
int one = 0;
for (auto &c : s) one += (int)(c == '1');
int t1 = 0, t2 = 0;
for (int i = 0; i < n; i ++ )
if (s[i] == '1')
{
if (one > 1) t1 = (t1 + qp(2, n - 1 - i, one - 1)) % (one - 1);
t2 = (t2 + qp(2, n - 1 - i, one + 1)) % (one + 1);
}
for (int i = 0; i < n; i ++ )
{
int p = one;
if (s[i] == '0')
{
p ++ ;
cout << 1 + work((t2 + qp(2, n - 1 - i, p)) % p) << '\n';
}
else
{
p -- ;
if (!p) cout << "0\n";
else cout << 1 + work(((t1 - qp(2, n - 1 - i, p)) % p + p) % p) << '\n';
}
}
return 0;
}
F - Sugoroku
题目链接： F - Sugoroku
题意：
从 $1$ 出发，走到 $n+1$ 点，每一次可以走 $[1,m]$ 步，且某些地方不能停留。求最少步数以及方案，如果存在多种方案，则输出 每次走的步数 字典序最小的方案。
解题思路：
不难想到用 DP ，定义 $f[i]$ 为从起点走到 $i$ 的所有方案，属性是最少次数，但由于要求方案，因此还需要在每个能够走到到 $i$ 的点中，找一个 最靠左边 的。
为什么最靠左边呢？
可以简单证明一下，假如 $i$ 前面的 $a,b(a<b)$ 均可走到 $i$ ，让整个步数序列字典序尽量小，那么就应该让前面走的跨度尽量小，因此选靠左边的。
一开始有点傻，直接用最暴力的方法——树状数组，套个二分，找到 $[max(1,i-m),i-1]$ 中步数最少的、最靠左边的点转移，但后面看了看别人的代码突然想起这不就是求固定长度的滑动窗口的最值问题吗，直接用单调队列搞定，多简单，好傻。
注意事项：
树状数组代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) (x & -x)
using namespace std;
const int N = 100010, INF = 0x3f3f3f3f;
int n, m;
int f[N], g[N];
int tr[N];
char s[N];
void build()
{
for (int i = 1; i <= n; i ++ )
{
tr[i] = f[i];
for (int j = 1; j < lowbit(i); j <<= 1)
tr[i] = min(tr[i], tr[i - j]);
}
}
void update(int x)
{
for (int i = x; i <= n; i += lowbit(i))
{
tr[i] = f[i];
int len = lowbit(i);
for (int j = 1; j < len; j <<= 1)
tr[i] = min(tr[i], tr[i - j]);
}
}
int query(int l, int r)
{
int res = INF;
while (true)
{
res = min(res, f[r]);
if (l == r) break;
for (r -- ; r - lowbit(r) >= l; r -= lowbit(r))
res = min(res, tr[r]);
}
return res;
}
void print(int x)
{
if (x != 1)
{
print(g[x]);
cout << x - g[x] << ' ';
}
}
int main()
{
cin >> n >> m >> s + 1;
n ++ ;
memset(f, 0x3f, sizeof f);
f[1] = 0;
build();
for (int i = 2; i <= n; i ++ )
{
if (s[i] == '1') continue;
int L = max(1, i - m), R = i - 1;
int l = L, r = R;
int mn = query(l, r);
while (l < r)
{
int mid = l + r >> 1;
if (query(L, mid) <= mn) r = mid;
else l = mid + 1;
}
f[i] = f[r] + 1;
g[i] = r;
update(i);
}
if (f[n] >= INF) cout << "-1\n";
else print(n);
return 0;
}
单调队列代码：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, INF = 0x3f3f3f3f;
int n, m;
int f[N], g[N];
int q[N];
char s[N];
void print(int x)
{
if (x != 1)
{
print(g[x]);
cout << x - g[x] << ' ';
}
}
int main()
{
cin >> n >> m >> s + 1;
n ++ ;
memset(f, 0x3f, sizeof f);
int hh = 0, tt = -1;
q[ ++ tt] = 1;
f[1] = 0;
for (int i = 2; i <= n; i ++ )
{
if (s[i] == '1') continue;
while (hh <= tt && i - q[hh] > m) hh ++ ;
if (hh <= tt)
{
f[i] = f[q[hh]] + 1;
g[i] = q[hh];
}
else continue;
while (hh <= tt && f[i] < f[q[tt]]) tt -- ;
q[ ++ tt] = i;
}
if (f[n] == INF) cout << "-1\n";
else print(n);
return 0;
}
A - Reachable Towns
题目链接： A - Reachable Towns
题意：
给定 $n$ 个有序对，如果某个有序对的两个元素分别大于或分别小于另一个有序的两个元素，那么这两个有序对则属于同一个集合，求每个有序对所在集合的规模。保证所有有序对的第一元素两两不同，第二元素两两不同。
解题思路：
初看题意以为是二维偏序，后来发现并不是一对一的问题，它们的关系有传递性，于是想到并查集的操作。
当然二维偏序问题的处理技巧这里还是用到了，就是对有序对排序，这样一来，从前往后枚举时，当前有序对的第一个元素一定比前面的有序对的第一个元素要大，只需要考虑第二个元素就行。
而且可以发现，如果当前有序对的第二元素为 $y$ ，它的前面存在 $y_1,y_2(y_1<y_2<y)$ ，首先把它们合并到一个集合，接着后面可以不考虑 $y_2,y$ ，因为能够大于它们的，也一定大于 $y1$ 。
这样一来，可以用一个平衡树 $S$ 来维护第二个元素，对于当前有序对的第二个元素 $y$ ， $S$ 为空，或者它的最小值大于 $y$ ，那么当前有序对无法和之前出现的有序对所在集合合并，于是将 $y$ 加入 $S$ 。如果 $S$ 的最小值小于 $y$ ，那么首先将它们合并，然后对 $S$ 中其它小于 $y$ 的元素移除，同时也进行合并。
这样每个元素最多只会进出一次平衡树，时间复杂度是 $O(nlogn)$ 的。
代码如下：
#include <set>
#include <vector>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<pair<int, int>> a(n);
for (auto &[x, y] : a)
{
cin >> x >> y;
x -- , y -- ;
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int x, int y)
{
return a[x] < a[y];
});
vector<int> p(n), SIZE(n, 1);
iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x) -> int
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
};
set<int> S;
for (auto &i : order)
{
auto [x, y] = a[i];
auto it = S.begin();
if (it == S.end() || *it > y) S.insert(y);
else
{
int pa = find(y), pb = find(*it);
if (pa != pb)
{
SIZE[pb] += SIZE[pa];
p[pa] = pb;
}
it ++ ;
while (it != S.end() && *it < y)
{
pa = find(*it);
if (pa != pb)
{
SIZE[pb] += SIZE[pa];
p[pa] = pb;
}
it ++ ;
S.erase(prev(it));
}
}
}
vector<int> res(n);
for (auto &i : order) res[order[i]] = SIZE[find(a[order[i]].second)];
for (auto &u : res) cout << u << '\n';
return 0;
}
E. Cost Equilibrium
题目链接： E. Cost Equilibrium
题意：
给定一个长度为 $n$ 的序列，要使得所有元素相同，可以令 $a_i$ 减少 $x$ （称为源点）， $a_j$ 增加 $x$ （称为汇点），每次操作的花费是 $x\times |i-j|$ 重复这样的操作，直到相等，且要求每个数只能增加或减少最多一次。
如果一个序列的要变成所有元素相同的花费的最小值和最大值是相等的，那么这个序列就是平衡的，求所有给定序列的所有排列中，平衡序列有多少种。
解题思路：
题意也是有些绕，然后需要一系列观察：
- 如果它们的和无法被 $n$ 整除，则结果为 $0$ ，否则最终每个数都为平均数 $val$ ；
- 如果所有数都为 $0$ ，则结果为 $0$ ；
- 如果只有一个源点或只有一个汇点，则源点和汇点可以随意排列，也就是从 $n$ 个点中选择 $src_cnt+snk_cnt$ 个作为源点和汇点，即 $C_n^{src_cnt+snk_cnt}\times (src_cnt+snk_cnt)!$ ，当然要处理源点或汇点内部重复的情况；
- 如果源点和汇点个数都大于 $1$ ，那么如果要达到平衡，就必须分别集中则一边，也就是源点都在汇点的左边，或者源点都在汇点的右边，也就是从 $n$ 个点中选择 $src_cnt+snk_cnt$ 个作为源点和汇点，同时源点内部可以随意排列，汇点内部可以随意排列，即 $C_n^{src_cnt+snk_cnt}\times src_cnt! \times snk_cnt!$ ，当然也要处理源点或汇点内部重复的情况。
代码如下：
#include <map>
#include <numeric>
#include <iostream>
using namespace std;
const int N = 100010, mod = 1e9 + 7;
int n;
long long a[N];
int fact[N], infact[N];
void init(int n)
{
fact[0] = infact[0] = 1;
fact[1] = infact[1] = 1;
for (int i = 2; i <= n; i ++ )
{
fact[i] = (long long)fact[i - 1] * i % mod;
infact[i] = (long long)infact[mod % i] * (mod - mod / i) % mod;
}
for (int i = 2; i <= n; i ++ ) infact[i] = (long long)infact[i] * infact[i - 1] % mod;
}
int C(int a, int b)
{
if (a < b) return 0;
else return (long long)fact[a] * infact[b] % mod * infact[a - b] % mod;
}
int main()
{
init(N - 1);
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
long long sum = accumulate(a, a + n, 0LL);
if (sum % n)
{
cout << "0\n";
return 0;
}
int src_cnt = 0, snk_cnt = 0;
long long val = sum / n;
map<int, int> src, snk;
for (int i = 0; i < n; i ++ )
if (a[i] > val) src[a[i]] ++ , src_cnt ++ ;
else if (a[i] < val) snk[a[i]] ++ , snk_cnt ++ ;
int res = 0;
if (snk_cnt + src_cnt == 0) res = 1;
else if (snk_cnt == 1 || src_cnt == 1)
{
res = (long long)C(n, src_cnt + snk_cnt) * fact[src_cnt + snk_cnt] % mod;
for (auto &[x, y] : src) res = (long long)res * infact[y] % mod;
for (auto &[x, y] : snk) res = (long long)res * infact[y] % mod;
}
else
{
res = C(n, n - src_cnt - snk_cnt) * 2 % mod;
res = (long long)res * fact[snk_cnt] % mod * fact[src_cnt] % mod;
for (auto &[x, y] : src) res = (long long)res * infact[y] % mod;
for (auto &[x, y] : snk) res = (long long)res * infact[y] % mod;
}
cout << res << '\n';
return 0;
}
线性筛求各种信息模板
// 可以求每个数的：
// 最小质因子、质因子的种数、最小质因子的幂次
// 因子个数、因子之和
int primes[N], cnt; // 存放所有质数， cnt 为个数
int minp[N]; // minp[i] 表示 i 的最小质因子
int pcnt[N]; // 表示 i 有 pcnt[i] 个不同的质因子
int minp_cnt[N]; // 最小质因子的幂次
int fac_cnt[N]; // 因子个数
int fac_sum[N]; // 因子之和
int exminp[N]; // 除了最小质因子外的因子之和
bool st[N]; // st[i] 为 false 表示 i 为质数
void init(int n)
{
st[1] = true;
fac_sum[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
minp[i] = i;
primes[cnt ++ ] = i;
fac_cnt[i] = 2;
fac_sum[i] = i + 1;
minp_cnt[i] = 1;
exminp[i] = 1;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
minp[t] = primes[j];
if (i % primes[j] == 0)
{
fac_cnt[t] = fac_cnt[i] / (minp_cnt[i] + 1) * (minp_cnt[i] + 2);
fac_sum[t] = fac_sum[i] * primes[j] + exminp[i];
exminp[t] = exminp[i];
minp_cnt[t] = minp_cnt[t] + 1;
break;
}
else
{
fac_cnt[t] = fac_cnt[i] * fac_cnt[primes[j]];
fac_sum[t] = fac_sum[i] * fac_sum[primes[j]];
exminp[t] = fac_sum[i];
minp_cnt[t] = 1;
}
}
}
for (int i = 2; i <= n; i ++ )
{
int j = i / minp[i];
pcnt[i] = pcnt[j] + (int)(minp[i] != minp[j]);
}
}
