|
$n\le 100$对于询问 $[l,r]$，暴力枚举 $l',r'$，然后暴力计算，时间复杂度为 $O(mn^3)$。 或者简单优化一下到 $O(mn^2)$。期望得分 $10$。 $n\le 1000$先预处理出所有区间的权值 $v_{l,r}$。 然后可以用各种做法求出所有区间的子区间的权值 $ans_{l,r}$。 时间复杂度为 $O(n^2+m)$。期望得分 $30$。 特殊性质按位与，按位或，$\gcd$ 三种运算有一个很厉害的性质，以 $\gcd$ 为例：对于一个数 $x$，不断令 $x\gets \gcd(x,v)$，则 $x$ 值发生变化的次数为 $\log V$ 次。 具体的原因可以均摊分析，考虑 $x$ 的质因子可重集合，显然其大小不超过 $\log V$，每次取 $\gcd$，这个集合要么不变，要么大小至少减一，只有集合大小改变才会影响 $x$ 的值，所以 $x$ 值发生变化的次数为 $\log V$ 次。 按位与和按位或也是如此，每一位上只会从一种值变成另一种值，所以变化次数也不超过 $\log V$。 数据随机后，若一个区间长度超过 $100$，答案就极有可能变成 $0$ 了。 然后乱搞一下应该可以得到 $40$ 的分数。 $n\le 10^5$考虑离线扫描线。 有这样一种经典扫描方式，令 $r:1\to n$，假设当前扫到 $r$，我们让 $\forall l \in [1,r]$ 的位置 $v_l$ 加上区间 $[l,r]$ 的权值。 这样若对于询问 $[L,R]$，若 $r$ 扫到了 $R$，则查询 $v_{L\sim R}$ 的区间和即可。这是非常经典的增量贡献求答案的方法。 回到本题，使用上面所述的扫描线算法，因为上述特殊性质的存在，假设当前扫到 $r$，设 $A_i$ 为 $i\sim r$ 的区间按位与的和，$B_i,C_i$ 同理，则这三个数组分别可以划分为 $\log V$ 段，每一段内值相同。 这样我们得到 $3\log V$ 断点，设 $D_i=A_iB_iC_i$。则 $D_i$ 也被划分成 $\log V$ 段，每一段内部值相同。 那么我们令 $\forall i\in [1,r],v_i\gets v_i+D_i$，这样更新过程可以转化成对 $v$ 数组的 $\log V$ 段区间加法。 查询答案即为查询区间和，找断点可以二分加线段树，总而言之时间复杂度为 $O(n\log^2 n+m\log n)$，期望得分 $80$。 如果你用下文所述找断点的方法，用树状数组常数小的话也可以得到 $100$。 $n\le 5\times 10^5,m\le 5\times 10^6$考虑正解，静态询问，且 $q\le 5\times 10^6$，应该要做到 $O(1)$ 回答询问，考虑离线扫描线。 有这样一种不经典的扫描线方法：维护一个指针 $r$ 从 $1$ 扫到 $n$，每扫到一个位置就回答右端点在 $r$ 的询问的答案。考虑此时在第 $l$ 个位置上维护 $w_{r,l}$ 表示 $[l,r]$ 所有子区间的价值之和。 不难发现我们把题目又读了一遍。考虑当 $r-1\to r$ 时，$w_{r,l}$ 相比于 $w_{r-1,l}$ 的答案应该有怎样的变化。 注意 $w_{r,l}$ 的理解，可以理解成当指针扫到 $r$ 时的版本时，第 $l$ 个位置的值，并不需要真正维护二维数组，只需要滚动维护第二维即可，下文同样有类似的表达方法。 令 $A_{r,i}$ 表示扫到 $r$ 时 $i\sim r$ 的所有数按位与之和，$B_{r,i},C_{r,i}$ 同理，则需要更新： $$w_{r,i}\gets w_{r-1,i}+\sum_{j=i}^rA_{r,j}B_{r,j}C_{r,j}$$ 先考虑如何维护 $A_{r,i},B_{r,i},C_{r,i}$。不难发现，当 $r\to r+1$ 时，发生更改的 $A_{r,i},B_{r,i},C_{r,i}$ 都是 $1\sim r$ 的一段后缀。 对于 $x<y$，若 $C_{r+1,y}=\gcd(C_{r,y},c_{r+1})=C_{r,y}$，则显然有 $C_{r+1,x}=\gcd(C_{r,x},c_{r+1})=C_{r,x}$，因为 $C_{r,x},C_{r,y}$ 和 $C_{r,y},c_{r+1}$ 在集合上都是子集关系。 当 $r\to r+1$考虑这样一种更新方式，从 $r$ 出发，用 $r+1$ 的值倒着更新 $r-1,r-2,\dots$ 的位置，直到 $A_{r,i},B_{r,i},C_{r,i}$ 都不发生改变，则更新完成。 分析复杂度，以 $A_{r,i}$ 为例，这个位置对最终复杂度有贡献当且仅当某次更新时 $A_{r,i}$ 发生了改变，根据最上面的分析，这种改变次数是不超过 $\log V$ 的，所以更新的总的复杂度为 $O(n\log V)$。 此时,当 $r-1\to r$ 时，维护一个前缀和 $s_{r,i}$： $$s_{r,i}=\sum_{j=1}^nA_{r,j}B_{r,j}C_{r,j}$$ 则更新可以表示为： $$w_{r,l}\gets w_{r-1,l}+s_{r,r}-s_{r,l-1}$$ 令 $v_i=s_{i,i}$，则有： $$w_{r,l}=\sum_{i=l}^rv_i-\sum_{i=l}^rs_{i,l-1}$$ 前面的部分显然可以单独维护，后边的部分则是查询 $s$ 所有版本在位置 $i$ 上的历史和。 因为我们每次修改都是暴力修改 $s$，所以问题变成： 1. 单点修改某个位置的值 $s_i$。 2. 单点查询某个位置的历史和 这个东西已经非常简洁了，考虑第 $i$ 个位置的历史和 $hs_i$，$s_i$ 上一次修改的时间 $lst_i$，若在时刻 $t$ 修改 $s_i$ 为 $val$，则： $$hs_i\gets hs_i+(t-lst_i)s_i,s_i\gets val,lst_i\gets t$$ 则在 $t$ 时刻查询位置 $i$ 的历史和为： $$hs_i+(t-lst_i+1)s_i$$ 然后我们惊奇的发现这个问题就解决了。 时间复杂度为 $O(n\log n+m)$，期望得分 $100$。 代码实现首先是 $\gcd$，可以用 C++ 自带的 `__gcd` 函数，也可以手写二进制优化更相减损术的 $\gcd$，两种写法各有优劣。 然后是快读快输，这个题已经卡常到普通的 fread 和 fwrite 已经无法满足了，建议找个又臭又长的封装版快读快输使用。 然后将询问储存：对于储存询问，不建议将左右端点分开两个数组储存，建议直接用结构体或者 pair 来储存询问左右端点（我也不知道为什么啊，可能是寻址更快吧）。 然后是将离线：不要用 vector，可以用链表在端点处挂上询问。不要用 sort，可以用计数排序。 luogu 的原题需要严厉的卡常，这里不知道是否需要。
题目4251 我能在摸鱼被发现的情况下躲避教练的视奸吗
AAAAAAAAAA
 4
