hdu 3078 Network (LCA)

题目链接

题意:

一棵树,给出点权,问一条树链上第k大的点权,点权可以动态修改。

思路:

暴力即可orz(数据是真的水啊。

求路径上的点的时候需要用到LCA

 

 

codeforces #425 D. Misha, Grisha and Underground (dfs+rmq在线求LCA,讨论了一年)

题目链接

题意:

给出一棵树,以及三个点(可能重合),问两两组成的3条路径中,哪2条路径重合部分最长。

思路:

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

然后我开始分情况讨论,讨论了一年也没讨论完,哭哭

结论是:求出三个lca,并取深度最大的那个,就是我们要的三岔路口K,然后分别求出K到a,b,c三点的路径长度,取最大值+1就是答案。

所以我的问题在于,没有试图往一般性的方向考虑,以为讨论一下就可以了…

这大概就是所谓的猜结论?

感性的理解的话,LCA越深,意味着另一个点到LCA的距离越远,也就是相交的路径越长

但是我的话,估计还是很难在短短不到一个小时内得出这样一般性的结论orz…

这大概就是数学方面的天赋差距把…T T

 

 

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.

 

题意:给n个数,求所有的组合,和为定值,每个数可以重复用)

思路:。。。。一开始用顺着枚举子集的思路。。。发现。。并不好搞。。。?还不如直接dfs…

 

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.

思路:dfs即可。记得要回溯一下…

 

codeforces #375 D. Lakes in Berland (dfs)

题目链接

题意:n*m个格子,有*和.两种类型。定义一个湖为边相邻的只有.组成的最大点集合,且任何一个.不在边界上。现在给出一个n*m的图保证至少有k个湖。问填多少个.成*,才能使得恰好有k个湖。

思路:贪心,先处理出所有的湖的大小,然后从小往大填。

注意dfs的时候如果某个“可能”的湖遇到了边界,要把之前打的标记撤销掉。

 

 

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

题目链接

题意:求约数个数恰好为n个的最小的x

思路:这道题是作为反素数的例题出现在acdreamer的博客里的。

但是实际上,这道题应该和反素数没有关系。

如果题目问的是最小的约数个数大于等于n的x,那么答案一定是反素数…打表就行了。。。

但是问的是恰好,比如如果n为5,那么最小的x是16,但是x不是反素数。

所以其实就是个dfs啦。

理论依据是:

一个数 A 可以分解成 p1k1 * p2k2 * …… * pnkn 其中p为素数。这样分解之后,A的因子个数

S = (k1+1) *( k2+1) * …… *( kn+1)

 

以及要找的是一个最小的x,满足约数个数等于n。

那么关于反素数的两个性质依然是满足的:

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

(2)同样的道理,如果,那么必有

 

 

 

 

 

 

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

hdu 3336 题目链接

题意:给一个字符串,问这个字符串的所有前缀的出现次数的和。

思路:这道题需要完全理解nxt函数是干嘛的。。nxt[i]表示的是字符串的0..i-1位中,前缀和后缀相等的串的最长长度为nxt[i]

这东西对于这道题有什么用呢?

举个例子,对于字符串ababa:

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

 

首先,我们不是很关心nxt[i]具体的值,只关心nxt[i]是否大于0.如果大于0,比如对于nxt[3]==1,说明字符串0..2位置中,存在一个后缀和前缀相等,因此答案+1.

其次,其实我们仍然关心nxt[i]具体的值,对于nxt[5]==3,具体对应的含义是有后缀“aba”和前缀“aba”相等

但是这就完了吗?因为nxt[3]仍然大于0,对应“aba”中有一个前缀”a“和后者”a“相等。。。你可能要问。。这个不是刚刚算过了吗。。。然而这里其实算的是字符串2..4的”aba”。

看到有人说这是dp…不是很懂dp做法是什么鬼。。。

忘记取模wa了一发。。智力-2.

 

 

下面补一个dp做法好了。

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

转移方程为dp[nxt[i]] += dp[i];

