Think On Think
splayx · 共 90 篇文章
分析随笔_2
对于一些稍复杂的问题,并不像简单的问题那样一眼可以将解法看穿, 但是这些题目的解法往往也不会比简单问题的解法高深多少。 我们不妨先得到朴素的解法,但不能停留在该解法表面的观摩, 而是要积极的去挖掘朴素解法的特点, 然后加以优化而获得原本问题的解法。
2012-04-13 13:55 · 分析 · 评论(0)
分析随笔_1
一个问题,看呈现在我们面前的有哪些对象,哪个对象会是突破口呢? 不妨对他们逐个进行分析,发现了他们之间的联系? 对于单个对象的分析,其实也是要找突破口,有哪些“口”呢? 我们也要善于将思维方法进行分类,正着搞不行,反着呢? 一个对象也可能会由多个对象组成的,这好像又回到了问题的开端。 很多问题往往只是个组合问题,即可以分解为一些已经被解决的简单问题, 在积累一定简单问题的解决方法的基础上,只要善于分析,可以解决很多看似新颖的问题。
2012-04-09 14:08 · 分析 · 评论(0)
525_1000
一个n * n的矩阵,每次操作如下,选择i, j,交换i, j行,交换i, j列,问从一个初始矩阵到达一个目标矩阵的最小操作步数。 经分析发现,这个矩阵是对称的,然后把它看做一个图的连接矩阵表,每次操作就相当于交换两个点的编号。 所以现在的问题就是枚举点一一对应的方式,然后找置换环,算出最小的答案就好了。 由于可以看出3个点的位置确定了所有点的位置,于是暴力枚举就有办法了。 补充: 如果不对称,而且每次操作是交换行或交换列呢。如果只是问能否到达,其实就是问两张对应的 二部图 是否同构。
2012-03-14 16:42 · SRM · 评论(0)
Prüfer sequence
结点编号为1,2,3....,n(n >= 2)的一棵树对应的prufer sequence是长度为n - 2的一个序列(序列元素为{1,2,...,n},于是生产树的总数为n^(n - 2)。 prufer sequence的产生方法: 将树的叶子结点逐个剥去,直至剩下两个结点。 剥第k个:取出当前的叶子编号最小的结点,设为y,设它的邻居的结点编号为x,设置ps[k] = x,剥去y。 显然树的形态和prufer sequence是一一对应的。 所以结论成立!
2012-03-01 16:14 · 数学 · 评论(0)
526_1000
给出n个单词和一个goodstring,从n个单词中随机选K个(每次选择是独立的)连接起来,称其为longstring, 求goodstring在longstring出现次数的期望。 矩阵乘法卡精度了,而且时间复杂也太高。。 解决这个问题的关键的得到以下结论: 在longstring中第m(m > L)个单词出现goodstring的次数只与前面的L个相关,L = goodstring.size()。 而这L个的每一个的选择都是独立的。即对每两个相同的单词(位置 > L),出现goodstring的期望值是一样的。 所以当K > L时,每加随机一个单词产生的goodstring的期望数也是一…
2012-02-29 20:47 · SRM · 评论(0)
533_1000
给出n个频率freq[n],用{"pi", "ka", "chu"}构造n个单词work[n],使得任意一个单词不是另一个单词的前缀,求work[0] * freq[0] + work[1] * freq[1] + ...的最小值,及其方法数。 用{"pi", "ka", "chu"}(2, 2, 3)构造一个字典树,联系哈弗曼编码,将freq降序排列,则长的先构造。 由于任意一个单词不是另一个单词的前缀,所以单词都再叶子结点上。 dp状态为(deep, k, t1, t2, t3) 表示已处理完深度至deep的结点,构造了k个单词, 深度为k + 1的叶子结点有t1个, 深度为k + 2的…
2012-02-28 15:14 · SRM · 评论(0)
526.5_1000
从N个三元组{matches, red, blue}取出尽量多的组,使得取出的{matches}的任何非空子集的异或都不为0,也就是两个人用来玩NIM游戏,先手必赢。在必赢的情况下,求出最小的sum{red} * sum{blue}.. 问题1:取出的{matches}任何非空子集都是先手必赢,可以采用贪心的方法,利用|{matches}| == 矩阵的质。 问题2:使得sum{red} * sum{blue}最小,我们定出贪心的顺序。 对于问题2, 对于每个最优解OPT, 定义: sigma{OPT.red[i]} = R and sigma{OPT.blue[i]} = B. 定义: w…
2012-02-15 21:59 · SRM · 评论(0)
兔子跳
一只兔子每次可以跳a[0], a[1], ..步,a[k] < a[k + 1], 且a[k] | a[k + 1],这只兔子跳了几步, 总长度是LEN,如果兔子每次都跳得尽可能的远,那么兔子经过的点, 必定是所有总长度是LEN的跳法都经过的点。 http://apps.topcoder.com/wiki/display/tc/SRM+527
2012-02-11 22:59 · 数学 · 评论(0)
532_450_1000
450P是个动态规划的题目,由于没有发现本质的状态,没能在比赛中做出来。 开始看数据那么小考虑怎么状态暴力求出来,然后再预处理一下,复杂度过不去。 思考的方向仍未改变,即还是考虑已处理的点构成的状态,需要记录的信息非常多,而且不能利用奇偶性。 就这样纠结到最后。 状态设计:已处理的点构成的状态,未处理的点构成的状态,以上两种情况混合。这里的处理也许换成扫描更合适。 1000P也是个DP题目,div1-hard难得能比较顺利地想出来,记录一下思维过程吧。 将K种颜色顺序化。 首先想到的是状态为d(n, m, tmax, K), 处理倒数第K种颜色,n行,行的长度为m, 每行最多拥有这种颜色的个…
2012-02-10 14:09 · SRM · 评论(0)
stl迭代器边界值的左++和左--
今天对stl中vector和set迭代器边界值的++和--做了些试验。 也查看了一下源码。发现 vector.begin()的值左--就会报错,原因是源码中有以判断如果是第一个元素时不可以进行这个操作, vector.end()的值左--却可以,最后的运算是地址值的--, set.begin()的值左--变成set.end() set.end()的值左--变成最后一个元素 set.end()的值左++会报错。源码中作了特殊判断。 set.end()好像是红黑树中特殊的结点。 但是set中的所有正常的元素(end除外)都可以++,--,O(∩_∩)O~ 临时编码的时候使用set,会因为这些tr…
2012-02-07 16:16 · 常识 · 评论(0)
528_1000
这个题目转化为以下问题是关键: 1. X[i] * P1 + Y[i] * P2 <= cookies[i] (For every i). 2. S = X[0] + X[1] + ... X[n-1] = Y[0] + Y[1] + ... Y[n-1] 3. .X[i] + Y[i] <= S (For every i) 这个其实很显然,而且S具有单调性,为二分做准备。 但是如果一开始就直接陷入高复杂度的dp中,而忽视了这个简单的单调性就比较悲剧。 二分判断d[S][S] 是否可以达到,这样的dp一般可以转化为d[N]最大可以跟什么数搭配,于是二维的状态降了一维。 const int N…
2012-02-03 08:53 · SRM · 评论(0)
530_900
Question: S[N]是T[N]的一个置换,求所有S[i]和T[i]差的绝对值的和恰好为moves的置换方法数。 Solution: 将S从小到大排序,从左往右进行动态规划。 状态(t, k, s)表示处理到第t个元素,它(不包含)之前有k个元素是要跟它(包含)后面的元素匹配的,s表示下来(包含)的匹配的所有差的绝对值的和。 注意到一点第t个元素前面的还未用来匹配的数也是等于k。 转移分5种情况。 1) S[t]跟S[t]匹配 2) 一个S[t]跟S[t]前面的数匹配,有一个S[t]还没有用来匹配 3) 一个S[t]跟S[t]后面的数匹配,有一个S[t]还没有用来匹配 4) 两个S[t…
2012-02-01 12:38 · SRM · 评论(0)
使用sort进行拓扑排序的比较函数
C++等语言自带的sort函数使用的排序算法基本都是快速排序,快速排序是一种不稳定的排序算法,也就是说两个相等的元素排序前后的相对位置是有可能变化的。在使用sort对一个有偏序关系的序列进行拓扑排序时,比较函数的设计要特别注意。例如我们对格点(x,y)进行排序,使得如果有x0 <= x1 而且 y0 <= y1时,(x0,y0)在(x1,y1)前面。 代码大致如下: const int N = 10; struct Node { int x, y; void init(int _x, int _y) { x = _x; y = _y; } }node[N * N]; bool cmp(con…
2011-09-29 20:16 · 常识 · 评论(0)
519_900
1. 数据小, 充分挖潜数据的特点 2. 该DP的DP, 该枚举的枚举 3. 注意将一些枚举简化成O(1)的式子: a[i] + a[i + 1] + ... + a[j] = sum[j] - sum[i - 1] import java.util.*; import java.util.regex.*; import java.text.*; import java.math.*; import java.awt.geom.*; public class VerySmoothDecompositions { public BigInteger [] BI = new BigInteger…
2011-09-20 16:06 · SRM · 评论(0)
517_600
d[u][v] : 用v - u次交换把第u个至第v个变成升序的方法数 t[u][k][v] : 最后一次交换k, k + 1两个位置的数的方法数 可见, d[u][v] = sum{t[u][k][v] | k = u, .., v - 1} t[u][k][v] = zh[v - u - 1][k - u] * d[u][k] * d[k + 1][v] 两个状态相互推算!! 递归写法思路比较清晰. class AdjacentSwaps { public: int theCount(vector <int>); }; const int mod = 1000000007; const …
2011-09-15 20:51 · SRM · 评论(0)