题意：

N*M的格子，每个格子放着电脑（2）、椅子（1）其中之一或为空（0）。

每个工程师需要一张椅子，以及这张椅子相邻的与该椅子构成直角的两台电脑进行办公。

电脑和椅子都是独占的，问这N*M个格子最多可以容纳多少工程师。

题目分析：

首先可容纳工程师的最大数量等于没有重合的组成直角的电脑、椅子、电脑数量；

即最后结果的限制在于：能凑成直角的椅子的数量，以及每把椅子周边四种电脑组合的选择；相邻的成直角的三个格子（拐角为椅子，两边为电脑）构成一个组合；

这里很关键的一个特征就是构成电脑对的两台电脑一定正好相差一行，即可以认为椅子可分为两类；

于是可以往二分图匹配方向上想，椅子分为两类分别在一边，另外考虑一把椅子只能用一次的限制转换为拆点。

最后解法就是建图求最大流：

对于所有的电脑，建立从源点到所有奇数行有电脑的点的边，从偶数行有电脑的点到汇点的边，（每台电脑得独占）边权均为1；

对于每把椅子，（由于一把椅子只能用一次）拆成相连的边权为1的两个点（流入点、流出点）；

对于每把椅子周边的电脑组合，分别建立从奇数行电脑到椅子流入点，椅子流出点到偶数行电脑的两条边，边权为1；

从源到汇求最大流即可。

规模估算：点数最多为500*500*2+2，边数最多为500*500*3，最大解为500*500/4，考虑到图的特殊性质算法时间复杂度可以接受。

代码如下（不含网络流模版部分）：

const int DX[] = {0, 1, 0, -1};
const int DY[] = {1, 0, -1, 0};

struct Graph g;
int N, M;
int table[505][505];

int main()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &table[i][j]);
		}
	}
	g.clear();

	int S = N*M, T = N*M+1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (2 == table[i][j]) {
				int id = i*M+j;
				if (i % 2 == 1) {
					g.insert(S, id, 1);
				} else {
					g.insert(id, T, 1);
				}
			}
			else if (1 == table[i][j]) {
				int myid = i*M+j, altid = myid+T+1;
				g.insert(myid, altid, 1);
				for (int d = 0; d < 4; d++) {
					int x = i + DX[d], y = j+DY[d];
					int nx = i + DX[ (d+1)%4 ], ny = j+DY[ (d+1)%4 ];
					if (x < 0 || x >= N || y < 0 || y >= M) continue;
					if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
					int cid = x*M + y, nid = nx*M + ny;
					if (2 == table[x][y] && 2 == table[nx][ny]) {
						if (x % 2 == 1) {
							g.insert(cid, myid, 1);
							g.insert(altid, nid, 1);
						} else {
							g.insert(nid, myid, 1);
							g.insert(altid, cid, 1);
						}
					}
				}
			}
		}
	}
	cout << g.maxflow(S, T) << endl;

	return 0;
}

ps: 作为”难题不会水题不快”的菜鸟，这次北大校赛跟大神组队混严重拖后腿，在场上也就能看看题敲敲模版了——还好这次有一道H是纯模版题，于是整场比赛居然摸了下键盘，sigh~

这个列表用来检查基础知识挺好的，只是感到压力很大！

来源：http://blog.renren.com/blog/232287273/799725113

最近有熟人找工作。贴出来一份本科生应该会的知识点总结吧。找工作的同学也可以帮我加一些内容，可能会有遗漏。同时也算是本科生的一个总结吧，在大学四年应该要学点什么东西回家吧。

粗体是比较重要，但是经常被人遗漏的一些知识点。斜体是有点偏的东西，有点难，会则好，不会有兴趣的可以看看。没兴趣没必要看了。

暂时这些，想起来再加。

基础知识

CPU：主频，Cache

内存：内存到CPU有较大latency

磁盘：机械装置。磁盘结构，工作原理。磁盘操作：read/write/seek三个操作。扇区大小：512Bytes，新硬盘已经有4K扇区的了。

磁盘中有NVRAM做Cache

知道什么是RAID，RAID的几种配置。

数据结构

每个数据结构都应该知道：为什么要有这个数据结构，能做什么不能做什么，空间复杂度和每种操作的时间复杂度。简单的数据结构要很熟练的写出代码或伪代码。

数组

链表（单向，双向/环形）

二项堆。要求要会用数组实现。

哈希表

Bloom Filter（经常被人忽略的一个重要的东西）

并查集 （Union Find Set）

字典树（Trie/Prefix Tree）

二叉搜索树（最普通的那个）

AVL Tree

