首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
梨小畅
获赞
161
粉丝
10
关注
8
看过 TA
7
男
大连海事大学
2026
C++
IP属地:辽宁
无
私信
关注
拉黑
举报
举报
确定要拉黑梨小畅吗?
发布(58)
刷题
梨小畅
2021-11-06 20:40
已编辑
大连海事大学 计算机类
题解 | #HH的项链#
B HH的项链 在线做法:主席树 思路 last[i]: 数字 i 上一次出现的位置,第一次出现则为 0 w[i]: 位置 i 上的数字,上一次出现的位置,第一次出现则为 0 求[l,r]内的数字种类,即求 w[i] < l 的数量,i属于 [l,r] ps: w[i] 取整范围为 [0,n-1],为避免出现 0,所以我们将 w[i] 加 1,因此 w[i] 可取值 [1,n] Code #include <bits/stdc++.h> using namespace std; const int N = 1e6+10; int n,m,idx; int rt[...
0
点赞
评论
收藏
转发
梨小畅
2021-11-06 15:59
大连海事大学 计算机类
题解 | #[NOIP2012]借教室#
A 借教室 法一:线段树 区间修改 / 懒标记 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6+10; int n,m; int w[N]; struct node{ int l,r; ll lazy; ll minm; }tr[N*4]; void pushdown(int u){ auto &rt=tr[u],&le=tr[u<<1],&ri=tr[u<<1|1]; ...
0
点赞
评论
收藏
转发
梨小畅
2021-09-16 18:17
大连海事大学 计算机类
题解 | # F Train Wreck#
F 题 邻接表 + 优先队列 + 贪心 思路 (1) 建树 — 邻接表 初始时,只有根节点 (序号0),遇到 '(' 即入栈时 则建立新节点,遇到 ')' 即出栈时,则执行"退后操作" 建立新节点时,新节点的序号为入栈序号,新节点的父亲为 now 结点 now 结点,指当前我们指向的结点 因此,建立新节点 即 新建一个 now 结点的子节点,"退后操作" 即 让 now 指向 now 的父节点 建好树后,共有 n+1 个结点,n 条边 n+1 个结点,指最初的 0 结点 与 新建的 n 个新节点(2) "染色" — 贪心 + 优...
0
点赞
评论
收藏
转发
梨小畅
2021-09-15 17:55
大连海事大学 计算机类
题解 | #War of Inazuma (Easy Version)#
H 题 前置知识 假设 A 、B相邻,A 二进制表示中 1 的个数为 x ,B 二进制表示中 1 的个数为 y 那么,y 必为 x+1 或 x-1(x = 0 时,y 只能为 x+1 ) 因此,x 和 y 的奇偶性,必不同思路 我们令,二进制表示中 1 的个数为偶数的顶点的属性为 ‘0’,反之为 ‘1’,便可以实现: 对于任意一个顶点 A ,与其相邻的顶点必与其属性不同 证明如下: 假设 A顶点、B顶点 相邻,且 A、B 的属性相同 不妨令,A 二进制表示中 1 的个数为 x ,B 二进制表示中 1 的个数为 y 那么 x 和 y 的奇偶性,必不同,因此 A、B的属性也必不同,这与假设矛盾...
0
点赞
评论
收藏
转发
梨小畅
2021-09-14 20:00
大连海事大学 计算机类
题解 | #C Looooops#
C Looooops 思路 k 位存储系统,意思是能储存的最大数为 2^k-1,越过了会变为 0 所以 A + x*C B(mod 2^k)利用扩欧求得 x 即可 Code #include <bits/stdc++.h> using namespace std; typedef long long ll; ll exgcd(ll a,ll b,ll &x,ll &y){ if(!b){ x=1,y=0; return a; } ll d=exgcd(b,a%b,y,x); y-=a/b*x...
0
点赞
评论
收藏
转发
梨小畅
2021-09-01 21:17
大连海事大学 计算机类
题解 | #漂亮数#
线性筛 + 前缀和 思路 先用线性筛把漂亮数给筛出来,然后利用前缀和的性质做到 O(1) 查询 Code #include <bits/stdc++.h> using namespace std; const int N = 1e8+10; int cnt; bool st[N]; bool vis[N]; int sum[N]; int primes[N]; void Init(){ for(int i=2;i<=N;i++){ if(!st[i]) primes[cnt++]=i; for(int j=0;primes[j...
0
点赞
评论
收藏
转发
梨小畅
2021-08-21 19:06
大连海事大学 计算机类
题解 | #打鼹鼠#
打鼹鼠 二维前缀和 + 树状数组(二维) Code #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5000; ll tr[N][N]; int n,m; int lowbit(int x){ return x & -x; } void add(int x,int y,int v){ for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=m;j+=lowbit(j)) tr[i][j...
0
点赞
评论
收藏
转发
梨小畅
2021-08-21 19:02
已编辑
大连海事大学 计算机类
题解 | #简单题#
简单题 思路 转为括号序列,左括号:区间左端点,右括号:区间右端点 t = 1 时,L 处的左括号数目加 1,R 处的右括号数目加 1 t = 2 时,令 [1,x] 区间的左括号数目 减去 [1,x-1] 区间的右括号数目 = k k 就是 位置 x 上的元素(初始为0) 的变化次数,k 为偶数 答案为 0,否则为 1Code #include <bits/stdc++.h> using namespace std; const int N = 1e5+10; int tr[N],trr[N]; int n,m; int lowbit(int x){ retur...
0
点赞
评论
收藏
转发
梨小畅
2021-08-21 19:03
已编辑
大连海事大学 计算机类
题解 | #校门外的树#
校门外的树 思路 转为括号序列,左括号:区间左端点,右括号:区间右端点 k = 1 时,l 处的左括号数目加 1,r 处的右括号数目加 1 k = 2 时,[1,r] 区间的左括号数目 减去 [1,l-1] 区间的右括号数目 就是答案 Code #include <bits/stdc++.h> using namespace std; const int N = 1e5+10; int tr[N],trr[N]; int n,m; int lowbit(int x){ return x & -x; } void add(int t[],int x,int...
0
点赞
评论
收藏
转发
梨小畅
2021-08-18 17:24
已编辑
大连海事大学 计算机类
题解 | #花神游历各国#
不需要懒标记,区间修改转为单点修改 思路 已知:0 或 1 开根号后 仍是 0 或 1,又因为 1e9 最多开 5 次根号就会变成 1(每个数最多修改 5 次) 所以本题的区间修改 可以变为单点修改 + 剪枝为什么不会超时? 对于查询操作,单次查询时间复杂度为 O(logn),最多执行 m 次,所以最坏是 O(m*logn) 对于修改操作,单点修改时间复杂度 O(logn) 又因为有剪枝,每个点最多修改 5 次,且 m 次操作,最多修改 n 个点,所以最坏是 O(5*n*logn) 所以总时间复杂度约为 max(O(m*logn),O(5*n*logn)) flag 取值的含义 fla...
0
点赞
评论
收藏
转发
梨小畅
2021-08-12 22:21
大连海事大学 计算机类
题解 | #[NOIP2011]选择客栈#
思路 枚举右端点 i 当 fee[i] <= p 时,对其有贡献的左端点是:i 左侧所有与 i 同色的点 当 fee[i] > p 时,对其有贡献的左端点分为两种: (1) i 左侧,所有与 i 同色的,fee[j] <= p 的 j 点 显然: 位置 j < 位置 i (2) i 左侧,所有与 i 同色的,在某个 j 点左侧的点 ps:j 就是 (1) 中的 j 为了方便 fee[i] > p 的情况,我们在 fee[i] <= p 时 才对 num[color] 进行更新 注: color[i] :第 i 个客栈的配色 num[color...
0
点赞
评论
收藏
转发
梨小畅
2021-08-12 22:17
已编辑
大连海事大学 计算机类
题解 | #选择客栈#
思路 枚举右端点 i 当 fee[i] <= p 时,对其有贡献的左端点是:i 左侧所有与 i 同色的点 当 fee[i] > p 时,对其有贡献的左端点分为两种: (1) i 左侧,所有与 i 同色的,fee[j] <= p 的 j 点 显然: 位置 j < 位置 i (2) i 左侧,所有与 i 同色的,在某个 j 点左侧的点 ps:j 就是 (1) 中的 j 为了方便 fee[i] > p 的情况,我们在 fee[i] <= p 时 才对 num[color] 进行更新 注: color[i] :第 i 个客栈的配色 num[color...
0
点赞
评论
收藏
转发
梨小畅
2021-08-12 16:55
大连海事大学 计算机类
题解 | #与众不同#
离散化 + dp + ST 表 参考楼上大佬的题解,总结出下面的思路 r[i]:以 i 作为左端点时,其右端点的位置. 则以 i 为起点时,目标序列的最大长度为 r[i] - i + 1 r[i] 具有非减性质,这为二分提供了前提条件 对于区间[L,R],求其内部最长"好序列"的长度时,区间内每个点都有可能是“最长好序列”的左端点 所以有两种情况:(1)存在 r[i] > R 的左端点 (2)不存在 r[i] > R 的左端点 对于(1): r[i] 大于 R 的左端点中,我们只需要考虑它们中最左边的那个(考虑r[i]的非减性,可用二分),得到 ans1 ...
0
点赞
评论
收藏
转发
梨小畅
2021-08-11 20:06
大连海事大学 计算机类
题解 | #超级钢琴#
ST 表 + 优先队列 + 前缀和 题意 给一个长度 为 n 的序列,让你从中选 k 个长度在 [L,R] 范围内的区间 (同一个区间不可选多次) 要求:这 k 个区间的区间和 相加 得到的值 应该最大 思路 (1):求出前缀和 (2):枚举 i 令其作为区间左边界,则右边界ri可取值 [i+L-1,i+R-1] 使用RMQ在区间[i+L-1,i+R-1]里找到pos => 目标区间里最大值的下标,即:对于左端点 i 有最大区间和 sum[pos] - sum[i-1] 同时,我们把 {i:此时的左边界,i+L-1:右边界最小值,i+R-1:右边界最大值,最大区间和} 作为一个结构体放...
0
点赞
评论
收藏
转发
梨小畅
2021-08-11 11:40
大连海事大学 计算机类
题解 | #[JSOI2008]最大数MAXNUMBER#
线段树 或 ST 表 法1:线段树 #include <bits/stdc++.h> using namespace std; const int N = 2e5+10; int m,d; struct node{ int l,r; int maxm; }tr[N*4]; void pushup(int u){ tr[u].maxm=max(tr[u<<1].maxm,tr[u<<1|1].maxm); } void build(int u,int l,int r){ tr[u]={l,r}; if(l==r...
0
点赞
评论
收藏
转发
1
2
3
4
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务