首页 > 其他分享 >CSP-S 2023 题解

CSP-S 2023 题解

时间:2023-10-22 20:34:36浏览次数:39  
标签:pre le frac bc 题解 矩阵 合法 2023 CSP

CSP-S 2023 题解

密码锁

发现总状态数只有 \(10^5\) 个,枚举 \(O(n)\) 暴力判断即可,复杂度 \(O(10^5 n)\)。

或者每一个状态只对应了 \(81\) 个状态,枚出来,取交集即可,复杂度 \(O(81 n)\)。

消消乐

好的,来一波抽象做法 QwQ

我看到这道题的第一眼:这不就是 QOJ 6504 Flower's Land 2 吗。

于是考虑对每一个元素赋一个矩阵 \(M_i\),奇偶分开赋正逆矩阵,例如 aaa 就为 \(M_a, M_a^{-1}, M_a\) 或者 \(M_a^{-1}, M_a, M_a^{-1}\)。

于是一个区间合法当且仅当 \(\prod M_i = I\),这可以考虑矩阵满足结合律,但是不满足交换律。

其实换成任意一种满足结合律,但是不满足交换律的东西来都可以维护。

暴力枚举是不可取的,考虑前缀和,则合法当且仅当 \(pre_r \times pre_{l - 1}^{-1} = I\)。

考虑两边同时乘上 \(pre_{l - 1}\),那么合法当 \(pre_r = pre_{l - 1}\)。

于是用一个桶或者 map 记录一下数量即可求出答案,注意需要开 long long

如果是 \(2 \times 2\) 的矩阵,求逆的话就别用高斯消元了,推一下式子即可得到:

\[\begin{pmatrix} a & b \\ c & d \\ \end{pmatrix} \begin{pmatrix} \frac 1 a + \frac {bc} {a (ad - bc)} & \frac b {bc - ad} \\ \frac {-c} {ad - bc} & \frac a {ad - bc} \end{pmatrix} = I \]

或者可以用自逆矩阵,但我声称那没必要。

代码:云剪贴板 - 洛谷


然而这还不够优秀,(其实可以另开炉灶),我们基于矩阵继续优化。

其实不难发现,对于一个合法的区间,\(\prod M_i\) 可以被划分为若干个合法区间。

如果我们使得每一个合法区间最小,那么划分可以证明是唯一的。

例如 abbacddc 就可以分为 abbacddc 两个区间。

于是对于每一个 \(i\),考虑找到最后一个 \(pre_i = pre_j\) 的 \(j\) 记为 \(t_i\)。

我们考虑如何快速的递推求出 \(t_i\)。

如果我们已经求出了 \(t_{i - 1}\),也就是 \(\prod_{t_{i - 1} \le k \lt i} M_i = I\) 那么对于 \(i\) 来说,我们需要找到前面的某一个 \(j\) 使得。

发现 \(t_i - i\) 这个区间一定形如 \(x (某合法串) \cdots (某合法串) x\),于是初始答案为 \(x = t_{i - 1}\),我们不断的跳 \(t_{x - 1}\) 直到 \(S_x = S_i\) 为止,那么此时一定满足 \(t_i - i\) 是合法的且是最小的,利用 kmp 的复杂度分析可以得知这就是 \(O(n)\) 的。

最后 \(O(n)\) 的扫一遍,记 \(f_i\) 表示以 \(i\) 结尾的合法串的个数,\(f_i = 1 + f_{t_i - 1}\),答案为 \(\sum f_i\)

代码在剪切板底部:云剪贴板 - 洛谷

结构体

超级模拟,利用 object id 完成模拟即可。

只是注意 addrfix 与对应的 align

种树

显然二分答案,然后考虑如何检查。

发现可以快速的求解出最晚能放置的时间 \(f_x\),由于树形结构存在依赖,考虑 \(O(n)\) 的更新一次:\(f_x = \min(f_x, \min_{y \in Son(x)}f_y - 1)\)。

然后将 \(f_x\) 排序,存在合法的操作序列当且仅当 \(\forall i, i \le f_i\)。

现在就可以得到一个 \(O(\log V (n \log V + n \log n))\) 的抽象做法了(我的考场做法,还跑得挺快,自测数据用了 500ms)

其实可以 \(O(n)\) 的判断,优化如下:

可以发现树生长的过程是一段一次函数和一段二次函数,那么将断点预处理一下,每次可以 \(O(1)\) 的求解一个方程,解出最晚能放置的时间 \(f_x\),这部分就是 \(O(n)\) 的了。

