lifehappy - 个人主页动态 - 牛客网

发布(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++...

流火七月：好强

投递美团等公司10个岗位 >

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...

0 点赞评论收藏

分享

2021-04-27 14:28

江西师范大学后端

小 Q 与函数求和 1

小 Q 与函数求和 1 所以预先处理次幂，及，即可同时算得，以及，整体复杂度，稍卡常，得写 add sub 函数才能过。 #include <bits/stdc++.h> using namespace std; const int N = 5e6 + 10, mod = 998244353; int prime[N], inv[N], phi[N], mu[N], f[N], g[N], a[N], n, k, cnt; bool st[N]; inline int add(int x, int y) { return x + y < mod ? x + y ...

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...

0 点赞评论收藏

分享

2021-02-02 13:53

江西师范大学后端

#我的牛年守护神# 冲冲冲，拿牌进厂

0 点赞评论收藏

分享

2021-01-14 15:57

江西师范大学后端

[HAOI2006]旅行COMF

[HAOI2006]旅行COMF 根据数据范围求解，有，好了，直接暴力贪心地选择一段值连续的边，然后判断是否联通即可。 所以我们只要预先对边按照排个序，然后用并查集判断是否联通即可。 #include <bits/stdc++.h> using namespace std; const int N = 5e3 + 10; struct Edge { int x, y, w; Edge(int _x = 0, int _y = 0, int _w = 0) : x(_x), y(_y), w(_w) {} void read() { scanf("%d ...

0 点赞评论收藏

分享

2021-01-13 19:48

已编辑

江西师范大学后端

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

0 点赞评论收藏

分享

2021-01-08 13:39

江西师范大学后端

小M和天平 能称得给定的质量，大致有两种情况，一、给定的石子直接组合可以得到物品的质量，这就可以通过背包来直接得到了。 二、（一些石子 + 物品） = （另一些石子），也就是能够从石子中挑出两堆，这两堆的差值为我们所需称量的。 #include <bits/stdc++.h> using namespace std; const int N = 1e4 + 10; int dp[N], a[N], n, m, sum; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", ...

0 点赞评论收藏

分享

2020-12-22 17:52

已编辑

江西师范大学后端

[HNOI2017]礼物

[HNOI2017]礼物 我们要使最小，我们能对两个序列进行一些操作。 对序列的操作，我们得到。 对序列的操作，我们得到。 有，得到$a, u一定是一个定值， ，其中也一定是一个定值，然后这就是一个开口向上的二次函数有极小值，可分类讨论求得， 接下来我们考虑如何求解的最大值了 由于我们可以对其中任意的一个串循环移动，假设我们对逆时针移动次，上式就变成了。 要是是一个定值就好了，这就是多项式相乘的某一项，我们就能通过求解，从这一点出发，我们构造为一个常数。 另，有，上式有，， 对于确定的，这就是一个多项式相乘的某一项了，我们把数组加倍，然后求一次就能得到所有的答案了， 当然为了运算方遍我们得提前...

0 点赞评论收藏

分享

2020-12-22 17:50

江西师范大学后端

Jamie and Tree 操作一 直接更新； 操作二 第一步先找，这时有一个结论中最深的，然后分情况讨论。 不在的子树上: 直接区间更新 在的子树上: 先把整棵树更新一遍+x，然后找到路径上与的儿子节点，然后更新他的子树-x 操作三: 不在的子树上： 直接 在的子树上: 类似操作二。 最后，操作二要特判一下，操作三要特判一下，这个时候直接修改或者查询整个的区间。 #include <bits/stdc++.h> #define mid (l + r >> 1) #define lson rt << 1...

0 点赞评论收藏

分享

2020-12-22 18:02

已编辑

江西师范大学后端

小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 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务