sunny_forever
sunny_forever
全部文章
分类
题解(57)
归档
标签
去牛客网
登录
/
注册
梨小畅的空间
全部文章
(共57篇)
题解 | #HH的项链#
B HH的项链 在线做法:主席树 思路 last[i]: 数字 i 上一次出现的位置,第一次出现则为 0 w[i]: 位置 i 上的数字,上一次出现的位置,第一次出现则为 0 求[l,r]内的数字种类,即求 w[i] < l 的数量,i属于 [l,r] ps: w[i] 取整范围为 [0,...
树状数组
离线
主席树
2021-11-06
3
627
题解 | #[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 n...
二分
差分
线段树
懒标记
2021-11-06
1
651
题解 | # F Train Wreck#
F 题 邻接表 + 优先队列 + 贪心 思路 (1) 建树 — 邻接表 初始时,只有根节点 (序号0),遇到 '(' 即入栈时 则建立新节点,遇到 ')' 即出栈时,则执行"退后操作" 建立新节点时,新节点的序号为入栈序号,新节点的父亲为 now 结点 now 结点,指当前我...
思维
优先队列
dfs
邻接表
贪心
2021-09-16
3
535
题解 | #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’,反之为 ...
思维
位运算
2021-09-15
2
527
题解 | #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...
exgcd
2021-09-14
1
473
题解 | #漂亮数#
线性筛 + 前缀和 思路 先用线性筛把漂亮数给筛出来,然后利用前缀和的性质做到 O(1) 查询 Code #include <bits/stdc++.h> using namespace std; const int N = 1e8+10; int cnt; bool st[N];...
前缀和
数学
线性筛
2021-09-01
3
866
题解 | #打鼹鼠#
打鼹鼠 二维前缀和 + 树状数组(二维) Code #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5000; ll tr[N][N]; int n,m; int...
前缀和
树状数组
2021-08-21
1
665
题解 | #简单题#
简单题 思路 转为括号序列,左括号:区间左端点,右括号:区间右端点 t = 1 时,L 处的左括号数目加 1,R 处的右括号数目加 1 t = 2 时,令 [1,x] 区间的左括号数目 减去 [1,x-1] 区间的右括号数目 = k k 就是 位置 x 上的元素(初始为0) 的变化次数,k 为偶数...
树状数组
2021-08-21
1
476
题解 | #校门外的树#
校门外的树 思路 转为括号序列,左括号:区间左端点,右括号:区间右端点 k = 1 时,l 处的左括号数目加 1,r 处的右括号数目加 1 k = 2 时,[1,r] 区间的左括号数目 减去 [1,l-1] 区间的右括号数目 就是答案 Code #include <bits/stdc++.h&...
树状数组
括号序列
2021-08-21
3
503
题解 | #花神游历各国#
不需要懒标记,区间修改转为单点修改 思路 已知:0 或 1 开根号后 仍是 0 或 1,又因为 1e9 最多开 5 次根号就会变成 1(每个数最多修改 5 次) 所以本题的区间修改 可以变为单点修改 + 剪枝为什么不会超时? 对于查询操作,单次查询时间复杂度为 O(logn),最多执行 m 次,所...
线段树
思维
2021-08-18
1
729
首页
上一页
1
2
3
4
5
6
下一页
末页