省流
跳题的胜利，跳 D 写 E 打出 cf 表现分 \(1750\)。
10.18
内含剧透，请vp后再来。
不是题解！！！！！！！
赛前
好困好困好困好困好困。
赛时
A 模拟不谈。
B 模拟不谈。注意可以用个 map 存出现过的字符串很方便。
C 题有两个操作，往栈内加入一个新的括号或者删掉栈顶，输出现在是否括号匹配。那么可以把左括号视为 \(1\)，右括号视为 \(-1\)，总和为 \(0\) 时才可能匹配，而匹配要求所有右括号左边都有自己的左括号，所以当总和出现过一次负的之后，后面所有的情况都不可能匹配。按照这个模拟就行。
D 题看了一眼感觉很数学，同时发现 E 题的评分差不多，于是决定先看一眼 E。
E 题求一颗树上每个点距离最远的点的编号。做两次 dp，第一次从下往上算出每个点内部子树最远和次远的点和距离，第二次从上往下，先传递父节点除了这个子树内的最远节点（如与子树根节点最远节点相等则传入父节点的次远节点），然后判断这个子节点在整个树上的最远和次远节点，然后继续传下去即可。比较显然的树上 dp。
回看 D 题，题目给了两个数 \(a\) 和 \(b\)，要求选择一个数 \(1 \leq x \leq b\)，使 \(a\) 和 \(a + x\) 拼接起来的数是一个完全平方数。设 \(a + x\) 的长度为 \(t\)，可以得到
于是我选择直接对每一个 \(t\) 算出 \(x\) 的上下限，然后枚举上下限内的所有 \(y\)，果不其然轻而易举的 TLE 加 WA，时间就结束了。
赛后
赛后补题，发现 WA 的原因是上限没考虑 \(b\)，而 TLE 则是有更好的。已经计算出上下限，而小于一个数的完全平方数的个数就是这个数开方，然后就可以利用类似前缀和的思想算出这个数。以及注意要使用 sqrtl 来用 long double 开方。
2025年10月20日