上午感觉不错,下午改不出题,晚上破防。
简略思路:
T1
本质应该是 DP 维护一次函数。
不会正解。晚上看了好久、好多篇题解还是不会。有点静不下心来看比较长的题解。
放点别人的题解,有空再来研究:
https://www.cnblogs.com/flywatre/p/17236732.html
https://blog.51cto.com/u_15300835/3064939
https://www.cnblogs.com/C202044zxy/p/15082636.html
https://www.luogu.com.cn/article/u2zqliav
T2
\(2 \times n\) 很特殊,发现结论,即一直往右走,撞到障碍就往上下走,然后接着往右走,这样贪心应该是对的。
然后有各种做法:
-
yzj 学长的线性做法:考虑把障碍分段。首位两段可能不连续,预处理后直接走。中间段时连续的,直接统计。好像有些特判。
-
另一位学长的倍增做法(好像还有一位学长也用的倍增):按步数倍增。最后要看是不是在同一行,答案可能要加 1。我不清楚细节怎么写,另有 jsh 所言要特判三种情况:u、v 重合;u、v 在同一列;u、v 不连通(是不是这三种我忘了,这三种是我凭回忆和自己的想法写的,可能不对,可能不是 jsh 所说的)(实际上她说的是不是三种我都不太确定,应该是吧)(在某些方面记忆力不好加上一天接触的信息不少是这样的 \kel)。
-
题解的线段树做法:都是用 DS 来维护,考虑维护的段的四个端点间的最短路([四条,同一列的之间不维护](?))。另一位学长有一个比较像的分块做法,听说它们本质是相同的。
然后我还一种都没写。
T3
背包:
- DP。
- 生成函数。(我当时想的是拉格朗日插值,然后发现好像不行,因为最后的[“多项式”](??)次数太高了)
- 暴力状压枚举。
\(n=20\) 直接状压枚举,\(n=40\) 就想到折半状压。
先想的是动态开点线段树。然后要写的时候发现直接数组存,upper_bound 二分即可。
T4
看到出现次数什么的想到 xor hashing。
题解的思路:
每种颜色都出现奇数次不好处理。考虑转换成每种都出现偶数次,这样 xor 起来为 0 就满足限制了。转换的方式是把每种颜色都删掉一次在询问区间中的出现。
怎么删?把每个颜色区间(输入给的区间)的左端点都不考虑,相当于把左端点右移一位;然后再把每个询问区间(我们想判断它是否符合限制的区间)的左端点右移一位。发现这样应该是可行的。感觉这是个很妙的转化。
然后算前缀 xor 和,用个 unordered_map 来辅助统计。[unordered_map 应该不会被卡,因为 hash 值是随机的。](??)
另外要注意减去一种颜色也没有的情况的贡献。这是特殊的。
我的思路:
对于一个询问区间,统计两个东西:
- 其中每 种 颜色的 hash 值的 xor 和。
- 其中每 个 颜色所属种类的 hash 值的 xor 和。(这样描述不太清楚,其实就是 1 是每种颜色只统计一次,2 是每种颜色出现了多少次就统计多少次)
当这两个东西相等的时候这个区间就可行(此时先不管什么颜色都没有的区间,即先认为这种区间也是可行的)。那么这两个东西 xor 起来等于 \(0\) 就说明这个区间可行。
于是用[扫描线](???)。枚举询问区间右端点,查可行区间的长度之和。用 01-Trie 维护。
但是相比正解(指题解做法)不太好写。我今天考场上写挂了。
2024.8.21
标签:xor,21,2024.8,题解,学长,端点,区间,颜色,集训 From: https://www.cnblogs.com/huangkxQwQ/p/18372723