- 2024-08-31[luoguP4051/JSOI2007] 字符加密
题意给定字符串\(s\),输出将\(s\)的所有循环同构的字符串排序后,每个字符串的末尾的字符。sol因为要对循环同构的字符串排序,因此我们可以将\(s\)复制一遍,拼在后面,计算\(sa\),满足\(sa_i\len\)的所有元素的相对位置即为排序后字符串的相对位置,输出即可\(sa\)的计算详见
- 2024-08-20[题解]P4052 [JSOI2007] 文本生成器
P4052[JSOI2007]文本生成器正难则反,我们发现用总字符串个数\(26^m\),减去不可读的字符串个数,就是答案。要使一个字符串不可读,就不能让任何模式串在其中出现。如果某个主串的第\(i\)位与自动机的节点\(j\)相匹配,那么如果状态\(j\)包含模式串(即有一个前缀是一个模式串),那么不管主
- 2024-07-13【反悔贪心】P2949WorkSchedulingG+P4053[JSOI2007]建筑抢修题解
这两天遇到了几个很神奇的题目——能反悔的贪心。赶紧记录一下。例1(用时一定模型)用时一定:每个任务完成的耗时都是一样的。题面:Luogu-P2949WorkSchedulingG大体思路是:先把所有任务按照截止时间从小到大排序,然后枚举,遇到一个能做任务的就把他做了,把他的贡献加入一个
- 2023-07-22「刷题记录」[JSOI2007] 文本生成器
第一道AC自动机+DP题。题目链接:P4052[JSOI2007]文本生成器-洛谷|计算机科学教育新生态(luogu.com.cn)利用容斥原理的思想,答案就是所有串的数量减去不可读的串的数量。设\(dp\left(i,j\right)\)表示串长为\(i\),在AC自动机上走到编号为\(j\)时不经过单词结
- 2023-05-24[JSOI2007]建筑抢修
[JSOI2007]建筑抢修跟经典题poj1456非常像。首先如果两个都被选入那么截至时间T2小的放前面肯定更优,所以我们先按T2排序。然后逐个遍历建筑,建立一个维修时间为关键字的大根堆,如果前面花费的总时间+维修的时间小于当前的T2,直接加入。否则判断是否小于堆顶,如果小于堆顶则替换,因为
- 2022-10-14P4053 [JSOI2007] 建筑抢修
[JSOI2007]建筑抢修题目描述小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏:经过了一场激烈的战斗,T部落消灭了所有Z部落的入侵者。但是T部落的基地里已经有
- 2022-09-29[JSOI2007]祖玛
做题时间:2022.9.28\(【题目描述】\)给定一排\(N\)个整数,可以向之间插入任意一个整数,得到相邻的多于2个相同的整数就可以把他们消除掉,其余整数按顺序合并起来,也可以继续
- 2022-08-23[JSOI2007]文本生成器【AC自动机+DP】
下定决心想要将这份爱意传达给你,与你在一起的每一刻总是那么值得珍藏,你的存在左右着我的思绪,实在是不想错过这样的美好,真的不和我在一起吗?我的学术生涯,虽然有点奇妙,
- 2022-08-17[JSOI2007] 字串加密
题链:luoguJS同学?Description让JS同学对环形字符串进行重组加密。加密规则是:列出\(n\)个字符串并字典序升序,一次取末尾字符作为加密后的长度为\(n\)的密码串。