写得超好的摄影入门

http://www.midphoto.com/chinese/essays/photobook/photographyreview.htm
http://www.midphoto.com/chinese/essays/photobook/photographyreview2.htm  (这篇强烈推荐)
http://www.midphoto.com/chinese/essays/photobook/photographyreview3.htm

作者连载中，希望能早点完成，嘻嘻。

[zz]用光学原理解释景深的本质

http://www.cloudward.net/playground/article.asp?id=135

用光学原理，并作图解释了景深，非常透彻。
由于有图片，只贴了个地址。

光圈的光学原理

原帖标题： 焦距、光圈、变焦、测光等光学原理和应用
地址： http://itbbs.pconline.com.cn/topic.jsp?tid=1602485

焦距、光圈、变焦、测光等光学原理和应用
数 码相机的焦距、通光孔径、光圈（以F值表示）三者有如下光学关系式：f / d = F   ，式中：f为焦距、长度单位mm；d为通（曝）光孔直径、长 度单位mm；F为光圈值，无因次。由此关系式可以看出，曝光孔径越大，F值越小，而光圈越大。这就是为什么F值越小（如佳能750的最大光圈为 F2.8），光圈越大的由来。
    根据凸透镜成像的光学原理：1/u + 1/v = 1/f  这里u 、 v 、 f  分别为物距、像 距、焦距。在摄影技术里，物距u就是被拍摄景物到数码相机镜头（镜片组组成的透镜中心）的距离；像距v就是透镜所成影像到透镜中心的距离；焦距f就是镜头 透镜的聚光焦点到镜头中心的距离。人的眼睛看外部景物，也如同透镜、相机镜头，是一样成像的原理。当然，数码相机的变焦镜头并不是单个透镜成像那样简单。 数码相机变焦镜头，是由多片光学聚光玻璃球面镜片与非球面防色散镜片组成，通过镜片移动实现变焦距、变光圈的复杂光学成像镜头。但其光学原理是相同的。这 里要说明一点，本来通过透镜所成影像是倒立的实像，但为了满足人们的视觉习惯，经过相机内部光学组件的处理，使我们在LCD看到的就是正立的影像啦。
当 我们手持数码相机将镜头对向被拍摄景物，今暂以人为例，那末人到镜头的距离就是物距u，。若被拍摄人和相机都不再移动，那末物距u的值就是固定的。这时， 我们往往需要通过镜头调焦，即改变焦距f值（光圈也在改变），来获得人的影像大小和影像清晰度。从上面的光学公式可以看出，当物距u保持不变，若焦距f变 到最小，即通常所说的广角端，光学关系式若得到平衡，那末像距v必须变为最小。根据相似三角形定理，像距v最小，所成人像也为最小，但此时光圈最大，可视 场景范围为最大；反之，若将焦距f变到最大，即通常所说的长焦端，光学关系式若得到平衡，那末像距v必须变为最大，同理，所成人像也为最大，但此时光圈最 小，可视场景范围亦为最小。我们看到，在来回搬动变焦盘（广角/长焦）时，人像会随之作远近、大小变化。
以上是通过调焦改变像距，得到合适的影像 大小。同理，可以通过调焦，改变像距使所成人像刚好落在CCD感光元件面上，这样拍摄下来的人像是清晰的。 若所成影响落不在CCD感光元件面上，则所成 影像模糊不清。这就是通常说的对焦不准(当然对于晃动，严格说来，也属焦距变动、对焦不准)。对焦所成人像通过等距的反光镜反射到LCD夜镜屏和取景器 上，以便摄影者观察把握。在调焦过程中，有的数码相机光圈和快门会作自动变化匹配；有的则可手动调节光圈和快门，从而获得比较清晰的影像。
通过调 焦使人的眼睛判断影像的大小问题不大，但要求判断的清晰度十分准确很难做到，所以在拍摄之前，要半按快门进行智能测光对焦，以便得到清晰度十分准确的影 像，接下来再全按下快门完成曝光，经过相机内部数字影像处理器等的短暂处理，这样一幅美妙的影像就会最终被拍摄下来了。

关于现在，关于未来 -- 收到HK的studnet visa

现在的我是中山大学的一个UG student，未来两年我将是CUHK的一个 PG Student(MPhil)；
现在的我极其渴望在研究生期间能享有自己的single room，然而未来我却只能住在share room，天意弄人；
现在的我是孤独的，未来的我也会是孤独的；
现在的我是渴望学术研究道路上有所建树的，未来的我却也许无法突破而选择工作；
现在的我充满幻想，未来的我也许会更现实吧；

