题意：给出一张许多人的年龄和生日表。你需要从年轻到年老输出人们的名字。（没有人年龄相同） 排序 //author: CHC//First Edit Time: 2015-09-05 19:00#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1e+4;const int MAXM=1e+5;const int INF = numeric_limits<int>::max();const LL LL_INF= numer ...

题意：我们有一个数列A1,A2…An，你现在要求修改数量最少的元素，使得这个数列严格递增。其中无论是修改前还是修改后，每个元素都必须是整数。 请输出最少需要修改多少个元素。 对于任意两个数A[i]A[i]A[i],A[j]A[j]A[j](i>ji>ji>j) 如果满足A[i]−A[j]≥i−jA[i]-A[j] \geq i-jA[i]−A[j]≥i−j可以使得[i,j][i,j][i,j]区间内的数都是可修改为递增的，可以将上面那个式子转换为A[i]−i≥A[j]−jA[i]-i \geq A[j]-jA[i]−i≥A[j]−j，这样子，我们可以先求出新的数字A[i]−iA[i]-iA[i]−i的最长的不需要改变的长度，也就是最长不下降子序列，这个序列中的数不需要改变，答案为n-最长不下降子序列长度 //author: CHC//First Edit Time: 2015-09-05 12:55#include <iostream>#include <cstdio>#include <cstring>#include < ...

恩。。CDQ分治是个神奇的东西。。其思想基于分治。。可以实现大部分离线的带修改的询问 资料：http://www.cnblogs.com/zig-zag/archive/2013/04/18/3027707.html //author: CHC//First Edit Time: 2015-09-04 13:18#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1e+5 + 1000;const int INF = numeric_ ...

题意：给定n个关于X的不等式，问最多有多少个成立。 每个不等式为如下的形式之一： X < C X <= C X = C X > C X >= C 输入 第一行一个整数n。 以下n行，每行一个不等式。 数据范围: 1<=N<=50,0<=C<=1000 输出 一行一个整数，表示最多可以同时成立的不等式个数。 样例输入 4 X = 1 X = 2 X = 3 X > 0 样例输出 2 这道题有毒。有好多人都是枚举过的。但是奇怪的是，枚举+0.5和枚举+0.1的结果是错误的。。= =！！！ 恩。。如果考虑N非常大 达到10w的话应该怎么做？先mark下，以后来补。

题意：幻想乡有一个赛车场。赛车场里有N个地点。同时地点之间还有单向的道路存在。 这些道路使得赛车场形成了一个外向树的结构。也就是说，道路将这N个地点连成了一个有根树。并且所有的边都是从父亲指向孩子的。 由于幽香喜欢刺激，每次她去赛车场都会从根节点出发，选择最长的一条路径来玩。 但是现在幽香感觉最长的路径还是太短了，她打算在赛车场里新建一条道路使得新的最长路径最长。 同时，如果道路形成了一个环，那么可能会出现交通事故，所以幽香新建的道路不能导致环的出现。 你能帮幽香算出新建一条道路后的最长路径吗？幽香知道根节点一定是1号点。 先求出最远的那个点，当然那个点肯定是叶子节点，然后再枚举其他叶子节点，计算从那个点到这个叶子节点能走的距离，要计算那个叶子节点和当前叶子节点的LCA，然后计算下距离加起来就行了。。 //author: CHC//First Edit Time: 2015-08-30 20:10#include <iostream>#include <cstdio>#include <cstring>#include <cmath> ...

题意：众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的： 勇太有一张nn个点mm条边的无向图，每一条边的长度都是1。现在他想再在这张图上连上一条连接两个不同顶点边，使得1号点到nn号点的最短路尽可能的短。现在他想要知道最短路最短是多少，以及再保证最短路最短的情况下，他有多少种连边的方案。 当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？ 简单题。。 //author: CHC//First Edit Time: 2015-08-29 22:38#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits&g ...

题意：众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的： 对于一棵树TT,令F(T,i)F(T,i)为点1到点ii的最短距离（边长是1）. 两棵树AA和BB是相似的当且仅当他们顶点数相同且对于任意的ii都有F(A,i)=F(B,i)F(A,i)=F(B,i). 两棵树AA和BB是不同的当且仅当他们定点数不同或者存在一个ii使得以1号点为根的时候ii在两棵树中的父亲不同。 一棵树AA是特殊的当且仅当不存在一棵和它不同的树和它相似。 现在勇太想知道一棵树到底是不是特殊的。 当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？ 画画图找下规律就行了。。 //author: CHC//First Edit Time: 2015-08-29 19:06#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include < ...

题意：给n个点n条边，判断图是否为哈密顿通路。 直接暴力搜 //author: CHC//First Edit Time: 2015-08-30 16:12#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1010;const int INF = numeric_limits<int>::max();const LL LL_INF= numeric_limits<LL>::max();struct Edge &# ...

题意很简单。就不说了。。 可以用费用流来做。。 建图:对于每个点uuu，都拆开为两个点uuu和u′u'u′，uuu表示入u′u'u′表示出 1.uuu->u′u'u′ 两条边，一条边的流量为1，费用为-1，一条边的流量为1，费用为0，代表这个点能走两次，但只计算一次的量。 2.u′u'u′->vvv 若是从u可以走到v，则连边，流量为2，费用为0,这里可以优化掉大量的边，如果u->v v->x 那么u->x就没有必要了。 3.ststst->uuu 流量为1，费用为0 4.u′u'u′->etetet 流量为1，费用为0 5.sstsstsst->ststst 流量为2，费用为0 这题。。如果直接暴力建边，用queue会被卡T。因为会成负环。这个时候用stack才可以过。 优化过的建图方式。。用queue要3000+MS 而用stack的话只需要300+MS。。 //author: CHC//First Edit Time: 2015-08-27 17:33#include <i ...

题意：给一个n*m的格子，每个格子有一个字母，只有向下和向左两种走法，现在要求，从左上角走到右下角，走过的格子的字母是回文的有多少种走法？ DP，枚举步数，因为是回文串，所以应该是对称的，步数应该为(n+m)2\frac{(n+m)}{2}2(n+m)​向下取整，可以知道，以左上角为起点走，走step步，走到的点是固定的，假设从左上角走到(r1,c1)(r_1,c_1)(r1​,c1​)这个点，并且走了step步，那么明显有r1+c1=step+1r_1+c_1=step+1r1​+c1​=step+1(由(1,1)(1,1)(1,1)走到(r1,c1)(r_1,c_1)(r1​,c1​))，从右下角走到(r2,c2)(r_2,c_2)(r2​,c2​)这个点，并且走了step步，那么明显有r2+c2=n+m+1−stepr_2+c_2=n+m+1-stepr2​+c2​=n+m+1−step(由(n,m)(n,m)(n,m)走到(r2,c2)(r_2,c_2)(r2​,c2​))，那么对于每一个c1c_1c1​和c2c_2c2​都直接用公式算出对应的r1r_1r1​和r2r_2r2​ ...