Red Black Tree（不要求会写……太复杂了，知道和AVL Tree的区别就好）

B-Tree B+-Tree （最好知道两者的区别，尤其要求要会写，知道为什么B-Tree会比AVL/RBTree快）

Skew/Leftist Heap(用来做merge的heap）

Splay

算法

二分搜索（一定要会！别小看了，代码不是很好写）

各种排序：

冒泡排序（也还是看一看吧……）

quick sort

merge sort（数据量远远大于内存容量的时候排序最佳）

heap sort

bucket sort

radix sort （异常重要。Google笔试之一：N个数，每个都是[0, N^2)，O(N)时间内排序）

搜索（深度优先，广度优先。要求熟练）

动态规划（Dynamic Programming）（最优子结构来加速）Bellman-Ford的那个定理最好能弄明白

Dijkstra/Floyd/Bellman-Ford最短路径算法

网络流（好吧……至今我反正是没在项目中用到过……但是应该还是会用的）

语言

这块东西都非常重要！除了斜体以外都重视一下。

C的一些知识：

#include是预处理，是把头文件拷贝到当前行。注意include hell，注意头文件一定要#ifndef #define #endif

static意义。static还可以保证symbol不被export。可以避免链接时重名。（因为C没有namespace）

内存：stack和heap。Heap在Programming Language里面会说。C里面就realloc/malloc/free就够了，也可以了解一下calloc。

Near和far已经不再使用了。（这货从来没在unix上存在过吧？）

内嵌汇编（反正我是不会，随查随用）

void foo()和void foo(void)在函数声明时候是不同的（这个和C++不一样）

weak symbol（这个我也没搞懂）

C的symbol table不会做像C++一样做Name Mangling 。可以直接根据函数名称来用里面的函数（dlopen/LoadLibaray）

Sequence Point是什么。要知道

volatile的语义（一会还会在体系结构里面出现）

C++的一些知识：

别告诉面试官你精通C++

C++是多根继承

知道啥是virtual function，知道有virtual table的存在。

Constructor的时候不要virtual function（要知道为什么）

Destructor的时候不要throw（要知道为什么）

Destructor要virtual，如果你打算别人继承你的话。

New/free就是malloc加constructor和destructor

有个叫placement new的语法，让你直接调用constructor

Name Hiding （有点恶心的东西）

C++会做name mangling，把函数重命名。

除了public继承，还有private继承。（我不会T.T）

有virtual继承，为了解决多继承对象冗余的。太恶心，一般人不会用。

template是个过于灵活的东西，它有图灵完整性（这个知道一下即可），也就是说，任何编程能解决的问题，C++可以在编译期搞定。（假设没有编译器自己的限制）

template不能把成员方法的实现写在.cpp文件里。（除非编译器支持export关键字，但是目前没有支持的编译器）

最简单的container style template要会用要会写。STL那些container要会用！Std::vector, std::list, std::map…

Design Pattern和Modern Design Pattern（重口）那些东西会一点就行。

Singleton（会单线程的即可，多线程的略重口）

知道啥叫Wrapper/Adapter，这个很简单。就是用另外一个借口包装一下而已么。

知道Factory这个Pattern

Policy Based Design。Modern那书里面口味最轻的。

了解一下Prototype, Bridge什么的就够了。用的不多。

编译期算出来fibonacci数列的第N项……编译期输出素数序列……（呃……口味重一些）

知道啥是boost，最好会用boost::thread，boost::function的库。

Java一些知识：

Java相对来说和谐很多了。没啥好说的。

Java是单根继承。没多继承。可以implements几个interface。但是interface明显是纯虚的。

Java有个东西叫Reflection的，需要知道，需要会用。

Java的很多东西都要用到上面提到的design pattern，但是其实这东西就会那几个常见的就可以了。

Java可以写GUI程序。有两大比较时髦的库，一个是swing，一个是SWT。最好会一个。

Java可以写Web程序，有Java Servlet标准和JDBC标准。熟悉一下即可。

很多库，会也行，不会也行。问题不大。什么hibernate, JPA. Spring/Guice(我喜欢用), Struts等……

呃，不会写web程序但是需要知道tomcat是啥吧……类似的还有jetty和glassfish等。

操作系统

进程，什么是进程。（呜，具体定义不必太具体）

什么是用户态什么是内核态。为什么会有两个态。（为了安全）

进程通过系统调用让内核做一些事情。最好知道系统调用发生了什么。系统调用是CPU辅助的，不是普通的系统调用。

知道什么是虚拟内存。知道内存是分页的。

虚拟内存怎么实现的：需要知道有个东西叫做页表。Page Table

知道CPU对虚拟内存要有支持。（具体：MMU，soft tlb (MIPS)/ hard tlb (x86)。x86下是CR3寄存器，MIPS下是写入和读取tlb entry）

知道x86下，虚拟内存地址空间是4G，Linux下内核态1G用户态3G。Windows一般是2G/2G。所以linux 32位下，分配2.7-2.8G内存以后基本就没法再分配了。Windows下这个限制会更大。（所以才要用64位系统嘛……-w-）

需要知道世界上有个叫做mmap/CreateMapping的东西!（为啥大家都不知道？）

什么是线程。线程模型和进程的区别（共享heap……当然stack不可能是共享的……）

什么是Fiber，为什么Fiber不能直接用来实现线程。

知道什么是mutex。知道race condition。知道这货多恶心多难写。（写了10000行多线程代码做毕设的泪流满面……）

知道mutex乱加后果是很严重的。（deadlock。Thread1: lock(A), lock(B) Thread2: lock(B), lock(A)）

知道怎么用mutex(lock/trylock/unlock)实现read/write lock。

知道有个东西叫做condition variable。知道这货的来源是一个叫做monitor的模型。

知道pthread怎么用……pthread_create/pthread_mutex_lock/pthread_cond_wait。这个一定要会，花不了多长时间的。

知道fork()，知道vfork()。知道Linux上fork的实现很快。NT上CreateProcess很慢。

知道什么是时间片，什么叫分时调度。几种常见的调度……Round Robin什么的

知道什么叫swap。进程中的虚拟内存用的太多了，物理内存没那么大。

知道虚拟内存可以被swap到disk。

有个东西叫做I/O cache，读写磁盘的时候会用内存存住一些来加速访问。

I/O cache的内存有限，所以要page replacement algorithm。虚拟内存中哪页内存到disk也是这个问题。

常见的page replacement algorithm有LRU等（知道LIRS，ARC会很管用哦……)

