2024年1月9日模拟赛
由于今天 div 1 换了题,导致 div 1 和 2 就只有 1 道题一样,就只放 div 2 的题算了,而且还没有改完……有一道是线段树。其实我很不擅长的就是线段树了……多练练。
今天冬月廿八,感觉又感冒了……希望快快好起来。说到这里,想起一件事情。昨天放学的时候在路口看到一辆从路边启动的汽车撞倒了一辆正常行进中的摩托车(兴许是电瓶车),那个场面……并没有那么严重,汽车刚刚启动而已,希望人没事,但是看起来也没啥事,还是希望没事🙏🙏🙏🕯🕯🕯。
题解
今天的题目还是很有难度的。来简单讲一下。
A. 纸条
就是把一个长为
显然容易想到__int128
,然后最后再取模速度直接快了将近 10 倍!卡常小技巧!
这道题我用了一个宏,但是变量没打括号,最开始挂了!警示后人!
B. 染色问题
题意很简单,
然后
显然 NPC。正解是什么呢?就是考虑一条边两端点颜色相同和不相同的这两个权值,一种染色方案就是这些边对应权值乘起来。那么初始都是
这里还有另一种更显然的做法。就是先搞出 dfs 树,然后有额外边对吧。然后暴力枚举额外边中任意一个端点的“相对颜色”,然后暴力树上 dp 就可以了。最后假设 dfs 到了这几个特殊点颜色总共
P.S. 我们最开始没有看懂第二种的代码,我把它扔给文心一言,没有任何题面的提示,就是叫它解读代码,然后它竟然识别出了这个代码是 k 染色问题还大致说了每个变量的作用。太抽象了!难以置信。网上唯一搜到的 csdn 博客还要钱……虽然继续问它它也说不清楚,但能说出是染色问题还是很厉害的!
C. 序列
看起来是个线段树板题啊。
你需要维护两个初值为
共
看题解很线段树板子啊,但我线段树这个科技树点得不是很多啊。
题解是这样说的。
离线扫描线扫序列,问题转化为维护时间维对应的序列,区间对
区间信息需要记录区间最小值、区间严格次小值、区间最小值个数、区间和、区间历史和;
标记需要记录对
对结点应用标记时,如果标记的
其余部分的处理使用 区间最值问题与历史最值问题 的标准做法。
总时间复杂度
后记
没啥可记的呢?没意思。希望大家能找到自己的归属。
- 标题: 2024年1月9日模拟赛
- 作者: 混氏新子
- 创建于 : 2024-01-09 22:38:13
- 更新于 : 2024-01-10 22:46:13
- 链接: https://blog.huasushis.cn/2024/2024年1月9日模拟赛/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。