NOIp总结——第一次参加NOIp非正式选手

luobobei · 2024-11-30 19:14:24 · 生活·游记

进考场时，什么都不熟悉。感觉下面都是大佬，我什么都不会。

T1一上来开幕雷击。我开始想了一个贪心，将两个字符串通过固定字符分成区间用结构体存储，再贪心遍历一遍数组，当其中一个字符串固定字符但另一个没有，并且另外一个字符所在区间有可以与固定字符串匹配的字符就移动并且分割区间，但是我没有考虑到分割区间时两个区间0和1的分布情况，我按照原字符串分割就 \small\color{red}WA 了，写了350多行代码，用了3个小时没写出来。听别人说，T1用了DP+并查集A了大样例，但是我想不出来怎么用并查集。
T2开始写时考试时间就只有一个半小时了。我看了题目想不出来正解，就骗了 m=0 的分。当 m==0 时，没有限制，每一个二元条件都是 v^2 的可能，总可能性为 v^{2\times n-2} 总可能。应该考虑进行递推，若区间的长度可以方下 x 个二元限制，则 f(x) 为方案数， f(x)=v^{2x}-v^{2x-2}+v^2\times f(x-2) ，进行递推得 f(x)=v^{2x}-v^x+v^{x-1} 。最后把每两个箱子之间的情况乘起来即可。
T3紫题，没有思路。题解说 k=1 时可以确定路径，想一想也是。答案是 \Pi_i(d_i-1)! 。当 k=2 会重算 \Pi_{u\in path(x,y)}(d_u-2)! 扣除重复。最后通过神奇的树型结构的推导与dfn，转移子树内算重的方案数 g_u 为 g_u+(f_v(d_u-2)!(当(u,v)为关键边))或g_v(d_u-2)!。来自父亲的贡献从上往下递推，即可得到。
T4数据结构题，需要用到线段树。我对线段树并不熟悉，只是知道简单线段树模版。要将预处理出的线段树上每个节点表示为区间的全部答案。考虑建立一个平面，表示左端点到 m 的距离和右端点到 m+1 的距离。权值 a_i 表示 [i,m+1] 范围内 LCA 的深度。

总结这次比赛，考了非常多关于树的知识，比如并查集、线段树(合并)、LCA等。日后的学习对树型结构的认识有待加强。虽然这次只是体验，但是能体现出对信息学学习要更加认真，并且要学好数学，建立数学模型，进行推导。