文件系统。这个要会用！

Open/read/write/seek/close/opendir/readdir/closedir/stat等等……都要会

最好也要会pread/pwrite。多线程的读写文件的时候有用。

知道什么是data什么是meta data。（文件内容是data，非文件内容是meta data）

知道FAT文件系统，知道它为啥烂。了解一些时髦的文件系统，如果ext3/xfs。了解一下就够了，没必要都懂。

网络

主要Application Layer用的比较多。当然啦，我是说软件开发的职位，网络工程师那就明显不同了。

需要了解HTTP。现在随便一个地方就做网站，HTTP协议是至少要知道的。知道什么是GET/POST，知道有cookie这个东西。

知道SSL是什么。

写过网络程序……知道什么bind()/listen()/accept()/connect()，这些要会用。（参数记不清没事）

知道DHCP

会换DNS是什么。知道ssh是什么。（潜台词……会翻墙）

知道有个traceroute可以用，知道有个wireshark可以用。

知道TCP和UDP的区别

简单知道TCP的怎么保证数据完整性的。知道TCP怎么握手的（SYN/SYN_ACK/ACK)，知道怎么断开的(FIN/FIN_ACK)，知道主动断开会出现TCP_TIME_WAIT这个状态。（这个状态在Linux下会持续一分钟……）

知道TCP的几种congestion control（太难了……不会）

Programming Language

好吧，编译器前端是我的软肋。但是我个人认为它比较理论，不太实用。（但是似乎国内课本一直比较强调这些？）反正我用到的编译器的parser都是手写的，不过如果你真的不幸找到了一份编译器前端的工作……如MS,Apple,IBM，反正你的日子也不好过:)。所以呢……

只要知道FSM/LL/LALR就够了。状态优化，AST生成和优化，flex,bison我觉得可以统统无视掉了。就从IR产生后了解就好了。

编译器几种常见的优化，要知道。比如用寄存器，而不是每次都访问内存，（顺便，扔掉你的8086汇编知识。x86和x86_64有好多通用寄存器的）比如将定长循环展开，比如inline某些短的函数。

知道什么叫强类型和弱类型。以及类型检查，类型推导(type inference)

然后就是多而复杂的runtime知识。

知道什么叫libc，知道malloc的一些实现细节：（百度面试题）小的内存chunk从Heap分配，大内存走mmap。知道over_commit_ratio

知道malloc是线程安全的，多线程调用malloc的时候不用上锁。知道malloc在有些特殊情况下可以很慢，是个潜在的性能瓶颈。知道如何优化。（用给力的malloc实现，如google的tcmalloc，facebook/bsd的jemalloc；fixed size object可以自己手动写内存池）

