木屋

mhlwsk的博客


  • 首页

  • 关于

  • 标签

  • 归档

  • 搜索

hihoCoder1513 (小Hi的烦恼)[bitset]

发表于 2018-09-01 | 更新于 2020-07-30 |

题目链接:https://hihocoder.com/problemset/problem/1513

题目大意:给定许多人的五门课排名,询问每个人有多少人所有课的排名都能碾压他。

小Hi:今天我们来解决“五维数点”问题。
小Ho:什么是“五维数点”问题呢?
小Hi:抽象来说,我们现在有n个在五维空间中的点$(X_i,Y_i,Z_i,Q_i,W_i)$。现在对于每个点,我们需要知道所有坐标均比它小的点的数量。
小Ho:这个问题看起来似曾相似,如果是在二维空间中似乎是一个经典的运用线段树解决的题目。
小Hi:对。但是现在是在五维空间中,看起来难度大了很多。
小Ho:我想用集合的角度去考虑这个问题。对于每一维,比如说X维,我们能通过按X维的坐标排序,不难求出对i点来说X维比i点小的所有点的集合。现在的问题就转化成对点i来说,求出X维,Y维,Z维,Q维,W维分别比i所在那一维小的集合的交的大小。
小Hi:对!你的思路很好。但是集合大小是O(N^2),如果暴力实现的话时间复杂度就达到了O(N^2)。
小Ho:那该怎么办呢?
小Hi:我们想想可以用什么合理的方法来表示集合以此来加快求集合交的操作。
小Ho:我觉得一种比较直观的方法是用一个长度为n的01串,第i位为0表示i不在集合中,1表示i在集合中。
小Hi:不错哟!那你仔细观察一下,求集合的交到底具有什么性质?比如对于n=6,集合{1,4,5}和集合{2,4,5,6}来说,它们的交是{4,5}。
小Ho:集合求交在01串中可以这么看:若两串第i位都是1,则交的串第i位是1,否则第i位就是0。这个例子中两个集合的01串分别为100110,010111。它们的交就是000110,也就是{4,5}。
小Hi:是的。我们把这个问题转化成了对01串的操作。你有没有发现,这其实类似于二进制中”and”的操作。如果我们把01串看成一个二进制的大整数,那么集合求交就变成了对两个大整数做”and”的操作。
小Ho:哈!有道理。但是这看起来复杂度似乎依旧是O(N^2)的。
小Hi:啊!但是你有没有想过,我们可以利用程序语言中的32位整数加速这个”and”,也就是说我们每32位压缩成一个32位整数,这样本来我们需要32次的操作,一下就变成了做一次位运算“并”的操作。所有我们最后的复杂度能优化成O(N^2/32)。
小Ho:原来如此!那具体怎么实现这个“压缩”的过程呢?
小Hi:其实c++/Java已经为我们设计了这样一种数据结构来解决这种问题。它的名字叫bitset/BitSet。它类似于数组,但是你可以直接对其做位运算。bitset中还有一些有用的函数,如count/cardinality可以快速算出二进制中有多少个1(这其实是一个不太好做的问题)。
引用自题目页提式

感觉比较难想到的是单独对于每一维排序后可以直接$O(n)$递推出每个人这一科的排名关系。

阅读全文 »

POJ3678 (Katu Puzzle)[2-SAT]

发表于 2018-09-01 | 更新于 2020-07-30 |

题目链接:http://poj.org/problem?id=3678

2-SAT模板题,注意四种条件中a & b = 1和a | b = 0的情况,前者需要u^1 -> u, v^1 -> v连边,后者需要u -> u^1, v -> v^1连边。
相当于无论如何都要选u^1(无论如何都要选v^1)。

阅读全文 »

BZOJ2208 (连通数)[bitset, Floyd]

发表于 2018-09-01 | 更新于 2020-07-30 |

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2208

其实这题可以用Floyd…
用bitset跑Floyd传递闭包处理出每一对点之间的连通关系,然后$O(n^2)$枚举两个点之间是否连通计数即可。
感觉bitset常数还是比较小的。

阅读全文 »

BZOJ2734 (集合选数)[状压DP, 矩阵]

发表于 2018-09-01 | 更新于 2020-07-30 |

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1087

考虑到选取集合中的元素不能是乘2或乘3相邻,我们尝试构造一个矩阵:
$$
\begin{bmatrix}
x & 3x & 9x & \cdots \\
2x & 6x & 18x & \cdots \\
4x & 12x & 36x & \cdots \\
\vdots & \vdots & \vdots & \ddots \\
\end{bmatrix}
$$
这样只需要在矩阵中选取不相邻的元素就能满足题意了。
这个矩阵的长宽是log级的,因此问题转化成了类似互不侵犯King的问题。
$x$代入不是2或3倍数的数构造多个矩阵,结果根据乘法原理相乘就是答案了。

阅读全文 »

CodeForces 101343J (Husam and the Broken Present 2)[状压DP]

发表于 2018-09-01 | 更新于 2020-07-30 |

题目链接:http://codeforces.com/gym/101343/problem/J

题意:构造一个序列包含所给的N个子序列(N≤15),求构造序列的最短长度。
考虑状态压缩,有2^N种状态,设dp[i][j]表示状态为i,以第j个子序列结尾的最小长度;
状态转移:从以第j个子序列结尾的状态转移到以第k个子序列的状态:
dp[i|(1 << (k-1))][k] = min{dp[i][j]+a[k][0]-num[j][k]} (其中,a[k][0]表示第k个子序列的长度,num[j][k]表示第j个子序列的后缀与第k个子序列的前缀重合部分的长度)
注意:先将被其他子序列包含的子序列删去……
引用自GraceSkyer

