1.RangeMinimum、Maximum Query问题（计算单调区间内出现最多（少）的次数）

对元素的起点做离散化，再把离散化后的位置作为线段树的[l, r),记录次数为t.

对输入区间a, b:

如果（a = b）{很好处理}，

如果（a = b – 1）{分别计算a、b的次数，取大（小）的一项}，

题目链接：http://poj.org/problem?id=1474

写这题的目的是看完了zzy的论文，写了半平面交，验证一下正确性，结果发现我写的问题还是很多的。

题目大意是问能不能放一个摄像机，使得摄像机能看到整个多边形内部。

这题和1279和3130差不多，过了这题再去对付那两题就简单多了。

题目链接： http://acm.pku.edu.cn/JudgeOnline/problem?id=2826

大致意思是给你两条线段，问组成的开口向上的V形区域能盛多少雨水。雨水是垂直落下的。

显然线段不相交，或者平行，重合，或者有一条斜率为0时结果为0.00

然后还有一种情况结果为0的，就是高的那条线段被低的挡住了。

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1986

这是一道并查集+树的题，采用Tarjan离线算法

首先BS一下出题的人，也太懒了吧，还要我们看1984题才知道输入

题目的意思是告诉一个节点数为40000的树，问我们两个节点间的距离。实际上就是找出公共父节点，Tarjan算法写挫了很容易TLE，我开始用Vector就写搓了，结果TLE，后来重写，自己写邻接表然后AC了。

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2446

这是一道匹配题，把行数（r）和列数（c）按（r+c）%2分成两组，然后连边，做一次二分图匹配，可以直接用匈牙利算法

匹配数等于两组的元素个数则为YES，否则NO

代码如下：

#include 
#include 
#include 
#include 
#include 
using namespace std;

int py[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
/**
 * 最大二分图匹配
 * 最大二分图匹配 = 最小点覆盖
 * Base 1
 */
#define MAXM 1024 //行
#define MAXN 1024 //列
bool mat[MAXM][MAXN] = {false};
bool isMatchedR[MAXN] = {false};
int matchedR[MAXN];//调用前初始化: memset(matchedR, 0, sizeof(matchedR));

bool getLeftPath(bool matin[MAXM][MAXN], int pos, const int &n)
{
    int i;
    for(i = 1 ; i <= n ; i ++)
    {
        if(matin[pos][i] && !isMatchedR[i])
        {
            isMatchedR[i] = true;
            if(!matchedR[i] || getLeftPath(matin, matchedR[i], n))
            {
                matchedR[i] = pos;
                return true;
            }
        }
    }

    return false;
}
long GetMaxMacthNumber(bool matin[MAXM][MAXN], const int &m, const int &n)
{
    int i,ans = 0;
    for(i = 1 ; i <= m ; i ++)
    {
        memset(isMatchedR, false, sizeof(isMatchedR));
        if(getLeftPath(matin, i, n))
            ans++;
    }
    return ans;
}

bool mapbs[35][35];
int index[35][35];
int main()
{
    int m, n, k, i, j, r, c, tx, ty;
    scanf("%d %d %d", &n, &m, &k);
    memset(matchedR, 0, sizeof(matchedR));
    memset(mapbs, true, sizeof(mapbs));
    for(i = 0; i < k; i ++)
    {
        scanf("%d %d", &c, &r);
        mapbs[r][c] = false;
    }
    for(i = 0; i < 35; i ++)
        mapbs[0][i] = mapbs[i][0] = mapbs[n + 1][i] = mapbs[i][m + 1] = false;

    r = c = 0;
    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= m; j ++)
        {
            if(mapbs[i][j])
            {
                if((i + j) % 2 == 0)
                    index[i][j] = ++ r;
                else
                    index[i][j] = ++ c;
            }
        }
    }
    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= m; j ++)
        {
            if(mapbs[i][j] && (i + j) % 2 == 0)
            {
                for(k = 0; k < 4; k ++)
                {
                    tx = i + py[k][0];
                    ty = j + py[k][1];
                    if(mapbs[tx][ty])
                    {
                        mat[index[i][j]][index[tx][ty]] = true;
                    }
                }
            }
        }
    }

    if(r != c || GetMaxMacthNumber(mat, r, c) != r)
        printf("NO\n");
    else
        printf("YES\n");
    return 0;
}

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3659

这题不算难题了，基本算是中等题

题目大意是给出一颗树，在一些点建一个信号塔，信号塔覆盖范围是其所在点和邻近点，问最少几个信号塔可以覆盖全区域

思路是树状DP（后序遍历），有三个状态，分别记录父节点建塔，本节点建塔和子节点建塔的最少建塔数量

