文章

1. 题目 传送门=￣ω￣= 2. 题解 比较弱智的模板题 听说可以用分块做 然而我们是来做 lct 的模板题的呀！ 不难发现题目中隐藏了一棵树！ 如果能从 i 跳到 j，那么就设 j 为 i 的父亲（在树上）设所有出界了的位置的编号都为 n+1（就好像在 n+1 的位置竖了一面墙，你弹上去，pi 阅读更多…

1. 题目 biubiu 2. 题解 这题不能直接预处理出 phi，因为数组开不下。。 设 gcd(i,n)==k ->gcd(i/k,n/k)==1 。 所以 i/k 有 phi[n/k] 种选法 。 ans=sigma(phi[k])1<=k<=n; 还是过不了。。。 设 f[ 阅读更多…

题目描述 小 J 开了一家科技公司，他的核心团队里有小 X，小 A，小 W 等 m 人，为了保密需要，小 J 想要只有当 n 个人到场的时候才能打开核心机密保险柜，那么请问：（1）小 J 要在保险柜上装多少把锁？（2）每个人分配多少把钥匙？（3）要怎么分配？ 例如当 m=4（小 J，小 X，小 阅读更多…

1. 题目 biubiu 2. 题解 ans=$sigma((gcd(x,y)-1)×2+1)$（1<=x<=n,1<=y<=m）设 f[d] 为 gcd(x,y)==d 的 x，y 对数 g[d] 为 gcd(x,y)%d==0 的 x，y 对数 g[d]=sigma(f 阅读更多…

题意：给定一个序列，要求可以插入、删除小于某个值的所有数、所有值同时加上 x、查询当前第 k 大的数。 思路： 首先，我们感觉这是一道 Splay 的裸题，但是看到需要区间加减就懵了。 但是仔细一想不难发现，由于所有的加减操作是对全部数据而言的，所以我们可以建立一个变量保存全部的数相对于 Splay 阅读更多…

题意：给定一圈石子，将相邻的两堆石子合并，花费为合并后的石子数。给定一开始每一堆石子的个数，求合并的最小花费。(石子堆数<=1000) 分析： 由于是一圈石子，所以我们将其倍增以消除环的影响，然后很自然可以得出状态转移方程：设 f(i,j) 表示从 i 到 j 的石子合并的最小花费，sum[i 阅读更多…

1. 题目 BZOJ 传送门=￣ω￣= LUOGU 传送门=￣ω￣= 2. 题解 之前发了个 treap 版的 现在发个 splay 版的 #include <bits/stdc++.h> using namespace std; typedef long long LL; templa 阅读更多…

砍树自动机（鲁迅很生气）题意： Wilbur 的门前有 2 棵枣树很多棵枣树排成一排 (n<=2000)，枣树的高度均为 h。wilbur 为了成为一只 beaver(河狸)，发明了砍树自动机。它会每次选择这一列树两端的某一棵树 (各有 0.5 的概率被选择)，将其砍倒，受风速的影响，砍倒的 阅读更多…

1. 题目 LUOGU 传送门=￣ω￣= BZOJ 传送门=￣ω￣= 2. 题解 学 lct 太累娱乐一下 获得了满满的满足感 树链剖分模板题 首先 install 操作就是先查询根节点 (0) 到当前节点的路径，再把这个路径上所有值设为 0 然后 uninstall 操作就是操作子树，子树在线段树 阅读更多…