ryp 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-14 21:39:25
设两个数为 $u, v$，且 $u = 2^{k_1}p_1, v = 2^{k2}p_2, p_1 \equiv p_2 \equiv 1 \mod 2$。
两种情况。不等和相等。对于不等的，钦定 $k_1 \lt k_2$，那么 $u + v = 2^{k_1} (p_1 + p_2 2^{k_2-k_1})$。由于 $p_1$ 奇，后面偶，所以贡献就是直接加起来。
然后就是相等。考虑到很恶心的是我们不知道这俩东西加起来会除多少个 $2$。暴力枚举 $k_1$ （$k_2$），再暴力枚举一个 $k$，表示 $u + v = 2^k p$ 其中 $p$ 奇。由于值域 $10^7$ 直接开桶维护数量以及和。但是恶心的是这么算会重，于是做一个唐的没边的容斥。属于是高射炮炮决蚊子，张成泽馋死了。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-15 07:30:16
给定两个排列 $A$ 与 $P$，定义一次操作表示对于所有的 $1\le i \le n$，将 $A_i$ 替换为 $A_{P_i}$。要求进行任意非负整数次操作，求能得到的字典序最小的排列。
我们由 $i$ 向 $P_i$ 连一条有向边，那么可以得到一张图。考虑到现在一次操作实际上就是每个下标步进一次。
这时我们发现，确定操作次数，最终的排列就确定；换句话说，确定某一个点移动多少步，整个排列就确定。由此，结合要让字典序最小，很自然地考虑到要让每个环上的第一个位置最小。
但是这样可能冲突。考虑有两个大小为 $3$ 和 $6$ 的环，假设第一个环上移动 $2$ 步最优，第二个环上移动 $1$ 步最优。这时无论怎么操作，两个环都无法同时最优。换句话说，这两个同余方程没有公共解。
由于我们还要保证字典序最小，那么显然是尽量满足前面的环，即最小位置在最前面的环。后面的环怎么办？考虑枚举每个环上移动的步数 $k$，使得 $k$ 和前面的同余方程不冲突，在此条件下满足字典序尽可能小（即最小位置放尽可能小的数）。
怎么判断某个 $k$ 是否满足前面的同余方程？考虑到这个同余方程的模数是前面所有环长的 $\text{lcm}$，是阶乘级别的，没法直接做（然而官方题解拿 Python 水了）。考虑到
$$ x\equiv a \pmod m \Leftrightarrow x\equiv a_i\pmod {m_i^{\lpha_i}} $$
其中 $m_i, \lpha_i$ 是 $m$ 的标准分解。
那么可以分解出环长的质因子。设 $f(p)$ 表示当前同余方程的解模 $p$ 的值。那么枚举操作次数 $k$ 的同时，要满足对环长的每一个质因子 $p$，$k \bmod p$ 都和 $f(p)$ 相同。满足这个条件的情况下，再让字典序尽可能小。
于是我们做完了。
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
int ps[N], minp[N], res[N], z[N], p[N], w[N], f[N], nr = 0;
bool vis[N];
void sieve (void)
{
for (int i = 2; i < N; i++) {
if (!minp[i]) ps[++nr] = i, minp[i] = i;
for (int j = 1; ps[j] * i < N; j++) {
minp[i * ps[j]] = ps[j];
if (i % ps[j] == 0) break;
}
}
}
int main (void)
{
int n;
cin.tie (0)->sync_with_stdio (false);
cin >> n;
sieve ();
memset (f, -1, sizeof f);
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1; i <= n; i++) cin >> z[i];
for (int i = 1; i <= n; i++) if (!vis[i]) {
int j = i;
vector<int> q, p;
while (!vis[j]) vis[j] = true, q.push_back (j), j = w[j];
int l = q.size (), t = l;
while (t > 1) {
int u = minp[t], w = 1;
while (t % u == 0) t \/= u, p.push_back (w *= u);
}
int k = -1;
for (int i = 0; i < l; i++) {
for (auto j : p) if (f[j] != -1 && i % j != f[j]) goto nxt;
if (k == -1 || z[q[k]] > z[q[i]]) k = i;
nxt:;
}
for (int i = 0; i < l; i++) res[q[i]] = z[q[(i + k) % l]];
for (auto v : p) f[v] = k % v;
}
for (int i = 1; i <= n; i++) cout << res[i] << " \n"[i == n];
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-20 20:48:19
看到题解区大神都写了 01 trie / 分治，根本看不懂，怎么办！
但是不要急！本题可以用根本没有思维含量的小常数基数排序 + 树状数组 $O(n\log n \log V)$ 狠狠草过去！
这就是基数排序带给我的自信
我们直接狠狠贪心，从高到低枚举每一位，然后计算异或上这一位或是不异或的逆序对数。如果变少了，就直接选上这一位。然后就做完了。
但是……
如果你就这样天真的写了一颗平衡树 / 离散化 + 树状数组交上去，就会发现出题人狠狠的草爆了你的码！
但是！
众所周知，存在一种叫做基数排序的东西……它可以用线性的时间把一堆整数排序。
我们这里的问题是，离散化的速度太慢，是个线性对数。考虑到可以用基数排序替代快速排序 + 二分进行离散化，于是我们就做完了。
附一个基数排序离散化模板，它是本题的大功臣！
void radix_sort (int n)
{
int mx = 0;
for (int i = 1; i <= n; i++) ww[i] = { w[i], i };
for (int i = 1; i <= n; i++) q[w[i] & 0x7fff]++, mx = max (mx, w[i] & 0x7fff);
for (int i = 1; i <= mx; i++) q[i] += q[i - 1];
for (int i = n; i >= 1; i--) rr[q[w[i] & 0x7fff]--] = ww[i];
for (int i = 0; i <= mx; i++) q[i] = 0;
mx = nr = 0;
for (int i = 1; i <= n; i++) q[rr[i].fi >> 15]++, mx = max (mx, rr[i].fi >> 15);
for (int i = 1; i <= mx; i++) q[i] += q[i - 1];
for (int i = n; i >= 1; i--) ww[q[rr[i].fi >> 15]--] = rr[i];
for (int i = 0; i <= mx; i++) q[i] = 0;
for (int i = 1; i <= n; i++) w[ww[i].se] = nr += i == 1 || ww[i].fi != ww[i - 1].fi;
}
以及 Submission
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-23 11:28:54
考虑到题目中的操作实际上就是给区间加上某个值，询问就是问某点和第一次大于等于 $k$ 的时间。
考虑到可以直接用可持久化线段树模拟这个过程。
可持久化线段树是可以用标记永久化的方法来实现某些区间操作的。具体来说，我们不将某个点上的标记下传，而是在询问时一路加上所有标记。
然后二分一个最早的树即可。实现不难。
#include <iostream>
using namespace std;
using i64 = long long;
const int N = 1e6 + 10;
struct node { i64 s; int l, r; } sg[20 * N];
int rt[N], id[N], cnt = 0;
void upd (int &u, int v, int x, int y, int l, int r, i64 k)
{
int mid = (x + y) \/ 2;
sg[u = ++cnt] = sg[v];
if (l <= x && y <= r) return sg[u].s += k, void ();
if (l <= mid) upd (sg[u].l, sg[v].l, x, mid, l, r, k);
if (r > mid) upd (sg[u].r, sg[v].r, mid + 1, y, l, r, k);
}
i64 qry (int u, int x, int y, int p, i64 tag)
{
int mid = (x + y) \/ 2;
if (x == y) return sg[u].s + tag;
if (p <= mid) return qry (sg[u].l, x, mid, p, tag + sg[u].s);
else return qry (sg[u].r, mid + 1, y, p, tag + sg[u].s);
}
int main (void)
{
int n, q, qid = 0;
cin.tie (0)->sync_with_stdio (false);
cin >> n >> q;
for (int i = 1; i <= q; i++) {
int opt;
cin >> opt;
if (opt == 1) {
int x;
i64 y, k;
cin >> x >> y >> k;
id[++qid] = i, upd (rt[qid], rt[qid - 1], 1, n, x, y, k);
}
else {
int l = 1, r = qid, ans = -1, x;
i64 y;
cin >> x >> y;
if (qry (rt[qid], 1, n, x, 0) < y) {
cout << "0\n";
continue;
}
while (l <= r) {
int mid = (l + r) \/ 2;
if (qry (rt[mid], 1, n, x, 0) >= y) r = (ans = mid) - 1;
else l = mid + 1;
}
cout << id[ans] << '\n';
}
}
return 0;
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-24 16:48:41
考虑证明按照 $s + w$ 贪心的正确性。
我们的贡献和位置是无关的，因此我们要证的仅仅是当 $s_i + w_i \lt s_j + w_j$ 时，若 $j$ 可以放在 $i$ 上头，那么 $i$ 就一定能放在 $j$ 上头。也就是说：任意一种方案，都可以是排序后顺序构造。
设 $p_i$ 表示当前方案中 $1$ 到 $i$ 所有箱子的重量和，那么我们已知 $p_{i-1} \le s_i, p_{j-1}\le s_j$，要证 $p_{i-1}\le s_j, p_{j-1} - w_i + w_j \le s_i$。
放缩代入得证。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-25 07:30:34
考虑到两个子树的并就是整个树，那么一个颜色在两个子树同时存在，当且仅当它在某一个子树中的出现次数不为它在整棵树里头的出现次数。
那么就做完了。因为这时候我们就可以钦定 $1$ 为根，然后对 $1$ 为根的每一个子树算一下它的答案。线段树维护这个是简单的。
然后可以线段树合并 / 树上启发式合并，做完了。
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int rt[N], z[N], cntq[N], head[N], res[N], ecnt = 1, cnt = 0, n;
struct edge { int v, nxt; } e[N * 2];
struct node { int s, k, l, r; } sg[50 * N];
void add (int u, int v)
{
e[++ecnt] = { v, head[u] }, head[u] = ecnt;
}
\/\/ 考虑到实际上就是不等于总出现次数的点的数量。可以直接线段树做。
void push_up (int i) { sg[i].s = sg[sg[i].l].s + sg[sg[i].r].s; }
void upd (int &u, int x, int y, int p)
{
int mid = (x + y) \/ 2;
if (!u) u = ++cnt;
if (x == y) return sg[u].s = cntq[x] != ++sg[u].k, void ();
if (p <= mid) upd (sg[u].l, x, mid, p);
else upd (sg[u].r, mid + 1, y, p);
push_up (u);
}
void merge (int &u, int v, int x, int y)
{
int mid = (x + y) \/ 2;
if (!u || !v) return u += v, void ();
if (x == y) return sg[u].s = (sg[u].k += sg[v].k) != cntq[x], void ();
merge (sg[u].l, sg[v].l, x, mid), merge (sg[u].r, sg[v].r, mid + 1, y);
push_up (u);
}
void dfs (int u, int last)
{
int nr = 0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (v == last) nr = i \/ 2;
else dfs (v, u), merge (rt[u], rt[v], 1, n);
}
upd (rt[u], 1, n, z[u]), res[nr] = sg[rt[u]].s;
}
int main (void)
{
cin.tie (0)->sync_with_stdio (false);
cin >> n;
for (int i = 1; i <= n; i++) cin >> z[i], cntq[z[i]]++;
for (int i = 1, u, v; i < n; i++) cin >> u >> v, add (u, v), add (v, u);
dfs (1, 0);
for (int i = 1; i < n; i++) cout << res[i] << '\n';
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-28 10:40:32
要合理分配时间，合理为正解分配思考时间，冷静分析题目性质，不要不敢想正解。思路还是要打开。
场上要冷静考虑状态以及转移，不要因为急就临时更改做法。简单题的分数要拿到手。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-07 10:38:22
题意：一个石子堆，初始为空，每次操作可以放上一枚石子。设当前石子的数量是 $x$，那么这一轮有 $P_x$ 的概率一个石子掉落（石子掉落后 $x$ 仍不变）。求石子堆到 $n$ 个的期望步数。
设 $f_i$ 表示由 $i - 1$ 个石子堆到第 $i$ 个的期望步数。考虑从第 $i - 1$ 个石子堆上后发生了什么。
一种可能是全掉完了。概率是 $P_i^i$，代价是 $\sum\limits_{j=1}^i f_j$；
另一种可能是掉到某一个 $j$ 就不再掉，概率是 $P_i^{i-j} (1 - P_i)$，代价是 $\sum\limits_{k=j+1}^i f_j$。这里 $j\in [1, i]$。
还有根本没有掉的，但是根本没有贡献。
这个式子拆开 $1 - P_i$ 项化简，可以得到一个 $O(N)$ 转移。由于 $P_i$ 只有 $100$ 种，因此可以对每一种 $P_i$ 前缀优化。最终复杂度是 $O(n\max P)$。
先看 Subtask 1。设 $f(i, j)$ 表示 Bob 已经进行了 $i$ 轮，已经选择了 $j$ 轮加法，最后的值。
现在我们不知道 Alice 会选什么。但是设她会选 $t$，那么
$$ f(i, j) = \min (f(i - 1, j) - t, f(i - 1, j - 1) + t) $$
Bob 会让答案尽可能小，所以外面套一个 $\min$。这个式子显然是在取到均值的时候最大，因此 Alice 会取这两个转移路径的均值。于是我们得到
$$ f(i, j) = \dfrac {f(i - 1, j) + f(i - 1, j - 1)} 2 $$
边界是 $j = 0$ 和 $i = j$。$j = 0$ 时，Bob 全都选减法，因此 Alice 全给 $0$。$j = i$ 时，Bob 全选加法，因此 Alice 全给 $k$。
对于 Subtask 2，考虑每个位置对 $f(n, m)$ 的贡献。能贡献的位置只有 $f(i, i) = ki$，贡献路径是 $(i, j) \rightarrow (i + 1, j), (i + 1, j + 1)$，也就是竖着或者斜着走，方案数是 $n - i - 1\choose m - j$。贡献是多少？一开始的贡献是 $ki$，随着往下走一行，会除以一个二。一共走 $n - i$ 行，因此除以 $2^{n-i}$。
所以最后的答案是
$$ \sum\limits_{x=1}^{n-1} \dfrac{{n-x-1\choose m-j} kx}{2^{n-x}} $$
比较奇妙。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-07 20:37:13
一秒能处理的是 $\min(x, y)$，用 $n$ 除，上取整即可。
$a_n$ 一定是正贡献，$a_{n-1}$ 一定是负贡献，其他的数可全分配成正贡献。因为只有正数，所以最优。
考虑设当前已确定的长度为 $L$，已确定的一个子串为 $Q$。每次尝试扩大 $Q$，往它的后面加上 $0$ 或者 $1$；如果答案都是 $0$，说明已经到达了结尾，需要改变扩展方向。
场上想到了大部分做法，但是没有考虑到第一次往后扩展不到的时候就可以直接往左扩展，因此询问次数超限。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-08 16:31:27
考虑到最后拼接成的值域区间是连续的。我们维护拼接出这段区间需要几个原序列中的区间。
考虑固定值域右端点 $r$，维护 $[l, r]$ 在原序列中的段数。考虑加入一个数，如果原序列中和他相邻的数还没有被加入，那么它是不会相邻的，序列段数全都加一。
如果和它相邻的某一个已经加入了，那么段数和原来一样。特别地，如果它的左右两边都已经被加入了，那么段数还要减去一。
我们每次数的就是以它为右端点，左边为 $1$ 或者 $2$ 的数的数量。考虑到每个数都是正的，那么 $1$ 或者 $2$ 一定是最小值或者次小值。于是我们做一个最小值 / 次小值计数就好了。线段树维护完了。
鲁ICP备2025150228号