这里还是涉及到nxt函数的含义

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

这就说明,对于长度为i的前缀,有一个长度为nxt[i]的前缀,出现在了该长度为i的前缀的后缀处。

后往前扫的原因是,对于长度为i的前缀,其长度为nxt[i]的前缀可能仍然有一个长度为nxt[nxt[i]]的前缀,

从后往前可以保证,当从len扫描到i时,已经将i+1~len的贡献累加到dp[i]

 

 

 

poj 3310 Caterpillar (树的直径+并查集判环+dfs判断连通性)

poj3310 题目链接

题意:给出一个无向图。。。问是否满足。。联通,并且无环,并且能找到一条路径,图中所有的顶点要么在这条路径上,要么与这条路径上的顶点相邻。

思路:一个一个来。。。联通的话任意起点开始跑一遍dfs? 开一个bool数组标记走过的点。。最后扫一遍。。看是否有点没走过

环的话并查集就好。。

关键是第三个条件。。。根据题中题中的例子。。感觉如果存在这样的路径。。。那么这样的路径应该尽可能长?

于是想到求直径。。。然后在bfs的时候顺便记录路径。。。这样我就知道直径是哪些点。。。然后对于所有点。。判断是否在这条直径上或者与之相邻就好。。。

具体做法是。。。开了一个bool数组ok标记直径上的点。。。在存边的时候用一个to[]数组表示相连。。。to[u]=v,to[v]=u…

然后只要ok[i]或者ok[to[i]]满足其一就好。。。