知道jvm是什么东西……（就是那个叫做java的程序……= =）

知道靠谱的jvm在运行.class文件的时候是有可能编译成本地代码运行的（我是说x86机器代码），这个功能叫做JIT(Just In Time Compile)。所以面试的时候别犯傻的说java慢是因为java解析执行！

Java有GC。Sun JVM里面有很多GC算法。

GC算法的本质要知道，就是对象互相引用形成一个图，然后我们知道当前要用的一些对象（比如在stack上的，比如JVM本身持有的root object），然后求子图的连通性。和这些要用对象连通的对象就是有用的对象，剩下的就是垃圾。

常见的算法要知道：mark and swap, mark and copy, mark and compact，知道什么是generational GC。

Sun JVM里面的一些算法如果知道更好。

数据库

数据库是最复杂的系统之一了。所以我也没打算自己把它弄懂-_-

SQL应该会吧，最基本的不能忘。高级的呢……用的时候再查吧。

transaction的性质-ACID

知道为了保证transaction的性质有数据库各个层次的锁。row lock, table lock什么的

各种方向的锁，S/X/U至少要知道，所谓的compability matrix要看得懂。

transaction具体实现要知道一些。了解即可。

知道journal/shadow paging这两个approach

知道journal具体怎么工作的。

undo/redo log。（顺便提一下file system也有这个东西，但是很多file system只有redo log，没有undo，因为没必要保证高consistency，也必要保证很高的scalability）

最后，知道ARIES这个名字。算法具体不用了解。

传统的DB现在其实都不行了，DBMS这方面的research都表明，现在硬件快起来以后，传统数据库的很多资源很浪费。现在有了各种NOSQL（其实是no relation）数据库。

总之，最重要的是transaction，别老看SQL什么的。

体系结构

体系结构对程序员来说是偏理论的知识了，但是需要尽可能深入的了解一些东西，理论扎实写程序才快嘛。这里我列出一些本科学过的有点用途的理论知识，当然随着深入，理论知识会越来越有用，当然也就完全不局限这点东西了。

知道CPU是多周期的，流水线作业的。

知道对CPU来说……Cache大是很王道的……知道存在instruction cache和data cache

知道CPU有寄存器……知道有特殊寄存器和通用寄存器……（MIPS也存在特殊寄存器的！当然要用特殊指令写入，读取……这块内容被课本无情的阉割掉了）

知道世界上存在RISC CPU………………（-_-|||）

知道有x86有浮点寄存器。（某面试题……32位下void pass_a_double(double* d)和void pass_a_double(double d)哪个快……后者，虽然多拷贝了4个字节，但是传入的时候会优化成浮点寄存器）

volatile的语义。可变的，所以每次读写都会直接写入内存（或者cache），编译器不允许做任何优化到寄存器的优化。

知道乱序执行，知道CPU有多线程技术来回切换/多套原件。知道CPU有多核……（喂…………）

知道SIMD是什么概念。会用最好。（我不会）

知道CPU里面内存访问是有Cache的，这也是为什么BTree会比rbtree/avltree快！同理，很多数据结构都要尽量”成块”，这样减少了CPU的cache miss。

知道有branch prediction就行。

知道CPU对操作系统提供了很多支持……比如系统调用，虚拟内存。（如果能知道是怎么提供的更好）

知道x86提供了虚拟化支持，对操作系统或者虚拟机有直接支持。跑虚拟机会快一些。（要是你能娓娓道来怎么支持的………………直接找intel让他们给你发offer吧，或者去世界TOP10的学校读PHD没问题了………………-_-|||）

AI

AI的面试知识也不少，但是我不做那块东西。对于码农知道一些也无坏处吧，我认识的一个朋友他现在就要对AI有点了解的码农……

知道A*是什么算法，知道heuristic search的理论要求（就那个不等式就行……）

逻辑推理？我也不知道有没有用哎……DPLL什么的似乎还用过一次？@.@

first order logic的一些科普知识……-w-主要是防止面试官问你悖论相关的问题。哦耶。

基本的概率要会计算吧！条件概率，bayes公式不能忘记！

会点随机更好，知道markov chain是啥就行……

知道HMM，Viterbi算法（其实就是DP……）。（好吧HMM我也忘得差不多了）

知道bayesian network，知道mcmc。（我从来没用上过……不码这方面的东西的说）

总结

四年过去了，总要学点东西吧……很多人都说计算机四年什么都没学，或者学的东西从来没有用上过。我觉得应该还是他们不知道哪些重要哪些不重要吧。我们学校的教学首先内容落后，其次重点都放在理论上，很多实际的东西大家没有接触过，不知道应该会哪些知识。我作为一个小小的码农，就说说我四年学到的这些基础知识，这些基础知识都是码代码的时候用过的，但愿对你有用。

