题意简述有一个$n$个节点的图,还有$m$条边。找到一颗生成树,使得最大边和最小边之间差最小。 n<=2000,m<=15000,边权<=2e9。 思路框架边按边权排序;枚举最小边,枚举最大边,直到联通为止$break$。并查集维护。 看起来是$O(m^2)$,但实际情况会快很多。 ...
51nod 1105 第k大的数 题解
题意简述有两个序列$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$中有多少 ...
洛谷 6070 [RC-02]GCD 题解
题意简述求$\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 ...
洛谷 5947 [POI2003]Trinomial 题解
题意简述$T$组数据。给定$n,m$,求$(x^2+x+1)^n$中,$x^m$项的系数是多少。答案对$3$取膜。(这个膜数很神奇!注意!突破点就在这!) $T<=1e4$,$n<=1e15$,$m<=2n$。 思路框架答案是$C_{2n}^m\times (m\% 2+1)$,对 ...
洛谷 5826 【模板】子序列自动机 题解
你以为我只是单纯的子序列自动机吗?其实我是是子序列自动机+可持久化数组哒! 但是我看见一个大神给出了一个特别神仙又巧妙的思路!我不禁要写一篇题解记录下这神奇的思路! 而且代码贼短哦~比可持久化数组好写到不知道多少倍呢www 题意简述给定一个序列$A$长度<=1e5,还要一些要询问的字符串$B$ ...
洛谷 5631 最小mex生成树
题意简述mex(S)表示集合S中没有出现的最小自然数。给定一个n个点m条边的带权无向图,求生成一颗树,使得边权集合的mex值最小。 n<=1e6,m<=2e6。边权范围是1e5。 思路暴力思路:检验一个值x,把边权不等于x的边权加入,判断是否能生成树 小小优化:先把边按边权排序。然后用分 ...
洛谷 5080 Tweetuzki 爱序列 题解
题意简述给一个集合$a$,大小为$n$。请你选出若干个数,按某种顺序排好,对于每个数(除了最后一个),它的下一个数要么是他两倍,要么是它$\dfrac{1}{3}$。你最多能从$a$选出多少个数满足这样的条件? $n<=1e5$,$1<=a_i<=3e18$。 比如${4,8,16 ...
洛谷 5021 & libreoj 2952 赛道修建 题解
题意简述给你一颗树有n(n<=5e4)个点,边权<=1e4。请你选出m(1<=m<n)条链,没有公共边,允许有公共点,使得$m$条链的边权和的最小值最大。 思路二分+树上贪心检验 具体思路首先二分是显然的,“最小值最大”是特点,而且显然有单调性。 关键在于,我们钦定了最小值m ...
洛谷 5020 货币系统 题解
题意简述一个货币系统由长度为$n$的正整数序列$a$组成。每个数珂以用无限次。定义两个货币系统是等价的,对于任意一个正整数$x$,要么两个都能凑出$x$,要么两个都不能。 给定一个货币系统$(n,a)$,$n<=100$,$a_i<=25000$,请你求出一个和它等价的货币系统,使得这个 ...
洛谷 4830 Tomoya loves Nagisa
题意简述某人考试,他女朋友会帮他作弊。只有一个单选题,有n个选项。每次,这个人会选择一个选项,他女朋友帮他排除一个他没选的错误选项。然后他一共有k次更换选项的机会。请你求出,到最后,这个人最大有多少概率蒙对,如果这个人采取最优策略的话。 思路大家知道“三门问题”么? 参考链接 真正理解了这个问题之后 ...