300iq contest 2 B Bitwise Xor 题解
发表于
分类于
题解
题目链接：300iq contest 2 B. Bitwise Xor
乡下人没见过 Trie 树，学会了。
1 | #include<bits/stdc++.h> |
AT_agc044_c [AGC044C] Strange Dance 题解
发表于
分类于
题解
乡下人 × 2。这次是低位在上。
1 | #include<bits/stdc++.h> |
CF1801F Another n-dimensional chocolate bar 题解
发表于
分类于
题解
本文迁移自洛谷原文。
考虑到最多只会有一个 $b_i \ge \sqrt{k}$。
- 没有任何一个 $b_i \geq \sqrt{k}$。
那么我们可以考虑类似 meet-in-the-middle 的做法。
令 $f_{i,j}$ 表示考虑了前 $i$ 个数，此时乘积为 $j$，$\lfloor\frac{a_1}{b_1}\rfloor\lfloor\frac{a_2}{b_2}\rfloor\dots\lfloor\frac{a_i}{b_i}\rfloor\frac{1}{a_1a_2\dots a_i}$ 的最大值，$g_{i,j}$ 的定义类似，不过是从 $n$ 开始倒着的。dp 的时候枚举 $i$，枚举 $j$，再枚举满足 $j\times k \le$ 第二维大小的所有 $k$ 即可。
则我们这种情况下的最好答案就是枚举一个中间断点 $i$，和 $i$ 左边的部分的乘积 $j$，$f_{i,j}\times g_{i+1,\lceil\frac{k}{j}\rceil}$ 的最小值了。
此时我们需要证明，在所有选择的 $b_i$ 都 $\le \sqrt{k}$ 的情况下，$f$ 和 $g$ 的第二维都只要开到 $k^{\frac{3}{4}}$ 即可。
不妨设一个 $x$，初始为 $b_i$ 最大的位置，令 $p$ 为 $x$ 左边所有 $b_i$ 的乘积，$q$ 为 $x$ 右边所有 $b_i$ 的乘积。
我们贪心的考虑，如果 $b_x^2\times p <q$，就让 $x+1$；如果 $b_x^2\times q < p$，就让 $x-1$。在移动 $x$ 的同时维护 $p$ 和 $q$ 的值。
此时第二维就需要开到一个 $\min(p,q)\times b_x$ 的大小。因为 $p \times q \times b_x$ 是 $O(k)$ 级别的，所以 $\min(p,q)\le \sqrt{\frac{k}{b_x}}$，故第二维只需要开到 $\sqrt{\frac{k}{b_x}}\times b_x=\sqrt{k\times b_x}$ 即可。因为 $b_x\le \sqrt{k}$，所以 $\sqrt{\frac{k}{b_x}}\times b_x \le k^{\frac{3}{4}}$，得证。
综上，该部分复杂度为 $O(n\times k^{\frac{3}{4}}\times\log(k))$。
- 存在恰好一个 $b_i \geq \sqrt{k}$。
那么我们可以直接枚举这个 $i$，发现 $i$ 左侧和右侧 $b_j$ 的乘积均 $\le \sqrt{k}$。令 $h_j$ 表示现暂时不选 $b_i$，其他所有位置都选之后乘积为 $j$ 时的最大值。这个可以利用 $f_{i-1}$ 和 $g_{i+1}$ 快速处理。
然后我们枚举除了 $b_i$ 的所有 $b_j$ 的乘积 $t$，推出 $b_i$ 的值最小是多少，计算出 $\lfloor\frac{a_i}{b_i}\rfloor\frac{1}{a_i}$ 即第 $i$ 个数的贡献，乘上 $h_t$ 即可。
该部分复杂度为 $O(n\sqrt{k})$。
综上，总复杂度为 $O(n\times k^{\frac{3}{4}}\times\log(k))$，可以不知道为什么但只跑了 1.5s 通过此题。
1 | #include<bits/stdc++.h> |
AT_arc052_d [ARC052D] 9 题解
发表于
分类于
题解
本文迁移自洛谷原文。
题目翻译是错误的，正确的如下：
给定两个正整数 $K,M (1\le K,M \le 10^{10})$，你需要求出有多少个正整数 $N$ 满足 $1 \le N \le M$ 且 $N \equiv S_N (\bmod K) $，其中 $S_N$ 是 $N$ 的各位数字之和。
题解：
这个 $10^{10}$ 的数据范围并不常见，但是可以发现大概是根号的复杂度。
显然无法分块，考虑怎么做到根号分治。我们先对 $K$ 设定一个阈值 $T$，其中 $T$ 是 $\sqrt{M}$ 级别。
- $K \ge T$
当 $1 \le N \le 10^{10}$ 时，最大的 $S_N$ 不过 $9\times 10=90$，所以我们可以去先枚举数字和 $S$，然后就可以发现，$\bmod K= S$ 的 $N$ 的个数不会超过 $\lfloor\frac{M}{K}\rfloor +1$ 个。直接枚举这些数就可以了。复杂度 $O(S_N\times \frac{M}{K})$。
- $K \le T$
我们可以考虑把 $K$ 做为一维压到数位 dp 里了。令 $dp_{i,j,sm,0/1}$ 表示考虑到从高到低第 $i$ 位，此时的数 $\bmod K = j$，数字和为 $sm$，是否已经小于 $m$ 的数的个数。这样就可以 dp 了，复杂度 $O(\log k \times S_N\times K)$。
均衡一下取 $K=10000$ 最优。
Code:
1 | #include<bits/stdc++.h> |
AT_arc023_4 [ARC023D] GCD区间 题解
发表于
分类于
题解
本文迁移自洛谷原文。
题目大意：
给出一个长度为 $n$ $(1 \le n \le 10^{5})$ 的序列和 $m$ $(1 \le m \le 10^{5})$ 个询问。对于每个询问，输入 $x$ $(1 \le x \le 10^{9})$，输出满足 $gcd(a_l,a_{l+1},…,a_r)=x$ 的 $(l,r)$ 的对数。
题解：
考虑我们固定一个起点 $l$，从 $l$ 到 $n$ 扩张区间的右端点 $r$，考虑区间 gcd 的变化。
显然，这个 gcd 最多只会变化 $\log A$ 次（$A$ 是值域），因为每次变化必然是砍掉一个（或一些）质因数，而质因数的个数是 $\log A$ 级别的。
所以我们可以考虑枚举开头，每次二分出下一个变化点的位置，每个开头二分 $\log A$次，就可以求出所有可能的 gcd 的值并得到出现次数了。
注意用 $ST$ 表预处理一下 gcd，复杂度就可以做到 $n \log A \log n$ 了。
Code:
1 | #include<bits/stdc++.h> |
AT_arc045_d [ARC045D] みんな仲良し高橋君 题解
发表于
分类于
题解
本文迁移自洛谷原文。
题目大意：
平面上有 $2n+1$ 个点，两个点可以构成一组配对当且仅当它们的横坐标或纵坐标相等。
对于从 $1$ 到 $2n+1$ 的每个 $i$，询问在去掉第 $i$ 个点后，剩下 $2n$ 个点是否能配成 $n$ 对，满足每个点恰好出现在一组配对中。询问间互相独立。
- $1 \leq n \leq 10^5$
题解：
先有一个很重要结论：
如果有两个点 $x,y$ 他们能匹配上，我们对 $x,y$ 之间连一条边。
然后，如果一个连通块的大小是偶数，那么它一定可以达到完美匹配。
证明：
考虑取出两个当前没有匹配上的点 $x$ 和 $y$。
由于他们是在一个连通块里，所以一定可以找到一条从 $x$ 到 $y$ 的路径。
将这条路径上相邻的进行匹配，如果有摧毁的原有匹配那么按照与路径平行的方向找到下一个待匹配的，可以证明一定能将两个匹配被摧毁的不在路径上的点匹配到一起。
所以，如果原图有多个连通块：
如果有多个大小为奇数的连通块，则所有答案都是
NG。也就是说，我们可以无视掉所有大小为偶数的连通块（这些块内的点的答案都是
NG，因为删掉这种点，最终还是会有至少一个大小为奇数的连通块，不符合）。所以，我们只要在那唯一一个大小为奇数的连通块中，考虑删掉那些点可以使得剩下所有连通块的大小都是偶数。
然后发现这玩意很像一个圆方树，所以建出圆方树后跑一下就行了。
注意：
如果暴力建原图的话边的条数是 $O(n^2)$ 的，所以我们可以对行和列的 $id$ 分别建点，然后将点连向行/列即可。
最终只有 $2\times n+1$ 个点是真的，大小算 $1$，那些代表行/列/点双的点大小都要算 $0$。
Code:
1 | #include<bits/stdc++.h> |
AT_arc028_4 [ARC028D] 注文の多い高橋商店 题解
发表于
分类于
题解
本文迁移自洛谷原文。
题目大意：
给定 $n$，$m$。有 $n$ 种商品，编号从 $1$ 到 $n$，第 $i$ 种商品最多能拿 $a_i$ 个。
共 $q$ 次询问。每次询问给定 $k$，$x$，求第 $k$ 种商品 恰好 拿走 $x$ 个的前提下，在 $n$ 种商品中一共拿走 $m$ 个商品的方案数。两种方案不同当且仅当存在一种商品在二方案中被拿走的个数不同。输出答案对 $10^9+7$ 取模的结果。
$1 \leq n,m,a_i \leq 2\times 10^3$
$1\leq k\leq n$
$1\leq x\leq a_k$
部分分是 $1 \le n,m,q \le 100$ 和 $1 \le n,m \le 100$。
题解：
部分分是基础 $dp$。
令 $dp_{i,j}$ 表示考虑到第 $i$ 种物品，当前已经选了$j$ 个时的方案数。转移为 $dp_{i+1,j}=\sum\limits_{\max(0,j-a_i)}^{j} dp_{i,j}$。
然后每次询问暴力求一遍 dp，可以拿到第一个部分分。
然后我们可以发现第二个部分分中 $n$ 小 $q$ 大，就可以考虑预处理出所有询问要恰好拿走的商品 id 做最后一个物品的 dp 数组（很容易发现这些商品之间的顺序无关紧要），就可以了。预处理复杂度 $O(n^2m)$。
正解还是要看到这个商品之间的顺序无关紧要。
再观察这个转移式子，$dp_{i+1,j}=\sum\limits_{\max(0,j-a_i)}^{j} dp_{i,j}$。
考虑反过来由 $dp_{i+1}$ 推向 $dp_{i}$，会有什么效果？
$dp_{i,j}$ 相当于 $dp_{i+1,j}-dp_{i+1,j-1}$ 再加上 $dp_{i,j-a_{i}-1}$（如果 $j \ge a_{i}+1$）。
再根据商品之间无关紧要，$dp_{n+1}$ 这个数组为考虑完全部的 $n$ 个物品之后得到的 dp 值，前面商品的顺序再怎么换也不会影响到它，所以我们可以枚举假设最后一个选的是 $i$ 号物品，$O(m)$ 的倒推即可。总时间复杂度 $O(nm+q)$。
Code:
1 | #include<bits/stdc++.h> |
AT_arc047_d [ARC047D] ナナメクエリ 题解
发表于
分类于
题解
本文迁移自洛谷原文。
题目大意：
有一个 $n\times n$（$1\le n \le 5000$）的正方形矩阵，初始全部为 $0$，下标从 $0$ 开始。
有 $q$（$1 \le q \le 5000$）次操作：
$1$ $a$ $b$ $c$ 将所有满足 $a \le x+y \le b$ 的点 $(x,y)$ 的值加上 $c$。
$2$ $a$ $b$ $c$ 将所有满足 $a \le x-y \le b$ 的点 $(x,y)$ 的值加上 $c$。
$3$ $a$ $b$ $c$ $d$ 查询所有满足 $a \le x \le b$， $c \le y \le d$ 的点 $(x,y)$ 的最大值，并求出值为最大值的点的个数。
部分分：$1 \le n \le 500$
题解：
我们考虑维护两个数组 $s1,s2$，其中 $s1_i$ 表示所有满足 $x+y=i$ 的点加的和，$s2_i$ 表示所有满足 $x-y=i$ 的点加的和。
对于一个点 $(x,y)$，他的值就是 $s1_{x+y}+s2_{x-y}$，所以我们维护 $s1,s2$ 就可以知道全矩阵的值了，$1$ 和 $2$ 操作的复杂度都为 $O(nq)$。
关键在于这个询问。
我们可以枚举所有可能的 $sum$（就是 $x+y$ 的值），那么可以发现，那些在 $sum$ 已知的条件下可行的 $x-y$ 就是连续的一些奇数或者偶数。用数据结构维护可以做到 $O(qn\log n)$，得到部分分。
再继续考虑。
考虑特殊化，查询的是一个正方形。
如果我们从小到大枚举所有的 $sum$，且枚举的时候让 $step=2$（就是按照 $sum$，$sum+2$，$sum+4 \dots$ 的顺序枚举），可以发现每次只会新增两个可能的 $x-y$，不会变少，所以我们只要暴力用新增的两个 $x-y$ 更新就行了。
同理，我们再按照 $sum+1$，$sum+3\dots$ 的顺序枚举，两种情况合并后就是答案了。
再考虑把查询一般化为长方形，则可以按照类似辗转相减法的方法每次割出最大的正方形去查询，然后合并所有的答案，可以证明单次询问复杂度为 $O(n)$，故总时间复杂度为 $O(nq)$。
Code:
1 | #include<bits/stdc++.h> |
AT_arc048_d [ARC048D] たこ焼き屋とQ人の高橋君 题解
发表于
分类于
题解
本文迁移自洛谷原文。
题目大意：
给你一棵有 $n$ ($1 \le n \le 10^5$) 个节点的树，其中一些节点是特殊节点，相邻两个点的距离为 $1$。
有 $q$ ($1 \le q \le 10^5$) 次询问，每次给你两个点 $u,v$，你需要求出从 $u$ 走到 $v$ 的最小时间。
一开始，你的速度是每 $2$ 个时间单位走 $1$ 个距离单位。假设在某一时刻你到了一个特殊节点，那么你的速度就会变为 $1$ 个时间单位走 $1$ 个距离单位，这次询问内有效。
题解：
显然有两种过程：
从 $u$ 直接走到 $v$，花费时间 $2\times dist(u,v)$。
从 $u$ 走到 $u,v$ 链上某个节点 $x$，再从 $x$ 走到某个特殊节点 $y$，再从 $y$ 返回 $x$，最后从 $x$ 走到 $v$。
第一种情况平凡，我们考虑第二种。
有以下结论：
第二种情况下的答案 $ans=dist(u,v)+dist(u,x)+3\times dist(x,y)$
$y$ 一定是到 $x$ 距离最近的特殊节点。显然，因为 $y$ 只和 $3\times dist(x,y)$ 一项有关。
所以我们可以跑一遍 bfs 处理出到所有节点最近的特殊节点的距离 $\times 3$ （记为 $C(x)$） 是多少。
然后在 $u,v$ 已知的情况下，$dist(u,v)$ 容易算出，我们只需要求出 $dist(u,x)+3\times C(x)$ 的最小值就可以了。
$dist(u,x)$ 比较难算，但我们可以用一个分类讨论的套路把它拆开来：
令 $l$ 为 $u,v$ 的 LCA，进行分类：
- $x$ 在 $u \rightarrow l$ 这条链上
此时 $dist(u,x)=deep_u-deep_x$（$deep_x$ 为节点 $x$ 的深度），所以在 $u$ 给定的情况下，我们需要求得的是 $C(x)-deep_x$ 的最小值，可以直接树剖或者倍增维护。
- $x$ 在 $l\rightarrow v$ 这条链上
同理，不过 $dist(u,x)$ 变为 $deep_u+deep_x-2\times deep_l$，维护 $C(x)+deep_x$ 的最小值即可。
Code:
1 | #include<bits/stdc++.h> |