Manacher实例 作者: rin 时间: July 18, 2020 分类: 未分类 评论 [前坑](https://lo-li.net/1311-manacher-%E7%AE%97%E6%B3%95%E6%B1%82%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html)  符号说明: * `i`为字符串中的下标,`S`是预处理后的字符串 * `P[i]`代表以`i`为中心(含)的地方,回文的半径长度。例如`P[1]=1`意为以`'#'`为中心的最长回文子串为`"#"`,半径长度为1;同样,`P[16]=4`意为以`'x'`为中心的最长回文子串`"#p#x#p#"`的半径`"#p#x"/"x#p#"`的长度4 * `id`代表当前已知的最长回文子串的中点;`mx`代表该子串的半径长度+1 * 带圈数字代表步骤 ①、起始状态,`i=0,mx=0,id=0` 此时`i=1 >= mx=0`,即此位置已经超过了已知的最长回文范围(因为才开始嘛),同时也能确定`P[1]=至少=1`。 因此现在需要以`i=1`为中心,从其半径范围外两边开始逐一比对。(两边就是`i±P[i]`) 发现`'$'≠'a'`,扩展不下去了便停止,更新`id=1,mx=id+P[id]=1+1=2` ②、`i=2,mx=2,id=1` 此时`i=2 >= mx=2`,同样超过了已知的最长回文范围(注意`mx`是边界+1),同理能确定`P[2]=至少=1`。 继续扩展发现`'#'='#'`,则`P[2]++`,再继续无法扩展`$≠b`。 更新`id=2,mx=id+P[id]=2+2=4` ③、`i=3,mx=4,id=2` 此时`i < mx`了,说明`i`在**已知最长的回文子串(id=2的那个)**的势力范围内了。那么根据对称性,`i=3`在前面就有一个“分身”`j=2*id-i=1` 现在想求的`P[i]`就和`P[j]`有一种关系:`P[i]`=**可能**=`P[j]`,那么此时以`i`为中心的回文子串最右的下标就**有可能**扩展到`i+P[i]-1`,例如此时:  `i+P[i]-1=3+1-1=3 < mx=4`,`3`仍处在**能保证对称的势力范围内**,那么上面的“可能”变成“一定”。 (当然现在串还太短效果不是很明显,可以参考后面的⑥;同时“不可能”的情况请参考文末) ④、⑤同理 ⑥、`i=6,mx=10,id=5` `P[6]=P[4]=2`,现在能从下标`6-2=4`和`6+2=8`的位置开始对比,而对称区域内的都不用再比了。所以就利用了已知的信息跳过了很多次对比。 然后`'b'≠'a'`停止,`6+2=8 < mx=10`,说明仍然处于最长的那个子串内部,所以不更新`mx,id` …… 如此便能算出所有的`P[i]`并且能得到最长的长度。 ------------ “不可能”的情况 换一个例子  此时`i=11,id=8,mx=14` 根据预判,`P[11]=P[5]=5`。但是下标`11+5=16 >= mx=14`,预判超过了**能保证对称**的部分,于是剩余的部分`14,15`就要和`8,7`暴力对比。
[POJ1017]Packets 作者: rin 时间: February 1, 2017 分类: ACM,贪心 11 条评论 # 题目描述 一家工厂生产的产品以相同的高$$h$$,六种不同的长宽$$1\*1,2\*2,3\*3,4\*4,5\*5,6\*6$$包装。 送货时集装的箱子的高也为$$h$$,长宽为$$6*6$$。 根据每种尺寸的产品的个数求出最少需要多少箱子来装。 # 输入 输入包含多组数据 每组数据为一行六个数,分别代表边长$$1$$到$$6$$产品的个数。 输入以六个$$0$$结束。 # 输出 每组数据输出一行一个数,代表最少需用的箱子个数。 # 样例输入 ``` 0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0 ``` # 样例输出 ``` 2 1 ``` --- - 阅读剩余部分 -
[ICPC2016Dalian Onsite]官方题解 作者: rin 时间: November 6, 2016 分类: ACM 7 条评论 [PDF版](http://pan.baidu.com/s/1bpkkoTD) > 添加 `-D__STDC_FORMAT_MACROS`以支持`PRId64` #Problem A Wrestling Match ##提交情况:170/434 ##解题思路 本题做法比较随意,此处说两种: 1. 读入数据,建好图以后,以每一个点为开始遍历的起始节点,搜索整个图,在搜索的过程中判断是否出现冲突 2. 用并查集维护题目中所谓『好选手』以及『坏选手』的关系,在建立并查集的过程中,就可判断冲突 总的来说,第2种做法需要处理的特殊情况较少,并且计算量照第1种做法少,所以标程采用第2种做法。 - 阅读剩余部分 -
[CCPC2016Hefei] I / HDU5969 作者: rin 时间: November 5, 2016 分类: ACM,位 4 条评论 [http://acm.hdu.edu.cn/showproblem.php?pid=5969](http://acm.hdu.edu.cn/showproblem.php?pid=5969 "http://acm.hdu.edu.cn/showproblem.php?pid=5969") >###Problem Description >B君和G君聊天的时候想到了如下的问题。 给定自然数$$l$$和$$r$$ ,选取2个整数$$x,y$$满足$$l \leq x \leq y \leq r $$,使得$$x|y$$最大。 其中|表示按位或,即C、 C++、 Java中的|运算。 ###Input 包含至多10001组测试数据。 第一行有一个正整数,表示数据的组数。 接下来每一行表示一组数据,包含两个整数$$l$$,$$r$$。 保证 $$0 \leq l \leq r \leq 10^{18}$$。 ###Output 对于每组数据输出一行,表示最大的位或。 1.钦定上界就是$$y=r$$ :hj-huamoji52: 2.判断$$l$$和$$r$$二进制位数的大小关系$$lenL, lenR$$ 3.如果不相等,那么$$x=(111111\ldots )_{2}$$($$lenR-1$$个1)一定大于等于$$l$$,小于等于$$r$$,那么$$l|r$$的结果就是$$2^{lenR}-1$$ 4.如果相等,令$$x=l$$,将$$x,r$$的最高位对齐,从高位往低位一位一位比较,把碰到的第一个不同的位$$i$$,置$$x[i]=0$$,再将$$x$$剩下的都置1 - 阅读剩余部分 -
更新 作者: rin 时间: October 23, 2016 分类: 未分类 15 条评论 最近因为受不了Wordpress瞎改文章,转向Typecho:hj-huamoji28: ~~顺便~~为了上http/2重新编译配置了几遍vps:hj-huamoji27: 然后魔改了一下markdown的解析,加入了好用的表情:hj-huamoji25:(从853那里搞到的 现在除了emoji、Twemoji、Font awesome之外还可以使用我自定义的表情(我觉得叫**hua**mo**ji**比较好:hj-huamoji60:) 使用方法:套两个半角冒号 ``` :hj-ovo: ``` :hj-ovo: - 阅读剩余部分 -