SSuryxin

题解

ACM个人赛题解(2) CF(1) dp(2) 图论(12) 数论(1) 笔记(5)

/ 注册

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

The Triangle

题意：给你一个倒三角形，计算从顶部开始到底部某个地方的路径中所有数字总和的最大值，每次只能向左斜向下或者右斜向下走思路：使出秘技dp 根据雨巨的说法，有两种，我从哪里来？我到哪里去？对于我从哪里来，写状态方程的话是这样的： dp[i] [j] = max(dp[i - 1] [j] + tr...

2021-03-09

0 533

过河卒

过河卒题意：对于n * m的棋盘，棋盘中有九个点不能走，问你一个大头兵从左上角走到右下角的路径有多少条思路：使出秘技dp 状态转移方程是：tr[i] [j] = tr[i - 1] [j] + tr[i] [j - 1] 有一些细节： 🐎走的八个点的坐标得找对，同时得判这八个点是否符合题...

dp

2021-03-09

1 623

带门和钥匙的迷宫

迷宫题意: 有一个二维迷宫，需要从S点走到E点，每一步之能选择上下左右四个方向前进一格。W代表墙壁，D代表一扇门，需持有钥匙才能通过，K代表钥匙，经过该点钥匙就会自动进入你的口袋，'.'代表是空的，可以走。问你从起点到终点最少需要几步？思路：因为问的是最短路的长度，所以是bfs题但是这个题...

2021-02-28

2 947

纪念品分组

题意：对一堆价值为tr[i]的纪念品进行分组，每组最多两件，且每组的价值不能超过w，输出最少的分组数目思路：是个贪心，需要找到最少的数目，就得尽量让小的去找大的，还得是总和不超过w 我们可以取两个变量l和r，一个在数组头一个在数组尾，开始找，如果说tr[l] + tr[r]的值小于等于w，就说...

2021-02-26

0 745

[SCOI2005]扫雷MINE

传送门题意：有一个n行两列的矩阵，第一列放雷，第二列代表其周围八个方向的总雷数，现在给你第二列的数，求第一列雷有多少种摆法？思路：对于第一个格子，只有有雷和没有雷的情况，而当第一个格子确定了，根据第二列的第一个和第二个数和第三个数就能确定第二个格子有没有雷，所以这个题只需要讨论第一个格子有没...

2021-02-25

0 511

「土」巨石滚滚

传送门题目描述：帕秋莉掌握了一种土属性魔法，她使用这种魔法建造了一个大型的土球，并让其一路向下去冲撞障碍，土球有一个稳定性x，如果x < 0，它会立刻散架，每冲撞一个障碍，土球会丧失ai的稳定性，冲撞之后，又会从障碍身上回馈bi的稳定性帕秋莉想知道，如果合理的安排障碍的顺序，在保证...

贪心

2021-02-25

0 570

Subsequence

尺取法 Subsequence 题意：给你长度为n的序列，找一个连续子序列的和大于等于s，问该子序列的长度最短为多少思路：尺取法用两个变量来代替尺子的两端，我用i代替左端，j代替右端最开始序列和sum小于s，就让sum加上tr[j]，并让j++ 当sum-tr[i]大于等于s时，说明序列删...

2021-02-24

0 564

种类并查集

传送门食物链题意：有三种动物，其食物链形成一个环，即A吃B，B吃C，C吃D。现在有n个动物，每个动物都属于ABC中的一种，给你k个描述，判断这k种描述的真假，求出假话的总数。每次描述输入三个数字d，x， y。 d = 1时，表示X和Y是同类 d = 2时，表示X吃Y 思路：对于每个动物，...

种类并查集并查集

2021-02-23

0 525

1029.巧分整数

题意：将n分成k个数，每个数不能为0，分法不能重复（不考虑顺序）思路：神奇的dp！ dp[i] [j] = dp[i - j] [j - 1] + dp[i - j] [j] (dp[i] [j]指将i分成j份）因为每个数不能为0，所以对于数i，先减去j，得到能支配的数，在将这些数进行分配。...

2021-02-06

0 567