题目链接：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] )}

链接: 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=1720

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

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

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

注册表常用键值意义

[HKEY_CURRENT_USER\Software\Policies\Microsoft\Internet Explorer\Control Panel]

;〖Internet Explorer选项类〗

“HomePage”=dword:00000001 ;禁止更改主页设置〖0=可修改〗

“Cache”=dword:00000001 ;禁止更改Internet临时文件设置〖0=可修改〗

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

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

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

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3309

一道典型的Hash题

题目很好理解。这里不复述

由于输入语句最大数量200000，不用Hash铁定TLE。然后数据量不超过10000，所以必然有很多search和reply的操作。

/**
 * Hash模板
 * Based: 0
 * template<unsigned long _SZ,class _T, unsigned long *pFun(_T _Off)>
 * class _My_Hash_ToInt
 * 传入数据大小_SZ,传入类型_T,Hash函数
 * 传入类型_T必须重载 = 和 == 符号
 * 收录了ELFHash函数
 * 主要是为了判重的简化些的模板
 * Hash算法性能比较见 http://www.cnblogs.com/lonelycatcher/archive/2011/08/23/2150587.html
 */

const long hashsize = 51071; //Hash表大小(注意修改)
// 各种Hash算法
unsigned int SDBMHash(char *str)
{
    unsigned int hash = hashsize;

    while (*str)
    {
        // equivalent to: hash = 65599*hash + (*str++);
        hash = (*str++) + (hash << 6) + (hash << 16) - hash;
    }

    return (hash & 0x7FFFFFFF);
}

// RS Hash Function
unsigned int RSHash(char *str)
{
    unsigned int b = 378551;
    unsigned int a = 63689;
    unsigned int hash = hashsize;

    while (*str)
    {
        hash = hash * a + (*str++);
        a *= b;
    }

    return (hash & 0x7FFFFFFF);
}

// JS Hash Function
unsigned int JSHash(char *str)
{
    unsigned int hash = 1315423911;

    while (*str)
    {
        hash ^= ((hash << 5) + (*str++) + (hash >> 2));
    }

    return (hash & 0x7FFFFFFF);
}

// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
    unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
    unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);
    unsigned int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);
    unsigned int HighBits         = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
    unsigned int hash             = hashsize;
    unsigned int test             = 0;

    while (*str)
    {
        hash = (hash << OneEighth) + (*str++);
        if ((test = hash & HighBits) != 0)
        {
            hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
        }
    }

    return (hash & 0x7FFFFFFF);
}

// ELF Hash Function
unsigned int ELFHash(char *str)
{
    unsigned int hash = hashsize;
    unsigned int x    = 0;

    while (*str)
    {
        hash = (hash << 4) + (*str++);
        if ((x = hash & 0xF0000000L) != 0)
        {
            hash ^= (x >> 24);
            hash &= ~x;
        }
    }

    return (hash & 0x7FFFFFFF);
}

// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = hashsize;

    while (*str)
    {
        hash = hash * seed + (*str++);
    }

    return (hash & 0x7FFFFFFF);
}

// DJB Hash Function
unsigned int DJBHash(char *str)
{
    unsigned int hash = 5381;

    while (*str)
    {
        hash += (hash << 5) + (*str++);
    }

    return (hash & 0x7FFFFFFF);
}

// AP Hash Function
unsigned int APHash(char *str)
{
    unsigned int hash = hashsize;
    int i;

    for (i=0; *str; i++)
    {
        if ((i & 1) == 0)
        {
            hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
        }
        else
        {
            hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
        }
    }

    return (hash & 0x7FFFFFFF);
}

// 程序模板
template<typename _T>
class _My_Hash_ToInt_Data
{
public:
    _My_Hash_ToInt_Data()
    {
        times = 0;
        next = -1;
    }
    _T data;
    long times;
    long next;
};
template<long _SZ,class _T, unsigned long pFun(_T& _Off)>
class _My_Hash_ToInt
{
public:
    _My_Hash_ToInt()
    {
        memset(hash, -1, sizeof(hash));
        length = 0;
    };
    ~_My_Hash_ToInt(){};
    long find(_T _Off)
    {
        long pos = hash[pFun(_Off)];
        while(pos >= 0)
        {
            if(data[pos].data == _Off)
                return pos;
            else
                pos = data[pos].next;
        }
        return -1;
    }
    long insert(_T _Off)
    {
        long oldPos = pFun(_Off);
        long pos = hash[oldPos];
        while(pos >= 0)
        {
            if(data[pos].data == _Off)
            {
                data[pos].times ++;
                return pos;
            }
            else
                pos = data[pos].next;
        }
        data[length].data = _Off;
        data[length].times = 1;
        data[length].next = hash[oldPos];
        hash[oldPos] = length ;
        return length ++;
    }
    void clear()
    {
        length = 0;
        memset(hash, -1, sizeof(hash));
        memset(data, -1, sizeof(data));
    }
    //Member
    long length;
    _My_Hash_ToInt_Data<_T> data[_SZ];
    long hash[hashsize];
};

