2020牛客多校第二场H-Happy Triangle

\(对查询的边x,分为两种情况 \)

\(第一种,x为最大边,只需要找离x最近且比x小的两条边判断a+b>x就够了,此处可用multiset \)

\(第二种,x不是最大边,那么需要找到一个b,使得b \geq x,b-a<x \)

\(可用平衡树或线段树进行维护,此处用动态开点线段树来解决 \)

\(区间[l, r]权值为min_{x_i \in [l, r]}\{x_i-x_{i-1}\} \)

 

2020牛客多校第二场C-Cover the Tree

\(很明显,记叶子节点数为s,则k=\left \lceil \frac{s}{2} \right \rceil \)

\(那么如何匹配呢?首先要选取一个非叶子节点作为根,然后对其进行dfs得到dfs序\)

\(按照dfs序大小排序得到叶子节点u_1, u_2, …, u_s \)

\(于是u_i跟u_{i+\frac{s}{2}}进行匹配,若s为奇数,则最后一个点跟根节点进行匹配 \)

 

2020牛客多校第二场A-All with Pairs

\(对每个s_i的前缀s_{i, 1…j}进行与所有后缀比较,相同的次数记为res_{i,j},此处可以用哈希进行比较 \)

\(因为要取最大前缀,所以要用kmp求出next数组后res_{i,next[j]} -= res_{i, j},注意一下下标的偏移 \)

\(答案就是\Sigma_{i=1}^n\Sigma_{j=1}^{len_i}j^2res_{i,j} \)

 

2020牛客多校第一场A-B-Suffix Array

\(令c_i=min_{1\leq i < j, t_j=t_i}\{j-i\} \)

\(B数组其实就是c_1 c_2 c_3 … c_n的后缀数组 \)

\(要注意若没有t_j=t_i,则c_i = n,同时c_{n+1} = n+1 \)

\(答案就是后缀数组的逆序 \)

 

计算电压[洛谷P2011]

题目背景

相信不少人轻松灭掉 1,2 两题(蒟蒻无视此句) ,我相信,大家对物理也是很有兴趣的(众人:我们对揍人也是很有兴趣的) ,那么,再奉上 100 分给Physicaler 们。

题目描述

现给定一个电阻网络,已知其中每条边上的电阻,和若干个点和负极之间的电压(电源电压不变) ,现在求任意两点之间的电压。

输入格式

第一行三个数n,m,k,q,表示n个节点(可能是几个点用导线相连接,与一个点等价,编号为1-n,0号节点为电源负极),m个定值电阻,每个定值电阻连接两个点,k表示电源正极有k个接口,有q个询问。

以下k行,每行两整数,表[……]

继续阅读

[LOJ10013]曲线

三分法适合求解凸性函数的极值问题

\(设当前求解的区间为[l, r],令lmid = l+\frac{r-l}{3},rmid = r-\frac{r-l}{3},计算f(lmid), f(rmid)\)

将其中函数值更优的点叫做好点,函数值较差的点叫做坏点

最优点与好点会与坏点同侧,据此缩小区间

\(因为a≥0,所以S是开口向上的二次函数,F(x)=\max \{S_{i}(x)\} 也满足单调性,可用三分法求其区间最小值\)

 

[LOJ10012]Best Cow Fences

\(二分答案,判断是否存在长度不小于L的字段,平均数不小于二分的值\)

\(如果把数列中每个数都减去二分的值,就转化为判定是否存在一个长度不小于L的子段,子序列和非负\)

\(用前缀和维护数列,就可用O(1)的时间查询平均数\)

\(这题由于精度问题,需要先将读入的数乘上1000再整数二分……乘完之后还要开long long\)

 

[LOJ10011]愤怒的牛

求最小距离尽可能大,采用二分答案的方法

\(对二分的最小距离d进行校对,若不满足条件则减小,满足条件则增大\)

 

[LOJ10010]糖果传递

\(设x_{i}为第i个同学从第i-1个同学获得的糖果数,若x_{i} < 0,则第i-1个同学从第i个同学获得-x_{i}个糖果\)

\(特别地,x_{1}为第1个同学从第n个同学获得的糖果数\)

\(均分后,每个同学拥有的糖果为avg = \frac{\sum_{i = 1}^{n}a_{i}}{n},则\)

$$avg = a_{1}+x_{1}-x_{2} \\ avg = a_{2}+x_{2}-x_{3} \\ … \\ avg = a_{n}+x_{n}-x_{1}$$

\(改写一下,有\)[……]

继续阅读

[LOJ10009]钓鱼

\(枚举每一个湖k作为终止点,期间的钓鱼次数则为\frac{60H+5\sum_{i=1}^{k-1} T_{i}}{5}\)

\(要使钓到数量最多,则需要保证每一次钓到的鱼最多,用优先队列维护\)

\(要注意\frac{60H+5\sum_{i=1}^{k-1} T_{i}}{5}>0才能将湖k作为终止湖\)

\(当优先队列最大值为0时直接跳出循环,这一步剪枝很重要!\)