DFS

题目链接 题意： # 一棵树，给出点权，问一条树链上第k大的点权，点权可以动态修改。 思路： # 暴力即可orz(数据是真的水啊。

题目链接 题意： # 给出一棵树，以及三个点（可能重合），问两两组成的3条路径中，哪2条路径重合部分最长。 思路： # LCA还是一下就能想到的，rmq+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个数，求所有的组合，和为定值，每个数可以重复用)

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即可。记得要回溯一下… 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月07日 星期五 14时32分54秒 4File Name :79.cpp 5************************************************ */ 6class Solution { 7 8public: 9 10 int n,m; 11 const int dx4[4]={1,-1,0,0}; 12 const int dy4[4]={0,0,-1,1}; 13 bool vis[1005][1005]; 14 int len; 15 16 bool yes( int x,int y) 17 { 18 if (x>=0&&x<=n-1&&y>=0&&y<=m-1) return true; 19 return false; 20 } 21 22 bool dfs( int x,int y,int cur,vector<vector<char> > & maze,string & st) 23 { 24// printf("x:%d y:%d cur : %d\n",x,y,cur); 25 if (cur>=len) return true; 26 for ( int i = 0 ; i < 4 ; i++) 27 { 28 int nx = x + dx4[i]; 29 int ny = y + dy4[i]; 30 if (!yes(nx,ny)) continue; 31 if (vis[nx][ny]) continue; 32 if (maze[nx][ny]!=st[cur]) continue; 33 vis[nx][ny] = true; 34 bool res = dfs(nx,ny,cur+1,maze,st); 35 if (res) return true; 36 vis[nx][ny] = false ;//好像还要回溯一下啊？ 37 } 38 return false; 39 } 40 41 bool exist(vector<vector<char>>& board, string word) { 42 n = board.size(); 43 if (n==0) return false; 44 m = board[0].size(); 45 if (m==0) return false; 46 len = word.length(); 47 cout<<"len:"<<len<<endl; 48 char beg = word[0]; 49 for ( int i = 0 ; i < n ; i++) 50 for ( int j = 0 ; j < m ; j++) 51 if (board[i][j]==beg) 52 { 53 memset(vis,false,sizeof(vis)); 54 //起点忘记打标记了。。。智力-2.。。 55 vis[i][j] = true; 56 bool ok = dfs(i,j,1,board,word); 57 cout<<"ok:"<<ok<<endl; 58 if (ok) return true; 59 } 60 return false; 61 62 63 } 64 65};

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

题目链接 题意：求约数个数恰好为n个的最小的x 思路：这道题是作为反素数的例题出现在acdreamer的博客里的。 但是实际上，这道题应该和反素数没有关系。 如果题目问的是最小的约数个数大于等于n的x，那么答案一定是反素数…打表就行了。。。

hdu 3336 题目链接 题意：给一个字符串，问这个字符串的所有前缀的出现次数的和。 思路：这道题需要完全理解 nxt 函数是干嘛的。nxt[i] 表示的是字符串的 0..i-1 位中，前缀和后缀相等的串的最长长度为 nxt[i]。

poj 3310 题目链接 题意：给出一个无向图，问是否满足：连通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。 思路：一个一个来。连通的话任意起点开始跑一遍 dfs？开一个 bool 数组标记走过的点，最后扫一遍，看是否有点没走过。

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

poj1470题目链接 题意：求两点的lca. 思路：dfs+rmq. 读入技巧。 读入比较坑爹。。。 学会了一种新的读入技巧。 scanf("%2s",st); 表示读一个长度为2的字符串。。。读的时候会忽略各种空白字符。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月19日 星期四 15时44分12秒 4File Name :code/poj/1470.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=905; 34int n; 35vector <int> edge[N]; 36int in[N]; 37int E[2*N],R[2*N]; 38int depth[2*N]; 39int p; 40int dp[2*N][12]; 41int cnt[N]; 42void dfs( int u,int dep) 43{ 44 p++; 45 E[p] = u ; 46 depth[p] = dep; 47 R[u] = p; 48 int siz = edge[u].size(); 49 for ( int i = 0 ; i < siz ; i ++) 50 { 51 int v = edge[u][i]; 52 53 dfs(v,dep+1); 54 p++; 55 E[p] = u; 56 depth[p] = dep; 57 } 58} 59 60int _min( int l,int r) 61{ 62 if (depth[l]<depth[r]) return l; 63 return r; 64} 65void rmq_init() 66{ 67 for ( int i = 1 ; i <=2*n+2 ; i++) dp[i][0] = i; 68 69 for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++) 70 for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++) 71 dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 72} 73 74int rmq_min( int l,int r) 75{ 76 if (l>r) swap(l,r); 77 int k = 0; 78 while (1<<(k+1) <= r-l+1) k++; 79 return _min(dp[l][k],dp[r-(1<<k)+1][k]); 80} 81int main() 82{ 83 #ifndef ONLINE_JUDGE 84 freopen("code/in.txt","r",stdin); 85 #endif 86 87 while (scanf("%d",&n)!=EOF) 88 { 89 ms(in,0); 90 for ( int i = 1 ; i <= n ; i++) edge[i].clear(); 91 for ( int i = 1 ; i <= n ; i++) 92 { 93 char ch[5]; 94 int x,num; 95 scanf("%d%2s%d%1s",&x,ch,&num,ch); 96// cout<<"x:"<<x<<" num:"<<num<<endl; 97 98 for ( int i = 1 ; i <= num ; i++) 99 { 100 int y; 101 scanf("%d",&y); 102 edge[x].push_back(y); 103 in[y]++; 104// cout<<"y:"<<y<<endl; 105 } 106 } 107 108 int root ; 109 for ( int i = 1 ; i <= n ; i++) if (in[i]==0) root = i ; 110// cout<<"root:"<<root<<endl; 111 p = 0; 112 dfs(root,0); 113 rmq_init(); 114 115 ms(cnt,0); 116 117 int q; 118 scanf("%d",&q); 119// cout<<"q:"<<q<<endl; 120 while (q--) 121 { 122 char ch[5]; 123 int x,y; 124 scanf("%1s%d%d%1s",ch,&x,&y,ch); 125 int LCA = E[rmq_min(R[x],R[y])]; 126// cout<<"x:"<<x<<" y:"<<y<<" LCA:"<<LCA<<endl; 127 cnt[LCA]++; 128 } 129// cout<<"n:"<<n<<endl; 130 for ( int i = 1 ; i <= n ; i++) 131 { 132// cout<<"cnt[i]:"<<cnt[i]<<endl; 133 if (cnt[i]==0) continue; 134 printf("%d:%d\n",i,cnt[i]); 135 } 136 } 137 138 #ifndef ONLINE_JUDGE 139 fclose(stdin); 140 #endif 141 return 0; 142}

poj1330题目链接 题意：给出一棵树，求两点的lca. 思路：将lca转化成rmq在线求解。 代码部分参考了：参考代码 感觉实现得很巧妙。。。 把树存成了有向图，dfs遇到的时候一定是第一次遇到，此时更新R. 然后第二次遇到某个点就是在回溯的时候了。

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.

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)，那么在三岔路口牛群就会分裂．否则，牛群不会分裂，她们都将在这里待下去，平静地吃草． 请计算，最终将会有多少群奶牛在平静地吃草．

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.

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(Tqn);

