RainAir
My OI Blog
RainAir

动态规划
文章归档

JZOJ 2019.11.05 模拟赛总结

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

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

JZOJ 2019.11.02 总结

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

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

JZOJ 2019.10.30模拟赛总结

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

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

「JZOJ6281」串

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

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

「JZOJ6284」玩具

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

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

「JZOJ6391」区间

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

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

「CF379D」New Year Letter

题目描述 令 $s_i$ 表示第 $i$ 个字符串,我们有递推式 $s_i = s_{i-2}+s_{i-1}$(其中+ 是将两个字符串拼接起来的符号) 现在需要你构造出长度为 $n$ 的 $s_1$ 和长度为 $m$ 的 $s_2$ ,满足 $s_k$ 中串 AC 作为子串出现了 $x$ 次。 $3 \leq k \leq 50,0 \leq x \leq…

   65   2019-10-21   65 去吊打作者

ARC099 题解

C - Minimization 普及组题,不说了。 代码 D - Snuke Numbers 题意 将 $x$ 的数字和记作 $S(x)$。 称 $n$ 是好的,当且仅当 $\forall m>n, n \leq m$ 。 求第 $K$ 个好的数字。 保证答案不超过 $10^{15}$。 题解 全场最难的题。。。 我们设 $f(x)$ 表示满足 $\f…

   55   2019-10-18   55 去吊打作者

「CF599E」Sandy and Nuts

题意 给你若干限制,限制为 $lca(u,v) = c$ 和 $(u,v)$ 有连边,数一下以一为根的满足限制的树的个数。 $n \leq 13$,限制总数 $\leq 100$ 题解 这个题目太神仙了。。远古 CF 场的题目还是好。 考虑设 $f_{v,S}$ 表示 $v$ 节点子树内的点是 $S$ 的树的个数。答案是 …

   73   2019-10-11   73 去吊打作者

「CF388D」Fox and Perfect Sets

题意 定义一个集合 $S$ 是好的,当且仅当: 1. $\forall x\in S,y \in S $ 有 $x \oplus y \in S$,这里 $\oplus$ 是异或操作。 2. 集合最大值 $\leq n$ 求这样的集合的个数,模 $10 ^9+7$ 题解 这是个好题(至少我觉得我是想不出来) 首先一个观察是这样的集合一…

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