rk_no

题解

/ 注册

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

「土」秘法地震（二维前缀和）

题目：给一个nm的01矩阵。问有多少个kk的含1矩阵。（n最大1000）做法：二维前缀和。跟板子没啥区别。。利用二维前缀和可以快速得到某矩形区域中数字的和。那么枚举所有k*k矩阵的右下角位置，利用二维前缀和得到矩阵中1的数量，大于零则ans++即可。代码： #include <bi...

2020-05-21

0 579

比赛（二进制枚举）

题目：你在打比赛，这场比赛总共有12个题。对于第i个题，你的队伍有a[i]的几率解决它。有b[i]的概率从左边那个队那里听会这个题的做法，有c[i]的概率从右边那个队那里听会这个题的做法。请问最终你们队伍解出0-12题的概率分别是多少？做法：每道题做出来的概率可以直接算出来。然后只有12道题...

2020-05-21

0 639

简单瞎搞题(bitset暴力)

题目：一共有 n个数，第 i 个数是 xixi 可以取 [li , ri] 中任意的一个值。设，求 S 种类数。1 ≤ n , li , ri ≤ 100 做法：建个1e6的bitset。从1到n枚举每个数的取值。用bitset左移k位表示前面能表示的所有数+k。就这样直接暴力就行了。代...

2020-05-21

0 749

maze（bfs搜索）

题目：一个n*m的迷宫。问从起点走到终点最短用时。往上下左右走1格花费1s。用一次传送门花费3s。做法：简单题。从起点开始bfs搜到达所有点的最短用时就好了。从每个点转移到上下左右位置以及该点可以开启的传送门的位置。题目不难，细节比较多一点。可以看看我的写法，用优先队列优化bfs。代码：...

2020-05-13

0 829

codeJan与旅行(思维，枚举)

题目： codeJan 非常喜欢旅行。现在有 n 个城市排在一条线上，并且 codeJan 的位置不和任何一个城市的位置重叠。codeJan 想要游览 m 个城市，同时因为时间是不断变化的，游览一个城市多次也是允许的，但是不能永远待在一个城市，否则那样太无聊了。给出这些城市的位置，codeJan 想...

2020-05-12

0 649

过河（离散化dp）

题目：青蛙要从数轴0跳到L（L最大1e9）。每次跳跃步长在[s,t]区间（s、t≤10）。数轴上有m（m最大100）个石头。问青蛙最少跳上的石头数量。做法：表示从0跳到i最少跳上的石头数量。枚举所有步长转移即可：表示当前位置是否是石头。然而发现L很大，数组开不了这么大，所以我们需要对石头间...

2020-05-12

0 885

加分二叉树(记忆化搜索)

题目：一棵二叉树的中序遍历是1、2、3...n。每个结点有点权a[i]。让你确定一棵树使val最大。最后输出val并给出先序遍历序列。（n最大100）做法：一个区间DP的题。但感觉dfs码起来更清晰，思路是一样的。对[l,r]区间确定的一棵二叉树，它的我们通过枚举根节点的位置来转移：转移...

2020-05-12

1 978

Moovie Mooving（状压DP）

题目： n部电影，有时长和若干放映起始时间。Bessie可以在某部电影的放映阶段去看这部电影或中途离开。他不会看同一部电影2次。问Bessie最少需要看几部电影使得他在0~L时间段内一直看电影。(n最大20) 做法：状压DP。表示在状态下Bessie能连续看电影到的最远时间。是二进制状态。第i...

2020-05-12

0 771

模拟战役（dfs，贪心）

题目： 2个4*n的图，表示后手和先手部署炮台的方案。问先手那方在消灭后手所有炮台的条件下最多能保留自己多少炮台。做法：先求出后手和先手炮台联通块数量和。若，无解。否则，由于先手每次打击后必定暴露一个联通块。我们贪心选择暴露炮塔数量少的联通块就行了。所以先手方最多能保留最大的个联通块中的炮台数...

2020-05-11

0 827

[SCOI2012]滑雪与时间胶囊（最小生成树）

题目： a180285非常喜欢滑雪。他来到一座雪山，这里分布着M条供滑行的轨道和N个轨道之间的交点（同时也是景点），而且每个景点都有一编号i（1 ≤ i ≤ N）和一高度Hi。a180285 能从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边，且i 的高度不小于j。与其他滑雪爱好者不同，a1...

2020-04-30

3 882