//节点类（注意修改）
class node
{
public:
    char str[60];
    bool operator == (node &strin)
    {
        return !strcmp(str, strin.str);
    }
    node& operator = (node &strin)
    {
        strcpy(str, strin.str);
        return (*this);
    }
};
//扩展Hash函数（注意修改）
unsigned long ELFHashEx(node &strIn)
{
    return ELFHash(strIn.str);
}
_My_Hash_ToInt<10005, node, ELFHashEx>hash;//Hash类例子

题目： http://acm.hdu.edu.cn/showproblem.php?pid=3336

水题一道，主要是测试数据很水

不解释，贴代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

char str[200005];
vector<long>glo_Pos;
int main()
{
    int t;
    long output,i,n,j;
    scanf("%d",&t);
    while(t --)
    {
        output = 0;
        glo_Pos.clear();
        scanf("%ld %s", &n, str);

        for(i = 0; i < n; i ++)
        {
            if(str[i] == str[0])
            {
                glo_Pos.push_back(i);
                output ++;
            }
        }
        output = output % 10007;
        for(i = 1; i < n; i ++)
        {
            for(j = 0; j < glo_Pos.size();j ++)
            {
                if(str[i] == str[glo_Pos[j] + i])
                    output = (output + 1) % 10007;
                else
                {
                    glo_Pos.erase(glo_Pos.begin() + j);
                    j --;
                }
            }
        }

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

3636 Nested Dolls

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

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

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

题目链接：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

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

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

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

OK，贴代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>chirld[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];
}

题目链接: http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=2528

这题又是线段树+离散化

慢慢的对离散化有点感觉了,但是这题我还是错了3次

题目大意是一层一层地叠板子,问最后能看到几块

输入是板子的开始和结束位置

在ACM的竞技场上走过了一年。这一年是充满艰难的一年，这一年是充满困惑的一年。这也是充满激情的一年。这之间有欢笑，有惊喜,也有黯然失色的悲伤.苦战一年，却没有拿到任何的成绩， regional的失败让我刻骨铭心也深深感受到了实力的差距。伤感之余也让我想起了我们ECUST的ACM之歌,我又看了一遍，每次看这篇文章都会有种说不出的感动与激情。让我有了继续走下去的力量。明年，再战ACM，等着我们，我们要成为明年名副其实的ACMer。

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

线段树+离散化

ACM预选赛过去了,可是我们队什么都没拿到,这给我们的打击是相当大的,这也很大程度上体现了我们的不足

一直没能静下心,来,今天决定不能再这么悲伤下去,我要奋斗,继续学习,就从之前的断点线段树开始

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

这道题伤了我很久脑筋

因为是a+b+c=d,数据量是1000,很自然地想到a+b=d-c

这样转化为n^2的算法.

但是我开始枚举d-c的集合二分查找a+b的几何不知道为什么WA掉了

//最长单调子序列 复杂度nlog(n)
//参数(原序列,序列长度,生成的序列),传入序列长度必须大于0
//返回值中lengthRecord中前k项表示长度为k的最小字序列
//LIScmp为关系函数,原函数表明lengthRecord为递增(不含等于)
typedef double LISTYPE;
#define LISMAXN 10000
int LIScmp(LISTYPE a,LISTYPE b)
{
    return a < b;
}
long LISLength(LISTYPE list[],long n,LISTYPE lengthRecord[])
{
    long length = 1,lth;
    LISTYPE lR[LISMAXN];
    lR[0] = list[0];

    for(int i = 1 ; i < n ; i ++)
    {
        //二分查找,复杂度 log(n)
        int b,e,m;
        b = 0;
        e = length - 1;
        while(b <= e && e >= 0)
        {
            m = (b + e) / 2;
            if(LIScmp(lR[m],list[i]))
                b = m + 1;
            else
                e = m - 1;
        }
        lR[b] = list[i];
        if(b >= length)
            length ++;
    }
    /*
    *计算序列部分
    *复杂度nlog(n)
    */
    lth = 1;
    for(int i = 1 ; i < n ; i ++)
    {
        //二分查找,复杂度 log(n)
        int b,e,m;
        b = 0;
        e = lth - 1;
        while(b <= e && e >= 0)
        {
            m = (b + e) / 2;
            if(LIScmp(lR[m],list[i]))
                b = m + 1;
            else
                e = m - 1;
        }
        lR[b] = list[i];
        if(b >= lth)
            lth ++;
        if(lth == length)
        {
            for(b = 0 ; b < length ; b ++)
                lengthRecord[b] = lR[b];
            break;
        }
    }
    //计算序列部分代码与之前的类似,可以直接Copy然后修改
    return length;
}