题意给出一个长度为 $n(\le 2\times 10^6)$ 的数列，有 $m(\le 2\times 10^6)$ 次询问，求 $[l,r]$ 之间有多少个出现了两次及以上的数。题解和 HH的项链 差不多，只是要求出现两次。所以把树状数组维护的值修改一下，变成只有出现了两次才更新节点的权值。先预处理出每种数字下一次和下下次出现的位置 $nxt[]$ 和 $nxt2[]$，并把所有数字出现...
A.Yet Another Dividing into Teams略B.Books Exchange题意题解把关系连边后，可以发现一定是形成若干个环，那么 $O(n)$ 搜索一遍即可。#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()
{
char ch...
当时比赛的时候没做出来这题，做了 洛谷3586 才知道这题的做法。题意有 $N(\le 3\times 10^5)$ 张卡，卡上有数字 $A_i(\le n)$ 。$\forall k$ ，问：每次取 $k$ 张数字互不相同的卡，能取多少次。题解记录每个数字出现的次数为 $s_i$ ，问题就转化为：每次选 $k$ 个正数 $-1$ ，最多操作多少次。然后就可以直接用 洛谷3586 的结论了（...
题意给出一个长度为 $n(\le 10^6)$ 的全 $0$ 序列，要求支持以下操作：单点修改给出 $(c,s)$ ，每次取 $c$ 个正数 $-1$ ，问能否操作 $s$ 次。题解先考虑操作 $2$ 。设 $\geq s$ 的数有 $x$ 个，这些数每次都可以取，此外还需要 $(c-x)$ 个数。设 $< s$ 的数的和为 $sum$ ，如果 $sum < (c-s)\time...
题意有 $n(\le 1000)$ 个人，每个人有分数 $s[i]$ 。有 $S$ 组限制 $(A,B)$ ，要求 $s[A] > s[B]\times k$ 或 $s[A] > s[B]\times \frac{1}{k}$ ，如果不满足则 $A$ 需要女装。已知 $t$ 个人的初始分数。求最大的 $T$ ，使得限制变为 $s[A] > s[B]\times (k-T)$...
题意略（太复杂了不想写）题解令 $f[i]$ 为不大于 $x$ 的最大斐波那契数，那么 $x$ 的父亲节点就是 $x-f[i]$ 。斐波那契数列的第 $58$ 项刚好小于 $10^{12}$ ，所以预处理前 $58$ 个就行了。求两个节点的 $\text{LCA}$ 可以用一种类似树剖的方法，不断地取 $u$ 和 $v$ 中的较大值跳到父节点，直到 $u$ 和 $v$ 相等。层数最多只有 $...
题意给出一个 $n(\le 2\times 10^5)$ 点的树。从 $C$ 出发，先到 $A$ 和 $B$ 中较近的点，然后到另一个点。求可能的路径最大值。题解$A\rightarrow B$ 这段路径是肯定要走的，然后还有一段 $\max_c (\min (AC,BC))$ 。显然 $AB$ 是直径，然后从 $A,B$ 出发分别 $\text{dfs}$ 一次求出距离即可。#includ...
题意给出一棵 $n(\le 10^5)$ 个点的树，要求选连续的 $k$ 个点，使得其它城市到这些点距离的最大值最小。题解可以发现树的中心一定要选，然后中心的周围再选 $k-1$ 个点。先求出直径，然后找到中心。再以中心为根，找到所有节点到叶节点的距离 $res[i]$ 并从大到小排序，然后选前 $k$ 个节点即可。可以证明这些节点一定是连续的。#include<bits/stdc++...
双倍经验：洛谷2195 HXY造公园题意给出一个有 $n(\le 3\times 10^5)$ 个点 $m(\le 3\times 10^5)$ 条边的森林。要求支持两种操作：求 $x$ 所在树的直径将 $x,y$ 所在的树合并，要求合并后树的直径最小题解合并可以用并查集来实现，用 $ans[x]$ 表示 $x$ 子树中的直径长度。对于操作 $1$ ，直接输出 $ans[x]$ 。对于操作 ...
题意对于一棵二叉树，如果它所有节点的左右子树交换后和原树一样，那么称它为对称二叉树。给出一棵 $n(\le 10^6)$ 个节点的二叉树，求它所有对称子树中节点个数的最大值。题解可以发现，如果一个节点 $x$ 的左子树的 左->中->右 遍历和右子树的 右->中->左 遍历相同，那么以 $x$ 为根的子树就是棵对称二叉树。所以对于一个点，维护以它为根的子树的两种遍历方...
题意略题解$\because a,b\geq 0 \ , \ \therefore y\geq x$ ，不妨设 $y=x+k(k\geq 0)$ ，原式化为：$$k^2+2kx=ax+b\tag{1}$$当 $a=2k,b=k^2$ ，即 $a^2=4b$ 时有无数组解，输出 inf 。否则 $(1)$ 式可以化为：$$(a-2k)x=k^2-b$$$$x=\dfrac{k^2-b}{a-2...
在与机房大佬们的合作下，rk89，rating+=140。题解代码中省略的程序头：#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define ha 1000000007
#define ui unsigned int
#de...
Day -inf[数据删除]Day 0上午和wzx打前一天晚上的CF，结果我B题就不会（我看标签里有个 combinatorics 就不停的推排列组合式子，结果就一傻逼题），rp++；然后3min猜到C题结论5min切了，rp--。后来又因为初始化问题调了1h的D，rp++。下午被徐妈逼迫复习初赛，到头来还不是没考。我就装模做样的看了一下，还发现个资料上的锅，剩下的时间全在颓废。晚上回去参加...
题意给出黑点白点各 $n(\le 100)$ 个，要求一个黑点连接一个白点，并且所有线段都不相交。题解所有线段不相交 $\rightarrow$ 两两连最近的点 。那么把距离变成负数就是KM算法裸题了，但这道题有个神奇的坑点：如果在 find() 里更新顶标的偏移值 d ，就会T；而改在外面更新就A了。我也不知道为什么，看来以后得改下KM算法的写法了。#include<bits/std...
Codeforces Round #572 (Div. 2) 题解题意给出一个长度为 $n(\le 1000)$ 的序列和 $k$ ，求所有长度为 $k$ 的子序列中美丽值之和。美丽值定义为序列中的数两两之间差值的最小值。题解利用差分的思想。令 $g(x)$ 为美丽值 $\geq x$ 的子序列个数，那么答案就是 $\sum_{i=1}^\infty g(i)$ 。先把序列从小到大排序，这样...