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

发布(349) 评论刷题收藏

2021-04-21 11:35

已编辑

江西师范大学后端

完全二叉树的后序遍历转层序遍历

因为是完全二叉树，所以可以用数组模拟，原理同树状数组。 后序遍历倒过来就是根-右-左。数据结构课上也是这样建树的。 #include <bits/stdc++.h> #define sc(x) scanf("%d", &(x)) #define pr(x) printf("%d ", x) using namespace std; typedef long long ll; const int N = 1e5 + 7; const ll mod = 1e9 + 7; int post[N], a[N]; int n, p = 1; v...

算法竞赛之路

0 点赞评论收藏

分享

2020-11-27 22:20

已编辑

江西师范大学后端

九九乘法表，划掉对角线，前缀和优化。完事。 class Solution { public: static const int mod = 1000000007; typedef long long ll; vector<int> getSum(vector<int>& a, vector<int>& query) { ll size = a.size(), n = query.size(), x; ll sum[100007], tmp[100007]; sum[0] = tmp[0] = 0; vector<int> ans;...

算法竞赛之路

0 点赞评论收藏

分享

2020-11-27 21:17

江西师范大学后端

牛牛摆玩偶二分

二分间距然后模拟即可 class Solution { public: typedef long long ll; static bool cmp(const Interval& a, const Interval& b) { return a.start < b.start; } bool chk(int n, int m, const vector<Interval>& a, int d) { int x = a[0].start, endx = a[m - 1].end; --n; //第一个点落在第一个区间的起始点上 int p = 0; fo...

算法竞赛之路

0 点赞评论收藏

分享

2021-05-13 21:27

已编辑

江西师范大学后端

滑窗单调队列

感谢青竹大佬。 单调队列：固定长度区间的最大值最小值 最大值：维护递减的区间 10 5 6 4 9 6 3 5 8 6 1 2 4#include <cstdio> #include <iostream> using namespace std; const int maxn = 1e6 + 7, mod = 1e9 + 7; typedef long long ll; inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (c...

算法竞赛之路

0 点赞评论收藏

分享

2020-11-24 17:18

已编辑

江西师范大学后端

HDU3410 两边找最大单调栈

题意 给定一个数列。 对于每一个，找两边的第一个比它大的值，然后在区间里找最大值，再在里找最大值。 思路 单调栈，再加一个判断。 Solution #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 7; #define sc(x) scanf("%d", &(x)) #define me(L) memset(L, 0, sizeof(L)) int L[N], R[N], st[N], a[N]; int main() { int n, t, T; ...

算法竞赛之路

0 点赞评论收藏

分享

2020-11-24 16:53

江西师范大学后端

九九乘法表 JavaScript 的延时和变色

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>九九乘法表</title> <style type="text/css"> td { width: 100px; border: 5px solid white; padding: 15px; background-color: aqua; text-align: center; color: aqua; font...

0 点赞评论收藏

分享

2020-11-24 16:47

已编辑

江西师范大学后端

HDU 1506 单调栈

题意  找到一个面积最大的矩形区域。 思路 对于每一个，找左边第一个比它矮的，再找右边第一个比它矮的。此处可用单调栈实现。 就得到了一个以为最大高度可行区间。就可以算出来这个区域。 单调栈的弹栈操作：清除无用的数据。已经有了更小的，如果要找左边第一个比它小的值，前面的次小数据就没有任何意义了。所以如果要做左边第一个比它小的值，就应该维护栈内的递减。 Solution #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 7; #define sc(x) scan...

算法竞赛之路

0 点赞评论收藏

分享

2020-11-24 16:36

已编辑

江西师范大学后端

数据分析单调栈

题意 给定一个长度为的数组。找它的长度为的区间中的最大值，求这些所有的最大值的集合里的最小值。 思路  利用单调栈，对于每一个，找出来左边第一个比它大的，找出来右边第一个比它大的。并且把它们的下标分别存和里。 对于每一个，它能作为最小值的最长区间已经确定了。那么就可以通过比较得到一部分长度的区间的最优答案了。如样例1，执行到这里的时候就是[1,3,1061109567,1061109567,5,6] 此时区间长度为3和4的时候，最小的可选最大值仍未确定。那么就应该从高位继承。为什么是从高位继承呢？因为要选定的是集合的最大值，而高位的值必然是低位的值的可选项，而低位的则未必是高位的可选项。  S...

算法竞赛之路

0 点赞评论收藏

分享

2020-11-22 23:31

江西师范大学后端

生涯回忆录排列组合

题意 给定一个集合，问它的所有子集里，最小的没出现过的正整数之和是多少。 solution 先桶一遍。因为只有个数，所以每个区间的贡献（也就是每个区间没出现过的最小正整数）的取值范围必定在。所以其实桶只需要统计范围内就可以了。 那么只需要遍历桶：  #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 500010, mod = 20000311; int n, cnt[N]; ll qkpow(ll a, ll b) { ll ans = 1; while (b) { i...

算法竞赛之路

0 点赞评论收藏

分享

2020-11-23 21:41

已编辑

江西师范大学后端

生成平衡数组的方案数前缀和

删除一个数后，这个数后面所有数都向前挪动一位，所以原本奇数位的数变成了偶数位，偶数位的数变成了奇数位。 那么对于一个删除的下标位置，删除该元素后，后面所有奇数下标元素的和其实就是移除之前，后面所有偶数下标元素的和。 所以维护两个前缀和：奇数位和偶数位，然后模拟即可。 class Solution { public: int waysToMakeFair(vector<int>& nums) { int n = nums.size(); vector<int> odd(n + 1, 0); vector<int> even(n + 1, 0); for...

算法竞赛之路

0 点赞评论收藏

分享

2020-11-20 23:05

江西师范大学后端

HDU 1002 大数加法怀旧

#include <bits/stdc++.h> using namespace std; void pre(string &s) { int n = s.length(); int i = 0; while (s[i] == '0') ++i; s = s.substr(i, n); //清除前导零 reverse(s.begin(), s.end()); //竖式右对齐 } string slove(string a, string b) { pre(a), pre(b); int lena = a.length(), lenb = b.length(); if (le...

算法竞赛之路

0 点赞评论收藏

分享

2020-11-20 21:19

已编辑

江西师范大学后端

完全k叉树模拟

完全k叉树，每层节点数量是已知的，直接推过去模拟就可以了 class Solution { public: long long tree2(int k, vector<int>& a) { long long ans = 0; int n = a.size(); int fa = 0; for (int i = 1; i < n;) { //第i个节点 for (int j = 0; j < k && i < n; ++j, ++i) //每遍历k个换一次父亲 ans += (a[fa] ^ a[i]); ++fa; } return an...

算法竞赛之路

0 点赞评论收藏

分享

2020-11-20 21:19

已编辑

江西师范大学后端

切木棒斐波那契

本题和https://ac.nowcoder.com/acm/contest/5758/F 一模一样。 显然是斐波那契。不能构成三角形的极限情况必然是。 class Solution { public: /** * * @param a long长整型 木棒的长度 * @return int整型 */ int stick(long long a) { long long b = 0, c = 1, i = 0; while (c <= a) { a -= c; c += b; b = c - b; ++i; } return i; } }; 随便递推一下都行。

算法竞赛之路

0 点赞评论收藏

分享

2020-11-20 19:36

江西师范大学后端

JavaScript 杂项笔记

npm换源加速 手动后缀 --registry=https://registry.npm.taobao.org -g 欢用cnpm npm install -g cnpm --registry=https://registry.npm.taobao.org

0 点赞评论收藏

分享

2020-11-14 02:53

已编辑

江西师范大学后端

从叶子节点开始考虑：对于每一个叶子节点，如果它本身可以被K整除，那么肯定可以直接对它和它父亲做切割。也就是说，在这种情况下，父子相连的边是一定要删掉的。 而如果不满足这一条件，这条父子相连的边最后一定会加入答案，由于需要让每一个联通块的点权之和都满足，所以如果叶子，就把叶子的点权加到父节点上即可。 自下而上的逻辑方式让DFS的实现更合理。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1000000 + 7; int to[N << 1], nxt[N ...

算法竞赛之路

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务