lifehappy

分类

未归档(1) 每日一题(2) 题解(78)

/ 注册

全部文章（共81篇）

小 Q 与树（dsu on tree + segment tree）

小 Q 与树给定一棵带权的树，每条边的距离都为，要我们求，如果考虑 dsu on tree，则是枚举，分两种情况统计答案：，则，则我们只要知道集合中有多少个点，以及即可，设点的个数为，，则上式等价于。，则，则我们只要知道，以及即可求得答案，上式等价于。所以可以对点权离...

2021-04-27

10 730

小 Q 与函数求和 1

小 Q 与函数求和 1 所以预先处理次幂，及，即可同时算得，以及，整体复杂度，稍卡常，得写 add sub 函数才能过。 #include <bits/stdc++.h> using namespace std; const int N = 5e6 + 10, mod = 99824...

2021-04-27

2 926

min_25推导及例题总结

min_25 筛一个亚线性筛，复杂度大概是。使用求前缀和，有两个基本特征：① 积性函数，② 满足质数点为多项式。算法思路给定，设为一个积性函数，质数点为多项式，求。先求出内的所有质数，以及。求出，为第个质因子。我们设，质数或者最小质因子大于的值之和。考虑从推到，我们也就是...

2021-03-23

2 868

牛客挑战赛48 E 速度即转发（树套树）

速度即转发给定一个长度为的数组，里面元素为。有两种操作：修改。给定，设，求内满足的最大整数。保证任何时刻数组值域在，对于查询操作。有个简单的想法树状数组套主席树，对于操作一，直接修改即可，对于操作二，二分答案，显然三个的算法，复杂度有点大可能过不了，考虑在线段树上二分答案，假设我...

2021-03-22

2 733

苍天阻我寻你，此情坚贞如一（线段树 + 二分）

苍天阻我寻你，此情坚贞如一给定两个长度为的数组，满足，每个数字表示向前走步，如果是负数则后退嘛，设小执行数组，小执行数组。有三种操作：把数组中下标为的数修改为。把数组中下标为的数修改为。如果小起始位置在，小起始位置在，问如果他们各自按照数组执行，在第几步能够行动轨迹重合。如何判定行动...

2021-03-20

8 688

2020 ICPC 济南 F. Gcd Product

Gcd Product 观察式子，不难发现，二者对于给定的都是可以确定的，跟变量无关，设，得到，接下来我们考虑化简。，则，可得：同余方程。由，则，所以。由，则，因为，所以有。所以，分别在膜下有且只有唯一解，有，可得，要使，相当于在的基础上给组合分配，凑得。设，所以解的个数就是，则...

2021-02-21

4 1270

[HAOI2006]旅行COMF

[HAOI2006]旅行COMF 根据数据范围求解，有，好了，直接暴力贪心地选择一段值连续的边，然后判断是否联通即可。所以我们只要预先对边按照排个序，然后用并查集判断是否联通即可。 #include <bits/stdc++.h> using namespace std; cons...

2021-01-14

3 856

New Year Tree

New Year Tree 首先看到颜色的范围是，容易想到用二进制数来存储，二进制的第i位表示是否有第i种颜色接下来我们只要求得整棵树的序，然后维护一个异或线段树即可，支持区间修改，区间查询即可，比较套路的裸题吧。 #include <bits/stdc++.h> #define mi...

2021-01-13

1 836

小M和天平

小M和天平能称得给定的质量，大致有两种情况，一、给定的石子直接组合可以得到物品的质量，这就可以通过背包来直接得到了。二、（一些石子 + 物品） = （另一些石子），也就是能够从石子中挑出两堆，这两堆的差值为我们所需称量的。 #include <bits/stdc++.h> usin...

2021-01-08

2 871

[HNOI2017]礼物

[HNOI2017]礼物我们要使最小，我们能对两个序列进行一些操作。对序列的操作，我们得到。对序列的操作，我们得到。有，得到$a, u一定是一个定值，，其中也一定是一个定值，然后这就是一个开口向上的二次函数有极小值，可分类讨论求得，接下来我们考虑如何求解的最大值了由于我们可以对其中任意...

2020-12-22

4 818