发现合法的序列只需要判断 \(\le n\) 的部分即可,因为对于 \(f_i \ge n\) 的时候存在 \(i \le n \le f_i\),一定满足条件。

所以可以开一个 \(O(n)\) 的桶,前缀和一下数量 \(c_i\),满足 \(\forall i, c_i \le i\) 即合法,这样就可做到 \(O(n)\)。

于是得到了一个 \(O(n \log V)\) 的优秀做法。

标签:pre,le,frac,bc,题解,矩阵,合法,2023,CSP
From: https://www.cnblogs.com/jeefy/p/17781040.html

相关文章

  • 2023 CSP-J/S 游寄
    赛前停课了两个星期,打了好几场模拟赛。(吐槽一下,说是CSP-S模拟赛,但难度和知识点早就超了提高了)。模拟赛的质量很高,学到了很多算法和小技巧。当然,每天都被爆踩。上午:CSP-J开题仍然延续老传统:顺序开题。apple很快找到了性质:逢三取一,打了一会就切了。road一开始考虑了dp......
  • CSP-S 2023 总结
    CSP-S2023总结第一次搞csp-s复赛,感觉没考好。估分150+,感觉要寄。先全部看一遍,第三题看了一眼就走了,其他题大概有一点思路,感觉大概150的样子。T1一开始读错题乱搞了30分钟才发现,然后有花了15分钟打完。T2第二题花了一小时想不到正解,就搞了个\(O(n^2)\)的水法。打完之后......
  • Pycharm 2023.2 最新po jie版安装教程(附激活码,亲测有效)
    申明:本教程Pycharmpojie补丁、激活码均收集于网络,请勿商用,仅供个人学习使用,如有侵权,请联系作者删除。若条件允许,希望大家购买正版!前言笔者分享一种比较靠谱的Pycharm pojie方案:激活脚本+激活码(全自动模式),即本文教程所写,这种方法适合最新的几个版本,具体步骤跟着本文教程一步......
  • CSP-S 2023游记
    CSP-S2023游记Day?-Day-1备考,思考了很多种的骗分算法,查看准考证。每天依然在做模拟赛,感觉对DS题的感觉不太良好。Day0比赛前一天,感觉心情不是十分紧张。上午玩了一下NOILinux,挺好玩的。下午有老选手给我们讲保龄经验,挺乐的,然后挺期待CSP的题的吧,只要不太变态就可以了(许......
  • 洛谷题解 | AT_abc321_c Primes on Interval
    目录题目翻译题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2样例#3样例输入#3样例输出#3题目简化题目思路AC代码题目翻译【题目描述】你决定用素数定理来做一个调查.众所周知,素数又被称为质数,其含义就是除了数字一和本身之外不能......
  • 「CSP 2023」邮寄
    day-10086没事干来开个坑临近才想起马上CSP2023了...开始复习(得知提高\(>60\)就能二等233333,于是乎报了提高)day-48csp-j模拟赛100+0+90+10=200有点崩day-41初赛资料终于发了,还以为学校准备放弃我们了day-36这一周都在背初赛资料还要搞WHK。。。32页给我脑子背ML......
  • 吃薯片2023游记
    吐槽:开赛太热,后半场太冷,可能是第一排太靠前门导致的。啥都想不了,啥都想不了,啥都想不了,啥都想不了,啥都想不了。没有c++14属实答辩(虽然不是他的问题,但是删了=c++14忘打=c++11属实难绷)。shift+空格打不出空格真是ex。体验极差。正文:题解:T1:水题,先看数据范围,然后暴力找交集......
  • 2023-2024-1 20231405 《计算机基础与程序设计》第四周学习总结
    2023-2024-120231405《计算机基础与程序设计》第四周学习总结作业信息作业属于哪个课程https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP作业要求在哪里https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP/homework/13009作业的目标自学《计算机科......
  • [ABC234E] Arithmetic Number 题解
    题目传送门一道枚举题。暴力枚举数字位数、首位、等差数列的公差即可。注意公差的枚举范围,并且需要看看末尾合不合法。顺便提一下,我是用字符串存储枚举的数字的,所以写了一个check函数代替大于号。Code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;......
  • [ABC231E] Minimal payments 题解
    题目传送门一道贪心题。感觉很裸啊,模拟赛时随便乱写了个暴力递归就能过。每次找最接近钱数\(x\)的面额\(num\),如果比钱数少那么答案为剩下\(x\bmodnum\)钱数的答案加上\(x\divnum\)。否则答案则为剩下\(num-x\)钱数的答案加上\(1\)。Code#include<bits/stdc++.h......