又是1A,蛤蛤蛤蛤蛤,我好神啊(误

 

 

 

 

hdu 3225 Flowers Placement (dfs+匈牙利算法剪枝,太神了)

hdu 3225题目链接

 

题意:给出一个n*m的矩阵。每个格子有一个数。每行1..n必须每个出现一次。每列1..n每个数最多出现一次。现在要添加一行,并且补违反上述规则。问添加的方案中字典序第k小的方案。如果一共不足k种方案,那么输出-1.

 

思路:有点像八皇后。。。就是纯搜。。。不过n好大。。。这么搜会TLE…

想了半天也没思路。。。看了题解。。发现是用二分图匹配来剪枝。。

比较重要的一点是。。。

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

我们可以根据这个来剪枝。

具体做法:

我们先求出一个完备匹配,然后搜索每个位置能够种的花,假设当前位k置种了花i,那么判断k+1–n位置能不能形成一个完备匹配(即能否种出满足条件的花),若能那么当前位置可以种该花,继续搜索,若不能这返回

 

然后把一个false写了true.调了一个小时。。。。。。。。。。。。。。无语凝噎。

 

poj 1470 Closest Common Ancestors (lca,rmq+dfs,读入技巧)

poj1470题目链接

题意:求两点的lca.
思路:dfs+rmq. 读入技巧。
读入比较坑爹。。。
学会了一种新的读入技巧。

scanf(“%2s”,st);

表示读一个长度为2的字符串。。。读的时候会忽略各种空白字符。

 

 

 

 

poj 1330 Nearest Common Ancestors (lca,用dfs+rmq在线求解)

poj1330题目链接

题意:给出一棵树,求两点的lca.
思路:将lca转化成rmq在线求解。

代码部分参考了:参考代码

感觉实现得很巧妙。。。
把树存成了有向图,dfs遇到的时候一定是第一次遇到,此时更新R.
然后第二次遇到某个点就是在回溯的时候了。

算法学习链接

BZOJ 1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐 (dfs)

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.

Sample Output

2

牧场3,4是这样的牧场.

思路:爆搜,从每个奶牛开始做dfs,统计每个点到达的次数,到达为k次的就是合法的牧场。 我一开始的思路有点麻烦,也是从每个奶牛做dfs,然后把所有路径上经过的奶牛所在地存到一个数组里,每次访问一个新的点,就把所有奶牛数组里存进这个点的set里。。。但是实际上并不需要知道有哪些奶牛。。所以一个计数数组足矣。

BZOJ1621: [Usaco2008 Open]Roads Around The Farm分岔路口 (DFS)

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

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

Description

约翰的N(1≤N≤1,000,000,000)只奶牛要出发去探索牧场四周的土地.她们将沿着一条路走,一直走到三岔路口(可以认为所有的路口都是这样的).这时候,这一群奶牛可能会分成两群,分别沿着接下来的两条路继续走.如果她们再次走到三岔路口,那么仍有可能继续分裂成两群继续走.    奶牛的分裂方式十分古怪:如果这一群奶牛可以精确地分成两部分,这两部分的牛数恰好相差K(1≤K≤1000),那么在三岔路口牛群就会分裂.否则,牛群不会分裂,她们都将在这里待下去,平静地吃草.    请计算,最终将会有多少群奶牛在平静地吃草.

Input

两个整数N和K.

Output

最后的牛群数.

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只.最后有三群奶牛.

 

思路;可分的条件是n>=k+2并且n和k的奇偶性相同。dfs即可。

 

BZOJ1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场 (BFS)

 

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.

 

农夫JOHN的农夫上有很多小山丘,他想要在那里布置一些保镖(……)去保卫他的那些相当值钱的奶牛们。 他想知道如果在一座小山丘上布置一名保镖的话,他总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有N行(1 < N < = 100)和M列( 1 < M < = 70) 。矩阵中的每个元素都有一个值H_ij(0 < = H_ij < =10,000)来表示该地区的海拔高度。请你帮助他统计出地图上到底有多少个小山丘。 小山丘的定义是:若地图中一个元素所邻接的所有元素都比这个元素高度要小(或它邻接的是地图的边界),则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是:若一个元素与另一个横坐标纵坐标和它的横纵坐标相差不超过1,则称这两个元素邻接。 问题名称:guard 输入格式: 第一行:两个由空格隔开的整数N和M 第二行到第N+1行:第I+1行描述了地图上的第I行,有M个由空格隔开的整数:H_ij.

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

Sample Input

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

Sample Output

3

HINT

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

Source

[Submit][Status][Discuss]

HOME Back\

 

 

题目的中文描述的数据范围有问题!

题目的中文描述的数据范围有问题!

题目的中文描述的数据范围有问题!

思路:BFS,我的做法是预处理所有“坏点”,也就是如果点(i,j)的相邻点中有比点(i,j)高的,那么点(i,j)就是坏点。

然后bfs的时候,对于存在一个坏点的联通块(只有数字相同的点能构成一个联通块)都标记成坏点。

然后用左上角开始做bfs…注意遇到坏点跳过但是不要直接标记访问,因为可能之后的点会用到之前的坏点标记自身。

然而因为数据范围有问题wa了好多次。。。

于是看了题解:

大概都是另一种做法(而且都加入了输入挂,不懂,怎么感觉这些人是互相抄的2333)

从最高的点开始做dfs,每次把不大于当前点高度的点都访问掉。。。算作一次访问。

访问次数就是答案。

想了下确实比较巧妙,比较好写,然而比我的写法要慢。

然而窝不懂为什么这种写法数组开小就是返回RE,而我的写法数组开销就是返回WA…

选区_049

 

我的做法(800ms,bfs):

 

 

网上题解的做法(940ms,dfs):

hdu 5416 CRB and Tree ( 2015 多校 #10 )

http://acm.hdu.edu.cn/showproblem.php?pid=5416
题意:给出一棵树(n<=1E5),定义二元函数函数f(u,v) (u可以等于v)表示节点u到节点v经过的路径的权值的异或和。给出q组查询(q<=10),每组一个s,问有多少对无序点对(u,v)满足f(u,v)=s.
思路:类似codeforces #340 div 2 E XOR and Favorite Number
先dfs,处理出从根节点都任意节点的异或前缀和。然后对于每个询问o(n)扫一遍,统计sum[i]^s出现多少次。 总的时间复杂度为O(T*q*n);