avatar-decorate
lifehappy level
获赞
594
粉丝
42
关注
43
看过 TA
52
江西师范大学
2023
后端
IP属地：广东
暂未填写个人简介
私信
关注
发布(88) 评论 刷题 收藏
头像
2022-03-19 16:15
已编辑
江西师范大学 后端
美团笔试 3.19（AK代码）
A （暴力）   找到最大的满足折扣的券，然后判断即可。   #include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 10; int a[N], b[N], c[N], d[N], n, m; signed main() {   cin >> n;   for (int i = 1; i <= n; i++) {     cin >> a[i];   }   for (int i = 1; i <= n; i++) {     ...
流火七月：好强
投递美团等公司9个岗位
0 点赞 评论 收藏
分享
头像
2021-04-27 20:14
江西师范大学 后端
小 Q 与树（dsu on tree + segment tree）
小 Q 与树 给定一棵带权的树，每条边的距离都为，要我们求，  如果考虑 dsu on tree，则是枚举，分两种情况统计答案：  ，则，则我们只要知道集合中有多少个点，以及即可，  设点的个数为，，则上式等价于。 ，则，则我们只要知道，以及即可求得答案，  上式等价于。  所以可以对点权离散化，然后用线段树来维护上面需要的四个值，即可进行 dsu on tree，整体复杂度。 由于上面的统计我们都是进行的单向计算，所以还要对上述计算完后的答案乘以即可。 #include <bits/stdc++.h> #define ls rt << 1 #define rs rt ...
0 点赞 评论 收藏
分享
头像
2021-03-23 20:01
江西师范大学 后端
min_25推导及例题总结
min_25 筛 一个亚线性筛，复杂度大概是。 使用求前缀和，有两个基本特征：① 积性函数，② 满足质数点为多项式。 算法思路 给定，设为一个积性函数，质数点为多项式，求。  先求出内的所有质数，以及。 求出，为第个质因子。  我们设，质数或者最小质因子大于的值之和。  考虑从推到，我们也就是要减去最小质因子等于的贡献， 考虑如何递归计算积性函数前缀和。  设，最小质因子大于等于的值之和，所以这个积性函数的前缀和即为。  对于，中质数的贡献我们是已知的，接下来考虑计算合数对答案的贡献。  我们枚举合数的最小质因子以及最小质因子的次幂，考虑从推到，也就是在原来的基础上加上，  所以有  这里的是...
0 点赞 评论 收藏
分享
头像
2021-03-22 23:13
江西师范大学 后端
牛客挑战赛48 E 速度即转发 （树套树）
速度即转发 给定一个长度为的数组，里面元素为。 有两种操作：  修改。 给定，设，求内满足的最大整数。  保证任何时刻数组值域在，对于查询操作。 有个简单的想法树状数组套主席树，对于操作一，直接修改即可，对于操作二，二分答案， 显然三个的算法，复杂度有点大可能过不了，考虑在线段树上二分答案， 假设我们当前所在的区间是，显然左子树代表的值域范围是，右子树所代表的是， 如果答案在右子树，则答案最少为，这个时候只要判断是否有即可， 如果成立，则说明答案最少为我们可以进入右子树搜索，否则我们进入右子树搜索，最后我们到达的叶节点即为最优的答案 我们在递归的时候，两个变量，当我们进入左子树的时候，把右子树...
0 点赞 评论 收藏
分享
头像
2021-03-20 21:48
江西师范大学 后端
苍天阻我寻你，此情坚贞如一（线段树 + 二分）
苍天阻我寻你，此情坚贞如一 给定两个长度为的数组，满足，每个数字表示向前走步，如果是负数则后退嘛，设小执行数组，小执行数组。 有三种操作：  把数组中下标为的数修改为。 把数组中下标为的数修改为。 如果小起始位置在，小起始位置在，问如果他们各自按照数组执行，在第几步能够行动轨迹重合。  如何判定行动轨迹重合： 假设小走过的区间为，小走过的区间为，如果重合则有， 接下来如何确定小和小走过的区间，设数组的前缀和数组为，数组的前缀和数组为， 数组的前缀最小，前缀最大值数组为，数组的前缀最小，前缀最大值数组为， 由小，小的初始位置，可以确定。 所以有一个较为暴力的算法 二分 + 线段树 去答案，当时这...
0 点赞 评论 收藏
分享
头像
2021-02-21 21:50
已编辑
江西师范大学 后端
2020 ICPC 济南 F. Gcd Product
Gcd Product 观察式子，不难发现，二者对于给定的都是可以确定的，跟变量无关， 设，得到， 接下来我们考虑化简。 ，则，可得： 同余方程。 由，则，所以。 由，则，因为，所以有。 所以，分别在膜下有且只有唯一解，有， 可得，要使， 相当于在的基础上给组合分配，凑得。 设，所以解的个数就是，则有： 先做一次迪利克雷卷积得到，再做一次互质迪利克雷卷积得到，最后迪利克雷卷积得到答案。 #include <bits/stdc++.h> using namespace std; const int N = 5e5 + 10, mod = 998244353; int prime[N]...
0 点赞 评论 收藏
分享
头像
2021-02-02 13:53
江西师范大学 后端
0 点赞 评论 收藏
分享
头像
2020-12-22 17:52
已编辑
江西师范大学 后端
[HNOI2017]礼物
[HNOI2017]礼物 我们要使最小，我们能对两个序列进行一些操作。 对序列的操作，我们得到。 对序列的操作，我们得到。 有，得到$a, u一定是一个定值， ，其中也一定是一个定值，然后这就是一个开口向上的二次函数有极小值，可分类讨论求得， 接下来我们考虑如何求解的最大值了 由于我们可以对其中任意的一个串循环移动，假设我们对逆时针移动次，上式就变成了。 要是是一个定值就好了，这就是多项式相乘的某一项，我们就能通过求解，从这一点出发，我们构造为一个常数。 另，有，上式有，， 对于确定的，这就是一个多项式相乘的某一项了，我们把数组加倍，然后求一次就能得到所有的答案了， 当然为了运算方遍我们得提前...
0 点赞 评论 收藏
分享
头像
2020-12-22 17:50
江西师范大学 后端
Jamie and Tree
Jamie and Tree  操作一  直接更新；  操作二  第一步先找，这时有一个结论中最深的，然后分情况讨论。 不在的子树上:  直接区间更新 在的子树上:  先把整棵树更新一遍+x，然后找到路径上与的儿子节点，然后更新他的子树-x  操作三:  不在的子树上：  直接 在的子树上:    类似操作二。   最后，操作二要特判一下，操作三要特判一下，这个时候直接修改或者查询整个的区间。 #include <bits/stdc++.h> #define mid (l + r >> 1) #define lson rt << 1, l, mid #def...
0 点赞 评论 收藏
分享
头像
2020-12-22 18:02
已编辑
江西师范大学 后端
小V和gcd树
小V和gcd树 树上问题，每次询问与两点有关，可以确定应该使用树链剖分来求解了。 这个问题中涉及到边的查询，树链剖分中有一个很常用的操作就是边权下放到点权上， 但这个操作一般是对有根树而言的，当然我们虚拟号节点为跟节点也是一样的。 我们假设这棵树的根节点为号节点，然后把所有的边权下放到其对应的节点上（1号节点所代表的边权就为空了）。 对于查询操作：查找，用树链剖分在最短路上跳转遍历所有的边，然后统计答案。 对于修改操作：查找，对于每个节点，我们需要修改其与父节点的权值，其与儿子节点的权值。 但是这样只能过的测试点，所以考虑如何优化。 查询操作是无法优化了，我们只能考虑如何简化修改操作毕竟是无法...
0 点赞 评论 收藏
分享
头像
2020-12-22 17:48
江西师范大学 后端
Beautiful Subarrays
Beautiful Subarrays 有 所以我们可以先求一遍异或前缀和，然后再通过枚举右端点，去查找有多少个左端点符合要求。 假设我们当前枚举到这个位置，前个数的异或前缀和是，我们要查找异或值大于等于的, 这里我们可以去找一个，满足，这个时候大于等于的数就是满足要求的数了， 这个操作我们可以通过一颗树来实现。 分四种情况:  a 的当前位二进制数是0，k的当前位二进制数也是0，如果我们选择一个数的当前位是1，  与a异或之后会变大，的位对答案有贡献，所以我们加上答案，然后到当前位上是0的地方去继续寻找。 a的当前位二进制数是0， k的当前位二进制数是1，我们要使查找值不变小，一定要到当前位...
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了：
牛客网
牛客网在线编程
牛客网题解
牛客企业服务