NOIP模拟12

冷不防 2021-10-26 14:58 270阅读 0赞

也算是最近几次比较水的一次吧。

考试时看T1像个打表找规律的题，扔了，去看T2，带修莫队？？不会，完戏。看了T3，我决定还是去看T1。

看着T1，我突然发现T2是个大水题：主席树就行，不带修，修改时只需修改一棵主席树上的权值。不管了，先切了它。十分钟码完，40行，两个样例都是一边过。。。突然心里特别虚，于是我决定打个对拍，一拍就错（不要迷信样例，包括大的！）。

从头到结束半个小时T2就搞定了，然后我去推T1的式子，通过打表我们可以发现：一只兔子与其爸爸的差必然为斐波那契数列中的一项，那一项就是比这只兔子小的最大的一项。于是我们就可以二分出这一项，一直往上扫就可以得到答案。10^12大概到了59项，所以复杂度60\*log60\*m，好像有点玄（考后证明这样也能A）。。。。于是想到，可不可以类似倍增lca的思路（将每一个数唯一分解为若干2的k次幂之和），将每一个数唯一分解为若干斐波那契数之和，即可知道他们的爸爸与深度。然后就愉快的AC了这道题。

大概还有50min，去看T3，看了看，好像倒着扫就可以确保字典序最小，k=1直接硬判，k=2可以用并查集维护，但是没有想到在值域上求解。所以打了个在点上求解的，理论复杂度O（n^2）。

最后一看，T3炸了？输出ans->输出ans+1，分数12->40，把else放在另一个if里面，分数40->72，改了改扩展域并查集，分数72->84，

最后被玄学了：

1 printf("%d\n",ans);
    2 int len=h.size();
    3 for(int i=len-1;i>=0;i--)
    4     printf("%d ",h[i]);

wa84到死，不知怎么回事，后来改成了这样：

1 printf("%d\n",ans);
    2 for(int i=ans-2;i>=0;i--)
    3     printf("%d ",h[i]);

感觉没啥用，也没交，后来交了一下，A了？

T1A掉了，T2莫名其妙wa了，什么鬼，我拍了2个小时呢，发现颜色可以>n，改了之后，T了？

卡了卡常，A掉了。

感觉这次还行，至少三道题都是正解思路（除了T3在值域求解），但是因为种种原因炸成了100+75+12=187，rk4

没了

转载于:https://www.cnblogs.com/hzoi-cbx/p/11295319.html

发表评论取消回复

表情：

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

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

相关阅读

相关 NOIP模拟34

考试的时候被T2卡了一年。。。。考虑了一下正解的式子，然后没去给左边分解因数，去给后面乘倍数。。。理论复杂度O（n^2），实际好像卡不掉的样子。但是由于我智障的打了一棵主席树，

川长思鸟来/ 2023年08月17日 16:48/ 0 赞/ 89 阅读

相关 NOIP模拟27

两个机房又和在一起考试开场看了看T1，感觉挺水的，过。 T2，这个式子有点奇怪，暂时没什么思路，过 T3，好像保留最后几位换个根处理一下就行了，过，先去打T1 于是T

淡淡的烟草味﹌/ 2023年08月17日 16:48/ 0 赞/ 15 阅读

相关 noip模拟测试19

-------------------- T1：Count 　　首先容易发现块的大小一定是n的约数，枚举约数$O(\\sqrt n)$ 　　考虑怎么判定　　设块大小为

悠悠/ 2023年08月17日 15:43/ 0 赞/ 80 阅读

相关 noip模拟测试18

-------------------- T1：引子　　呃呃呃…… 　　大（？）模拟，好像也不难写？　　模拟灌水过程就完了？？？ ![ContractedBloc

素颜马尾好姑娘i/ 2023年08月17日 15:43/ 0 赞/ 75 阅读

相关 [noip模拟]分组行动

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

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

相关 20190725 NOIP模拟8

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

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

相关 NOIP模拟 8

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

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

相关 [NOIP模拟25]题解

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

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

相关 NOIP模拟12

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

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

相关 NOIP模拟测试18

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

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