腾讯云开发者社区-腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

数据结构与算法

专栏作者

1812

文章

1332152

阅读量

135

订阅数

洛谷P2196 挖地雷(dp)

编程算法 go

题意 [题目链接] Sol 早年NOIP的题锅好多啊。。这题连有向边还是无向边都没说(~~害的我wa了一遍~~) 直接f[i]表示到第i个点的贡献转移的时候枚举从哪个点转移而来然后我就用一个n^2的算法过了一道n <= 20的题？？。。 #include<cstdio> #include<algorithm> #include<vector> using namespace std; const int MAXN = 101; inline int read() { cha

2018-12-04

4800

洛谷P1970 花匠(dp)

直接用\(f[i][0/1]\)表示到第\(i\)个位置，该位置是以上升结尾还是以下降结尾

2018-12-03

4850

51nod 1597 有限背包计数问题 (背包分块)

对于前\(m\)个直接暴力，利用单调队列优化多重背包的思想，按\(\% i\)分组一下。复杂度\(O(n\sqrt{n})\)

2018-10-25

5010

洛谷P1730 最小密度路径(floyd)

很显然的一个dp方程\(f[i][j][k][l]\)表示从\(i\)到\(j\)经过了\(k\)条边的最小权值

2018-10-22

4940

牛客提高R5 A.同余方程

设\(solve(x, y)\)表示\(i \in [0, x], j \in [0, y]\)满足题目要求的方案数

2018-10-22

3320

cf1059D. Nature Reserve(三分)

然后第二维的二分是没有必要的，直接拿圆的标准方程推一下取个最大值就行了。。。。。昨晚没想到qwq给数学老师丢脸了。。

2018-10-08

3800

牛客NOIP提高组(三)题解

考虑算一个位置的概率，若想要$k$步把它干掉，那么与他距离为$1$到$k - 1$的点都必须阻塞

2018-09-30

3370

cf643E. Bear and Destroying Subtrees(期望dp)

go 编程算法

$f[i][j] = \prod \frac{1}{2}f[son[i]][j-1] + \frac{1}{2}$

2018-09-30

3890

9.22模拟赛解题报告

go ios http html

T2读题就花了半个小时，而且一开始没认真理解题目的意思，前后各dp了一遍，后来仔细揣摩了一下题意，细心品味了一下出题人的语言，正着的dp好像是没用的。。。

2018-09-30

2510

9.21模拟赛解题报告

http 编程算法 go ios

上来看T1，咦？我好像做过这题在仙人掌上的版本。。树上更简单吧。。写+拍 1h，期间拍出了暴力的两个bug。。。

2018-09-30

2970

牛客NOIP提高组(二)题解

好难啊，$30$分的枚举颜色dp应该比较好想把，$f[i][j]$表示第$i$个位置，填了$j$个颜色，然后先枚举一下$1$的颜色，前缀和优化一下，$O(n a_i^2)$

2018-09-17

3600

BZOJ3004: 吊灯(结论毒瘤)

结论：若$k$是可行的，则至少有$\frac{n}{k}$个节点的大小为$k$的倍数

2018-09-17

2210

cf1027F. Session in BSU(并查集匈牙利)

$n$个人，每个人可以在第$a_i$天或第$b_i$，一天最多考一场试，问在最优的情况下，最晚什么时候结束

2018-09-17

4470

BZOJ4241: 历史研究(回滚莫队)

如果询问的两个端点在同一个块中，直接暴力计算，时间复杂度$O(\sqrt{n})$

2018-09-17

4310

HDU 3530Subsequence(单调队列)

给出$n$个数，找出最长的区间，使得区间中最大数$-$最小数 $>= m$ 且$<= k$

2018-09-17

3330

洛谷P3959 宝藏(模拟退火乱搞)

题意题目链接题面好长啊。。。自己看吧。。 Sol 自己想了一个退火的思路，没想到第一次交85，多退了几次就A了哈哈哈首先把没用的边去掉，然后剩下的边从小到大排序这样我们就得到了一个选边的序列，我们要求答案强制按照这个序列选每次退火的时候选两个点交换。枚举每个点，判断是否能更新答案，时间复杂度$O(200 * 1000 * N * M)$ /* */ #include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #in

2018-09-17

4460

洛谷P2062 分队问题(dp)

题意题目链接给定n个选手，将他们分成若干只队伍。其中第i个选手要求自己所属的队伍的人数大等于a[i]人。在满足所有选手的要求的前提下，最大化队伍的总数。注：每个选手属于且仅属于一支队伍。 Sol 直接dp，$f[i]$表示到第$i$个人最多分成几组很显然，一定是从上一个能放的位置转移而来 // luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #define LL l

2018-09-17

4530

ZR#331. 【18 提高 3】括号序列(栈)

那么若区间$(l, r)$是可行的，那么$s_{l - } = s_r$，证明自己yy一下吧。。

2018-09-17

3400

2018年湘潭大学程序设计竞赛G又见斐波那契(矩阵快速幂)

\begin{equation*} \begin{bmatrix} 1&1&1&1&1&1\\ 1 & 0&0&0&0&0\\ 0 & 0&1&3&3&1\\ 0 & 0&0&1&2&1\\ 0 & 0&0&0&1&1\\ 0 & 0&0&0&0&1\\ \end{bmatrix}^{i - 1}* \begin{bmatrix} F_{1}\\ F_0\\ 1\\ 1\\ 1\\ 1 \end{bmatrix}= \begin{bmatrix} 1&1&1&1&1&1\\ 1 & 0&0&0&0&0\\ 0 & 0&1&3&3&1\\ 0 & 0&0&1&2&1\\ 0 & 0&0&0&1&1\\ 0 & 0&0&0&0&1\\ \end{bmatrix}* \begin{bmatrix} F_{i - 1}\\ F_{i - 2}\\ i^3\\ i^2\\ i\\ 1 \end{bmatrix}= \begin{bmatrix} F_{i}\\ F_{i - 1}\\ (i + 1)^3\\ (i + 1)^2\\ i + 1\\ 1 \end{bmatrix} \end{equation*}

2018-09-17

2650

UOJ#386. 【UNR #3】鸽子固定器(链表)

如果我们按$s$排序后，我们就可以枚举$max \ s_i$和$min \ s_i$

2018-09-17

4080

点击加载更多

社区活动

腾讯技术创作狂欢月

“码”上创作 21 天，分 10000 元奖品池！

Python精品学习库

代码在线跑，知识轻松学

博客搬家 | 分享价值百万资源包

自行/邀约他人一键搬运博客，速成社区影响力并领取好礼

技术创作特训营·精选知识专栏

往期视频·千货材料·成员作品最新动态