稍微讨论了一下，可以用O(n)的时间复杂度和O(1)的附加空间实现：根据源链表依次复制出新链表的对应节点，并将新节点插入到源节点后，新链表的rand指针指向原链表的rand；然后遍历一遍链表，将新链表的rand指针指向对应元素的next元素（即新链表中对应的rand指针元素）；最后将新链表和源链表分离。

代码如下：

/*
 * Author: Lixiang Liu @ ICT, CAS
 * File Name: goso_list_copy.c
 * TODO:用C++类实现
 */
#include <stdio.h>
#include <stdlib.h>

struct node_t {
    int data;
    struct node_t *next;
    struct node_t *rand;
};

struct node_t * copylist(struct node_t **dest, struct node_t *src) {
    struct node_t *p, *q;
    p = src;
    while (p != NULL) {
        q = (struct node_t *)malloc(sizeof(struct node_t));
        q->data = p->data;/*XXX: copy p->data to q->data*/
        q->next = p->next, q->rand = p->rand;
        p->next = q;
        p = q->next;
    }
    p = src;
    while (p != NULL) {
        q = p->next;
        q->rand = q->rand->next;
        p = q->next;
    }
    p = src;
    *dest = p->next;
    while (p != NULL) {
        q = p->next;
        p->next = q->next;
        p = p->next;
        if (p != NULL) q->next = p->next;
    }
    return *dest;
}

int main(int argc, char *argv[]) {
    /*test code*/
    struct node_t *src, *dest, *p, *q;
    int i = 0;
    src = NULL;
    for (i = 0; i < 10; i++) {
        p = (struct node_t *)malloc(sizeof(struct node_t));
        p->data = 10-i;
        p->next = p->rand = src;
        src = p;
    }
    p = src;
    for (i = 0; i < 10; i++) {
        int j, s = ((i+1)*7) % 10;
        q = src;
        for (j = 0; j < s; j++) {
            q = q->next;
        }
        if (q == NULL) q = src;
        p->rand = q;
        p = p->next;
    }
    printf("------source list:\n");
    p = src;
    for (i = 0; i < 10; i++) {
        printf("%d\t%d \t%d\n", p, p->data, p->rand->data);
        p = p->next;
    }
    copylist(&dest, src);
    printf("====compare with destination list:\n");
    p = src, q = dest;
    for (i = 0; i < 10; i++) {
        printf("%d:%d\t%d -- %d\t\t%d -- %d\n", p, q, p->data, q->data, p->rand->data, q->rand->data);
        p = p->next;
        q = q->next;
    }
    /*free memory space*/
    p = src, q = dest;
    for (i = 0; i < 10; i++) {
        p = p->next;
        q = q->next;
        free(src);
        free(dest);
        src = p;
        dest = q;
    }
    return 0;
}

各种笔试面试有各种关于链表的题（复制、找环、反转等等），这种题考实现还好，用来考“算法”其实没啥意思（毕竟很多人用应试的方法来准备这种题）。

数据结构：

struct Node {
    char data;
    Node *next;
};

个人yy了一个O(n)时间复杂度的解法：先把单向链表的后一半反向，然后前后进行对比看是否相等，判断完后将单向链表恢复原样。

其他不多说，直接上代码（未测试）：

bool isParalindom(Node *head)
{
    bool res = true;
    int len = 0;
    Node *p = head, *q, *r, *s;
    while (p != NULL) p = p->next, len++; //求长度
    q = head;
    for (int i = (len+1) / 2; i >= 0; i--) q = q->next; //定位到链表的后一半（若为奇数个元素则跳过最中间元素）
    r = NULL;
    while (q != NULL) { //翻转链表的后一半
        p = q->next; q->next = r;
        r = q; q = p;
    }
    q = r;
    p = head;  res = true;
    while (r != NULL) {//判断前后是否对称
        if (r->data != p->data) {
            res = false;
            break;
        }
        p = p->next, r = r->next;
    }

    while (p->next != NULL) p = p->next;
    r = NULL;
    while (q != NULL) {//将后面一半翻转回链表的原样
        s = q->next; q->next = r;
        r = q; q = s;
    }
    p->next = r;
    return res;
}

这是一篇受密码保护的文章。您需要提供访问密码：

密码：

解答：很裸的状态压缩DP，状态为每行下面连成的图案状态（即最多可能有3^12种状态）。

