## 重组字母
#贪心
> [!note] 思路
>
> 首先看到字典序最小，我们就可以想到从前往后枚举答案的每一位，然后从小到大枚举字符，找到一个字典序最小、且填上之后后面不会无解的字符填上就行了。
>
> 如何判断填上之后后面有没有解呢？比较直观的思路是对于后面每个 cch 的字符记录出现次数。对于 $\texttt{a}$ 的出现次数，cwj 在后面 ${} \texttt{b} {}$ 的出现次数和 $\texttt{c}$ 的出现次数之和要超过它。$\texttt{b}$ 和 $\texttt{c}$ 同理。这样就可以做到 $\mathcal O(1)$ 判断了，总时间复杂度 $\mathcal O(n)$。
>
> 当然也可以往右做模拟。时间复杂度 $\mathcal O(n^2)$，在本题当中同样可以通过。
```cpp
int cnt[128], f[128], n;
string s, t, ans;
bool check(char c) {
if (cnt['b'] + cnt['c'] >= f['a'] &&
cnt['a'] + cnt['b'] >= f['c'] &&
cnt['a'] + cnt['c'] >= f['b']) {
return 1;
}
return 0;
}
int main() {
cin >> n >> s >> t;
for (char c : s) {
cnt[c]++;
}
for (char c : t) {
f[c]++;
}
for (char i : t) {
for (char j = 'a'; j <= 'c'; j++) {
if (i == j) {
continue;
}
if (cnt[j]) {
cnt[j]--;
f[i]--;
if (check(j)) {
ans += j;
break;
}
cnt[j]++;
f[i]++;
}
}
}
cout << ans << '\n';
return 0;
}
```
## 区间整除
#数学 #质数 #质因数分解
> [!note] 思路
>
> > [!important] 注意
> >
> > 以下记 $f(l,r)=\prod\limits_{i=l}^r i=l\times(l+1)\times\cdots\times r$
>
> 首先我们看到整除，就可以想到质因数分解。考虑对 $f(a,b)$ 和 $f(c,d)$ 进行质因数分解，等价于对所有 $i\in [a,b]$ 当中 $i$ 进行质因数分解，然后相同质因数的指数相加。
>
> 对于这种区间的问题，可以想到前缀和。但是由于在 $10^7$ 的范围内大约有 ${} 6\times 10^5$ 个质数，所以导致在 $i$ 较大的时候 $i!$ 的质因数分解底数数量会达到 $6\times 10^5$，当然无法直接保存。
>
> 考虑离线下来求。现在我们需要面对的问题就是对任意 $i\in \left[1,10^7\right]$ 进行质因数分解了。直接分解单个时间复杂度高达 $\mathcal O\left(\sqrt n\right)$，所以我们需要使用质数筛（$\mathcal O(n\log\log n)$ 或 $\mathcal O(n)$）求出每个数的最大质因子，然后使用单个时间复杂度 $\mathcal O\left(\log n\right)$ 的质因数分解。
>
> 由于本题值域达到了 $10^7$，$\mathcal O(n\log_2 n)$ 也是吃不消的。考虑转换思路，不专注于每个数的质因数分解，而专注与每个质因子的出现情况。
>
> 首先有 $f(l,r)=\cfrac{r!}{(l-1)!}$。我们枚举质因子 $i$（$i$ 肯定是质数列表里面的），那么 $f(l,r)$ 当中 $i$ 的出现次数就是 $r!$ 当中 $i$ 的出现次数减去 $(l-1)!$ 当中 $i$ 的出现次数。
>
> > [!question] 疑问
> >
> > 如何计算 $n!$ 当中 ${} p$ 作为质因子出现的次数呢？
>
> > [!success] 计算方法
> >
> > 枚举 $k$ 计算 $n!$ 当中 $p^k$ 的出现次数，那么出现次数为 $\cfrac{n}{p^k}$，累加起来即可得到 $p$ 作为质因子的出现次数（可能在同一个数当中出现多次）。
> >
> > 时间复杂度 $\mathcal O(\log p)$。
>
> 而 $a|b$ 等价于对于任意质因子 $p$ 在 $a$ 当中的出现次数不超过在 $b$ 当中的出现次数。所以，我们只需要枚举质数（质因子），计算他们在 $f(a,b)$ 和 $f(c,d)$ 当中的出现次数，判断是否小于等于即可。
>
> 时间复杂度 $\mathcal O(n\log\log n+Tm\log n)$，其中 $n$ 为值域，$m$ 为值域中质数数量（大约 $6\times 10^6$。使用线性筛可以将预处理优化到 $\mathcal O(n)$。
```cpp
const LL kMaxN = 1e7 + 5;
LL t, a, b, c, d;
bool p[kMaxN];
vector<LL> v;
void init(LL n) {
for (LL i = 2; i <= n; i++) {
if (!p[i]) {
v.push_back(i);
}
for (LL j : v) {
if (i * j > n) {
break;
}
p[i * j] = 1;
if (i % j == 0) {
break;
}
}
}
}
LL calc(LL n, LL p) {
LL res = 0;
for (LL x = p; x <= n; x *= p) {
res += n / x;
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
init(1e7);
for (cin >> t; t; t--) {
cin >> a >> b >> c >> d;
bool ans = 1;
for (LL i : v) {
if (i > b && i > d) {
break;
}
LL x1 = calc(b, i) - calc(a - 1, i);
LL x2 = calc(d, i) - calc(c - 1, i);
ans &= x1 <= x2;
if (!ans) {
break;
}
}
cout << (ans ? "Yes" : "No") << '\n';
}
return 0;
}
```
## 擦数游戏
#深度优先搜索 #二分 #排序
> [!note] 思路
>
> 首先应该对于 $|x-y|$ 转化，如果我们在选择的时候钦定 $x\ge y$ 则直接变成 $x-y$ 了。不难发现 $(a-b)-c$ 可以转化为 $a-b-c$，而 $a-(b-c)$ 可以转化为 $a-b+c$ 了。反过来，对于所有我们选的数，在中间随便填上 $+$ 或 $-$，都是可以转化为题目中的操作形式的。
>
> 所以问题就转化成了，对于每个 $a_i$，可以加到答案里，减到答案里，或者让答案不变。求最后操作了至少一次的大于等于 $0$ 的最小答案（或最小绝对值）。
>
> 对于 $n\le 10$，可以直接采用搜索的方式。每个数三种情况，额外记录是否已经操作过。时间复杂度 $\mathcal O(3^n)$。
>
> - [n] 不难发现几乎所有的分都在 $n\le 30$ 的上面，而 $n>30$ 分很少，所以对于 $n>30$ 直接输出 $0$ 即可。
>
> > [!error] 错误
> >
> > 然后我就 WA 了两个测试点。原因是对于 $n=31$ 仍有可能答案不为 $0$，而 $n\ge 32$ 才能输出 $0$。
>
> 对于 $n\le 30$，我们好像很难处理。忽然，我灵光乍现，发现 $n=15$ 的时候运算量只有 $1.4\times 10^7$，所以可以使用折半搜索。前半段和后半段分开搜，把前半段的答案记下来排序后半段完成之后就通过二分快速找到大于等于 $0$ 的最小和。
>
> 时间复杂度 $\mathcal O\left(3^{n/2}\log_2 3^{n/2}\right)$。当然，赛时被卡 TLE 了，赛后改的 AC 代码有很多玄学（可能导致 WA）的不正确优化。仅供参考思路。
```cpp
const LL kMaxN = 1e5 + 5;
LL a[kMaxN], n, ans = 1e18;
vector<LL> s[2];
void dfs1(LL x, LL sum, bool b) {
if (x > n / 2) {
s[b].push_back(sum);
return;
}
dfs1(x + 1, sum, b);
dfs1(x + 1, sum + a[x], 1);
dfs1(x + 1, sum - a[x], 1);
}
LL calc(bool b, LL x) {
auto i = lower_bound(s[b].begin(), s[b].end(), -x);
if (i != s[b].end()) {
return *i;
}
return 1e18;
}
void dfs2(LL x, LL sum, bool b) {
if (!ans || ans == 1) {
cout << ans << '\n';
exit(0);
}
if (sum > 5e9 || sum < -5e9) {
return;
}
if (x <= n / 2) {
ans = min(ans, sum + calc(1, sum));
if (b == 1) {
ans = min(ans, sum + calc(0, sum));
}
return;
}
dfs2(x - 1, sum, b);
dfs2(x - 1, sum + a[x], 1);
dfs2(x - 1, sum - a[x], 1);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
}
if (n == 1) {
cout << a[1] << '\n';
return 0;
}
if (n > 31) {
cout << "0\n";
return 0;
}
if (n == 31) {
cout << "1\n";
return 0;
}
dfs1(1, 0, 0);
sort(s[0].begin(), s[0].end());
sort(s[1].begin(), s[1].end());
dfs2(n, 0, 0);
cout << ans << '\n';
return 0;
}
```
## 逃离
#贪心 #优先队列 #排序
> [!quote] 何已为
>
> 赛时根本不会，想得过于复杂了，只写了 $n=1$，高达 $5$ 分。
> [!note] 思路
>
> 首先每个车的长度和初始位置是不能被改变的，但是可以通过加速器改变速度。对车按照左端点从小到大排序，然后从左往右遍历每个车。
>
> 由于车撞到它前面的车时就会强制减速到前车的思路，所以所有车之间相对位置不变，问题就等价于让第一辆车车尾超出 $t$ 时的速度最小。
>
> 对于第二辆车，如果第一辆车的速度超过了它并能在桥上赶上它，那么它的车尾就需要到达 $t+len_1$（$len_i$ 是 $i$ 车的长度）才能完成任务；如果第一辆车赶不上它，那么它的车尾到达 $t+len_1$ 时第一辆车也不会达到 $t$。所以令 $sum=\sum\limits_{j=1}^{i-1}len_j$，那么第 $i$ 辆车完成它的任务需要满足车尾到达 $t+sum$。所以我们可以计算所有车完成任务需要的实际距离，求出需要的时间。
>
> 然后就是贪心时间。我们的最终答案取决于每个车需要时间的最小值，所以用优先队列，每次取出需要时间最大的车进行升级。最后就可以得到答案。时间复杂度 $\mathcal O(n\log_2 n)$。
赛时没有想到转化真是太可惜了。
```cpp
const LL kMaxN = 3e5 + 5;
struct Node {
LL l, len, v, s;
double t;
friend bool operator<(const Node &a, const Node &b) {
return a.t < b.t;
}
} a[kMaxN];
LL n, t, m, k;
priority_queue<Node> q;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> t >> m >> k;
for (LL i = 1, l, r, v; i <= n; i++) {
cin >> l >> r >> v;
a[i] = {l, r - l, v};
}
sort(a + 1, a + n + 1, [](auto a, auto b) {
return a.l < b.l;
});
LL sum = 0;
for (LL i = 1; i <= n; i++) {
a[i].s = t + sum - a[i].l;
a[i].t = 1.0 * a[i].s / a[i].v;
q.push(a[i]);
sum += a[i].len;
}
while (m--) {
auto t = q.top();
q.pop();
t.v += k;
t.t = 1.0 * t.s / t.v;
q.push(t);
}
cout << fixed << setprecision(3) << q.top().t << '\n';
return 0;
}
```