主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
2025 XYD Summer Camp 7.28 智灵班分班考 Day2
最后更新于 2025-07-31 14:22:05
作者
under_the_time
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
## 时间线 - 13\:38 开题!看 T1,脑残以为只要对左端点做最长上升子段,成功浪费 10min。 - T1 秒题失败使我心态下降,先看了一遍题,wc 怎么 T2 在第一次考试神秘换题的过程中出现过???T3 看起来很乱搞,T4 神秘期望 dp 决定直接弃了。 - 回来看 T1,想到了一个超级做法:维护一个线段树表示当前所有温度能达到的最长维持长度,每次做**区间加 $1$、区间求 $\max$、单点修改、区间推平**!写写写,发现跑大样例常数起飞。 - 打算放着先去写 T2,推了推变成保证区间内每个数出现不超过 $2$ 次的情况下数合法区间个数,直接上异或哈希,每个数随机分配一个权值,问题变成求某个前缀异或和的出现次数。 - 然后经历了以下几次重构: - 使用 map 和 unsigned long long 范围的随机权值,跑 $5$ 次保证正确性,大样例需要整整 8s! - 把 map 改成 umap,复杂度线性但是常数爆炸! - 使用了快读,但是好像没什么用! - 把 umap 改成 01Trie 存储,复杂度 $O(64n)$ 但是小常,大样例却只够跑 $2$ 次! - 把范围从 unsigned long long 改成 unsigned int,收效甚微! - 把 01Trie 改成了 vector + 二分查找重标号,用数组存储出现次数,效果拔群,大样例足够稳定跑 $3$ 次! - 返回 T1 想想有没有常数更优的做法,发现合法区间的左端点关于右端点是单调的,某个区间合法当且仅当前面选中的区间的左端点的 max 不超过这个区间的右端点,直接 rmq 加双指针做到 $O(n\log n)+O(n)$,大样例稳定 1s 左右跑完,就放着不看了。 - 开始大战 T3!首先 $n\le 10$ 可以状压 + bfs 卑微的获得 20pts,然后把 bfs 中间过程输出了一下,试图盯真找规律。 - 找规律失败!但这道题感觉乱搞能拿很多分,因为是单组询问,所以尝试写若干个假做法然后拼起来取个 min。 - 结果是没有任何一个假做法能够 reach 到大样例…… - 欸?大样例?注意到 T4 的大样例有一个后缀 9,我就赌是出题人拿了一组数据当大样例,自信输出! - 最后就把 T1,T2 都拍了一下~~(上次挂分挂爽了)~~,竟然发现 T2 没判整个前缀都合法的情况,感觉赢麻了。 ## 得分 事实证明我赌对了!  ## 题解 ### T1 > 给定 $n$ 个区间 $[l_i,r_i]$,求一段最长的 $[L,R]$ 满足存在一种从所有编号在 $[L,R]$ 中的区间中挑一个数的方案,使得选出的数单调不降。 > > $1\le n\le 10^6$,$1\le l_i\le r_i\le 10^5$。 考虑合法的 $[L,R]$ 显然在 $R$ 增加时 $L$ 单调不降,而每个区间选的数肯定越小越好,因此每个区间选的数就是前面的区间的左端点的最大值,拿 st 表维护一下区间 $l_i$ 的最大值,双指针维护 $L,R$ 即可。时间复杂度 $O(n)$,貌似把 st 表换成单调队列就能变成线性。 ### T2 > 给定一个长度为 $n$ 的序列 $a$,值域在 $[1,n]$,求满足区间中出现的数都恰好出现 $2$ 次的区间个数。 > > $n\le 10^6$。 考虑固定区间右端点为 $r$,记 $a_i$ 上一次的出现位置在 $lst_{a_i}$,上上次在 $llst_{a_i}$;那么显然合法的区间左端点只能在 $[llst_{a_i}+1,lst_{a_i}]$ 中。我们可以动态的维护合法区间左端点的最远的取值,那么现在就相当于在保证每个数最多出现 $2$ 次的情况下,满足题意得区间个数。考虑 xor hash,给每个值分配一个随机权并求出前缀异或和 $s_i$,那么现在一个区间 $[l,r]$ 合法当且仅当 $s_r\oplus s_{l-1}=0$,即 $s_r=s_{l-1}$,也就是数某个特定区间中权值等于某个数的个数。这个特定区间可以双指针,存出现个数可以直接 umap,也可以重标号后在数组上操作。时间复杂度线性或带一个 $\log$。 ### T3 > 给定长度为 $n$ 值域在 $[0,3]$ 中的数组 $a$ 和 $b$,每次你可以指定一个区间 $[l,r]$,然后 $\forall i\in[l,r]$,令 $a_i\gets(a_i+1)\bmod 4$,求把 $a$ 变成 $b$ 所需的最小操作数。 > > $n\le 10^5$。 首先问题可以直接等价成给定一个数组 $a$,操作是区间模 $4$ 意义下减一,求把 $a$ 变成全 $0$ 的最小操作数。不妨考察 $a$ 的差分数组 $d$(假设 $a_0=0$),那么一个操作相当于:总是选定一个数 $x$ 把 $d_x$ 减 $1$,可以再选一个 $y$ 满足 $y>x$,然后把 $d_y$ 加一,目标是让 $d$ 全变成 $0$。如果不考虑取模那么有一个结论:答案就是 $\sum_{i=1}^n\max(0,d_i)$,现在有了取模相当于我们可以选一对 $i<j$,使 $d_i\gets d_i+4,d_j\gets d_j-4$。注意到 $d_i\in[-3,3]$,分类讨论: - 如果 $d_j=3$,那么选择 $j$ 令 $d_j\gets d_j-4$ 可以使答案减少 $3$;那么对于 $d_i\in\set{-3,-2}$,令 $d_i\gets d_i+4$ 就可以使答案总共减少 $2$ 或者 $1$,贪心地优先选择 $d_i=-3$ 的进行操作; - 如果 $d_j=2$,那么选择 $j$ 可以使答案减少 $2$,此时只有选择 $d_i=-3$ 的 $i$ 进行操作可以使答案减少 $1$; - 如果 $d_j\le 1$ 那怎么操作都没用,直接不管了。 贪心地从前往后进行操作即可。时间复杂度 $O(n)$。 不如 luqyou 的乱搞! ### T4 ~~疑似很难,摆了~~ To be continued.
正在渲染内容...
点赞
0
收藏
0