leiyuanze

摘要： 题目 网上搜 分析 我们可以认为插入一本书是在树中第 \(k\) 的位置进行插入操作 其中 \(k\) 为这本放入书架后的位置 考虑 \(fhq-treap\) 实现 我们将书编号为 \([0，n-1]\) 那么如果插入的书的位置为 \(k\)，实际上是在树中位置为 \(k+1\) 将前 \(k\) 阅读全文

摘要： 题目大意 给出一棵 \(n\) 个节点的树，删去其中两条边 使得分出的三个子树大小中最大与最小的差最小 分析 先一边 \(dfs\) 预处理出以 $1$ 为根每个点的 \(size\) 然后按 \(dfs\) 的顺序枚举一个点，表示删去这个点返回父亲的边 记这个点为 \(x\) 分类讨论 第一种情况 阅读全文

摘要： 总结与反思 很不幸，估分 $170$，可惜 \(T2\) 暴力 $50pts$ 全掉了 \(T1\) 结论题，如果想到了，\(O(n)\) 过，只有十几行代码 感觉不好想，不过还是 \(A\) 了 \(T2\) 差不多想到正解，但是没弄出来 于是打了 $50$ 分暴力 但是，因为想时有分类讨论，打时 阅读全文

摘要： 题目 \(m\) 次区间翻转操作，$1 \leq n，m \leq 100000$ 分析 平衡树模板 于是放上 \(fhq-treap\) 的板子 \(Code\) #include<cstdio> #include<algorithm> #include<ctime> using namespac 阅读全文

摘要： 题目 你有一棵 \(n\) 节点的树 ，回答 \(m\) 个询问，每次询问给你两个整数 \(l,r\) ，问存在多少个整数 \(k\) 使得从 \(l\) 沿着 \(l \to r\) 的简单路径走 \(k\) 步恰好到达 \(k\) 。 分析 考虑离线后按链记贡献 从 \(l\) 到 \(lca( 阅读全文

摘要： 题目 数轴上有很多单位线段，一开始时所有单位线段的权值都是 $1$。有两种操作，第一种操作将某一区间内的单位线段权值乘以 \(w\)，第二种操作将某一区间内的单位线段权值取 \(w\) 次幂。并且你还需要回答一些询问，每个询问需要求出某一区间的单位线段权值之积。由于答案可能很大，你只需要求出答案 \ 阅读全文

摘要： 题目大意 给出 $n，W，ct$ 表示有 $ct$ 个 $n$ 的约数，每个大小为 $d_i$ 且有 $a_i$ 个相同的 现将其放入 $W$ 大的空间中，问最多能装满多少空间 对于 $100%$ 的数据，$1\leq n\leq 10^4，1\leq a_i,W\leq 10^{15}$ 分析 显 阅读全文

摘要： 题目大意 对于 \(m = [1,\lfloor \frac n 2 \rfloor]\) 要求在一个序列中恰好选出 \(m\) 个不相邻的数使得权值和最大 其中 $1$ 的左边是 \(n\)，\(n\) 的右边是 $1$ 分析 比较经典的贪心 做法 链表记录一个点的前驱后继 然后每次选权值最大的点 阅读全文

摘要： 题目 \(\texttt{[USACO06NOV] Round Numbers S}\) 分析 数位 \(dp\) 入门题 一般我们需要当前位置 \(pos\)，有无前导零 \(lead\)，高位标记 \(limit\) 然后就依题弄 \(Code\) #include<cstdio> #inclu 阅读全文

摘要： 题目链接 无聊的序列 题目大意 给某个区间加上等差数列 解析 给原序列差分 然后加的操作只需要 在 \(l\) 出加上 \(k\) 在 \([l+1,r]\) 处加上 \(d\) 在 \(r+1\) 出加上 \(-[k+d*(r-l)]\) 消去影响 查询及查 \([1,p]\) 的和 \(Code 阅读全文

摘要： 题目 见洛谷 \(Code\) #include<cstdio> #include<iostream> using namespace std; const int N = 1e5 + 5; int n , m , fa[N]; struct Lheap{ int ls , rs , val , b 阅读全文

摘要： 题目描述 如题，主席树求区间内不同数字的个数 \(Code\) #include<cstdio> #include<cstring> using namespace std; const int N = 1e6 + 5; int n , m , a[N] , la[N] , rt[N] , size 阅读全文

摘要： 显然，下面的代码是求 \([l..r]\) 中不同颜色的种数 其中 \(block = \frac{n}{\sqrt{\frac 2 3 m}}\) 且奇数块中按 \(a.r > b.r\) 排（首块为偶数块） \(Code\) #include<cstdio> #include<cmath> #i 阅读全文

摘要： 题目 [\(SCOI2016\)]美味 分析 我们需要 \([l，r]\) 中的 \(a_i + x\) 满足它异或 \(b\) 最大 那么我们贪心的考虑 \(ans = a_i + x\) 对于 \(b\) 的第 \(i\)，如果是 $1$，那么我们希望能找到一个 \(a_i + x\) 使得它的 阅读全文

摘要： 题目 给定一棵 \(n\) 个节点的树，根节点为 1。每个节点上有一个颜色 \(c_i\)。 \(m\) 次操作。操作有一种：\(u\) \(k：\) 询问在以 \(u\) 为根的子树中，出现次数 \(\ge k\) 的颜色有多少种。 $2 \le n \le 105 ， 1 \le m \le 1 阅读全文