感觉这题有包含的情况是个坑啊,另外需要注意的是两串相等的情况,可以把它们特判成两串不包含的情况。

阅读全文 »

BZOJ1087 (互不侵犯King)[状压DP]

发表于 2018-09-01 | 更新于 2020-07-30 |

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1087

状压dp经典题
f[i][j][k]保存第i行(包括第i行)之前放了j个国王,当前行用二进制表示后对应十进制数为k的方案数。count[k]表示k所对应的二进制中1的个数。
状态转移方程比较显然:f[i][j][k]=sum{f[i-1][j-count[k]][p]};
其中k满足 (k&(k<<1))==0
其中p满足 (p&(p<<1))==0&&((p<<1)&k)==0&&(p&k)==0&&((p>>1)&k)==0
引用自sunshinezff

阅读全文 »

HDU2243 (考研路茫茫——单词情结)[AC自动机,矩阵乘法]

发表于 2018-08-29 | 更新于 2020-07-30 |

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2243

题目大意:给定n个模板串,问有多少个长度不超过L的含至少一个模板串的字符串。
首先考虑问题的相反问题,求有多少个不含任何模板串的字符串,并只考虑长度正好为$l$的字符串的数量,这个问题的解题方法见POJ2778(DNA Sequence)。
现在我们已经能计算长度为$l$的字符串的数量,但问题要求的是长度不超过$L$的字符串数量,答案对应的矩阵为 $A^1+A^2+…+A^L$ 。
令 $S_n=A^1+A^2+…+A^n$,则$S_n=S_{n-1}A+A$
$$
\left[ \begin{matrix} S_n & A \end{matrix} \right] = \left[ \begin{matrix} S_{n-1} & A \end{matrix} \right] \left[ \begin{matrix} A & 0 \\ E & E \end{matrix} \right] = \left[ \begin{matrix} 0 & A \end{matrix} \right] {\left[ \begin{matrix} A & 0 \\ E & E \end{matrix} \right]}^n
$$
这样就能用矩阵快速幂求出不含任何模板串的答案对应的矩阵了。接下来要用总方案数减去这个答案。
使用同样的方法求出$T_n=26^1+26^2+…+26^n$,并用$T_n$减去上述答案即可。
$$
\left[ \begin{matrix} T_n & 26 \end{matrix} \right] = \left[ \begin{matrix} T_{n-1} & 26 \end{matrix} \right] \left[ \begin{matrix} 26 & 0 \\ 1 & 1 \end{matrix} \right] = \left[ \begin{matrix} 0 & 26 \end{matrix} \right] {\left[ \begin{matrix} 26 & 0 \\ 1 & 1 \end{matrix} \right]}^n
$$

阅读全文 »

POJ2778 (DNA Sequence)[AC自动机,图论,矩阵乘法]

发表于 2018-08-29 | 更新于 2020-07-30 |

题目链接:http://poj.org/problem?id=2778

题意:给定m个模板串,问有多少种长度为n的字符串使得它不包含任何一个模板串。

首先根据模板串建出trie图。可以想到任意一个字符串都对应了trie图上从根结点起始的一条路径。因此问题转化为在trie图中从根结点开始长度为n的,且不经过某些点的不同路径数量。

设A是图G的邻接矩阵,即:
$$
a_{ij}=
\begin{cases}
0& \text{节点i和节点j之间无边相连} \\
n& \text{节点i和节点j之间有边相连且边数为n}
\end{cases}
$$
注:除非有自环,否则$a_{ii}$为$0$
令$B=A^l$,则$b_{ij}$表示节点$i$到节点$j$长度为$l$的不同路径的数量。

将邻接矩阵中不能经过的节点(单词节点和能通过后缀链接到达单词节点的节点)对应的行列全部置为0,然后用矩阵快速幂算出结果即可。

阅读全文 »

HDU2457 (DNA repair)[AC自动机,动态规划]

发表于 2018-08-29 | 更新于 2020-07-30 |

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2457

题目大意:给定n个模板串,再给一个待匹配串,问至少修改待匹配串的几个字符能使得它不包含任何一个模板串

可以想到一个满足条件的串一定能在trie图上沿边一直走却遇不到任何一个单词节点(或者能通过后缀链接跳转到单词节点的点),而这个trie图事实上构成了一个状态转移图,我们把它应用到DP的状态转移上。
令dp[i][j]表示处理到第i个字符且停留在trie图上第j个状态时的最小修改次数,则状态转移方程为dp[i+1][ch[j][c]]=min(dp[i][ch[j][c]],dp[i][j]+(idx(s[i])!=c))

阅读全文 »

HDU3065 (病毒侵袭持续中)[AC自动机]

发表于 2018-08-29 | 更新于 2020-07-30 |

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3065

这题是AC自动机模板题,统计每个模板串在文本串中的出现次数。下面贴上模板。

需要注意的是找到一个单词时,可以是直接找到了这个单词的单词节点,也可以是通过这个节点经由后缀链接跳转到了其它单词节点。因为有类似这种情况:10是1010的后缀,但如果匹配到1010显然也应该匹配一次10,这时应该通过后缀链接跳转过去修改10对应的匹配数。
注:后缀链接指向当前节点能通过fail指针跳转到的上一个单词节点的标号。

阅读全文 »
1234…13
mhlwsk

mhlwsk

I will persist until I win.

130 日志
80 标签
RSS
GitHub E-Mail
Links
  • 离光
© 2017 – 2020 mhlwsk
由 Hexo 强力驱动
|
主题 – NexT.Pisces