2023NOIP A层联测26 总结

联测26 总结"/>

2023NOIP A层联测26 总结

T1 求 ∑ i = 1 n ∑ j = i n ( ⨁ k = i j a k ) 2 \sum\limits_{i=1}^n\sum\limits_{j=i}^n\left(\bigoplus\limits_{k=i}^{j}a_k\right)^2 i=1∑n​j=i∑n​(k=i⨁j​ak​)2， n , a i ≤ 2 × 1 0 5 n,a_i\le2\times10^5 n,ai​≤2×105。先转成前缀和，然后就没思路了，直到快 9 点才发现 a i a_i ai​ 很小，大概 9 点半想到了 FWT 应该能做，然后5min回忆了一手，10min 码完，又开了 long long，检查了一会，去看 T2。结束后发现 WA 了，去检查发现 FWT 的数组应该是开到值域不是 n n n。题解的做法看不懂，赛时想过，但是有个地方不会搞。

T2 有 m m m 道题， n n n 个人中第 i i i 个人会 l i ∼ r i l_i\sim r_i li​∼ri​ 道，随机取一个区间的人去做题，问期望做出几道题， n ≤ 1 0 6 ， m ≤ 1 0 18 n\le10^6，m\le10^{18} n≤106，m≤1018。没什么思路，想歪了，考虑区间更新时会做题数的变化，后面直接去看 T3 了，最后打暴力时间回来写线段树暴力，写完还剩10min。题解做法是先考虑可重的，再用线段树减去重复的贡献。

T3 有 n n n 个点，每个点有点权 a i a_i ai​， q q q 次询问有两个操作，操作 0 0 0，连边 ( x , y ) (x,y) (x,y)，保证 x , y x,y x,y 不连通，操作 1 1 1 从 x x x 走到 y y y，问对于路径上的每个点是否点权不大于之前走过的点权之和，部分数据强制在线， n ≤ 1 0 5 , q ≤ 5 × 1 0 5 n\le10^5,q\le5\times10^5 n≤105,q≤5×105。首先发现了离线时可以先建好树再做询问，然后想能不能预处理出每个点到最近的祖先满足之间的点都满足条件，想了好久发现好像没什么性质，就打了20pts暴力。题解是巧妙的主席树+启发式合并。

T4 f ( i , j ) , g ( i , j ) f(i,j),g(i,j) f(i,j),g(i,j) 表示树上 i , j i,j i,j 路径的点权与，点权或，求 ∑ i = 1 n ∑ j = i n f ( i , j ) g ( i , j ) \sum\limits_{i=1}^n\sum\limits_{j=i}^nf(i,j)^{g(i,j)} i=1∑n​j=i∑n​f(i,j)g(i,j)，模 111121 111121 111121， n ≤ 1 0 5 n\le10^5 n≤105，叶子数量 ≤ 100 \le100 ≤100。直接上树剖暴力，大概打了20min，过了给的样例，结果最后 5min 发现手造hack 数据过不了，就急忙去检查，结果挂分了。题解用了叶子数量和与或的性质，tql。

期望得分：100+12+20+17=149

实际得分：70+12+20+7=109

总结：不要想当然，搞清楚变量的作用。检查时间要再给多一点，20min左右。技巧：树上信息维护可以考虑根到节点的信息，然后lca，期望->方案数。检查时间要造几组hack数据。对于模板相关实现还是不够熟练润用，noip赛前复习。