首页 > 其他分享 >2024.8.21 总结(集训 考试)

2024.8.21 总结(集训 考试)

时间:2024-08-21 23:04:53浏览次数:8  
标签:xor 21 2024.8 题解 学长 端点 区间 颜色 集训

上午感觉不错,下午改不出题,晚上破防。

简略思路:

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

背包:

  1. DP。
  2. 生成函数。(我当时想的是拉格朗日插值,然后发现好像不行,因为最后的[“多项式”](??)次数太高了)
  3. 暴力状压枚举。

\(n=20\) 直接状压枚举,\(n=40\) 就想到折半状压。

先想的是动态开点线段树。然后要写的时候发现直接数组存,upper_bound 二分即可。

T4

看到出现次数什么的想到 xor hashing。


题解的思路:

每种颜色都出现奇数次不好处理。考虑转换成每种都出现偶数次,这样 xor 起来为 0 就满足限制了。转换的方式是把每种颜色都删掉一次在询问区间中的出现。

怎么删?把每个颜色区间(输入给的区间)的左端点都不考虑,相当于把左端点右移一位;然后再把每个询问区间(我们想判断它是否符合限制的区间)的左端点右移一位。发现这样应该是可行的。感觉这是个很妙的转化。

然后算前缀 xor 和,用个 unordered_map 来辅助统计。[unordered_map 应该不会被卡,因为 hash 值是随机的。](??)

另外要注意减去一种颜色也没有的情况的贡献。这是特殊的。


我的思路:

对于一个询问区间,统计两个东西:

  1. 其中每 颜色的 hash 值的 xor 和。
  2. 其中每 颜色所属种类的 hash 值的 xor 和。(这样描述不太清楚,其实就是 1 是每种颜色只统计一次,2 是每种颜色出现了多少次就统计多少次)

当这两个东西相等的时候这个区间就可行(此时先不管什么颜色都没有的区间,即先认为这种区间也是可行的)。那么这两个东西 xor 起来等于 \(0\) 就说明这个区间可行。

于是用[扫描线](???)。枚举询问区间右端点,查可行区间的长度之和。用 01-Trie 维护。

但是相比正解(指题解做法)不太好写。我今天考场上写挂了。


2024.8.21

标签:xor,21,2024.8,题解,学长,端点,区间,颜色,集训
From: https://www.cnblogs.com/huangkxQwQ/p/18372723

相关文章

  • 2024.8.21
    DATE#:20240821ITEM#:DOCWEEK#:WEDNESDAYDAIL#:捌月拾捌TAGS <BGM="琴师--要不要买菜"><theme=oi-contest><[NULL]><[空]><[空]>```此情可待成追忆,只是当时已惘然--《锦瑟》李商隐```T1试卷答案(exam)时间限制:1s 内存限制:512......
  • 2024/8/21 模拟赛
    T1试卷答案试卷由若干道不定项选择题构成,只有ABCD四个选项。每道题的答案是一个按字典序排列的非空字符串。例如,A、CD是合法的答案,而BB、DC不是合法的答案。一张合法的试卷由k道题目组成。给定一个长度为\(n\)的由ABCD组成的字符串,进行\(Q\)次操作。支持区间加(将区间内......
  • 『模拟赛』暑假集训CSP提高模拟26
    Rank打得一般,倒数第二场了。。A.博弈直接搬了牛客的一套题。一眼没思路,模了一会放弃直接去打T2了,后来把\(\mathcal{O(n^2)}\)暴力打了拿30pts。正解用到了异或哈希。首先确定合法的数量即为总对数\(\frac{n(n-1)}{2}\)减去不合法的数量,而比较显然的,不合法的判断......
  • 2024.8.21 鲜花
    NeverGonnaGiveYouUpWe'renostrangerstoloveYouknowtherulesandsodoIAfullcommitment'swhatI'mthinkingofYouwouldn'tgetthisfromanyotherguyIjustwannatellyouhowI'mfeelingGottamakeyouunderstandNe......
  • [赛记] 暑假集训CSP提高模拟24
    与和100pts签到题但还是做了很久。。。考虑与的条件,可以发现,如果将$a$转化成二进制,那么二进制上为$1$的位置$x$和$y$都必须是$1$,所以首先将$s$减去$2\timesa$,然后再判断一下$(s-2\timesa)\operatorname{and}a$是否为$0$即可;赛时用......
  • 国内外ChatGPT镜像网站集合【2024-08-21最新】~
     一、GPT4o& &4.0turbo&GPT4omini介绍总有人问我,GPT4o、GPT4.0和GPT3.5有什么区别?国内怎么才能用上,听说很复杂以一张表来表达他们的区别吧GPT3.5、GPT3.5Turbo、GPT4.0均已经被官方放弃维护,也就是说我们其实已经使用不到这几个模型了。目前官方主流开放的模型有GP......
  • 【题解】Solution Set - NOIP2024集训Day12 树上启发式合并
    【题解】SolutionSet-NOIP2024集训Day12树上启发式合并https://www.becoder.com.cn/contest/5472「CF600E」Lomsatgelral直接dsuontree。记录每一个颜色的出现次数。「IOI2011」Race之前是用点分治做的。考虑dsuontree。每个子树内维护到根节点的距离为\(x\)......
  • 2024暑假集训测试30
    前言比赛链接。T1普及了一下异或哈希,T2、T3赛时应该算乱搞题,还搞挂了,T4高级平衡树题,不太可做。原题全部出自:2022牛客OI赛前集训营-提高组(第四场)。T1博弈部分分\(30pts\):\(O(n^2)\)暴力。正解:不难推出必胜策略就是\((x,y)\)路径上每个边权出现的次数不全为......
  • Selenium + Python 自动化测试21(PO+HTML+Mail)
            我们的目标是:按照这一套资料学习下来,大家可以独立完成自动化测试的任务。上一篇我们讨论了PO模式并举例说明了基本的思路,今天我们继续学习。        本篇文章我们综合一下之前学习的内容,如先将PO模式和我们生成HTML报告融合起来,综合的灵活的使用之......
  • 高级java每日一道面试题-2024年8月21日-框架篇[Spring篇]-使用IOC容器应该注意哪些?
    如果有遗漏,评论区告诉我进行补充面试官:使用IOC容器应该注意哪些?我回答:1.理解IOC的基本概念控制反转:在传统的编程模式中,程序会主动控制依赖关系的创建和管理。而在IoC容器中,这种控制权被反转给了容器本身。程序员只需要声明依赖关系,而由容器负责实例化和注入这些依......