poj1330题目链接 题意：给出一棵树，求两点的lca. 思路：将lca转化成rmq在线求解。 代码部分参考了：参考代码 感觉实现得很巧妙。。。 把树存成了有向图，dfs遇到的时候一定是第一次遇到，此时更新R. 然后第二次遇到某个点就是在回溯的时候了。 算法学习链接 /* *********************************************** Author :111qqz Created Time :2016年05月19日 星期四 15时05分31秒 File Name :code/poj/1330.cpp ************************************************ …

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 …

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)只奶牛要出发去探索牧场四周的土地．她们将沿着一条路走，一直走到三岔路口（可以认为所有的路口都是这样的）．这时候，这一群奶牛可能会分成两群，分别沿着接下来的两条路继续走．如果她们再次走到三岔路口，那么仍有可能继续分裂成两群继续走． 奶牛的分裂方式十分古怪：如果这一群奶牛可以精确地分成两部分，这两部分 …

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 …

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... /* *********************************************** Author :111qqz Created Time :2015年12月30日 星期三 19时55分15秒 File Name …

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)，每一个 …

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

http://codeforces.com/problemset/status 题意：n行m列的道路网络。共n*m条道路。每条道路都是单向的.问从任何一个路口出发能否到达其他的任何一个路口。 思路：需要注意的是。我从A点能到达B点，不代表B也能到达A.也就是说，某些点满足可以遍历所有点是不够的，只有当所有点都满足才可以。 /* *********************************************** Author :111qqz Created Time :2015年12月07日 星期一 08时55分48秒 File Name :code/cf/problem/475B.cpp …