首页 > African Sort
开通博客写题解
头像 lalalaterraria
发表于 2020-07-27 21:22:53
A African Sort题意: 给定排列 p，每次可以选一个下标集合等概率打乱包含的数并花费集合大小的代价，求给 p 排升序最优策略下最小代价的期望，对 998244353 取模 做法：一个permutation可以看成若干个环（i连p[i]），显然不存在大小不为1的环即为排序完成。那么对所有大 展开全文
去ta的博客 赞 (5) 回复(5) 收起
头像 yesuweiYYYY
发表于 2020-07-27 21:28:27
题目大意： 定义名为K-bag的一类数组：由几个k的全排列头尾链接组成的数组。如一个3-bag： 【1 2 3 3 2 1 2 1 3 】 是由【1 2 3】【3 2 1】【2 1 3】连接而成的数组。给你一个长度为n的数组和一个数k，(1<=n<=2e6,1<=k<=1e9 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 甜心小兔叽
发表于 2020-07-30 18:23:43
题意：定义矩阵的压强为 所有元素的和 / 最后一行的和。给一个n * m的矩阵，选取若干行和若干列，相交位置的元素提出来作为子矩阵，问所有子矩阵的最大压强 思路：若从原矩阵中选一行作为子矩阵的最后一行，为了使压强最大，选中列在该行上面的所有元素肯定都要选中，即行的选取一定是从第一行到某一行都选 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”