NOIP模拟 8

淩亂°似流年 2021-11-09 06:22 302阅读 0赞

T1

水题，可是没A，惭愧。

值得一提的是，虽然我忘了kmp，现场制造的kmp因为缺少针对题目的特判挂了，但是现场制造的kmp板子能过字符串板子题..

对..把板子改装了...而且改对了！

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 nx[0]=-1;
    2 for(int i=2,j=-1;i<=len;++i){
    3     while(~j&&ch[j+1]!=ch[i]) j=nx[j];
    4     nx[i]=++j;
    5 }

T2

也比较水，可是没A，惭愧。

初始化的时候清零犯了低错，死了。改了，A了。

记录一个骚操作，仔细品味发现它非常巧妙

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

for(register int i=fr[x];i;i=mo[i].pr)
        {
            register int y=mo[i].to;
            if(!dfn[y])
            {
                tarjan(y);
                low[x]=min(low[x],low[y]);
                if(low[y]>=dfn[x]&&dfn[y]<=dfn[n])//后一个条件保证了只在n的祖先处触发
                {
                    son++;
                    if(x!=1||son>1) cut[x]=1;
                }
            }
            else low[x]=min(low[x],dfn[y]);
        }

T3

做的很痛苦，改的也很痛苦，因为看不懂题解，只好。。

自主研发：前提：序列抽象为01，枚举断点转化成序列，每个序列把1挪到序列两端可以保证答案不漏

考虑每个1,它挪到左边代价为左边0的个数，右边代价为右边0的个数

所以往0多的方向走不如往少的方向走

一个1,它的哪边0多，在序列上具有单调性

所以就让它们左边0少的去左边，其余去右边

分界线就是0的数量的中点（偶数就是两个中间的0之间，奇数就是中间那个0）

每个断点，O（1）求解，复杂度O（N）

转载于:https://www.cnblogs.com/yxsplayxs/p/11246029.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/cc5f668da79f48c4b0207279715ac84c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，302人围观）

还没有评论，来说两句吧...

相关阅读

相关 [noip模拟]分组行动

题目描述最近，木木中学要举行一年一度的辩论赛了，我们活泼开朗乐观向上不寂寞不生病不挂科天天回家吃饭的新时代好少年--飞飞，自然是热情参与咯！辩论嘛，就有正方和反方两个

小鱼儿/ 2021年12月24日 16:29/ 0 赞/ 293 阅读

相关 NOIP模拟分糖果（贪心）

[就是这道题][Link 1] 【题目分析】竟然又是一道氵谷原题。。。。。。。关于排序的正确性以及正确的排序见[这篇博客][Link 2] 【代码~】

灰太狼/ 2021年11月26日 07:22/ 0 赞/ 320 阅读

相关 20190725 NOIP模拟8

今天起来就是虚的一批，然后7.15开始考试，整个前半个小时异常的困，然后一看题，T1一眼就看出了是KMP，但是完了，自己KMP的打法忘的一干二净，然后开始打T2，T2肝了一个t

清疚/ 2021年11月13日 16:42/ 0 赞/ 237 阅读

相关 NOIP模拟 8

T1 水题，可是没A，惭愧。值得一提的是，虽然我忘了kmp，现场制造的kmp因为缺少针对题目的特判挂了，但是现场制造的kmp板子能过字符串板子题.. 对..把板子改装了

淩亂°似流年/ 2021年11月09日 06:22/ 0 赞/ 302 阅读

相关 [NOIP模拟25]题解

A.字符串 Catalan数不能再裸了 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] includ

客官°小女子只卖身不卖艺/ 2021年10月30日 08:14/ 0 赞/ 334 阅读

相关 [20190725NOIP模拟测试8]题解

[Orz][] T1 大水题，考场上看到题目中什么前几位相同末尾加字母莫名慌的一批后来发现直接无脑哈希就能$O(n)$ KMP同样可切仔细读题，数组别开小

深藏阁楼爱情的钟/ 2021年10月29日 08:50/ 0 赞/ 294 阅读

相关 NOIP模拟12

　　也算是最近几次比较水的一次吧。　　考试时看T1像个打表找规律的题，扔了，去看T2，带修莫队？？不会，完戏。看了T3，我决定还是去看T1。　　看着T1，我突然发现T2

冷不防/ 2021年10月26日 14:58/ 0 赞/ 294 阅读

相关 2017NOIP模拟赛-科普基地

> 今天回来打的第一场NOIP难度的试题，结果惨不忍睹。写一下每道题的做法，然后每道题犯的\_\_弱智\_\_错误 > UPD:2018.9.15 突然这篇题解就变成很多大

小咪咪/ 2021年10月24日 01:50/ 0 赞/ 264 阅读

相关 NOIP模拟测试18

本博客禁止sjzyz观看为什么会变成这样呢……第一次有了秒切的T1，又有了想出了正解的T2。两件快乐事情重合在一起。而这两份快乐，又给我带来更多的快乐。得到的，本该是像梦境

╰+哭是因爲堅強的太久メ/ 2021年10月23日 16:44/ 0 赞/ 321 阅读

相关 7.22 NOIP模拟7

又是炸掉的一次考试 T1.方程的解　　本次考试最容易骗分的一道题，但是由于T2花的时间太多，我竟然连a+b=c都没判。。暴力掉了40分。　　首先a+b=c,只有一组解

朴灿烈づ我的快乐病毒、/ 2021年10月23日 07:43/ 0 赞/ 300 阅读