111qqz的小窝

老年咸鱼冲锋!

hdu 3078 Network (LCA)

题目链接 题意: 一棵树,给出点权,问一条树链上第k大的点权,点权可以动态修改。 思路: 暴力即可orz(数据是真的水啊。 求路径上的点的时候需要用到

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

题目链接 题意: 给出一棵树,以及三个点(可能重合),问两两组成的3条路径中,哪2条路径重合部分最长。 思路: LCA还是一下就能想到的,rmq+d

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个数,求所有

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)

题目链接 题意:nm个格子,有和.两种类型。定义一个湖为边相邻的只有.组成的最大点集合,且任何一个.不在边界上。现在给出一个nm的图保证至少有

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

题目链接 题意:求约数个数恰好为n个的最小的x 思路:这道题是作为反素数的例题出现在acdreamer的博客里的。 但是实际上,这道题应该和反素数

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

hdu 3336 题目链接 题意:给一个字符串,问这个字符串的所有前缀的出现次数的和。 思路:这道题需要完全理解nxt函数是干嘛的。。nxt[i]表示的是字符

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

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

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

hdu 3225题目链接 题意:给出一个n*m的矩阵。每个格子有一个数。每行1..n必须每个出现一次。每列1..n每个数最多出现一次。现在要添加一行

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在线求解。 代码部分参考了:参考代码 感觉实现得很巧妙。。。 把

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

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)只奶牛要出发去探索牧场四周的土地.她们将

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

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组查

hdoj 5606 ||bc #68 div 2 B tree

http://acm.hdu.edu.cn/showproblem.php?pid=5606 题意:一棵树,边权为0或者1,问对于每个点,距离它最近的点(包括自身)的个数是多少。输出将所有点的答案异或后的值。 思路:由于包括自身,自己

codeforces 29 C. Mail Stamps

http://codeforces.com/contest/29/problem/C 题意:给出n个边的关系,保证可以构成一条链。正向或者反向输出这个链。 思路:由于下标很大(1E9),而关系个数只有1E5..需要离散化。。而

codeforces #334 div 2 D.Moodular Arithmetic

http://codeforces.com/contest/604/problem/D 题意:一个恒等式 f(kx%p)=kf(x)%p ,k,p为常数,且满足x对于定义域为0..p-1的p的整数,值域也在0..p-1范围(不一定一一对应)。问满足题意的f有

codeforces 505 B. Mr. Kitayuta's Colorful Graph

http://codeforces.com/contest/505/problem/B 题意;给一个图,边有颜色。给q个查询,每个查询一对点x,y。问只经过某种颜色的边使得x能到y颜色数目。 思路:存颜色的时候卡了下。。本来打算

codeforces 475 B. Strongly Connected City

http://codeforces.com/problemset/status 题意:n行m列的道路网络。共n*m条道路。每条道路都是单向的.问从任何一个路口出发能否到达其他的任何一个路口。 思路:需要注意的是。我从A点