category: Solutions

以前遇到过的模型突然攻击我，被偷袭了。 ...

还是比去年要难的。 ...

填完了。 ...

Description 有一个字符串 $S$，有 $n_a$ 个 A 类串是其子串，有 $n_b$ 个 B 类串是其子串，另外有 $m$ 个支配关系，表示第 $x$ 个 A 类串支配第 $y$ 个 B 类串。 求一个长度最大的字符串 $T$，需要满足两个条件： 其可以分割为若干个 A 类串； 不妨设 $T=t_1+t_2+t_3+…+t_k$，$t_i=A_{id_i}$，那么对于所有的 $t_i,t_{i+1}$，都存在一个 $A_{id_i}$ 支配的 B 类串，使得这个 B 类串是 $t_{i+1}$ 的前缀。 只需要输出长度的最大值即可，若可以无限长，输出 $-1$。 $|S|,n_a,n_b,m\leq2\times10^5$，多组数据，每个数据点中 $|S|,n_a,n_b,m$ 的总和不会超过单组数据限制的 $10$ 倍。 ...

参考：出题人 Itst 的题解。 确实是神仙，不好想。 ...

这个提答还算小清新，不用跑很久，主要是观察数据性质。 ...

很多分类讨论的题，不对拍很容易被卡正确性。 ...

目前只有 Day1 的题目。 感觉 Day1 的三道题很 CF。 ...

一个奇妙的建模题。 ...

Description 有一棵初始为空的树，每次新给出一个点的父亲和它连向父亲边的权值以及这个点的权值，每次加点之后询问有多少点满足 $dis(i,j)\leq val_i+val_j$，强制在线。 $n\leq10^5$。 ...