搜索题做多了都是一个样……广搜题心得体会

 基本就是结合了广搜+状态压缩+剪枝的思路。

比如最近2008 sysu校赛预选的gene reprogram，2008广东省赛的fengshui，以及usaco的clocks(http://ace.delos.com/usacoprob2?a=RRbITFklHzA&S=clocks)
下面用gene reprogram做个例子，备忘一下。

-------------------------------------------------------------------------------

Problem

      As a gene engineer of a gene engineering project, Enigma encountered a puzzle about gene recombination.
      It is well known that a gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T.
      Enigma has gotten a gene, such as "ATCC" for example. And he wants to reorder this gene to a new one, "CTCA" for instance. He can use two kinds of operations: (1) exchange the first two letters, or (2) move the first letter to end of the gene. For example, "ATCC" can be changed to "TCCA" by operation two, and then "TCCA" can be changed to "CTCA" by operation one. Your task is to make a program to help Enigma to find out the minimum number of operations to reorder the gene.

Input

      The input contains several test cases. The first line of a test case contains one integer N indicating the length of the gene (1<=N<=12). The second line contains a string indicating the initial gene. The third line contains another string which Enigma wants.
For each kind of letter, the two strings have the same number of it.

Output

      For each test case, output the minimum number of operations.

Sample input

4
ATCC
CTCA
4
ATCG
GCTA
4
ATCG
TAGC

Sample output

2
4
6

-------------------------------------------------------------------------------

代码：

#include <stdio.h>
#include <string.h>
int len;
int before[15];
int after[15];
char mark[1<<24];            // 用于hash的数组
const int QLEN = 200000;    // 广搜队列长度

int bval,eval;

struct node
{// 广搜树节点
    int value;
    int level;
};
node q[QLEN];
int b,e;    // queue and its head,tail

void inc(int & p)
{// 使用循环队列的方法来保存节点
    if(++p == QLEN) p=0;
}

int zip(int * gene)
{// 状态压缩
    int result = 0,base = 1,i,j;
    for(i=len-1;i>=0;i--)
        result |= gene[i]<<((len-i-1)*2);
    return result;
}

int * unzip(int zipped,int * gene)
{// 解压缩
    int i;
    for(i=0;i<len;i++)
    {
        gene[i] = (zipped>>(len-i-1)*2)&3;
    }
    return gene;
}

int op1(int gene)
{// 对应题目的第一个操作
    int first = (gene>>(len-1)*2)&3;
    int second = (gene>>(len-2)*2)&3;
    int mask = (1<<(len*2))-1;    // for len=4, 11 11 11 11
    int mask1 = ~(3<<(len-1)*2) & mask; // for len=4, 00 11 11 11
    int mask2 = ~(3<<(len-2)*2) & mask; // for len=4, 11 00 11 11
    gene &= mask1;
    gene &= mask2;
    gene |= first<<(len-2)*2;
    gene |= second<<(len-1)*2;
    return gene;
}

int op2(int gene)
{// 对应题目的第二个操作
    int first = (gene>>(len-1)*2)&3;
    int m = (1<<(len*2))-1;             // for len=4, 11 11 11 11
    int mask = ~(3<<(len-1)*2) & m;  // for len=4, 00 11 11 11
    gene = (gene&mask) <<2;
    gene |= first;
    return gene;
}

void getGene(int * gene)
{// 输入gene
    char ch;
    for(int i=0;i<len;i++)
    {
        scanf("%c",&ch);
        switch(ch)
        {
        case 'A':gene[i] = 0;break;
        case 'C':gene[i] = 1;break;
        case 'G':gene[i] = 2;break;
        case 'T':gene[i] = 3;break;
        }
    }
    scanf("\n");
}

int search()
{// 进行搜索，返回结果所在的层数，就是所需要的最短步数
    while( b!=e )
    {
        node n = q[b]; // de-queue
        inc(b);
        if( n.value == eval ) return n.level;
       
        node temp;
        temp.value = op1(n.value);
        temp.level = n.level + 1;
        if( temp.value == eval ) return temp.level;
        if( mark[temp.value] != 1)
        {// en-queue
            q[e] = temp;
            inc(e);
            mark[temp.value] = 1;
        }

        temp.value = op2(n.value);
        temp.level = n.level + 1;
        if( temp.value == eval ) return temp.level;
        if( mark[temp.value] != 1)
        {// en-queue
            q[e] = temp;
            inc(e);
            mark[temp.value] = 1;
        }
    }
    return -1;
}

int main()
{
    freopen("order.in","r",stdin);
    while( scanf("%d\n",&len) != EOF)
    {
        memset(mark,0,sizeof(mark));
        b=0;e=0;
        getGene(before);
        getGene(after);

        bval = zip(before);
        eval = zip(after);
        node temp;
        temp.value = bval;
        temp.level = 0;
        q[b] = temp;    // 把初始状态压入队列
        inc(e);
        mark[bval] = 1;

        int result = search();
        printf("%d\n",result);
    }
    return 0;
}

-------------------------------------------------------------------------------

分析：
1.广搜
一般题目都是给出一个configuration，再给出几个操作op，要求使用这些op对初始状态进行变换，
直到状态变为目标状态为止，如果无法达到则输出-1.
一般有两种问法，比较简单的是问最少要多少步能达到；也可能会要求给出最短路径。
对于前者，无需保存整棵搜索树，只需要记录当前节点的层数即可，这时可以使用循环队列的方法来记录节点。
对于后者，则有必要保存整棵搜索树（所以此时状态压缩、空间分配很重要），才能进行有效回溯。不能使用循环队列，否则会覆盖回溯路径的父节点。
此时广搜队列的长度则能大则大了，不过用内存多少是给定的，就狠狠地用尽它吧！

2.状态压缩
一般题目都是给出一个向量或矩阵表示初始状态。则此时可以把每一个元素可能出现的状态记为base，
则整个状态可以看作一个base进制的数，第i个元素可以看作权为i的系数。
比如本题给出的元素状态有4种：A,C,G,T，我分别把它们记做0，1，2，3.
对于一个具有n位的串a，状态可以表示为一个int：
a[0]*4^0 + a[1]*4^1 + ... a[n-1]*4^(n-1)
因为n最大取12，则可能出现的最大数为4^13-1=64M,可能存在的状态有4^12=16M种。
比如串ACGT=0123,可以表示为0*64+1*16+2*4+3*1=27
一般化一点，可能出现的最大数为base^(n+1)-1，存在的状态有base^n种

此时往往可能出现的问题是：
由于base或n太大，使得一个int无法保存，或者使得剪枝操作无法进行（跟后面介绍的hash方法有关）

考虑到一个字节有8位，用以上的方法我们只利用了其中的2位，因此可以进一步使用位压缩方法进行压缩。

显然，可以使用00=0,01=1,10=2,11=3来表示这四种状态，使用移位的方法可以拼凑出需要的数字。
也许其中会写很多微操作的步骤，不过不用担心，做一个位操作比做一个乘除快多了。

比如本题，使用
    int result = 0,base = 1,i,j;
    for(i=len-1;i>=0;i--)
        result |= gene[i]<<((len-i-1)*2);
从最低位开始每次左移两位来拼凑出最后的int表示。

这样则充分利用了每一个位，使得状态压缩得更精简。

3.剪枝
剪枝的主要原则是发掘操作的顺序、重复，以删除无用的树枝。
比如问题中，可以观察到进行两次操作一则得到原串，进行k=串长度次数的操作二可以得到原串，
另外经过多次的op1，op2操作，也是有可能得到相同的串的。
而USACO的clocks题目，操作之间是无序的，即op1(op2(state)) = op2(op1(state))
而且四个op
此时如果已经搜索过某个状态及其生成的树而无结果，则下次不必再搜索。

剪枝的实现一般是通过顺序搜索或者hash实现的。
对于前者，每次生成新的状态便在队列中搜索是否存在相同元素，如果存在则不必加入；
对于后者，每次新生成的状态在一个开关数组中查询，如果标记了说明已经生成过了，如果没有标记则可以进行搜索，并且标记之，
一般使用char 的数组来完成标记，其实这就是一种桶大小为1，而桶数量为状态数的hash。

对于以上介绍的压缩方法，刚好可以利用hash方法来进行标记，因此这两种技术往往是一起使用的。威力不是一般的强大。
本题16M的状态刚好可以使用一个足够大小的char数组保存，大小为16MB（一般允许使用32MB-64MB的内存）

-------------------------------------------------------------------------------

后记：刚刚开始接触这种题目时，觉得混杂了这么多的算法和技巧很复杂，其实写多了就是一个样
代码也不长，简单的100行左右就好了。因此也可以说是简单题目。
不过很多题目的数据强度都是恰好能让人用尽内存和时间后AC的，所以也不容轻视。