NOIP day 1
T1
简单建图跑 bfs,vector 会被卡空间,用前向星才能过。
T2
注意到原串是否确定不重要,因为无非是把每种可能的转移都多做一遍。
把所有可能出现的回文串的一半插进 AC 自动机中,就可以转移了。
CSP day 1
T3
设 \(nxt_i\) 表示下一个与 \(a_i\) 值相同的位置到 \(i\) 的距离,两个串相等当且仅当 \(a_i\) 相等,哈希维护之即可。
T4
NOIP day 2
T1
发现这玩意是一个类似字典序的东西,每次贪心取最靠前的最小值即可。
T2
经典结论:到 \(u\) 最远的点是直径的端点。可以反证,如果不是,存在比直径更长的路径。
于是只要维护直径就可以了。
但是有人看到距离就想到了点分树。跳祖先时,在每个点处维护两个二元组 \((mx, pl)\),表示 \(pl\) 子树内距离 \(u\) 最远的点的距离为 \(mx\),需要保证两个 \(pl\) 不相同。查询时一边跳点分树祖先一边更新答案,存两大值是为了保证查询点和更新点不在当前点的同一棵子树内。
T3
只考虑差分数组,转化题意为:\(n\) 张卡牌,翻转有代价 \(1\),翻最少次使得朝上的面的数字两两不同。
这不就是填数游戏吗 但是你没做过。基环树是容易枚举环方向做的,树的话做一个换根 dp。
但有人没想到啊。左边是卡牌右边是值,设一张牌正面为 \(a_i\) 背面为 \(b_i\),则 \(i \to a_i\) 连容量 \(1\) 费用 \(0\) 的边,\(i \to b_i\) 连容量 \(1\) 费用 \(1\) 的边,这里两边用了 一样的标号,跑一个费用流。卡卡卡是能过的。
T4
分治,求前后缀 \(\min\),枚举产生贡献的点在 \(mid\) 的哪一侧,找两个函数的交点。
标签:NOIP,ZR,距离,day,2024,七连,CSP,pl From: https://www.cnblogs.com/purplevine/p/18403108