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

这题就是一道简单的两重三分

首先设e点为从ab上离开的点，f为从cd上进入的点

显然对固定点e,f从距c的距离的长度是一个单调函数或者先减后增的函数，这里可以三分算出最优解。这里是第一个三分

又是我们的OJ

题目链接：

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

Description

tancu likes space travels but he is a poor software developer and will never be able to buy his own spacecraft. That is why he is preparing to steal the spacecraft of Petru. There is only one problem - Petru has locked the spacecraft with a sophisticated cryptosystem based on the ID numbers of the stars from the Milky Way Galaxy. For breaking the system Stancu has to check each subset of four stars such that the only common divisor of their numbers is 1. Nasty, isn't it? Fortunately, Stancu has succeeded to limit the number of the interesting stars to N but, any way, the possible subsets of four stars can be too many. Help him to find their number and to decide if there is a chance to break the system.

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

我们的OJ

Description

We say that a set $$S = {x1, x2, …, xn}$$ 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:

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

题目大意

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

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

0-1分数规划

最优比例生成树

迭代法

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

对于集合s，令l* = max{ a(x) / b(x) } = a(x*) / b(x*).l为所求的最优解，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] )}

链接: 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];
}