题意简述有一个$n$个节点的图，还有$m$条边。找到一颗生成树，使得最大边和最小边之间差最小。 n<=2000，m<=15000，边权<=2e9。 思路框架边按边权排序；枚举最小边，枚举最大边，直到联通为止$break$。并查集维护。 看起来是$O(m^2)$，但实际情况会快很多。 ...

题意简述有两个序列$a$和$b$，长度都是$n<=1e5$，并且$a_i,b_i<=1e9$。然后有一个矩阵$A$，其中$A[i][j]=a_i\times b_j$。找到矩阵中第$k$大的元素$k<=1e9$且$k<=n^2$。 思路二分一个$mid$，然后找$A$中有多少 ...

题意简述求$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} \sum\limits_{p=1}^{n/j} \sum\limits_{q=1}^{n/j} [gcd(i,j)==1][gcd(p,q)==1]$。答案对998244353取膜。 $n<=2e ...

题意简述$T$组数据。给定$n,m$，求$(x^2+x+1)^n$中，$x^m$项的系数是多少。答案对$3$取膜。（这个膜数很神奇！注意！突破点就在这！） $T<=1e4$，$n<=1e15$，$m<=2n$。 思路框架答案是$C_{2n}^m\times (m\% 2+1)$，对 ...

你以为我只是单纯的子序列自动机吗？其实我是是子序列自动机+可持久化数组哒！ 但是我看见一个大神给出了一个特别神仙又巧妙的思路！我不禁要写一篇题解记录下这神奇的思路！ 而且代码贼短哦~比可持久化数组好写到不知道多少倍呢www 题意简述给定一个序列$A$长度<=1e5，还要一些要询问的字符串$B$ ...

题意简述mex(S)表示集合S中没有出现的最小自然数。给定一个n个点m条边的带权无向图，求生成一颗树，使得边权集合的mex值最小。 n<=1e6,m<=2e6。边权范围是1e5。 思路暴力思路：检验一个值x，把边权不等于x的边权加入，判断是否能生成树 小小优化：先把边按边权排序。然后用分 ...

题意简述给一个集合$a$，大小为$n$。请你选出若干个数，按某种顺序排好，对于每个数（除了最后一个），它的下一个数要么是他两倍，要么是它$\dfrac{1}{3}$。你最多能从$a$选出多少个数满足这样的条件？ $n<=1e5$，$1<=a_i<=3e18$。 比如${4,8,16 ...

题意简述给你一颗树有n(n<=5e4)个点，边权<=1e4。请你选出m(1<=m<n)条链，没有公共边，允许有公共点，使得$m$条链的边权和的最小值最大。 思路二分+树上贪心检验 具体思路首先二分是显然的，“最小值最大”是特点，而且显然有单调性。 关键在于，我们钦定了最小值m ...

题意简述一个货币系统由长度为$n$的正整数序列$a$组成。每个数珂以用无限次。定义两个货币系统是等价的，对于任意一个正整数$x$，要么两个都能凑出$x$，要么两个都不能。 给定一个货币系统$(n,a)$，$n<=100$，$a_i<=25000$，请你求出一个和它等价的货币系统，使得这个 ...

题意简述某人考试，他女朋友会帮他作弊。只有一个单选题，有n个选项。每次，这个人会选择一个选项，他女朋友帮他排除一个他没选的错误选项。然后他一共有k次更换选项的机会。请你求出，到最后，这个人最大有多少概率蒙对，如果这个人采取最优策略的话。 思路大家知道“三门问题”么？ 参考链接 真正理解了这个问题之后 ...