评论
2026-02-07 16:48:45
|
|
|
Pro4250 时空跳跃 题解$n\le 10$暴搜，时间复杂度 $O(n!m)$，期望得分 $20$。 $n\le 300$令 $p_u$ 表示 $u$ 的父亲节点。根据 $l_i\le r_i<i$，不难有 $p_u<u$。 设 $u<v$，则 $p_v$ 一定在 $(u,v)$ 的路径上。 考虑证明：若 $p_v$ 不在 $(u,v)$ 路径上，当且仅当 $v$ 时 $u$ 的祖先，根据 $p_u<u$ 可以得到 $u$ 的祖先编号小于 $u$，即 $u>v$，与 $u<v$ 矛盾，故原命题得证。 以上完成本题最为关键的结论证明。 若对于每一次加操作，都暴力完成，复杂度显然是指数级。 不过对于每一种加操作，都可以用 $(u,v)$ 表示（下文均假设 $u<v$）且 $(u,v)$ 的加操作可以转化为 $(u,p_v)$ 的加操作。 若对链 $(a,b)$ 的加操作对链 $(c,d)$ 的加操作有转化，必须满足 $b<d$。且对于 $a\ne b$ 的情况，对链 $(a,c)$ 的加操作和链 $(b,c)$ 的加操作之间不会互相转化。 也就是说，我们以第二维按照 $v$ 划分所有链，可以分成若干层，当前层只会影响这层之前的层，且层内部之间不会影响。 可以设计出一个递推状物，设 $g_{u,v}$ 表示所有操作对 $(u,v)$ 这条链加上的期望值，则有：
$${g_{u,p_v}\gets g_{u,p_v}+\frac{g_{u,v}}{r_v-l_v+1}}, u<p_u $$ $${g_{p_{v},u} \gets g_{u,p_v}+\frac{g_{u,v}}{r_v-l_v+1}}, u>p_u$$
注意到编码过程中，为了方便讨论，我们始终只对 $u<v$ 的状态操作，因此若出现 $p_v<u$ 的情况，要操作 $g_{p_v,u}$ 而不是 $g_{u,p_v}$。 其实是简单排列组合原理，每一层内部的转移因为无所谓，所以第一维的枚举顺序可以随便来。 递推完所有的 $g_{u,v}$ 后，考虑计算点 $u$ 的答案，根据结论，只要 $v<u$，那么 $(v,u)$ 的路径一定包含 $(p_u,u)$ 这条链，且对于任意 $(a,u),(b,u)$ 之间互不影响，说明 $(a,u),(b,u)$ 代表的加操作独立，可以直接加起来。 因此答案为 $\sum_{v<u}g_{v,u}$。直接做需要枚举每个点的父亲，时间复杂度 $O(n^3+m)$。期望得分 $60$。 $n\le 2000$考虑优化这个过程，把 $g$ 数组当成一个二维平面，代码中 $k>i$ 的部分实际上是对横着的一段加上了一个数。$k<i$ 的部分是对竖着的一段加上了一个数。 可以用二维差分优化，递推的过程中求差分的前缀和数组，因为要求前缀和，所以第一维的枚举顺序也需要确定。 时间复杂度 $O(n^2+m)$，期望得分 $100$。
题目4250 时空跳跃
AAAAAAAAAA
3
评论
2026-02-07 15:57:29
|
|
|
脑电波题，对上了就很简单。 $n\le 8$搜索看看吧，说不定常数小就有分了，时间复杂度 $O(?)$，期望得分 $0\sim 30$。 特殊性质 A结论：答案为 $n$，手模不难证明。 特殊性质 B结论：答案为 $1$，一望而知。 $n\le 2000$我们考虑每走过一轮周期位置的偏移。如果走过一轮后仍停留在原地，则答案就是将原树 dfs 一遍的指令数。 否则，我们每走过一个周期，一定会向下走，且会向下走相同的偏移量。假设当前位置是 $x$，走过一个周期后到了 $y$，则我们的指令必须包括 $x$ 的子树除去 $y$ 的子树的这个连通块。 可以枚举从根节点走一个周期偏移多少，然后从根节点开始，初始令 $x=1$，$y$ 为 $x$ 走制定偏移量的节点，将 $x$ 的子树除去 $y$ 的子树的这个连通块提出来，然后令 $x\gets y$ 重复这个过程，直到 $y$ 在给定的二叉树之外，此时提出的连通块就是 $x$ 的子树。 将提出的所有连通块并在一起，则我们的指令需要 dfs 这个连通块，剩下的随便做即可，复杂度 $O(n^2)$。
题目4210 Sayaku，移动
WAAAWAWWAW
2
评论
2026-02-07 15:56:05
|
|
|
特殊性质模拟即可，时间复杂度 $O(\sum |s_i|)$，期望得分 $10$。 $n\le 12$考虑状态压缩 dp，设 $f_{i,S}$ 表示将集合 $S$ 中的所有串插入到一个深度为 $i$ 的节点的方案数。 使用枚举子集的方式分裂 $S$ 到 $i+1$ 去转移，时间复杂度 $O(3^n|s_i|)$。貌似可以用高维前缀和优化到 $O(2^n|s_i|n)$。期望得分 $50$。 $n\le 20$正解和特殊性质关系不大。个人觉得正解要比特殊性质好写。 不难发现，若确定了每个字符串 $s_i$，则字典树的节点个数为： $$\sum_{S}(-1)^{|S|-1}\text{LCP}(S)$$ 其中 $\text{LCP}(S)$ 表示集合 $S$ 中所有字符串的最长公共前缀。 好的，若 $s_i$ 未确定，如何计算 $\text{LCP}(S)$其实非常简单？枚举最长公共前缀的长度 $i$，只需要保障前 $i$ 位相同，第 $i+1$ 位不相同即可，时间复杂度为 $O(2^n|s_i|)$，期望得分 $100$。
题目4299 学姐的下午茶
AAAAAAAAAA
3
评论
2026-02-07 15:38:59
|
|
|
Pro4184 轻重数字 题解[CCO 2024] Heavy Light Decomposition前置知识分块，DP 简要题意定义“好的数组”为一个数组内交替出现“轻元素”和“重元素”，轻元素即其在这个数组内是唯一的，重元素即其在数组内出现多次。 有 $n$ 个正整数 $a_i$，求其有多少种划分方案能使划分后的子数组均为好的数组。 分析样例我们首先要搞懂一个东西，就是划分后好的数组，是指这个子数组是好的，在这个子数组内的轻重元素与原数组并没有关系，每个子数组是互相独立的。 对于样例一，其划分方案如下： - $[1], [2], [3], [2], [3]$ - $[1], [2, 3, 2], [3]$ - $[1], [2], [3, 2, 3]$ - $[1, 2, 3, 2], [3]$ 对于样例二，其划分方案如下： - $[1], [2], [1], [3], [1]$ - $[1, 2, 1], [3], [1]$ - $[1, 2, 1, 3], [1]$ - $[1], [2], [1, 3, 1]$ - $[1], [2, 1, 3, 1]$ - $[1, 2, 1, 3, 1]$ 不明白的建议手推一下。 思路分析考虑转移我们定义 $dp[i]$ 为前 $i$ 个元素的合法划分的方案数。 那么，转移方程很显然：$dp[i] = \sum dp[j]$，其中 $j < i$ 且 子数组 $[j + 1, i]$ 是好数组。 实际上含义就是在 $j$ 处划分，新增一个子数组 $[j + 1, i]$，方案累加前 $j$ 个元素的方案数。 考虑好数组的约束如果 $[j + 1, i]$ 为好的数组，那么需要满足： 1. 类型交替：即数组内的元素轻重交替。 2. 奇偶性约束：如果重元素第一次出现在奇数位，那么奇数位全是重元素，反之。 因此我们如果直接枚举所有的 $j$ 去验证 $[j + 1, i]$ 是否为好数组，时间复杂度为 $O(n ^ 2)$。
考虑优化对于当前的位置 $i$，我们设其元素大小为 $v$，用 $odd[v]$ 和 $even[v]$ 来记录 $v$ 在奇数和偶数位最近的出现位置，这样的话可以确定 $j$ 的下界。 为了保证子数组 $[j + 1, i]$ 满足类型交替，需要避免 $v$ 元素在数组内出现奇偶性冲突，那么若 $j + 1 < \min(odd[v], even[v])$ 的话，则会使其冲突。 因此我们使 $minL$ 取所有元素 $min(odd[v], even[v]) + 1$ 的最大值，因此 $j > minL - 1$。 然后是最重要的分块，我们将原数组分块，每个块维护两个核心内容，$sum[k][b]$ 表示 $b$ 块满足在奇偶性 $k$ 下的合法的 $dp[j]$ 之和，$kpos[k][b]$ 是在 $k$ 的奇偶性下块 $b$ 是否满足。另外，为了维护分块时的单个元素， 我们维护 $pos[k][i]$ 是单个位置的 $i$ 是否满足奇偶性 $k$。 当我们查询 $[l, r]$ 内符合条件的 $dp[j]$ 之和时，对于整块，只需要判断 $kpos$ 是否有效，然后累加 $sum$ 即可，对于单个的块边缘的元素，则需要满足 $kpos$ 和 $pos$，有效则累加 $dp[j]$。 在区间更新时，只需要标记区间有效和无效，在完整的块上更新 $kpos$，零散的元素更新 $pos$ 和 $sum$。 时间复杂度分块的单次查询和更新的时间复杂度为 $O(\sqrt{n})$，时间复杂度为 $O(n \sqrt n)$。 简单卡常即可，最慢的点才两秒出头，对于四秒的时间限制完全够用。 代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<unordered_map>
#include<cstring>
using namespace std;
const int MOD = 1e6 + 3;
const int MAXN = 5 * 1e5 + 5;
int kpos[2][MAXN], sum[2][MAXN], pos[2][MAXN];
int L[MAXN], R[MAXN], id[MAXN];
int dp[MAXN], even[MAXN], odd[MAXN];
int a[MAXN], pre[MAXN];
pair<int, int> lst[MAXN];
int n, tot = 0, B;
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch>='0' && ch<='9')
x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
inline void update(int k, int l, int r, int x){
if(l > r) return;
int kl = id[l], kr = id[r];
if(kl != kr){
for(int i = kl + 1;i < kr;++ i){
kpos[k][i] += x;
}
if(l == L[kl]){
kpos[k][kl] += x;
}
else{
for(int i = l;i <= R[kl];++ i){
if(pos[k][i]){
sum[k][kl] = (sum[k][kl] + dp[i - 1]) % MOD;
}
pos[k][i] += x;
if(pos[k][i]){
sum[k][kl] = (sum[k][kl] - dp[i - 1] + MOD) % MOD;
}
}
}
if(r == R[kr]){
kpos[k][kr] += x;
}
else{
for(int i = L[kr];i <= r;++ i){
if(pos[k][i]){
sum[k][kr] = (sum[k][kr] + dp[i - 1]) % MOD;
}
pos[k][i] += x;
if(pos[k][i]){
sum[k][kr] = (sum[k][kr] - dp[i - 1] + MOD) % MOD;
}
}
}
}
else{
if(l == L[kl] && r == R[kl]){
kpos[k][kl] += x;
}
else {
for(int i = l;i <= r;++ i){
if(pos[k][i]){
sum[k][kl] = (sum[k][kl] + dp[i - 1]) % MOD;
}
pos[k][i] += x;
if(pos[k][i]){
sum[k][kl] = (sum[k][kl] - dp[i - 1] + MOD) % MOD;
}
}
}
}
}
inline int query(int k, int l, int r){
if(l > r) return 0;
int res = 0;
int kl = id[l], kr = id[r];
if(kl != kr){
for(int i = kl + 1;i < kr;++ i){
if(!kpos[k][i]){
res = (res + sum[k][i]) % MOD;
}
}
if(l == L[kl]){
if(!kpos[k][kl]){
res = (res + sum[k][kl]) % MOD;
}
}
else{
for(int i = l; i <= R[kl]; i++){
if(!pos[k][i] && !kpos[k][kl]){
res = (res + dp[i - 1]) % MOD;
}
}
}
if(r == R[kr]){
if(!kpos[k][kr]){
res = (res + sum[k][kr]) % MOD;
}
}
else{
for(int i = L[kr];i <= r;++ i){
if (!pos[k][i] && !kpos[k][kr]){
res = (res + dp[i - 1]) % MOD;
}
}
}
}
else{
if(l == L[kl] && r == R[kl]){
if(!kpos[k][kl]){
res = (res + sum[k][kl]) % MOD;
}
}
else{
for(int i = l;i <= r;++ i){
if (!pos[k][i] && !kpos[k][kl]){
res = (res + dp[i - 1]) % MOD;
}
}
}
}
return res;
}
int main(){
freopen("digit.in", "r", stdin);
freopen("digit.out", "w", stdout);
n = read();
B = 300;
for(int i = 1; i <= n; i += B){
L[++ tot] = i;
R[tot] = min(n, i + B - 1);
for(int j = i;j <= R[tot];++ j){
id[j] = tot;
}
}
// for(int i = 1;i <= n;++ i){
// cout << i << ' ' << id[i] << '\n;'
// }
dp[0] = 1;
for(int i = 1;i <= n;++ i) a[i] = read();
int leven = 0, lodd = 0, minL = 1;
memset(lst, -1, sizeof(lst));
for(int i = 1;i <= n;++ i){
sum[0][id[i]] = (sum[0][id[i]] + dp[i - 1]) % MOD;
sum[1][id[i]] = (sum[1][id[i]] + dp[i - 1]) % MOD;
dp[i] = dp[i - 1];
int v = a[i];
if(lst[v].second != -1){
update(lst[v].second & 1, lst[v].first + 1, lst[v].second, -1);
}
if(i & 1){
lodd = max(lodd, odd[v]);
odd[v] = i;
}
else{
leven = max(leven, even[v]);
even[v] = i;
}
lst[v] = {pre[v], i};
update(lst[v].second & 1, lst[v].first + 1, lst[v].second, 1);
pre[v] = i;
minL = max(minL, min(odd[v], even[v]) + 1);
if(leven < lodd){
dp[i] = (dp[i] + query(1, max(minL, leven + 1), i - 1)) % MOD;
}
else if (lodd < leven){
dp[i] = (dp[i] + query(0, max(minL, lodd + 1), i - 1)) % MOD;
}
}
printf("%d", dp[n] % MOD);
return 0;
}
题目4184 轻重数字
8
2 条 评论
2026-02-04 20:54:13
|
|
|
Pro3996 勇者 题解更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19349977
思路由于题目的数据范围，我们可以得知，大概是个 $n ^ 3$ 的玩意。 但是我们需要仔细想想怎么计数？ 首先，这个玩意和什么有关? 第一肯定是步数，第二是点是否走过，第三是这个点和为我们要的强连通图的关系。 然后我们考虑最难的问题，就是这个强连通图怎么判断，怎么累加答案？我们走到一个点的时候怎么判断其是否能与原来的形成一个强连通呢？还是说其目前自己和其他点成强连通，需要后续的操作去整。 不难发现，其实一个点，其强连通关系只有两种，第一种就是和起点在一个强连通里面，第二种，就是不在起点的强连通里面。 我们定义 $f_{i, j, k}$ 表示目前已经走了 $i$ 步，已经访问了 $j$ 个点，与起点 $1$ 形成的强连通的大小为 $k$。（以下所说的形成强连通均是与 $1$ 形成） 考虑转移。 首先走到点，第一种情况，是没有走过，于是我们有： $f_{i + 1, j + 1, k} \to f_{i + 1,j + 1, k} + f_{i, j, k} \times (n - j)$ 第二种，是走过，但是没有形成强连通的点： $f_{i + 1, j, k} \to f_{i + 1, j, k} + f_{i, j, k} \times (j - k)$ 第三种是，走过，且已经形成了强连通： $f_{i + 1, j, k} \to f_{i + 1, j, k} + f_{i, j, k} \times k$ 于是我们的答案就在 $f_{m, n, n}$。
代码
#include<iostream>
using namespace std;
#define int long long
const int MAXN = 305;
const int MOD = 1e9 + 7;
//f[i][j][k] 走了 i 步，访问了 j 个点，以 1 为根的 scc 大小为 k
int f[MAXN][MAXN][MAXN];
int n, m;
signed main(){
freopen("rotk.in", "r", stdin);
freopen("rotk.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
f[0][1][1] = 1;
for(int i = 0;i <= m - 1;i ++){
for(int j = 1;j <= n;j ++){
for(int k = 1;k <= n;k ++){
if(!f[i][j][k]) continue;
//没走的
f[i + 1][j + 1][k] += f[i][j][k] * (n - j) % MOD;
f[i + 1][j + 1][k] %= MOD;
//走过，但不在 1 的scc
f[i + 1][j][k] += f[i][j][k] * (j - k) % MOD;
f[i + 1][j][k] %= MOD;
//走过，在 1 的 scc
f[i + 1][j][j] += f[i][j][k] * k % MOD;
f[i + 1][j][j] %= MOD;
}
}
}
cout << f[m][n][n] % MOD << '\n';
return 0;
}
题目3996 勇者
AAAAAAAAAA
6
评论
2026-02-04 20:51:46
|