splayx
- 浏览: 82635 次
- 性别:
- 来自: 北京
-
最新评论
-
lazy_：
怎么感觉看起来像ReadWriteLock?
多线程下的一种编程模式 -
splayx：
方世玉 写道自旋锁，用于读远大于写的并发场景很合适，参考JDK ...
多线程下的一种编程模式 -
方世玉：
自旋锁，用于读远大于写的并发场景很合适，参考JDK内部的CAS ...
多线程下的一种编程模式 -
teasp：
你这个是类似轻量级锁的办法，对于写少读多的情况确实很合适。也可 ...
多线程下的一种编程模式
文章列表
对于一些稍复杂的问题，并不像简单的问题那样一眼可以将解法看穿，
但是这些题目的解法往往也不会比简单问题的解法高深多少。
我们不妨先得到朴素的解法，但不能停留在该解法表面的观摩，
而是要积极的去挖掘朴素解法的特点，
然后加以优化而获得原本问题的解法。
一个问题，看呈现在我们面前的有哪些对象，哪个对象会是突破口呢？
不妨对他们逐个进行分析，发现了他们之间的联系？
对于单个对象的分析，其实也是要找突破口，有哪些“口”呢？
我们也要善于将思维方法进行分类，正着搞不行，反着呢？
一个对象也可能会由多个对象组成的，这好像又回到了问题的开端。
很多问题往往只是个组合问题，即可以分解为一些已经被解决的简单问题，
在积累一定简单问题的解决方法的基础上，只要善于分析，可以解决很多看似新颖的问题。
一个n * n的矩阵，每次操作如下，选择i, j，交换i, j行，交换i, j列，问从一个初始矩阵到达一个目标矩阵的最小操作步数。
经分析发现，这个矩阵是对称的，然后把它看做一个图的连接矩阵表，每次操作就相当于交换两个点的编号。
所以现在的问题就是枚举点一一对应的方式，然后找置换环，算出最小的答案就好了。
由于可以看出3个点的位置确定了所有点的位置，于是暴力枚举就有办法了。
补充：
如果不对称，而且每次操作是交换行或交换列呢。如果只是问能否到达，其实就是问两张对应的二部图是否同构。
结点编号为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是一一对应的。
所以结论成立！
给出n个单词和一个goodstring，从n个单词中随机选K个（每次选择是独立的）连接起来，称其为longstring，
求goodstring在longstring出现次数的期望。
矩阵乘法卡精度了，而且时间复杂也太高。。
解决这个问题的关键的得到以下结论：
在longstring中第m(m > L)个单词出现goodstring的次数只与前面的L个相关，L = goodstring.size()。
而这L个的每一个的选择都是独立的。即对每两个相同的单词（位置 > L)，出现goodstring的期望值是一样的。
所以当K > L时，每加随机一个 ...
给出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 ...
526.5_1000
- 博客分类：
- SRM
从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]} ...
一只兔子每次可以跳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
532_450_1000
- 博客分类：
- SRM
450P是个动态规划的题目，由于没有发现本质的状态，没能在比赛中做出来。
开始看数据那么小考虑怎么状态暴力求出来，然后再预处理一下，复杂度过不去。
思考的方向仍未改变，即还是考虑已处理的点构成的状态，需要记录的信息非常多，而且不能利用奇偶性。
就这样纠结到最后。
状态设计：已处理的点构成的状态，未处理的点构成的状态，以上两种情况混合。这里的处理也许换成扫描更合适。
1000P也是个DP题目，div1-hard难得能比较顺利地想出来，记录一下思维过程吧。
将K种颜色顺序化。
首先想到的是状态为d(n, m, tmax, K), 处理倒数第K种颜色，n行，行 ...
stl迭代器边界值的左++和左--
- 博客分类：
- 常识
今天对stl中vector和set迭代器边界值的++和--做了些试验。
也查看了一下源码。发现
vector.begin()的值左--就会报错，原因是源码中有以判断如果是第一个元素时不可以进行这个操作，
vector.end()的值左--却可以，最后的运算是地址值的--，
set.begin()的值左--变成set.end()
set.end()的值左--变成最后一个元素
set.end()的值左++会报错。源码中作了特殊判断。
set.end()好像是红黑树中特殊的结点。
但是set中的所有正常的元素(end除外)都可以++,--,O(∩_∩)O~
临时编码的时候使用se ...
这个题目转化为以下问题是关键：
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] 是否可以 ...
Question：
S[N]是T[N]的一个置换，求所有S[i]和T[i]差的绝对值的和恰好为moves的置换方法数。
Solution：
将S从小到大排序，从左往右进行动态规划。
状态(t, k, s)表示处理到第t个元素，它（不包含）之前有k个元素是要跟它（包含）后面的元素匹配的，
使用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;
} ...
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 [] ...
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]
两个状态相互推算!!
递归 ...