分类： ACM题解

旋转+置换型

 

然后由于要取模，对在分母上的2N求逆元相乘即可
继续阅读“[暑期集训][数学][组合计数] Polya裸题 Invoker HDU 3923”

题意要求求出给定整数分解为2的幂之和的方法数量。（貌似这题还有两个加强版orz日后填坑

写出前几项后可以观察出来规律：当n为奇数的时候 f(n)=f(n-1)，当n为偶数的时候f(n)=f(n/2)+f(n-2)。

这个规律的由来其实很简单，奇数的时候一定每一种分解都有至少一个1，说明这个1不是造成这些分法不同的原因，那么去掉他之后这些分法仍然是不同的，也就是数量没有减少，所以f(n)=f(n-1)。        而偶数的时候可以观察到分法可以分为两类，一类是有1的，这时候必定至少有两个1（因为n为偶数），换句话说这一类里面每种分法都有两个1，那么跟奇数那个同理这个也不是造成这些分法彼此不同的原因，所以去掉之后仍然是不同的也就是数量不会减少，这一部分相当于是f(n-2)；   另一部分都是2的倍数，那么把他们全部除以2的话也仍然保持不同也就是数量没有变，也就是说这一部分相当于f(n/2)。

一开始没写记忆化果断T了几发。。。
继续阅读“[暑期集训][数学][递推] 51nod 1383”

很久很久没做过图论的题了，做一个忽然意识到自己记错了欧拉回路的意义emmm

就当是复习一下吧。

昨天哈，喝了不少酒干了傻事，该过去的就让他翻篇吧，
继续阅读“[训练指南][简单题][图论] 无向图的欧拉回路 Uva10054”

总感觉此题似曾相识，有很类似的求面积而非周长的题目？

题意给出长方形地图然后让求每个点对应的可贩卖的最大周长的矩形面积。考虑每一行的话，往上累计，然后就变成了一维的，在前面一些xx中求得最大/最小值的题，一般直接暴力会超时然后就用单调数据结构优化，这里左边每次动都相当于一个新的开始，所以就是添加和删除操作都在右侧进行，单调栈走起了。
继续阅读“[紫书][单调栈][思维] 求最大周长矩形 UVa12265”

紫书第八章这些题。。有点意思的啊。。

题意让往一个不规则的二维洞穴里面加水问每个地方都不碰到天花板的话最多能装多少水。当然很容易想到用在一点画一条横线然后与其他天花板不相交，但是没想出来怎么在低复杂度求和具体实现。看了紫书题解，才发现这条横线左右两边可以分开来求，这样求一边的时候就可以扫描一遍数组而不用O(n^2)去计算了， 继续阅读“[紫书][思维] 非常见模型 物理 思维与分析 UVa1442”

学习了一下这个算法，emmm不知道什么时候就会用到的感觉。本身功能是在O(n)时间内算出一个串的最长回文子串，其实这个过程也把每个点作为中心的最长回文串计算了一遍

这个算法的话主要是利用回文串的性质，回头整理好了再详细写。

继续阅读“[字符串] 最长回文子串 manacher算法模板题 HDU3068”

题目给了strcmp()的代码，然后问给出n个串两两之间strcmp总共会用到多少次==操作。建立一棵字典树，节点信息存储一个前缀之前出现的次数即可，另外还需要存储的信息是当前节点 是多少个串的结束点（这样就不用把’\n’也加入树了）

坑点的话，自己wa的原因是没有看到他大小写数字都可以有TAT我用我的只考虑了小写字母的Trie送了好几发wa（貌似每次这种题出错都是这样？

继续阅读“[训练指南][字典树][简单] strcmp的比较次数 UVa11732”

题意给一个字符串和单词字典，问把字符串分割成词典中存在的单词可以有多少种方法（单词可以重复使用）首先是像dp那样考虑，令d(i)为从第i个字符开始到结束的字符串的方案数，然后可以得出d(i)=sum{d(i+len(x))|单词x是S[i,l]的前缀}。然后就是找一个串有多少个单词前缀了。。。字典树搜索即可搞定，就是在Trie中查找S[i,l]，一路查过去把遇到的是单词节点的地方加上那里的d就可以了。
继续阅读“[训练指南][字典树] 使用前缀关系进行递推 字典树加速 LA 3942”