Posts

http://codeforces.com/problemset/problem/596/B 题意：初始序列全为0，问经过多少次变换，能变成序列b。一次变换是指，选定一个i，从i一直到最后每个元素都增加1，或者每个元素都减少1. 思路：很容易发现。后面的变换补影响前面的变换。每一个数字可以唯一由之前的增加和减少次数决定。所以我们用两个变量，记录之前做的增加和减少变换的次数。然后扫一遍即可。

http://codeforces.com/problemset/problem/600/C 题意：给定一个字符串。要求用最少的变换得到一个回文串。且在变换次数相同时要字典序最小的。输出变换后的字符串。 思路：对不能构成会文串有影响的是出现奇数次的字母。所以我们先统计每个字母出现的次数。然后按照出现奇数次的字母的个数分奇偶分别搞。偶数的话直接把后面一半变成前面一半。奇数的话，也是这样。输出的时候按照字母从a扫到z，如果有就输出一半。然后再倒着扫一遍。 输出另一半。这样可以保证是字典序最小。需要注意的是奇数的时候的输出情况。不要忘记中间那个字母。

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条道路。每条道路都是单向的.问从任何一个路口出发能否到达其他的任何一个路口。

http://codeforces.com/problemset/problem/158/B 题意：n组人，每组有si个（1<=si<=4），每辆车能装4个人。问最少需要多少辆车装下所有人并且保证同一组的人在一辆车里。 思路：统计人数分别为1,2,3,4的人数。对于4的直接加到答案。贪心的思路是：优先用人数少的去填人数多的。

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就行了。。

http://codeforces.com/contest/500/problem/B 题意：给定一个1至n的数的一种排列。给定一个n*n的矩阵，a[i][j]==0代表pi,pj不可以交换，a[i][j]为1代表p[i],p[j]可以交换。 问字典序最小的排列。。

http://codeforces.com/contest/377/problem/A 题意：给定一个n*m的maze. ‘.’代表空，‘#’代表墙。要求构造一种方案，使得将k个空格填成墙壁后不影响当前的连通性（即没有被填充的空格之间可以相互到达） 思路：一开始想从上往下从左往右构造。错误的认为四个角一定是可以变成墙的。

http://codeforces.com/contest/129/problem/B 题意：n个点。m条边。每一次会将图中度为1的点加入到等待队列中。然后一起删掉，记为一次操作。当删掉一个点的时候，与它相连的边也全部删掉。问一共做进行多少次操作。使得图中不再有度为1的点。 思路：重点是用开一个数组deg[i]记录点i的度。这样比用.size()高明太多。。因为我们并不需要知道具体删了哪条边。我们只要知道与点i相连的点的边数因为点i被删除而减少了1.

http://codeforces.com/contest/580/problem/C 题意：给出一棵树。每个叶子节点上有一个饭店。某些节点上有cat.现在问从根节点出发可以到达多少个饭店，保证在到达饭店的路径中补连续遇到m个以上的cat.

http://codeforces.com/problemset/problem/115/A 题意：给出n个人之间的上级下级关系。问如何分得最少的组，使得没一组中的人不存在上下级关系。 思路：用树的观点来考虑会很容易。可以看成给了一棵森冷。对于不同的树的相同层的点，不存在上下级关系，可以放在一个group.对于同一棵树，每一层要单独放一个group.所以答案是所有树的深度的最大值。

http://codeforces.com/contest/591/problem/B 题意：给定一个字符串。给出m组替换。对于某一组替换，给出x,y。将字符串中所有的字符x换成y，所有的字符y换成x. 字符串仅包含英文小写字母。

题意：一个长度为l的走廊。两个人站在两端点。互相向对方发射某种魔法。A的魔法速度为p米/秒，B的魔法速度为q米/s,魔法相遇以后会反射。反射会发射人那里会再次发射。问两种魔法第二次相遇的时候距离A的距离。 思路：由于每种魔法的速度保持肯定不变。。所以不管第几次相遇。相遇点都是同一个。。。ans=p*(p+q)/l;

http://codeforces.com/contest/598/problem/D 题意：给第一个地图。 ‘.’是能走的，‘’是不能走的。**每个‘.’和’‘之间有一幅画，**给出k个起点，问对于每组起点，最多能观察到多少副画。

题意：给一个字符串（1E4），然后给m次操作（m<=300），每次操作是给定一个区间l,r，然后进行k次（k<=1E6）cyclic shift (rotation) 变换。

题意：求1+2+..+n的和。。但是对于是2的整数幂的项数。。符号是-。。