http://www.cn210.com/onlinejudge/problemshow.php?pro_id=98

我们的OJ

Description

We say that a set 

is factor closed if for any xi ∈ S and any divisor d of xi we have d ∈ S. Let’s build a GCD matrix (S) = (sij), wheresij = GCD(xi, xj) - the greatest common divisor of xi and xj. Given the factor closed set S, find the value of the determinant:

Input

The input contains several test cases. Each test case starts with an integer n (0 < n < 1000), that stands for the cardinality of S.  The next line contains the numbers of S: x1, x2, …, xn.  It is known that each xi is an integer, 0 ≤ xi ≤ 2*109.  The input data set is correct and ends with an end of file.

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3757

题目大意

第一行输入n，k，f表示从n个服务器里选k个，传输大小为f（以Mb为单位）的文件

接下来输入每个服务器的吞吐量，带宽和资源消耗（pi，bi，ci）

题目链接： http://acm.pku.edu.cn/JudgeOnline/problem?id=2976

0-1分数规划

最优比例生成树

迭代法

证明：（前几次都是看别人的，这次自己证明）

对于集合s，令l* = max{ a(x) / b(x) } = a(x*) / b(x*).l为所求的最优解，x为对应的集合

注：b(x)必须恒大于0

然后令z(l) = min{ l × b(x) - a(x) }

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2728

和3757一样都是01分数规划的题，不同的是3757是用的二分，这里用的是Prim

0-1背包部分和3757一样

令m(l) = min{∑(1.0 * h[i][j] - l * dis[i][j] )}

h[i][j]是i到j的高度差，dis是距离，把m(l)作为边的权值（黑书上有）

链接: http://acm.pku.edu.cn/JudgeOnline/problem?id=1141 题目意思是输入一些括号，补充括号使之成为没有错误的括号就是只能有括号组在括号组里面，不能出现([)]或者([)]一类的情况 方法是DP，有点绕的DP DP方程是 bc[i][j] = min(bc[i][k] + bc[k][j]) 注：bc[i][j]表示字符i和字符j之间需要插入几个括弧 然后尽量多地分割字符串 不解释，贴代码：

这道题是我专门为了了解和学习树状数组而写的

这题用树状数组记录翻转次数,然后mod一个2,也可以不断地取反

还要用到二维的树状数组.于是我专门写了个模板用

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2155

题意大致是输入语句,Q表示要求输出A(x,y)是1还是0.C表示把(x1,y1)->(x2,y2)间的矩形中所有元素的1变成0,0变成1

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1720

这题纯计算几何就搞定了，开始我写了个很长很长的代码，但是Wa掉，也不知道是代码那里有疏漏还是精度问题

看来我的搜索真的很烂，简单的搜索都搞定的这么痛苦

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1724

题目大意是输入 拥有钱数，城市数，路的数量

然后输入格式是 起点，终点，路长，路费

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3513

题目大意是输入树状的家庭关系，问怎么买票（买家庭票还是个人票）最省钱并且票的数量最少

这道题是一道Hash+树状DP问题。编码长度相当可观，需要较好的编码能力

我这题编码就犯了几个低级错误，然后算法错误一次，导致了无数的WA

3636 Nested Dolls

