wangpucong

分类

题解(9)

/ 注册

全部文章（共9篇）

题解 | #[CQOI2007]涂色PAINT#

考虑区间,设表示将区间染色需要的最少染色次数, 然后我们考虑如何将区间合并,由于我们对于一段连续的区间可以在一次内涂完, 这就意味着如果我们就可以直接从和位置的答案里转移过来。否者，我们就要枚举断点,将区间分为两部分染色，并将两部分的结果相加，取最小的。具体转移方程如下: #include...

C

2021-12-05

0 353

题解 | #连续子数组最大和(ACM版本)#

so easy 直接上答案 #include <stdio.h> int main() { long long n=0,max,prev,cur; scanf("%lld",&n); scanf("%lld",&prev); max = p...

C

2021-12-02

0 414

题解 | #[C语言]设计LRU缓存结构#

题里面要求 set()和get()都是 O(1) 所以没啥说的，至少LRU中的每个数据需要双向链表存储，这样添加/删除/更新的时候才能做到 O(1) 为了实现通过key直接找到LRU中的数据，只能使用hash，这样才能满足O(1)，虽然会有冲突发生，但是也比每轮通过循环找key-value要好的多 ...

C

2021-11-30

0 425

题解 | #不相邻取数#

不相邻取数的最小场景就是间隔1个取数和间隔2个取数（间隔3个的可以看成是 2个间隔1个的取数，以此类推）所以我们只需要记录 dp[i] = max{aia_iai+dp[i-2] , aia_iai+dp[i-3]} 最大值一定位于 n或者 n-1中（从1开始） #include<st...

C

2021-11-29

2 488

题解 | #【模板】二维前缀和#

#include<stdio.h> int main() { int n,m,x1,y1,x2,y2; long long temp,q,arr[1001][1001]={0}; scanf("%d %d %lld",&n,&m,&q)...

C

2021-11-27

1 405

题解 | #abb字串#

cnt[i] 表示在索引为0~i-1 之间小写字母出现的次数，i-cnt[i]表示除了这个字符以外其他字符的数量，这样我们就可以统计出像 ab这样的字符串有多少个使用dp[i]记录 0~i-1 之间以字符s[i]结尾的字符串有多少 #include<stdio.h> int ma...

C

2021-11-27

5 461

题解 | #最长回文字符串#

最长回文字符串 #include<stdio.h> int main() { char A[55],B[55]; int n,max=0; scanf("%d",&n); for(int q=0;q<n;++q) { ...

C

2021-11-20

1 384

题解 | #二叉树的最小深度#

广度优先搜索计算二叉树最小深度 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { private: int...

C

2021-11-20

0 341

题解 | #二叉树的最小深度#

广度优先搜索计算二叉树最小深度 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { private: int...

C++ C

2021-09-30

0 569