Vacation Posted on 2019-07-23 | In acm , 做题记录 , 2019多校赛 , HDU 题目链接题意有$n$辆车在你前面开,你们都要过红绿灯(可以认为始终保持绿灯),每辆车都有最大速度v_{i},可以认为每个司机技术很好,可以保持和前一辆车零距离。现在问你你这两车要开到红绿灯处需要多久的 ... Read more »
Function Posted on 2019-07-23 | In acm , 做题记录 , 2019多校赛 , HDU 题目链接题意计算 \sum_{i = 1}^{n} gcd( \left \lfloor \sqrt[3]{i} \right \rfloor, i).对$998244353$取模。$1 \leq n ... Read more »
Operation Posted on 2019-07-23 | In acm , 做题记录 , 2019多校赛 , HDU 题目链接题意有n个数,每次要么询问区间的最大异或和,要么在最后加一个数。 思路首先很容易想到这个问题要维护区间线性基,每次询问得到区间线性基后从高位到低位贪心的选。似乎是一道线段树维护线性基的裸题,但 ... Read more »
GCD of Sequence Posted on 2019-07-21 | In acm , 做题记录 , HDU 题目链接题意给一个序列,让你计算有多少序列$b$满足:1.每个位置1 \leq b_{i} \leq m。2.gcd(b_{1}, b_{2}...b_{n})=d。3.和原来数列恰好有$k$个位置数 ... Read more »
Eddy Walker Posted on 2019-07-21 | In acm , 做题记录 , 2019多校赛 , 牛客 题目链接题意有一个大小为$n$的环,现在从位置$0$开始走,或前或后,直到走到所有点都经过一遍停下来,问停在M_{i}的概率。 思路我们可以手玩几个小的$n,m$。当$n$为2: p=1.当$n$为3 ... Read more »
Partition problem Posted on 2019-07-21 | In acm , 做题记录 , 2019多校赛 , 牛客 题目链接题意将2n个人分成两组,使每组n个人,最大化每组对另外一组所有人的竞争力的和。 思路dfs,在dfs时顺便在O(n)的时间内计算影响。12345678910111213141516171819 ... Read more »
Second Large Rectangle Posted on 2019-07-20 | In acm , 做题记录 , 2019多校赛 , 牛客 题目链接题意在一个01矩阵中找出第二大的满足全部由1构成的子矩阵。 思路首先预处理出每个位置向上最大连续1的高度,然后对每一行单调栈处理处这一行中,以每个高度为最高的矩形面积是多少。遍历所有矩形,找出 ... Read more »
FMT与FWT Posted on 2019-07-20 | In acm , Math 首先感谢几篇良心博客的博主,教程写得真的很好。真正理解快速沃尔什变换/快速莫比乌斯变换(FWT|FMT) (已完结)FMT 与 子集(逆)卷积FWT快速沃尔什变换学习笔记 集合卷积我们时常要解决一些与 ... Read more »
Euclidean Distance Posted on 2019-07-19 | In acm , 做题记录 , 2019多校赛 , 牛客 题目链接题意$n$维平面上有一个点,坐标是( \frac{a_{1} }{m}, \frac{a_{2} }{m}...),现在想找一个点$P$,试他们的欧几里得距离最短。要求$P$的坐标满足:1.p ... Read more »
ABBA Posted on 2019-07-18 | In acm , 做题记录 , 2019多校赛 , 牛客 题目链接题意一个长度为$2(n+m)$字符串只由$’A’,’B’$构成,且可以将它分成$n+m$个子序列,其中$n$个为$AB$,$m$个为$BA$。问这样的字符串有多少个。 思路dp$dp[i][j ... Read more »