rk_no

题解

/ 注册

全部文章 / 题解（共71篇）

子序列（dp，LIS变形）

题目：小美有一个由n个元素组成的序列{a1,a2,a3,...,an}，她想知道其中有多少个子序列{ap1,ap2,...,apm}(1 ≤ m ≤ n, 1 ≤ p1 < p2 ,..., < pm ≤ n)，满足对于所有的i,j(1 ≤ i < j ≤ m), 成立。输出答案...

2020-04-23

0 698

边的染色（思维）

题目： n个点，m条边的无向图。有些边被标记为0或1，有些还未标记。问你将剩下的边用0或1标记，满足图中所有环边权异或和为0的方案数。mod998244353 做法：这题不会，看题解才懂。。边权的方案不好弄，考虑点权。这里的思想就是，假如我确定了某个环上所有点的点权，使点权异或和为0。那么边（u...

2020-04-22

0 693

K-th Number(二分、滑动窗口)

题目：一个长为n的序列a[]，所有长度≥k的区间取出第k大的数形成一个新序列b[]。问b[m]的值。做法：显然我们不可能求出b中所有数然后取出第m个。所以想到二分这个数，设为x。然后问题就转化成判定性问题：a[]中所有连续区间的第k大的数≥x的区间个数是否≥m。用滑动窗口的做法使这个judg...

2020-04-21

0 679

糖糖别胡说，我真的不是签到题目（优先队列）

题目：从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1...

2020-04-20

0 658

华华给月月准备礼物（二分）

题目：二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将...

2020-04-20

0 813

Accumulation Degree（换根dp）

题目：一棵树，边有流量。让你找一个点u到所有叶子结点路径上流量和最大。做法：换根dp。首先选定一个非叶子结点为根，一遍得到子树到该子树下叶子结点的流量。（v是u的儿子结点，w是边的流量）。表示以为树根点，到所有叶子结点路径上流量和。显然此时我们以此为基础再一遍将根换到儿子结点，求得所有值...

2020-04-15

0 722

树学（换根dp或重心）

题目：牛妹有一张连通图，由n个点和n-1条边构成，也就是说这是一棵树，牛妹可以任意选择一个点为根，根的深度为0，对于任意一个非根的点，我们将他到根节点路径上的第一个点称作他的父节点，例如1为根，1-4的；路径为1-3-5-4时，4的父节点是5，并且满足对任意非根节点。整棵树的价值。。即所有点的深度...

2020-04-15

0 796

逆序对（组合数学）

题目：求所有长度为n的01串中满足如下条件的二元组个数：设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。答案对1e9+7取模。做法：由于到了。递推都做不了了，唯有推柿子大法。考虑每一位和前面的位对答案的贡献。第位上的0对答案无贡献。第位上的1对答案的贡献是前位上0的数...

2020-04-15

0 845

Xorto（xor前缀和）

题目：给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。1<=n<=1000,0<=数组元素<100000。做法：首先预处理出数组，表示这个区间元素的和。这样我们就可以得到任意区间的和。[l,r]区间的xor和 = prefix...

2020-04-14

1 945

Treepath（树形DP）

题目：给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。1<=n<=100000 做法：设1为根，树形DP求解。设：表示以为根的子树中结点到的路径为偶数的数量。表示以为根的子树中结点到的路径...

2020-04-14

0 974