说明:按无序更新,只更(会)水题
4632
题意:求字符串的回文子[序列]个数
区间DP,设\(dp[i][j]\)为\([i,j]\)范围内的回文子序列个数,
由容斥定理可得\(dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]\)
如果\(i\)和\(j\)本身就可以构成回文,那就多增加\(dp[i+1][j-1]+1\)个回文子序列(1代表只含\(i,j\)的子序列)
https://paste.ubuntu.com/p/Sjh9c9K9H7/
6315
题意:给出a,b数组,区间上两种操作,给\(a[L,R]\)+1s,或者求\(\sum_{i=l}^{r}a_i/b_i\)
一看就知道是吉司机乱搞型线段树(低配版),暴力剪枝就好
维护区间a的最大值和b的最小值,如果存在相交的部分则证明可能产生新的贡献,
此时暴搜到叶子把可能的a置回0并加上贡献就好
然后疯狂TTTT
网上搜了一波题解好像说是会改变lazy的判断?(虽然觉得没有道理但是我认(怂)了
于是换一种策略,既然lazy依赖与a的最值,那我们尽量不碰它,改为b的值翻倍
然后过了(???)
https://paste.ubuntu.com/p/3YnKKvQf68/
4630
题意:给定\(a[1...n]\),多次询问\([L,R]\)中的任意一对数使得\(gcd(a_i,a_j)\)最大
对于gcd,区间内至少存在两个相同的因子才能作为合法的解,存在两个相同因子且最大就是最优的解
对区间右端点进行离线排序,用线段树维护\([L,R]\)内最大的gcd(存在两次以上的因子)
具体的更新策略:记录因子\(j\)的上一次出现的地方\(last_j\),当\(last_j\)已存在时再插入\(last_j\)就能维护两次以上的信息,离线处理保证了后面的因子不会插入到当前查询范围的某个\(last_j\)中,具体看代码
https://paste.ubuntu.com/p/SzGh3DCpt3/
6133
题意:给出一棵树共\(n\)个顶点,每个顶点有一个权值\(val_i\),你需要对每个节点统计一个最优解
每个节点的解按照一定规则产生:取出该节点的子树下所有的顶点,把顶点任意排序成一个序列,设为\(v_1,v_2...,v_k\)
此时解为\(\sum_{i=1}^{k}\sum_{j=1}^{i}val_{v_j}\),最小的解为最优解
对于每个解的处理来说,子树下值小的顶点肯定放前面,按这样来贪心无疑是正确的(前缀贡献尽量小)
那么对于无序的插入过程,当前节点\(u\)的贡献为\(val_u+cnt+num*val_u\)
其中\(cnt\)为当前小于\(val_u\)的数字和,\(num\)为当前大于等于\(val_u\)的个数和
因为是子树问题，用树状数组暴力合并答案,复杂度\(O(nlog^2n)\)
https://paste.ubuntu.com/p/YCYKwxjMjS/
6096
题意:给定n个字符串,m次询问,每次询问多少个字符串前缀是pre且后缀是suf,前后缀不可相交
字典树同时存储前后缀,假设字符串长为len则更新2*len个节点,依次按s[0],s[len-1],s[1],s[len-2],s[2]...更新
对于询问,按pre[0],suf[len2-1],pre[1],suf[len2-2],...pre[len1-1],suf[0]查询
如果前后缀不等长则用特殊字符填充,询问若碰到特殊字符就当前层暴搜(由于后一层前后缀肯定存在确定字符,所以不会被卡)
必须要确保的是询问时字典树中任一字符串必须长度大于等于当前查询的前后缀长度和(xxx xx xx非法)
因此需要离线处理
时间复杂度\(O(能过)\)
https://paste.ubuntu.com/p/rWTpqp2tyT/
5039
题意:给定一棵树,树上有边权0和1,两种操作,求树中路径异或和为1的数量,修改边权
边的异或可表示为\((u,v)=(1,u)xor(1,v)\)
所以用节点来表示根到当前节点的路径异或和
修改一条边就变为修改改节点及子树所有节点的01值
查询直接往根查询0和1的数量相乘再翻倍(方向)即可
https://paste.ubuntu.com/p/NHZMcmWgbB/
4336
题意:N个物品,每次得到第i个物品的概率为pi,而且有可能什么也得不到,问期望多少次能收集到全部N个物品
期望采取倒推,\(dp[S]\)表示由状态S到全部收集的期望步数
\(dp[S]=(1-\sum_jp_j)dp[S]+\sum_jp_j*dp[S|1<<j]+1\),其中S不包括j
https://paste.ubuntu.com/p/szmqCbK6Sx/
4339
题意:给定不等长字符串s1,s2,两种操作,1对某一字符串修改单一字符,2询问从下标k开始匹配的子串最长的长度
昨天用线段树合并左区间疯狂WA,模了一下别人家的树状数组+二分的做法
对于s1[i]!=s2[i],则在树状数组中+1
这样对于询问只需二分最大的sum[x]-sum[k-1]==0即可
也就是说本身无序的数换做前缀就可以进行有序的处理
https://paste.ubuntu.com/p/gmdWXtqDBZ/
6356
题意:已知数组\(a[1...n]\)为0,m次更新\([L,R]\)使得\(a_i=max(a_i,v),L≤i≤R\),\(n≤100000,m≤5000000\),数据随机
线段树beats,树内维护区间最大值和最小值
最小值大于等于v和最大值小于等于v作为剪枝的依据,若不符合剪枝则暴搜
还有一种做法是可以update的ST表,感觉不错,待补充
https://paste.ubuntu.com/p/DpMKMNQQk6/
牛客练习赛24 - 凤凰(乱入
题意:树边容量为1,每个节点有1的流量,问花多少时间能把所有流量流到节点1
只看根节点下的每一条邻边的话,可以观察得出每条贡献1只凤凰,那么最高时限肯定是是根以外的最大子树
虽然很水但还是记一下吧