f[row][nxt_state] = sum(f[row-1][pre_state])，其中pre_state和nxt_state分别为一行合法时上边图案状态和下边图案状态。

对每一行，枚举其能形成的状态——即保证同行相邻两方块之间图案相同时的pre_state和nxt_state。

优化：以上方法复杂度为O(4^m*n)，对于所有图案都相同的极限数据，每行枚举次数为4^12=16777216，需要进行优化，这里合并同一方块不同翻转方案形成的图案相同的情况。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>

using namespace std;

typedef long long lint;

const int M = 12;
const int N = 12;
const lint MOD = 1000000007LL;

const int IDX[] = {0, 1, 2, 3, 0, 1, 2, 3};

int n, m;
int cr, pr, row;
char str[N][M][6];
lint f[2][551444];
char pre[N+1], nxt[N+1];

int get_val(char *st) {
    int res = 0;
    for (int i = 0; i < m; i++) {
        res *= 3;
        if (st[i] == 'R') res += 1;
        else if (st[i] == 'C') res += 2;
    }
    return res;
}

void dfs(int c, lint v, char con) {
    if (c == m) {
        pre[c] = nxt[c] = '\0';
        int nval = get_val(nxt), pval = get_val(pre);
        v = v * f[pr][pval] % MOD;
        f[cr][nval] = (f[cr][nval] + v) % MOD;
        return ;
    }

    int cnt = 0, vv[4];
    char pp[4], nn[4], cn[4];
    for (int i = 0; i < 4; i++) {
        if (c && str[row][c][i] != con) continue;
        char tp = str[row][c][ IDX[i+1] ], tn = str[row][c][ IDX[i+3] ], tc = str[row][c][ IDX[i+2] ];
        bool flag = true;
        for (int j = 0; j < cnt; j++) {
            if (pp[j] == tp && nn[j] == tn && cn[j] == tc) {
                flag = false;
                ++vv[j];
                break;
            }
        }
        if (flag) {
            pp[cnt] = tp, nn[cnt] = tn, cn[cnt] = tc;
            vv[cnt] = 1;
            ++cnt;
        }
    }

    for (int i = 0; i < cnt; i++) {
        pre[c] = pp[i], nxt[c] = nn[i];
        dfs(c+1, v * vv[i] % MOD, cn[i]);
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int ca = 1; ca <= T; ca++) {
        scanf("%d %d", &n, &m);
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                scanf("%s", str[r][c]);
            }
        }

        int all = 1;
        for (int i = 0; i < m; i++) {
            all *= 3;
        }

        cr = 0, pr = 1;
        for (int i = 0; i < all; i++) f[cr][i] = 1LL;
        for (int r = 0; r < n; r++) {
            cr ^= 1, pr ^= 1;
            row = r;
            memset(f[cr], 0LL, sizeof(f[cr][0])*all);
            dfs(0, 1, 'C');
        }

        lint ans = 0;
        for (int i = 0; i < all; i++) {
            ans = (ans + f[cr][i]) % MOD;
        }
        cout << "Case " << ca << ": " << ans << endl;
    }
    return 0;
}

问题描述：有n个阵地，已知我方在每个阵地上的士兵数，若我方士兵不为0则表示该阵地由我方占领，否则为对方占领。某些阵地之间有通道，我们认为士兵可以经过1单位时间从1个阵地移动到相邻（有通道相连）的阵地。对于一个阵地，如果其相邻的阵地中有非我方阵地，则表示其受到威胁，该阵地中我方人数。

现在求：对我方士兵进行一次1个单位的移动（调动），在保证我方不丢失阵地的情况下（即我方每个阵地上的人数不为0），使得我方所有受到威胁的阵地中人数最少的阵地的人数尽可能多。

算法：二分+网络流。

1、二分我方受到威胁的阵地最后的最少人数mid。

2、将我方阵地拆成两个点（前点–>后点），两个点之间边得容量为该点人数（限制一次流动）；

3、建边：source到我方阵地（前点）容量为该阵地人数的边；我方阵地（后点）到所有相邻的阵地，容量为我方阵地人数的边。

4、我方阵地（前点）到sink的边：若为收到威胁阵地，边容量为mid，否则为1；

5、验证所得最大流是否为满流即满足要求（受到威胁的阵地数*mid + 未受到威胁阵地数）。

