联赛总结_001

yjiong · 2023-09-24 22:01:45 · 个人记录

9.24

T1

给定一个 n(1 \le n \le 10^5) 个点、m(n-1 \le m \le 5 \times 10^5) 条边有向无环连通图，每条边都有边权，为一个字符串（字符串总长 \le 2 \times 10^6）。求以下两种定义下的最短路：

• 路径总长度最短，长度相同取字典序最小。

• 路径字典序最小。

输出此两条路径。

考场上读完 4 道题，发现就只有这道题看起来比较可做，然后就开始胡。先胡了一个简单的最短路，然后发现数组开不下。但是好像可以骗好多分，然后就开打了。刚打完 Dij 发现好像是 DAG，然后就换成了 Topo，果然要快一点。然后就开始写各种优化，写完发现过不了大样例了，干脆全部删完，瞬间清爽了好多。

然后发现过去 90min 了，我这是在干什么啊。

T2

给定一个常数 B 和询问次数，每次询问有 L,R(1 \le L,R \le 10^9)，求：

其中，对于一个函数 f(x)，f^{(k)}(x)=f(...f(x))，等式右边恰好有k个f。当 k \le 0 时，f^{(k)}(x)=x。

e.g.f^{(3)}{(x)}=f(f(f(x)))。

至暗时刻。

令最大 R 为 n，询问次数为 q，不难发现求完 phi 之后暴力是 O(q \times n^2) 的。如果预处理出 1 \sim i 的 max\varphi，复杂度变成了 O(q \times n)。（其实迭代 \varphi 也需要很多时间，但是考试时分析复杂度的时候没有分析到。）

然后我就开始脑残了。题目中那么大一个 \sum_{i=L}^{R}，这不明摆着用前缀和吗？然后我就真的是没看到。写了个极其 sb 的

for(int i = l; i <= r; ++ i)

然后就求答案啊，不难发现过程中的所有 \varphi^{(k)}(i)，k 要不了多大这个值就会变成 1，然后就一直是 1 不会改变了。然后就可以预处理出每个 i，\varphi(i) 变成 1 所需要的最小次数，节省了很多时间。

那么，其实在最小次数内，直接暴力迭代就好了啊，没错，脑残行为又开始了。我开了个 vector，这个 vector 可不是一般的 vector，它是

std::vector <int> ca[10000005];

它用来干啥呢？用来存一个数 \varphi(i) 经过 j 次迭代会成为哪个数。

没错，一个 10^7 的 vector 数组。估计没个 10 年脑血栓写不出来这种东西。于是我的 T2 就全部 MLE 了。。。

但是我也是有话要说的啊，这个 vector 在数据小的时候，后面的 size() 都是 0 啊，按理说不该全部 MLE 才对啊，然后交 luogu，发现是 40 分，且前面几个点使用的空间都十分凶险。问就是 STL 的事情少打听。

关键是考场上加上 vector 优化的代码跑大样例好像也没有优化什么时间。我好像也发现了这点，但是为什么最后没有把 vector 删掉呢？我也不是很清楚。

还有，题目中有这样一句话：

请注意，你可能需要 C++ 内置整型以外的类型来存储答案。

然后我就给统计的时候 ans 开了个 long\ long，发现大样例从跑 2500ms 直接飙升至 6500ms，吓得我赶快删掉了（其实是诈骗，答案显然不会爆 long\ long）。

还有就是，考场上突然就不会求 \varphi 了。幸运的是最后还是记起来了，但还是花了30min。这个故事告诉我们一定要牢记模板。

T3

给一棵 n(1 \le n \le 10^6) 个节点有根树的每一个节点赋一个不同的权值 w_i，使得满足 w_u \le w_{lca(u,v)} \le w_v 的点对数最多。

看完题，没有细想，打完 T2 发现时间只有不到 60min 了，就先去打 T4 暴力，打完回来发现有高达 8 分的 next_permutation，然后就开心地过了小样例。然后发现有一条链的情况，快乐输出 0 又骗了 8 分。欸，二叉树的情况好像也可以做啊，直接将给左子树分配的所有权值都严格小于右子树就好了啊。每个点产生 siz[ls] \times siz[rs] 的贡献，又快乐骗 8 分。留 10min 检查 file，欧耶。

T4

给定模式串P，维护文本串S，支持如下操作：

• 在S中间插一个字符串。

• 删除S的某一个区间。

• 将一个区间替换成一个字符串。

• 求区间内某字符出现的次数。

• 求区间内模式串的匹配次数。

最开始把题看错了，以为第三个操作是将区间内的每个字符都替换成同一个字符，这样我们就拥有了区间推平操作。没错，使用 Chtholly\_Tree 解决。然后回来发现题看错了，那么就把这些操作交给伟大的 STL::string 吧！

使用 substr() 函数，简单而快速地骗到暴力分。除开第 5 个操作是 O(n^2) 的以外，其它的操作都是 O(n) 的。

一遍过编译以及所有样例，还跑挺快，最后还有高达 60 分，算是最顺利的一道了。

乐。

说在中间

这次考试暴力的分数是给的很足啊，以至于我 T2 爆零还能勉强上线。让我想起去年的 CSP-S，当时考完下来只有 T2 的暴力分手拿把掐，以为最后只有 60pts 了，结果其它题还都能骗到分。后来老师也说这次模拟赛的还原度很高。看来我还是能在一定容错下拿到 1= 的。但是其他小伙伴挂的分就比较多了，以至于总体排名比较抽象。

也警醒我一定要把能拿的分拿满，毕竟 CCF 脚数据人尽皆知，说不定还有暴力分以外的意外之喜。

正解

T1

直接暴力将一条边权为字符串的边拆成若干条边，满足最后任意两个相邻点的边权都是一个字符。然后直接在新图上跑两种最短路即可。

具体地说，使用 bfs 找出每个点离起点的最短距离，由此将所有点分成若干层。如果要使路径长度最短，则将出现在最短路上的所有点存下来，每次走每层向下一层中最小的边权，直到走到终点；如果要使路径字典序最短，则直接走每层最小边权，直到走到终点。

T2

总的来说就是找一堆性质，肯定不止迭代次数不超过一个值这样的性质。然后分类讨论。

咕。

T3

咕。

T4

咕。