http://acm.hdu.edu.cn/showproblem.php?pid=5606 题意：一棵树，边权为0或者1，问对于每个点，距离它最近的点（包括自身）的个数是多少。输出将所有点的答案异或后的值。 思路：由于包括自身，自己与自己距离为0，那么最近的点一定也距离为0，所以就是找对于每个点与它相连的边权为0 的点的个数**。建图的时候可以不管边权为1的点。。因为这样的点不会对任何点的答案有贡献。**正解貌似是冰茶几。。我就是dfs搞了下。。找到每一个联通快的点数。。然后把某个联通快的所有点的答案都更新成点的个数。。。

http://codeforces.com/contest/29/problem/C 题意：给出n个边的关系，保证可以构成一条链。正向或者反向输出这个链。 思路：由于下标很大(1E9)，而关系个数只有1E5..需要离散化。。而且离散化的同时不能丢失边的关系。。。实际上。。直接用vector+map就好了。。。 map >e；即可。然后找到一个度为1的点。。做个dfs…

http://codeforces.com/contest/604/problem/D 题意：一个恒等式 f(kx%p)=kf(x)%p ,k,p为常数，且满足x对于定义域为0..p-1的p的整数，值域也在0..p-1范围（不一定一一对应）。问满足题意的f有多少个。 思路： f(0)=0，对于其他的值，当f（x）确定时，f（kx%p）也随之确定，那么把kx%p看做新的x,f（kkx%p）也随之确定…相当于【1，p-1】被分为r个小环，确定每个环可以任选一个数字，ans=p^r。环的个数可以用dfs跑一遍得到r. 注意当k=1的时候是特殊情况，f(x)恒等于f(x)那么答案应该有p的p次方种。因为对于p个f(0..p-1)，每一个都可以任意取p种值。

http://codeforces.com/contest/505/problem/B 题意；给一个图，边有颜色。给q个查询，每个查询一对点x,y。问只经过某种颜色的边使得x能到y颜色数目。 思路：存颜色的时候卡了下。。本来打算开一个二维的set用来存颜色。。。没想明白。。后来发现。。还是用vecotr就好啊。。。多开一维度vector。。或者。。vector 用 pair 都是可以的。。。因为颜色数不多。。可以暴力枚举每种颜色做一遍dfs 看只走有这条颜色的边x能否到y。。

http://codeforces.com/problemset/status 题意：n行m列的道路网络。共n*m条道路。每条道路都是单向的.问从任何一个路口出发能否到达其他的任何一个路口。 思路：需要注意的是。我从A点能到达B点，不代表B也能到达A.也就是说，某些点满足可以遍历所有点是不够的，只有当所有点都满足才可以。