开开心心写

ACM题解

ACM - dp(1) ACM - 二分(8) ACM - 数学(1) ACM - 矩阵(1) ACM-线段树(1) Android(3) angr(3) Crypto(5) CTF之旅(84) Linux(8) pwn(1) python(6) reverse(3) ubuntu(1) Windows(4) 大作业(1) 恶意代码分析实战(43) 数学(4) 数据结构专题班(15) 未归档(4)

/ 注册

全部文章 / ACM题解（共245篇）

POJ3613 Cow Relays 倍增floyd求最短路

第十届河南省赛I题~ 题意：从起点S，到终点E，跳上N次，花费的最小值是多少其中全图有M条边，表示从A点到B点花费L值首先注意到这个题点的标号不是常规的1到n，不是连续的，可以重新对点进行标号图论题，最短路径问题首先想模板，因为点数少，所以floyd：n^3可以求出任意两点之间...

2020-05-03

0 542

HDOJ 1693 插头dp

百度一下：基于连通性状态压缩的动态规划问题 #include <iostream> using namespace std; const int maxn = 12; __int64 dp[maxn][maxn][1<<maxn]; int mp[12][12]; in...

2020-05-03

0 335

2018 0CTF mayagame 插头dp

writeup是说：插头dp模板题 http://westerns.tokyo/writeups/0ctf2018quals.html#maya-game 代码添加注释： #include <iostream> #include <vector> #include <...

2020-05-03

0 356

BZOJ 1087 插头dp

这里的几个判断是通过下面这个博客，搞懂了轮廓线的定义以及状态转移的： https://www.cnblogs.com/iiyiyi/p/5846864.html 不过，这个图的轮廓线应该是这样的：我们当前需要做出来的决策是点（i，j），之前的1代表之前的状态已经确定好（否则是不合法的）红色线...

2020-05-03

0 427

POJ 2411 插头dp

这个题找到的题解很好，把轮廓线的原理解释得非常清楚 https://www.cnblogs.com/iiyiyi/p/5846864.html 其中，重点是这样一句话：轮廓线状压的表示不是按照纵坐标大小从左到右，而是按照从左到右，从上至下的顺序(K4..K0)来的也就是说，当我们填写图中O这个格...

2020-05-03

0 488

URAL 1519 formula 1 插头dp

假设我们当前已经填充成如图所示的情况：需要填写（i，j）这个格子了那么：我们有两个大类，六种情况~~~ 第一类：（i，j）格子本身是个障碍点，不可达那么，应该是如图：当左插头和上插头都不存在的时候，那么才是合法的状态，可以状态转移第二类：（i，j）...

2020-05-03

0 457

SGU448 Controlled Tournament 状压dp

题意： N名选手淘汰赛，要求指定的选手M夺冠。给定胜负关系矩阵，Aij=1，代表选手 i 能够战胜选手 j 。要求比赛树的高度尽量小，求所有可能的方案总数分析：这个树的高度尽量小很坑很坑，要怎么理解！树高尽量小是前提，然后才是选手M夺冠意味着，当N给定时，树的高度已经限定了，因为是淘汰赛，...

2020-05-03

0 421

状压dp POJ 3254 Corn Fields

链接：http://poj.org/problem?id=3254 题意：m*n的矩阵，每个格子中都有个0或者1，0表示不能放牧，1表示可以放牧，要求不能出现相邻的牧场都放牧了。求方案总数注意到这个题的m和n都特别小，都不超过12 那么：想到状态压缩枚举每一行的所有放牧的方案，用1表示放牧，用0...

2020-05-03

0 451

状压dp POJ1185 炮兵阵地

题目链接：http://poj.org/problem?id=1185 和POJ3254一个套路：只是把“相邻”的定义改了一下 POJ3254：相邻指的是上下左右各一格本题：相邻指的是上下左右各两格同样地：数据还是很小，那么我们可以枚举前一行，以及前两行的状态来实现dp转移 dp[i][j][...

2020-05-03

0 541

求前n个数的所有约数之和

n_max <= 10^12 思路1：暴力求解每个数的约数，然后相加时间复杂度：O(n ^ 3/2)：枚举每个数O(n)，对于每个数的分解需要O(n ^ 1/2) 思路2：从约数角度考虑，考虑每个可能约数的贡献对于1，一定是任意数的约数，所以1的贡献为1*n 对于2，...

2020-05-03

0 593