这次比赛成绩比预期差

开始Ultramanhu调整IDE

Q Boy从头开始看题

我的任务是倒数看题，最后看的题目是J，I，H，G

我看完J觉得J可做（哈密顿回路），但是需要很长时间。就首先放着继续看题

树状数组模块

ACM个人模板

POJ 2155 题目测试通过

/**
 * 树状数组模块
 * 下标从0开始
 */
typedef long DG_Ran;
typedef long DG_Num;
const DG_Num DG_MAXN = 1005;

//2^n
DG_Num LowBit(DG_Num n)
{
    return n & (-n);
}
//获取父节点索引
DG_Num DGFather(DG_Num n)
{
    return n + LowBit(n + 1);
}
//获取小的兄弟节点索引
DG_Num DGBrother(DG_Num n)
{
    return n - LowBit(n + 1);
}
//查找增加树状数组前pos项和
//参数(树状数组[in],索引[in],初始赋0即查找前n项和[out])
//复杂度:log(n)
void DGFind(DG_Ran *g,DG_Num pos,DG_Ran &sum)
{
    sum += *(g + pos);
    if(pos >= LowBit(pos + 1))
        DGFind(g, pos - LowBit(pos + 1), sum);
}
//查找对应线性数组元素
//参数(树状数组[in],索引[in]).
//返回值:对应线性数组元素log(n)
//复杂度:log(n)
DG_Ran DGFindEle(DG_Ran *g,DG_Num pos)
{
    DG_Ran a = 0 , b = 0;
    DGFind(g, pos, a);
    if(pos)
    {
        DGFind(g,pos - 1,b);
        return a - b;
    }
    else
        return a;
}
//树状数组,增加节点
//参数:树状数组[out],原数组大小[in],新增线性数组值[in]
//复杂度:log(n)
DG_Ran DGAdd(DG_Ran *g,DG_Num n,DG_Ran val)
{
    *(g + n) = val;
    DG_Num a = n;
    DG_Num b = 1;
    while((a & (~b)) != a)
    {
        *(g + n) += *(g + a - 1);
        a &= (~b);
        b <<= 1;
    }
    return n + 1;
}
//构建树状数组
//参数:线性数组[in],数组大小[in],树状数组[out]
//复杂度:nlog(n)
DG_Ran DGCreate(DG_Ran *g,DG_Num n,DG_Ran *tg)
{
    DG_Num i;
    *tg = *g;
    for(i = 1 ; i < n ; i ++)
        DGAdd(tg,i,*(g + i));
    return n;
}
//修改指定位置值
//参数:线性数组[in],数组位置[in],数组大小[in],新值[in]
//复杂度:log(n)
DG_Ran DGEdit(DG_Ran *g,DG_Num pos,DG_Num n,DG_Ran val)
{
    DG_Num f = DGFather(pos);
    DG_Ran o = *( g + pos );
    *( g + pos ) = val;
    if(f < n)
    {
        DG_Ran fv = val - o + *( g + f );
        DGEdit(g, f, n, fv);
    }
    return n;
}

//树状数组的翻转(树状数组的应用)
//一维  复杂度log(n)
//小于等于指定位置的元素的翻转<=pos
void DGDown1(DG_Ran g[],DG_Num pos,DG_Ran av)
{
    while(pos >= 0)
        g[pos] += av , pos = DGBrother(pos);
}
//获取位置pos的元素翻转次数
DG_Ran DGCUp1(DG_Ran g[],DG_Num pos , DG_Num n)
{
    DG_Ran t = 0;
    while(pos < n)
        t += g[pos] , pos = DGFather(pos);
    return t;
}
//二维  复杂度(log(n))^2
//小于等于指定位置的元素的翻转(0,0)->(x,y)
void DGDown2(DG_Ran g[][DG_MAXN],DG_Num x ,DG_Num y,DG_Ran av)
{
    while(x >= 0)
    {
        DG_Num tmp = y;
        while (tmp >= 0)
        {
            g[x][tmp] += av;
            tmp = DGBrother(tmp);
        }
        x = DGBrother(x);
    }
}
//获取位置(x,y)的元素翻转次数
DG_Ran DGCUp2(DG_Ran g[][DG_MAXN],DG_Num x ,DG_Num y , DG_Num n)
{
    DG_Ran t = 0;
    while(x < n)
    {
        DG_Num tmp = y;
        while (tmp < n)
        {
            t += g[x][tmp];
            tmp = DGFather(tmp);
        }
        x = DGFather(x);
    }
    return t;
}

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

题目要我们计算1，0的排列方式总数，并且对任意长的字符串，1的数量大于等于0的数量

我们可以把题目转化为从（0，0）点到（m，n）点的方法总数，且路径不经过y=x-1这条直线

/**
 * 线性筛法求素数表
 * 复杂度: O(n)
 */
const long MAXP = 1000000;
long prime[MAXP] = {0},num_prime = 0;
int isNotPrime[MAXP] = {1, 1};
void GetPrime_Init()//初始化调用
{
    for(long i = 2 ; i <  MAXP ; i ++)
    {
        if(! isNotPrime[i])
            prime[num_prime ++]=i;
        for(long j = 0 ; j < num_prime && i * prime[j] <  MAXP ; j ++)
        {
            isNotPrime[i * prime[j]] = 1;
            if( !(i % prime[j]))
                break;
        }
    }
}

线性筛法,即是筛选掉所有合数,留下质数

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

题目链接：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位置，如果都被占用就把原来的替换掉再给原来的字符串重新计算映射。这样下去可能出现死循环。会出现死循环就输出