题目链接：[http://acm.pku.edu.cn/JudgeOnline/problem?id=3636

](http://acm.pku.edu.cn/JudgeOnline/problem?id=3636)好吧，这题我看了解题报告。而且解题报告有错误的。只考虑w递增，没考虑w值相等的情况。

我自己这里加进去了判断。主要是看解题报告后才知道数据这么弱，就按他的写了

大意是给出N个玩具，要求放k组，其中每组都是大玩偶套小玩偶。在w（宽）和h（高）都大于

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3631

我讨厌这么长的题目

这题是模拟那个Hash算法，有点像我之前转载的那篇文章里提到的Hash

打造最快的Hash表(转) [以暴雪的游戏的Hash为例] 这里是用两个Hash函数算出两个Hash值h1和h2，如果h1位置已经被占用就检查h2位置，如果都被占用就把原来的替换掉再给原来的字符串重新计算映射。这样下去可能出现死循环。会出现死循环就输出

状态压缩+DP

1972的增强版

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2596

题意是给出小于10个的骰子，要求竖着叠成一条，而且每两个相接的骰子相接的面的数字相同

求侧面数字的最大和。如果叠不出来输出0

要注意的是1972题里必须按输入的骰子的顺序叠，而这里可以任意顺序，这样难度就大很多了

为什么我用线段数这么不灵活呢？

大概思路是线段数记录某牛之前的坐标小于这个牛的牛的坐标和和牛的个数

然后其他部分线性数组记录

OK，贴代码

#include 
#include 
#include 
#include 
using namespace std;

#define MAXN 20005
class cow
{
public:
    int v;
    int pos;
    cow(){};
    ~cow(){};
};

bool cmp(cow a,cow b)
{
    return a.v < b.v;
}
cow cw[MAXN];
long long belowXNT[MAXN];//树状数组，保存小于等于某坐标的牛的个数,计算时使用
long long belowXN[MAXN];//一般数组，保存小于等于某坐标和索引的牛的个数
long long velowXRT[MAXN];//树状数组，保存索引小于等于某的牛且坐标也小于它的牛的坐标之和,计算时使用
long long velowXR[MAXN];//一般数组，保存索引小于等于某的牛且坐标也小于它的牛的坐标之和
long long velowXRA[MAXN];//一般数组，保存小于等于某牛的坐标之和

int lowbit(int t)
{
    return t&(t^(t-1));
}
void setVal(int pos, int num, long long treeG[], int maxn)
{
    while (pos <= maxn)
    {
        treeG[pos] += num;
        pos += lowbit(pos);
    }
}
long long getSum(int pos, long long treeG[])
{
    long long sum = 0;
    while (pos > 0)
    {
        sum += treeG[pos];
        pos -= lowbit(pos);
    }
    return sum;
}



int main()
{
    int i,n;
    long long output = 0;
    memset(belowXN, 0, sizeof(belowXN));
    memset(belowXNT, 0, sizeof(belowXN));
    memset(velowXR, 0, sizeof(velowXR));
    memset(velowXRA, 0, sizeof(velowXRA));
    memset(velowXRT, 0, sizeof(velowXRT));
    scanf("%d",&n);
    for(i = 0 ; i < n ; i ++)
        scanf("%d %d", &cw[i].v, &cw[i].pos);

    sort(cw, cw + n, cmp);
    for(i = 0 ; i < n ; i ++)
    {
        velowXRA[i] = velowXRA[i - 1] + cw[i].pos;
        setVal(cw[i].pos, 1, belowXNT, MAXN);
        setVal(cw[i].pos, cw[i].pos, velowXRT, MAXN);
        velowXR[i] = getSum(cw[i].pos, velowXRT);
        belowXN[i] = getSum(cw[i].pos, belowXNT);
    }

    for(i = 1 ; i < n ; i ++)
        //output += cw[i].v * ((belowXN[i] - 1) * cw[i].pos - velowXR[i] + cw[i].pos + velowXRA[i] - velowXR[i] - (i - belowXN[i] + 1) * cw[i].pos);
        output += cw[i].v * ((belowXN[i] - i + belowXN[i] - 1 ) * cw[i].pos - 2 * velowXR[i] + velowXRA[i]);//这里是上面式子的简化版

    printf("%lld\n",output);
    return 0;
}

又来发解题报告了

这回是树状DP

/*
 * 树状DP
 * 首先把数据想象成树状的
 * 由于输入数据为树状，不需要构建树
 * 可令degree[i]为包括i且以i为根节点的所有子节点数量
 * dp[i]为删除i后的最大子节点数量或父亲节点数量 （这里我理解了很久）
 */
#include
#include
#include
using namespace std;
vectorchirld[10002];
int dp[10002] = {0}
    ,degree[10002] = {0}
    ,isJudged[10002] = {0};

int search(int pos,int &n);
int main()
{
    int n,i,a,b;
    bool isnone = true;
    scanf("%d",&n);
    for(i = 1 ; i < n ; i ++)
    {
        scanf("%d %d",&a,&b);
        chirld[a].push_back(b);
        chirld[b].push_back(a);
    }

    search(1 , n);

    for(i = 1 ; i <= n ; i ++)
        if(dp[i] * 2 <= n)
            printf("%d\n",i) , isnone = false;

    if(isnone)
        printf("NONE\n");
    return 0;
}

int search(int pos,int &n)
{
    int i,j;
    degree[pos] = 1;
    isJudged[pos] = 1;
    dp[pos] = 0;

    for(i = 0 ; i < chirld[pos].size() ; i ++)
    {
        if(!isJudged[chirld[pos].at(i)])//如果已经判断过就是父亲节点了
        {
            degree[pos] += search(chirld[pos].at(i) , n);
            if(dp[pos] < degree[chirld[pos].at(i)])
                dp[pos] = degree[chirld[pos].at(i)];
        }
    }

    if(dp[pos] < n - degree[pos])//判断父亲节点数量
        dp[pos] = n - degree[pos];
    return degree[pos];
}