int main()
{
    int T;
    scanf("%d", &T);
    for (int ca = 1; ca <= T; ca++) {
        int n;
        scanf("%d", &n);
        int num[n];
        int low = maxint, up = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &num[i]);
            up += num[i];
            low = min(low, num[i]);
        }
        bool gr[n][n];
        bool border[n];
        int nb = 0;
        memset(border, false, sizeof(border));
        for (int i = 0; i < n; i++) {
            char str[n+5];
            scanf("%s", str);
            for (int j = 0; j < n; j++) {
                if (str[j] == 'Y') {
                    gr[i][j] = true;
                    if (num[i] > 0 && num[j] == 0) {
                        border[i] = true;
                        ++nb;
                    }
                }
                else gr[i][j] = false;
            }
            gr[i][i] = false;
        }

        Graph g;
        int ans = -1;
        while (low <= up) {
            int mid = (low + up) / 2;

            g.n = 2*n+2;
            g.clear();
            int source = 2*n, sink = 2*n + 1, target = 0;
            for (int i = 0; i < n; i++) {
                if (!num[i]) continue;
                g.insert(source, i, num[i]);
                g.insert(i, i+n, num[i]);
                if (border[i]) {
                    g.insert(i, sink, mid);
                    target += mid;
                } else {
                    g.insert(i, sink, 1);
                    target += 1;
                }
            }
            for (int i = 0; i < n; i++) {
                if (!num[i]) continue;
                for (int j = 0; j < n; j++) {
                    if (!num[j]) continue;
                    if (gr[i][j]) {
                        g.insert(i+n, j, num[i]);
                    }
                }
            }

            int maxflow = g.maxflow(source, sink);
            if (maxflow == target) {
                ans = mid;
                low = mid + 1;
            } else {
                up = mid - 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

题目是很有趣的博弈模型。Petra和Jan轮流取good（商品？），Petra的策略是当前最优的，每次取所有good中对自己价值最大的，同等情况下取对Jan来说价值最小的（真和谐！）；Jan的策略是全局最优的，每次做出一个使自己最终所有取的good的价值的和最大的选择，同等情况下使Petra的最终价值和最大。

问最后结果即Petra和Jan取得的goodies的价值和分别是多少？

模型很经典，所以解答也很经典：简单DP，f[i][j]表示前i个中Jan取j个时能获得的最佳结果（即Jan取得的goodies值最大，同等情况下使得Petra取得的goodies最终的值最大），状态转移也很简单见代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1011;

typedef struct val_t {
    int p, j;
    bool operator<(const struct val_t &b) const {
        return (j < b.j || (j == b.j && p < b.p));
    }
};

bool pcmp(const struct val_t &a, const struct val_t &b) {
    return (a.p > b.p || (a.p == b.p && a.j < b.j));
}

struct val_t val[N];
struct val_t f[N][N];

int main()
{
    int T;
    scanf("%d", &T);
    for (int ca = 1; ca <= T; ca++) {
        int n;
        scanf("%d", &n);
        char person[11];
        scanf("%s", person);

        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &val[i].p, &val[i].j);
        }

        sort(val+1, val+1+n, pcmp);

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                f[i][j].p = f[i][j].j = 0;
            }
        }

        int np = n / 2;//number of goodies Petra would take
        f[0][0].p = 0, f[0][0].j = 0;
        if (strcmp(person, "Petra") == 0) {
            f[0][0].p = val[1].p;
            for (int i = 1; i < n; i++) {
                val[i] = val[i+1];
            }
            n--;
            np = n/2;
        }  else if (n == 1) {
            printf("%d %d\n", 0, val[1].j);
            continue;
        }

        int sum[n+1];
        sum[0] = 0;
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i-1] + val[i].j;
        }

        struct val_t ans;
        ans = f[0][0];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= (i+1) / 2; j++) {
                if (i-j > np) continue;

                struct val_t o1, o2, o3;
                o1.p = o1.j = 0;
                o2.p = o2.j = 0;

                f[i][j] = f[i-1][j];
                o1.p = f[i-1][j].p + val[i].p, o1.j = f[i-1][j].j;
                if (j > 0) {
                    o2.p = f[i-1][j-1].p, o2.j = f[i-1][j-1].j + val[i].j;
                }
                if (o1 < o2) f[i][j] = o2;
                else f[i][j] = o1;

                if (f[i][j] < f[i-1][j]) f[i][j] = f[i-1][j];

                if (i-j == np) {
                    struct val_t tmp;
                    tmp.p = f[i][j].p; tmp.j = f[i][j].j + (sum[n] - sum[i]);
                    if (ans < tmp) {
                        ans = tmp;
                    }
                }

            }
        }

        printf("%d %d\n", ans.p, ans.j);
    }
    return 0;
}

KMP失败函数性质的应用。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

