30 D. The BOSS Can Count Pairs (根号分治)

陈小白     2023.05.30     算法相关     抢沙发     391人打酱油
题目链接:https://codeforc.es/contest/1831/problem/D 大意是给出两个长度为n的数组a和b,确定存在多少个i和j,使得ai*aj=bi+bj,ai和bi范围在n以内。 考虑根号分治。 不太好求解,但是数据范围是有限的,通过题意我们可...

26 ACM真题/杂题

陈小白     2023.05.26     算法相关     抢沙发     272人打酱油
题目链接:https://codeforc.es/gym/444200/problem/F 大意是存在一个类字符串为ababa,修改为类似马拉车算法的,&|a|b|a|b|a|,给出每个位置以它为中心的回文半径的长度。 构造一个仅包含a和b的字符串,满足输入的2*n+2...

03 松鼠的新家 LCA+树上差分

陈小白     2023.05.03     算法相关     抢沙发     269人打酱油
题目链接:https://www.luogu.com.cn/problem/P3258 大意:从a1走到an,所经过的位置+1,求每个位置的值。 重点在于利用lca进行树上差分,考虑对于x走到y,令x走到公共祖先的点+1,y走到公共祖先的点+1。公共祖先只加一次,所以减去,公共...