水题记录(二)

10 / 10

##简单题

题意:给出矩形,支持给矩形中点加值和询问子矩形的和。

题解:如果空间大的话可以考虑用std::map的树状数组,但是只有$20MB$还要在线就只有$KDTree$可以做了。单点修改的时候直接加入一个$(x,y)$权值为$w$的点,维护矩形的和即可,简单题。

SJY摆棋子

题意:动态加点,询问最近点

题解:$KDTree$查询最近点对,写个曼哈顿距离的估价函数,查询的时候剪枝,注意对于子树的点,先查近的再远的,插入复杂度$O(nlogn)$,查询复杂度$O(n\sqrt n)$。

最佳团体

题意:给出一棵树,选儿子必须选父亲,求选$K$个人的总收益除总花费最高

题解:二分一个答案$mid$
$$
mid <= \sum p_i / \sum s_i
$$

$$
\sum p_i – \sum s_i * mid >=0
$$

$$
max{\sum (p_i – s_i * mid)} >= 0
$$

可以把每个点的权值看成$p_i-s_i*mid$,然后求这个$max$即可,可以树形$DP$

Hamming Triples

题意:给出$m$个长度为$n$的递增或者递减的$01$串,求三元组$(a,b,c)$,使得两两汉明距离的和最大,问最大的方案数

题解:首先考虑子问题,怎么求最大的和?注意到答案就是三个串完全相同的部分的长度乘2,我们可以确定答案的上界是$2 \times n$,考虑最小化这个完全相同的长度,可以使用二分或者$2-pointer$解决。考虑方案的计算,只需要维护每个串在对应的位置出现的次数,使用组合数的简单知识计算就可以了。代码细节很多,比较难打,错一点就全错。

序列的故事

题意:给出一个串,多次询问求区间最小循环节。

题解:如果知道长度,判断循环节的方法是判断$[l+len,r]$和$[l,r-len]$是否相等即可推出是否能构成循环节。

所以显然可以得到$O(q \sqrt n)$的做法:枚举长度每个因数,$Hash$或者后缀数组检验,会T

进一步的考虑,把一个串可以分成两份,可以分成三份,一定可以分成六份。也就是说我们只需要计算它的质因数能否进行分解,于是把复杂度降低到$O(qlogn)$

JC loves Mkk

题意:求一个环上的长度为$[L,R]$之间的糖果的美味度的平均值,个数要求是偶数。

题解:

先二分一个答案。
$$
max { \frac {\sum p} {num}}\geq mid \
\sum p-mid * num \geq 0 \
\sum (p – mid) \geq 0
$$
求$\sum(p-mid)$这个东西,也就是求一个连续的最大子段和,单调队列优化DP即可。记录转移方案,对于长度是偶数的限制,可以分开DP,奇数开头奇数结尾DP一遍,偶数开头偶数结尾DP一遍。总复杂度$O(nlogn)$

POJ Challenge 我爱你啊

题意:求一个串最多在另一个串中成为子串的个数(自己去看题

题解:for一遍没了,太水了

NOI2002 Savage

题意:环形山洞初始有一些野人,野人有寿命和每年移动的距离。求最小的山洞个数使得没有两个野人同时在一个山洞里,保证答案不超过$1e6$

题解:注意到没有单调性,想了好久都不会低于$O(1e6 * n^2)$的做法,只能看题解,发现都是$O(1e6*n^2)$的。

就暴力枚举答案,暴力判断相撞。
$$
C_i + year \times dis_i \equiv C_j + year \times dis_j (mod m) \
year \times (dis_i + dis_j) \equiv C_j – C_i (mod m)\
year \times (dis_i + dis_j) + temp * m = C_j – C_i
$$
解个方程就好了。

BJOI2015 树的同构

题意:给出$m$棵树,问最小的和它同构的树的编号。同构的定义是:跟换序号得到的树相同。

题解:对一棵树进行$Hash$,对于下图中这样的树,先对子树的$Hash$值进行排序,然后类似序列hash的方法计算当前树的Hash值


$$
NOW = H_1 * BASE ^ 3 + H_2* BASE ^ 2 + H_1* BASE + ONE
$$
这里的$BASE$和$ONE$都是自己定义的。对于一棵树,将它的每个点作为$root$计算一遍$hash$值,然后整体再$sort$一遍,对于同构的树,这样构造出的$Hash$是完全相同的。

Number

题意:有N个正整数,需要从中选出一些数,使这些数的和最大。若两个数a,b同时满足以下条件,则a,b不能同时被选 1:存在正整数C,使$a\ times a + b \times b=c \times c$ 2: $gcd(a,b)=1$

题解:之前把题看成两个之间任意一个满足就不行,写了个并查集,然后WA了,发现要求同时满足。把每个点拆成两个,不能同时选的连$INF$,最小割就好了。

Leave a Reply

Your email address will not be published. Required fields are marked *