111qqz的小窝

思路：

LCA还是一下就能想到的，rmq+dfs在线求。

leetcode 39. Combination Sum (dfs，求所有的组合，和为定值，每个数可以重复用)

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

leetcode 79. Word Search (dfs)

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

codeforces 27 E. Number With The Given Amount Of Divisors (dfs，反素数（假）)

S = （k1+1） *（ k2+1） * …… *（ kn+1）

（1）一个反素数的所有质因子必然是从2开始的连续若干个质数，因为反素数是保证约数个数为的这个数尽量小

（2）同样的道理，如果，那么必有

hdu 3336 Count the string （nxt函数的运用kmp+（dfs|dp )）

hdu 3336 题目链接

s          a    b    a    b    a
i          0    1    2    3    4   5
next[i]     -1   0    0    1    2   3

ans初始为len(因为长度为len的字符串有len个前缀，每个前缀至少出现一次)
next[3] = 1，ans + 1 = 6，next[1] = 0
next[4] = 2，ans + 1 = 7，next[2] = 0
next[5] = 3，ans + 1 = 8，next[3] = 1，ans + 1 = 9

dp[i]表示长度为i的前缀出现的此处，显然每个前缀至少出现了一次，所以初始化dp[i]=1  (1=<i <= len)

nxt[i]表示的是字符串的0..i-1位中，前缀和后缀相等的串的最长长度为nxt[i]

poj3310 题目链接

hdu 3225 Flowers Placement （dfs+匈牙利算法剪枝，太神了）

hdu 3225题目链接

n个数的某种排列，可以看做是一个位置集合{1..n}和数字集合{1..n}的二分图最大匹配

poj1470题目链接

scanf(“%2s”,st);

poj1330题目链接

1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 562  Solved: 352
[Submit][Status][Discuss]

Description

The cows are having a picnic! Each of Farmer John’s K (1 <= K <= 100) cows is grazing in one of N (1 <= N <= 1,000) pastures, conveniently numbered 1…N. The pastures are connected by M (1 <= M <= 10,000) one-way paths (no path connects a pasture to itself). The cows want to gather in the same pasture for their picnic, but (because of the one-way paths) some cows may only be able to get to some pastures. Help the cows out by figuring out how many pastures are reachable by all cows, and hence are possible picnic locations.

K(1≤K≤100)只奶牛分散在N(1≤N≤1000)个牧场．现在她们要集中起来进餐．牧场之间有M(1≤M≤10000)条有向路连接，而且不存在起点和终点相同的有向路．她们进餐的地点必须是所有奶牛都可到达的地方．那么，有多少这样的牧场呢？

Input

* Line 1: Three space-separated integers, respectively: K, N, and M * Lines 2..K+1: Line i+1 contains a single integer (1..N) which is the number of the pasture in which cow i is grazing. * Lines K+2..M+K+1: Each line contains two space-separated integers, respectively A and B (both 1..N and A != B), representing a one-way path from pasture A to pasture B.

1行输入KNM.接下来K行，每行一个整数表示一只奶牛所在的牧场编号．接下来M行，每行两个整数，表示一条有向路的起点和终点

Output

* Line 1: The single integer that is the number of pastures that are reachable by all cows via the one-way paths.

所有奶牛都可到达的牧场个数

Sample Input

2 4 4
2
3
1 2
1 4
2 3
3 4

INPUT DETAILS:

4<–3
^ ^
| |
| |
1–>2

The pastures are laid out as shown above, with cows in pastures 2 and 3.

2

1621: [Usaco2008 Open]Roads Around The Farm分岔路口

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 698  Solved: 513
[Submit][Status][Discuss]

Sample Input

6 2

INPUT DETAILS:

There are 6 cows and the difference in group sizes is 2.

Sample Output

3

OUTPUT DETAILS:

There are 3 final groups (with 2, 1, and 3 cows in them).

6
/ \
2 4
/ \
1 3

HINT

6只奶牛先分成2只和4只．4只奶牛又分成1只和3只．最后有三群奶牛．

1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 661  Solved: 292
[Submit][Status][Discuss]

Description

The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows. He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns. Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000). Help him determine the number of hilltops on the map. A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.

Input

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 describes row i of the matrix with M space-separated integers: H_ij

Output

* Line 1: A single integer that specifies the number of hilltops

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

3

HINT

三个山丘分别是：左上角的高度为4的方格，右上角的高度为1的方格，还有最后一行中高度为2的方格．

Source

[Submit][Status][Discuss]

HOME Back\