JZOJ 2019.10.30模拟赛总结
赛时T1 是个带环的博弈，我比较菜不会做 写了无环和有自环的点就跑了。 T2 这种题一看就很 $O(n^2)$ 可是我只会暴力 就跑了 $n$ 遍最短路，拿到了一点点暴力分 T3 一开始不会，发现 Sub1 可做 Sub2 可做 Sub5 可做。。。写了一场然后发现 Sub5 套个cdq 就过了，可惜这是在比赛结束前一分钟发现的 [流泪]最后 T1 不知道为什么爆零了 0+25+50=75...
赛时T1 是个带环的博弈，我比较菜不会做 写了无环和有自环的点就跑了。 T2 这种题一看就很 $O(n^2)$ 可是我只会暴力 就跑了 $n$ 遍最短路，拿到了一点点暴力分 T3 一开始不会，发现 Sub1 可做 Sub2 可做 Sub5 可做。。。写了一场然后发现 Sub5 套个cdq 就过了，可惜这是在比赛结束前一分钟发现的 [流泪]最后 T1 不知道为什么爆零了 0+25+50=75...
题目链接题意给你一个大串 $A$ 和若干小串 $B_i$，你可以做 $k$ 次操作：每次你可以选择从大串中删除一个小串，要求最后剩下的串尽量小，并输出长度 $lenA \leq 200,lenB_i \leq 10,m \leq 20$题解感觉自己做过 可惜不会做 首先我们考虑我们可以将删除操作变成删除在原串上的一段区间内和其匹配的字符串，我们考虑这种删除操作区间只可能不交或包含。不交的情况...
题目描述计数。有多少个长度为 $n$ 的排列，使得可以通过栈排好序并且第 $ps$ 个位置是 $x$。 $n \leq 10^6$题解首先我们考虑反过来：变成问你 $1 \cdots n$ 的排列通过栈可以生成多少在 $ps$ 位置为 $x$ 的序列。 考虑将这个过程抽象成括号序列：长度为 2n 的括号序列，左括号表示入栈，右括号表示出栈。 那么我们实际上是为了计数长度为 $2n$ 的括号序...
链接题目描述随机一棵以 $1$ 为根，且节点编号满足小根堆性质的树的期望最大深度。 $n \leq 200$题解这个题我考试的时候连 $n \leq 20$ 都不会..还是自己太菜了。一开始的一个想法是记 $f_{i,j}$ 表示前 $i$ 个点深度为 $j$ 的树的个数，然后发现不太能转移需要记录最后一层的节点个数。。然后还要记录前面层的所以复杂度就炸了。 然后我们考虑放宽限制，对森林计数...
题目链接题解一个我想不到的性质：每个点至多会被覆盖两次。 因为如果一个点被覆盖三次，那么肯定有一条线段的效果是可以被另外两条完全表达出来的，所以可以删去这个线段。 我们先将线段按照右端点排个序，有了这个性质，又因为它是个最优化问题，启发我们设 $f_{i,j}$ 表示考虑到了前 $i$ 个线段，最后一段被覆盖了一次的线段是 $[j,r_i]$ 的最小代价。答案就是所有 $r_i = n$ 的...