luo想要个气球

分类

未归档(1) 题解(58)

/ 注册

TA的专栏 27篇文章 0人订阅

27篇文章 984人学习

全部文章（共59篇）

【每日一题】逆序对

1. 算出前几项然后OEIS 2. 组合数学从低位到高位选择0或者1填数，当填到第i位的时候，如果第i位为0对答案是没有贡献的，如果是1就要算前面已经填好的长度为i-1的串中有多少个0，因此计算每一个位置为1时的贡献的和就是答案；当字符串的第i位为1时，它对答案的贡献就是长度为i-1的串的0...

2020-04-15

0 527

【每日一题】Running Median

题意：动态地输入输出，如果输入的数个数为奇数就输出当前的中位数对顶堆的经典题，附上大佬的关于对顶堆的博客一篇：https://www.cnblogs.com/SGCollin/p/9673252.html 这题需要动态地维护中位数，用一个大根堆和小根堆；构造对顶堆应满足以下性质：1.上面的堆是小根...

2020-04-08

0 614

【每日一题】树

题目要求对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。相当于切掉树上的 x 条边（0<= x <= min(n-1,k-1)），让原树变成x+1个连通块，每个连通块涂成一个颜色，问有多少种方案；ans = C(n-1,i)是从n-1条边选i条边切，分成i...

2020-04-08

0 552

【每日一题】数码

首先把【L ， R】的问题转化成【1 , R】-【1 , L-1】，因为想要求1 ~ n中有几个数约数有x，可以通过n/x求得；然后对于每个数码1,2,3....分别求，以1为例：求1 ~ n中约数数码为1的，应该要求这样的一些区间【1,1】、【10,19】、【100,199】【1000,1999...

2020-04-06

2 737

【每日一题】Shortest Path

题意：n个点的一棵树，选出n/2个点对，使得点对之间两点距离之和最小，n保证偶数sum[i]是以结点i包括结点i的子树结点个数，当sum[i]为偶数时，只需要让这颗子树中的点两两相连，代价就是该子树的所有边；当sum[i]为奇数时，就需要另外一个点与外面(即除这颗子树外)的点相连，最优当然是选择这颗...

2020-04-03

0 547

【每日一题】月月查华华的手机

题意：在文本串a中能否找到一个子序列等于字符串bi，有m个询问对a串预处理一个nxt[i][ch],表示是s[i]以及之后字符 ch 第一次出现的下标，这个预处理就是逆着推，从后面往前面做，每次先把nxt[i+1][ch]赋值给nxt[i][ch],然后再用当前字母更新nxt数组即nxt[i][s...

2020-04-01

0 608

【每日一题】Rinne Loves Edges

题意：原本一颗无根树，以s为根结点拉起，求这颗树中任意叶子结点都不可到达s的最小代价 dp[u]表示以u为根的子树中的所有叶子结点都到达不了u的最小代价 ①u是叶子结点时dp[u] = inf; ②其余 dp[u]:for(int v : son[u]){ dp[u] += min(dp[v]...

2020-03-31

0 571

【每日一题】滑动窗口

维护一个单调队列，以最小值为例，队首是最小值的下标，将新加入的元素加入到队尾，但要pop掉那些比新加入元素还要大的元素再加入队尾（即如果比队首最小值还要小将整个队列pop掉再加入队尾），但是队首元素不一定就是这个窗口的答案，它可能在窗口的左边，所以从队首开始pop掉那些下标比i-m还要小的元素，最大...

2020-03-30

1 533

【每日一题】数学考试

思路：先求得一个东西：sum[i]表示从区间[ai...ai+k-1]的区间和，求到n-k+1就OK了，后面的没用；然后呢，搞一个结构体，这个结构体有id和val：分别对应就是i和sum[i]；这个结构体按val排序；然后就可以干坏事了。。。。先枚举左区间的开头，从1到n-2k+1，对于每一个左区间...

2020-03-26

0 596