RainAir
My OI Blog
RainAir

RainAir’s Blog

  WC2020 & SDOI2020 Bless All!!!!!

密码保护:杂题集

这篇文章受密码保护,输入密码才能看哦

   731   2019-07-13   731 去吊打作者

后缀自动机学习笔记

作为菜鸡 OIer,本文尽量用通俗的语言去讲解后缀自动机。 当然学习后缀自动机前是有一点点前置知识的,我一块给说了。 有限状态自动机(DFA) 定义 确定优先状态自动机 $\mathcal{A}$ 是由: * 一个非空有限的状态集合 $Q$ * 一个输入字母表$\Sigma$ (非空有限的字…

   9   2020-01-28   9 去吊打作者

「CF1110H」Modest Substrings

好久不更博了~~~ 题目大意 定义一个数是好的当且仅当这个数 $x$ 满足 $l \leq x \leq r$ 定义一个长度为 $n$ 的字符串的价值是所有好的数在这个字符串的出现次数的和。 现在给你 $l,r,n$ 让你构造出满足价值最大的情况下字典序最小的串。 $1 \leq l \leq r \leq 1…

   3   2020-01-27   3 去吊打作者

JZOJ 2019.11.05 模拟赛总结

2019.11.05 模拟赛总结 赛时 开场看了 T1,发现实质上是对完全图求 $n-1$ 完备匹配,求完后就删掉。发现自己只会暴力(其实是构造题想不出来),就去看了 T2 T2 一开始感觉和树堆那个题差不多...?但是发现其实这个性质是不独立的 ,写了写代码发现了不独立之后,就只…

   233   2019-11-05   233 去吊打作者

JZOJ 2019.11.02 总结

赛时 T1 一看暴力分是之前做过的原题,所以就粘写完了 $O(n^2logn)$ 的暴力, T2 想了想,发现每次一定要把最小值移动到左边或右边,然后可以递归成子问题去做了 T3 建出来树之后只会暴力 dp。 最后 40+100+25 第三题挂了 20 分完美省三。 题解 A. Game $O(n^2logn…

   179   2019-11-03   179 去吊打作者

JZOJ 2019.10.30模拟赛总结

赛时 T1 是个带环的博弈,我比较菜不会做 写了无环和有自环的点就跑了。 T2 这种题一看就很 $O(n^2)$ 可是我只会暴力 就跑了 $n$ 遍最短路,拿到了一点点暴力分 T3 一开始不会,发现 Sub1 可做 Sub2 可做 Sub5 可做。。。写了一场然后发现 Sub5 套个cdq 就过了,可惜…

   177   2019-11-02   177 去吊打作者

「JZOJ6281」串

题目链接 题意 给你一个大串 $A$ 和若干小串 $B_i$,你可以做 $k$ 次操作:每次你可以选择从大串中删除一个小串,要求最后剩下的串尽量小,并输出长度 $lenA \leq 200,lenB_i \leq 10,m \leq 20$ 题解 感觉自己做过 可惜不会做 首先我们考虑我们可以将删除操作变成…

   133   2019-11-02   133 去吊打作者

「JZOJ6395」消失的序列

题目描述 计数。有多少个长度为 $n$ 的排列,使得可以通过栈排好序并且第 $ps$ 个位置是 $x$。 $n \leq 10^6$ 题解 首先我们考虑反过来:变成问你 $1 \cdots n$ 的排列通过栈可以生成多少在 $ps$ 位置为 $x$ 的序列。 考虑将这个过程抽象成括号序列:长度为 2n 的括…

   106   2019-11-02   106 去吊打作者

「JZOJ6284」玩具

链接 题目描述 随机一棵以 $1$ 为根,且节点编号满足小根堆性质的树的期望最大深度。 $n \leq 200$ 题解 这个题我考试的时候连 $n \leq 20$ 都不会..还是自己太菜了。 一开始的一个想法是记 $f_{i,j}$ 表示前 $i$ 个点深度为 $j$ 的树的个数,然后发现不太能转移…

   167   2019-11-01   167 去吊打作者

「JZOJ6391」区间

题目链接 题解 一个我想不到的性质:每个点至多会被覆盖两次。 因为如果一个点被覆盖三次,那么肯定有一条线段的效果是可以被另外两条完全表达出来的,所以可以删去这个线段。 我们先将线段按照右端点排个序,有了这个性质,又因为它是个最优化问题,启发我们设 $f_{…

   133   2019-10-28   133 去吊打作者

JZOJ CSP 模拟 10.23

A.珂学家 题目链接 题解 如果 $l,r$ 的范围不大的话,我们记 $S$ 表示将每个区间的权值都加在区间上后得到的序列,$A_i$ 表示第 $i$ 个区间区间加后得到的序列。我们考虑预处理:答案多项式$$Ans = S^2 - \sum_{i=1}^n A_i^2$$ 前面可以 NTT,后面发现是一些区间加…

   198   2019-10-25   198 去吊打作者
加载更多
标签
近期评论