Canan

分类

题解(31)

/ 注册

全部文章（共31篇）

涂色PAINT

题意：给定目标字符串状态，现给定一个空字符串，你每次可以对一区间进行染色，求最少染色次数。分析：染色问题首先想到dp，区间染色，我们定义 dp[i][j] 是区间 i 到区间 j 最小的涂色次数，那么答案就是 dp[1][n]。区间dp求解是由小区间合并成大区间的，也就是我们要从长度最短的区间...

2020-07-29

6 1238

乌龟棋（记忆化dfs）

题意：有一堆卡片，卡片上有1-4其中一个数，数字决定向前走的步数，走到某处就获得该点对应的分数，如何调整使用卡片顺序使得到达终点 n 时的得分最大。分析：动态规划每一步促使结果最优解，很明显思路是 dp 或者记忆化搜索（感觉搜索比较好写）dfs(int k,int a1,int a2,int ...

2020-07-24

0 868

区间权值（数学）

题意：分析：（不想打字所以放了张图片）对于每个前n项和，可以用前缀和进行预处理求出，然后负数取模注意下就可以了。代码： #include<iostream> #include<algorithm> #include<stdio.h> #include&l...

2020-07-24

1 761

小A的柱状图（单调队列）

题意：柱状图中已知每个矩形的宽和高，问矩形最大面积是多少？思路：单调栈的模板题，不过也能用单调队列来解决。对于每个位置，我们可以用单调队列（deque）维护一个单调递增的序列，当遇到递减情况时，统计前面前面形成矩形方案的最大值，同时不断维护队列单调性。（矩形底边宽可以用前缀和预处理求出）最后记得...

2020-07-24

0 722

矩阵取数游戏

题意：给定一个nm的矩阵，矩阵每个元素都有一个值a[i][j]，由第一行开始向下走，每次取该行的行首或者行尾的一个元素，得分贡献为所选元素2^k ,k表示第几次取数，由1开始，问得分最大值为多少？分析：由第一行开始走到最后一行，m个回合便可获得全部元素，因此对于每一行的取数对于其他行是无影响...

2020-07-10

0 820

毒瘤xor(异或)

https://ac.nowcoder.com/acm/problem/18979 题意：有n个数a1, a2, ..., aN，给出m个询问，每次询问区间[l,r]，请找出一个数x使得x异或区间每个数的和最大。分析：异或运算，异或1取反，异或0不变，为了使结果最大，因此如果某个数位为1，那么我们...

2020-07-04

0 823

借教室（线段数）

https://ac.nowcoder.com/acm/problem/16564题意：已知每天可以借出去的教室数量a[i],根据先到先得原则，按顺序分配教室，共有m个订单，第i个订单需要[li,ri]区间内借xi个教室，问到第几个订单开始无法满足（教室不够了）分析：m次区间[li,ri]进行修改...

2020-07-01

0 792

小A买彩票（dp）

题意：四种彩票中奖金额分别为1，2，3，4，且各种金额中奖率相等（良心）,小A买了n张彩票，问不亏本概率为多少？分析：模拟几次n发现，n每个中奖金额出现的概率总是由第n-1的概率转移过来的，具体转移方式有4种1，2，3，4，统计可行方式相加即可。因此我们可以用dp进行解决。设dp[i][j]...

2020-06-23

0 906

Forsaken喜欢数论（欧拉筛）

https://ac.nowcoder.com/acm/problem/53079题意：给定一数n，求1~n每个数的最小质因数的和。分析：可以用欧拉线性筛素数法，每个数仅使用其最小素因数筛去，开始先打个表，后面直接统计答案就行了。代码： #include<stdio.h> #incl...

2020-06-22

1 802

扫雷MINE

https://ac.nowcoder.com/acm/problem/20241题意：一个只有两列的扫雷，其中第二列没有雷，并且给出了第二列的数字，该数字表示以其为中心连通的八个格子共含雷的数量，问第一列雷有多少摆放方案？分析：很有趣的一道模拟题，按照题意自己手动模拟答案发现其实第一列雷的方案数...

2020-06-18

7 1553