//KMP: fail function
void get_next(char *sub, int *f, int slen) {
    int i, j;
    f[0] = -1;
    for (i = 1; i < slen; i++) {
        j = f[i-1];
        while (j >= 0 && sub[i] != sub[j+1]) j = f[j];
        if (sub[j+1] == sub[i]) f[i] = j+1;
        else f[i] = -1;
    }
}

int main()
{
    char str[1011];
    int next[1011], res[1011];
    bool flag[1011];
    int T;
    scanf("%d\n", &T);
    for (int ca = 1; ca <= T; ca++) {
        scanf("%s", str);
        memset(res, 0, sizeof(res));
        int n = strlen(str);
        res[1] = n;
        for (int st = 0; st < n; st++) {
            int len = n-st;
            get_next(str+st, next, len);
            for (int i = len-1; i > 0; i--) {
                int cur = i-next[i];
                if (cur > 0 && (i+1) % cur == 0) {
                    int t = (i+1) / cur;
                    for (int w = t; w > 1; w--) {
                        res[w] = max(res[w], (i+1)-cur*(t%w));
                    }
                }
            }
        }
        printf("Case #%d:", ca);
        for (int i = 1; i <= n; i++) {
            printf(" %d", res[i]);
        }
        printf("\n");
    }
    return 0;
}

现在你知道总共有n个水果，每个水果在某段时间[st,ed]会出现在屏幕上，问你最后能获得的最大得分为多少？

解答是dp:

1、水果进入屏幕时间点为切水果的关键时间点，所以按进入时间排序（离散化），状态为到某一时间点切一刀能获得的最大分数；

2、维护一个优先队列，按水果进入屏幕时间先后顺序入队，按水果消失时间出队。

3、当前时间点能切的水果为当前在屏幕上的水果。向前面时间点dp，当前能切的水果cut(i,j)为：出现在屏幕区间包含当前时间点的所有水果 – 同时出现在前一时间点的水果（已经被切了，即当前已经从屏幕上消失）。设当前为i，前一时间点为j，则dp[i] = max{ dp[j]+cut(j,i), j=0,…,i}

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

typedef struct intv_t {
    int st, ed;
    bool operator<(const intv_t &a) const {
        return (ed > a.ed);
    }
};

typedef struct que_t {
    int t;
    bool operator<(const que_t &a) const {
        return (t < a.t);
    }
};

bool ed_cmp(const struct intv_t &a, const struct intv_t &b) {
    return (a.ed < b.ed || (a.ed == b.ed && a.st > b.st));
}

bool st_cmp(const struct intv_t &a, const struct intv_t &b) {
    return (a.st < b.st || (a.st == b.st && a.ed > b.ed));
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int ca = 1; ca <= T; ca++) {
        int n;
        scanf("%d", &n);
        struct intv_t fruit[n];
        int xs[n*2];
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &fruit[i].st, &fruit[i].ed);
            fruit[i].ed += 1;
            xs[i] = fruit[i].st;
        }

        sort(xs, xs+n);
        int nx = 0;
        for (int i = 1; i < n; i++) {
            if (xs[nx] != xs[i]) {
                xs[++nx] = xs[i];
            }
        }

        int num[nx+2], in[nx+2];
        priority_queue<intv_t> q, qt;
        sort(fruit, fruit+n, st_cmp);
        int ix = 0, ans = 0, f[nx+3];
        for (int i = 0; i <= nx; i++) {
            while (ix < n && fruit[ix].st <= xs[i]) {
                q.push(fruit[ix]);
                ++ix;
            }
            while (!q.empty()) {
                struct intv_t now = q.top();
                if (now.ed <= xs[i]) {
                    q.pop();
                } else {
                    break;
                }
            }

            num[i] = q.size();
            f[i] = num[i] > 2 ? num[i] : 0;

            priority_queue<que_t> p;
            while (!q.empty()) {
                struct intv_t now = q.top(); q.pop();
                qt.push(now);
                struct que_t cur;
                cur.t = now.st;
                p.push(cur);
            }
            while (!qt.empty()) {
                struct intv_t now = qt.top(); qt.pop();
                q.push(now);
            }

            for (int j = i-1; j >= 0; j--) {
                if (p.empty()) break;
                while (!p.empty()) {
                    struct que_t cur = p.top();
                    if (cur.t > xs[j]) {
                        p.pop();
                    } else {
                        break;
                    }
                }
                int tmp = num[i] - p.size();
                if (tmp <= 2) tmp = 0;
                tmp += f[j];
                if (tmp > f[i]) f[i] = tmp;
            }
            //cout << i << " " << f[i] << endl;//

            if (f[i] > ans) ans = f[i];
        }

        printf("Case #%d: %d\n", ca, ans);
    }

    return 0;
}