http://codeforces.com/contest/510/problem/B 题意:给定一个maze,用不同的字母代表不同的颜色。问能否找到一个颜色相同的环(失少四个点组成) 思路:dfs一遍,如果遇到之前已经访问过的点,说明成环。需要注意的是,要注意由一个点向某方向移动,然后由反方向移动到该点所造成的误判。所以dfs除了要知道当前的坐标x,y,还要记录之前的坐标px,py.
阅读更多http://codeforces.com/contest/277/problem/A
题意:有n个人,每个人会一定数目的语言(可能为0),一个人学一门语言的代价为1,人和人之间沟通可以通过任意个中间人翻译。问最少的代价使得这n个人可以相互沟通。
阅读更多http://codeforces.com/problemset/problem/217/A 题意:有n个雪漂(那是啥?,从某个雪漂出发走直线,只有到达另一个雪飘才能停下来。问最少需要添加多少个雪漂,才能使得可以到达任何一个雪漂。 思路:横坐标相同或者纵坐标相同的两个点之间是可以到达的。先O(N2)扫一遍建图。记录这个森林中数的个数为cnt,cnt-1即为答案。因为对于任意两个不能相互到达的点。我们只需要再来一个雪漂就可以使得这两个点相互到达。
阅读更多http://codeforces.com/contest/445/problem/B
题意:一共有n种化学药品。m对关系,每对关系表示为x,y表示x和y相互反应。初始容器的danger值为1,当向容器中加入一个化学药品A,如果容器中存在化学药品和A反应,那么容器的danger值翻倍。否则不变。问一个最优的放置药品的顺序。
阅读更多http://codeforces.com/problemset/problem/522/A 题意:给定某条消息的传播路径。问最远传播的距离。。 思路:其实就是问树的深度。。直接dfs就行了。。
存的时候用map<string,vector
> mp;的方式存即可。
阅读更多http://codeforces.com/contest/377/problem/A 题意:给定一个n*m的maze. ‘.’代表空,‘#’代表墙。要求构造一种方案,使得将k个空格填成墙壁后不影响当前的连通性(即没有被填充的空格之间可以相互到达) 思路:一开始想从上往下从左往右构造。错误的认为四个角一定是可以变成墙的。
阅读更多http://codeforces.com/contest/580/problem/C
题意:给出一棵树。每个叶子节点上有一个饭店。某些节点上有cat.现在问从根节点出发可以到达多少个饭店,保证在到达饭店的路径中补连续遇到m个以上的cat.
阅读更多http://codeforces.com/problemset/problem/115/A 题意:给出n个人之间的上级下级关系。问如何分得最少的组,使得没一组中的人不存在上下级关系。 思路:用树的观点来考虑会很容易。可以看成给了一棵森冷。对于不同的树的相同层的点,不存在上下级关系,可以放在一个group.对于同一棵树,每一层要单独放一个group.所以答案是所有树的深度的最大值。
阅读更多http://codeforces.com/contest/598/problem/D
题意:给第一个地图。 ‘.’是能走的,‘’是不能走的。**每个‘.’和''之间有一幅画,**给出k个起点,问对于每组起点,最多能观察到多少副画。
阅读更多