梨小畅

题解

/ 注册

全部文章 / 题解（共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

2 439

题解 | #[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 461

题解 | # F Train Wreck#

F 题邻接表 + 优先队列 + 贪心思路 (1) 建树 — 邻接表初始时，只有根节点 (序号0)，遇到 '(' 即入栈时则建立新节点，遇到 ')' 即出栈时，则执行"退后操作" 建立新节点时，新节点的序号为入栈序号，新节点的父亲为 now 结点 now 结点，指当前我...

思维优先队列 dfs 邻接表贪心

2021-09-16

3 357

题解 | #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 394

题解 | #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 329

题解 | #漂亮数#

线性筛 + 前缀和思路先用线性筛把漂亮数给筛出来，然后利用前缀和的性质做到 O(1) 查询 Code #include <bits/stdc++.h> using namespace std; const int N = 1e8+10; int cnt; bool st[N];...

前缀和数学线性筛

2021-09-01

3 701

题解 | #打鼹鼠#

打鼹鼠二维前缀和＋树状数组（二维） 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 477

题解 | #简单题#

简单题思路转为括号序列，左括号：区间左端点，右括号：区间右端点 t = 1 时，L 处的左括号数目加 1，R 处的右括号数目加 1 t = 2 时，令 [1,x] 区间的左括号数目减去 [1,x-1] 区间的右括号数目 = k k 就是位置 x 上的元素（初始为0）的变化次数，k 为偶数...

树状数组

2021-08-21

1 356

题解 | #校门外的树#

校门外的树思路转为括号序列，左括号：区间左端点，右括号：区间右端点 k = 1 时，l 处的左括号数目加 1，r 处的右括号数目加 1 k = 2 时，[1,r] 区间的左括号数目减去 [1,l-1] 区间的右括号数目就是答案 Code #include <bits/stdc++.h&...

树状数组括号序列

2021-08-21

3 370

题解 | #花神游历各国#

不需要懒标记，区间修改转为单点修改思路已知：0 或 1 开根号后仍是 0 或 1，又因为 1e9 最多开 5 次根号就会变成 1（每个数最多修改 5 次）所以本题的区间修改可以变为单点修改 + 剪枝为什么不会超时？对于查询操作，单次查询时间复杂度为 O(logn)，最多执行 m 次，所...

线段树思维

2021-08-18

1 540