牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

模拟6 题解

A. 那一天我们许下约定在写出来复杂度为$O(nmd)$的简单dp后，我们考虑优化。题中D的范围远大与N和M，我们在dp的过程中，很多一个饼干都不给的天数是无效的一天。于是我们dp出用i的有效天分完n个饼干的方案数，然后把这i个有效天分配到d天里即可。 $ans= \sum \...

dp 组合计数最短路基环树

2019-07-21

0 331

模拟5 题解

星际旅行题中很特殊的给出，恰好2条边1次经过，m-2条边2次经过，让我有一点想到了欧拉路。然而考试中还是没有想到拆边这个巧妙的方法，只打了一个dfs。正解是将每条边拆为两条，问题转化为删去两条不同的边，使图中存在欧拉路。判断每个点的度即可。在每个边拆为两条之后，每个点的度一定是偶...

dp 组合计数图论欧拉路数论分块数学

2019-07-18

0 378

远古杂题 2

Base基站选址(线段树优化dp) 首先写dp转移式， $dp(i，j)$表示在第i位修建第j个基站。定义$l(i)$为能覆盖i的最靠左的基站，$r(i)$为能覆盖i的最靠右的基站， l和r数组均可以用二分求出， $dp(i，j)=min( dp(u，j-1)+cost(u，i)...

dp 数学高斯消元期望图论状压

2019-07-17

0 785

远古杂题 1

基因匹配Match（数据结构优化dp）题意 1~n 每个数一定出现五次在s1，s2中。求两个字符串的最长公共子序列。考虑n²的暴力写法，对于每一个i，与他相等的一定只有五个。所以可以记录相等的位置优化，分别查询该位置之前的最大值+1转移，Ans记录即可。对于1~n的带修改RMQ，可以...

线段树 dp 状压字符串矩阵

2019-07-17

0 465

[NOIP2013]华容道题解

[NOIP2013]华容道首先是一种比较显然的做法。整个棋盘，除了起点，终点和空格，其他的方块是等价的。对于终点，它始终不会变化，如果搜到终点结束搜索即可，所以我们不需要考虑终点。所以需要考虑的是空格的位置和起点方块的位置。定义$f(i1,j1,i2,j2)$为空格所在坐标$...

图论搜索

2019-07-17

0 457

奇袭 CodeForces 526F Pudding Monsters 题解

考场上没有认真审题，没有看到该题目的特殊之处：保证每一行和每一列都恰有一只军队,即每一个Xi和每一个Yi都是不一样的。于是无论如何也想不到复杂度小于$O(n^3)$的算法，只好打一个二维前缀和草草了事。所以还是要仔细审题。 $O(n^2)$算法：因为每行上只有一个军队，...

分治桶

2019-07-16

0 341

图论杂题

矩阵游戏 https://www.lydsy.com/JudgeOnline/problem.php?id=1059 刚开始以为只要每行每列都存在一个1，就是可行的解，然后发现可以被yxm简单的数据hack掉： 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 正解是...

图论二分图树上差分桶线段树 wqs二分

2019-07-16

0 386

赛艇题解

一颗赛艇 https://www.lydsy.com/JudgeOnline/problem.php?id=4584 虽然名字听起来很暴力（+1s），却是组合计数好题，在考试时都没有看出来是组合计数。对于子任务1/2 区间的总长度不超过1e6，可以将区间内的每个数离散化到一个区间里。...

数学组合计数 dp

2019-07-15

0 437

<span>一些树上dp的复杂度证明</span>

树上染色 https://www.lydsy.com/JudgeOnline/problem.php?id=4033 可怜与超市 http://hzoj.com/contest/62/problem/5 可以简单的列出状态转移方程。它的转移过程类似： ...

dp 复杂度证明

2019-07-15

1 540

记忆的轮廓期望四边形不等式dp|题解

记忆的轮廓题目描述通往贤者之塔的路上，有许多的危机。我们可以把这个地形看做是一颗树，根节点编号为1，目标节点编号为n，其中1-n的简单路径上，编号依次递增，在[1,n]中，一共有n个节点。我们把编号在[1,n]的叫做正确节点，[n+1,m]的叫做错误节点。一个叶...

期望四边形不等式数学 dp

2019-07-02

0 464