已注销

分类

ACM模版篇(139) C++(4) CONTESTS(31) dfs && bfs(59) GitHub(1) Linux(4) OpenGL(2) PHP(5) Python(7) QT(3) Script(4) STL(24) 位运算(3) 其他(37) 动态规划(148) 区间(22) 图形打印(6) 图论(96) 字符串(39) 打表(13) 排序(31) 数学相关(153) 数据结构(73) 数论(101) 暴力解题(31) 机器学习(10) 栈(14) 树(51) 每周都有那么几天不想学习(2) 汇编(6) 知识点总结(17) 笔试试题(15) 网络流(7) 职场老油条(1) 计算几何(17) 贪心(62) 逐梦者(97) 郑州-大连(2) 问题残余(4) 骑行也是追梦(1)

/ 注册

全部文章（共1342篇）

51Nod－1268－和为K的组合

ACM模版描述题解 N比较小，深度优先搜索即可。也可以使用动态规划，典型的0-1背包问题，可是K太大，正常情况会挂，然而这道题数据比较弱，K根本不到1e9的量级。所以如果K的数据稍微一强，就会挂，可以优化超大背包，二进制枚举N/2个状态，然后筛选出所有可能存在的状态，最后再二进...

2021-05-21

0 431

51Nod－1270－数组的最大代价

ACM模版描述题解动态规划，极端考虑法，每个A[i]要么取1，要么取B[i]。状态转移方程也很好推（dp[i][j]:j->0表示A[i]取1，j->1表示A[i]取B[i]）: dp[i][0] = max(dp[i - 1][0], dp[i - 1][1...

2021-05-21

0 596

51Nod－1272－最大距离

ACM模版描述题解方法有很多种，这里介绍两种写法。第一种比较容易想到的写法是将键值和下标封装在结构体中进行排序，然后从尾部检索一遍即可，复杂度O(nlogn)。第二种是使用单调栈优化，可以使复杂度低至O(n)。代码 One： #include <iostream...

2021-05-21

0 354

51Nod－1276－岛屿的数量

ACM模版描述题解先将岛屿和指令全部排序，然后过一遍指令，不断修正岛屿状态，将每条指令的结果转存一下，最后整体输出即可。复杂度Qlog(Q) + Nlog(N)…… 代码 #include <iostream> #include <algorithm> #...

2021-05-21

0 461

51Nod－1285－山峰和分段

ACM模版描述题解这里需要强调的是，峰如果被分割，依然算峰，所以，首先需要对点数据进行峰数据检索，然后处理得到一个pre数组用来存储前i个点数据中有几个峰。当然，我们最多分的段数受峰个数控制。代码 #include <iostream> #include <c...

2021-05-21

0 307

51Nod－1352－集合计数

ACM模版描述题解使用常规思路枚举的话一定会超时，这里需要用到扩展欧几里得算法求满足Ax + By = N + 1的方程大于0的最小值和A、B的最小公倍数，最后分析res可以拆解出来多少个C（最小公倍数）。代码 #include <iostream> #includ...

2021-05-21

0 457

51Nod－1393－0和1相等串

ACM模版描述题解前缀和+Hash记录，复杂度为O(N)。这里需要强调的是要考虑到01这种最长的情况是打头开始的串，所以需要对dif[MAXN] = 0;初始化。代码 #include <iostream> #include <cstdio> #incl...

2021-05-21

0 445

51Nod－1396－还是01串

ACM模版描述题解水题一道，将前i个字符中0和1的个数分别存一下，最后对比即可。代码 #include <iostream> #include <cstdio> #include <cstring> using namespace std;...

2021-05-21

0 385

51Nod－1402－最大值

ACM模版描述题解一开始看到这道题，感觉挺简单的，但是，我只关注了明沟，却忽略了暗坑！！！首先，这里我们将这些特殊点成为卡点，但是不是所有的卡点都能卡住数据的，其中，最容易想到的是t < x - 1的点是无法卡住数据的，所以我们可以直接忽略掉，那么剩下的卡点一定是可以卡住数...

2021-05-21

0 354

51Nod－1414－冰雕

ACM模版描述题解一开始高估了这道题难度，一直在想从中发现规律(￣┰￣*)，结果，╮(╯_╰)╭，只好暴力解之……还真的过了，这里给出一种一般的暴力解法和一种略微优化的暴力解题思路。代码 One： // 常规暴力解法 #include <iostream> #in...

2021-05-21

0 336