关于差分约束（转载）

（本文假设读者已经有以下知识：最短路径的基本性质、Bellman-Ford算法。） 比如有这样一组不等式：

$$ \begin{cases} X1 - X2 <= 0 \\ X1 - X5 <= (-1) \\ X2 - X5 <= 1 \\ X3 - X1 <= 5 \\ X4 - X1 <= 4 \\ X4 - X3 <= (-1) \\ X5 - X3 <= (-3) \\ X5 - X4 <= (-3) \end{cases} $$(1)

一、引言

　　计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。

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

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

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

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

好久不写代码，省赛之后一直在赶作业和复习。对自己还真没什么信心

话说回来试了一下联系赛

三道水题，虽然钱两题很快，但是竟然多敲了几个没用的字符导致WA掉了，会范这种错误表示最近状态不宜写算法题啊

int a = 12345678;
//格式为sring输出
Label1.Text = string.Format("asdfadsf{0}adsfasdf",a);
Label2.Text = "asdfadsf"+a.ToString()+"adsfasdf";
Label1.Text = string.Format("asdfadsf{0:C}adsfasdf",a);//asdfadsf￥1,234.00adsfasdf
Label2.Text = "asdfadsf"+a.ToString("C")+"adsfasdf";//asdfadsf￥1,234.00adsfasdf
double b = 1234.12543;
int a = 12345678;
//格式为特殊的string样式输出
Label1.Text = string.Format("asdfadsf{0:C}adsfasdf",b);//asdfadsf￥1,234.13adsfasdf
Label2.Text = "asdfadsf"+b.ToString("C")+"adsfasdf";//asdfadsf￥1,234.13adsfasdf
Label1.Text = string.Format("{0:C3}",b);//￥1,234.125
Label2.Text = b.ToString("C3");//￥1,234.125
Label1.Text = string.Format("{0:d}",a);//十进制--12345678
Label2.Text = b.ToString("d");//十进制--相同的类型，转换报错
Label1.Text = string.Format("{0:e}",a);//指数--1.234568e+007
Label2.Text = b.ToString("e");//指数--1.234125e+003
Label1.Text = string.Format("{0:f}",a);//定点数--12345678.00
Label2.Text = b.ToString("f");//定点数--1234.13
Label1.Text = string.Format("{0:n}",a);//数值--12,345,678.00
Label2.Text = b.ToString("n");//数值--1,234.13
Label1.Text = string.Format("{0:x}",a);//十六进制--bc614e
Label2.Text = b.ToString("x");//16--带有小数不能转换，出错
Label1.Text = string.Format("{0:g}",a);//通用为最紧凑--12345678
Label2.Text = b.ToString("g");//通用为最紧凑--1234.12543
Label1.Text = string.Format("{0:r}",a);//转来转去不损失精度--整数不允许用，报错
Label2.Text = b.ToString("r");//转来转去不损失精度--1234.12543
double b = 4321.12543;
int a = 1234;
自定义模式输出：
//"0"描述：占位符，如果可能，填充位
Label1.Text = string.Format("{0:000000}",a);// 001234
Label2.Text = string.Format("{0:000000}",b);// 004321
//"#"描述：占位符，如果可能，填充位
Label1.Text = string.Format("{0:####### }",a);// 1234
Label2.Text = string.Format("{0:####### }",b);// 4321
Label1.Text = string.Format("{0:#0#### }",a);// 01234
Label2.Text = string.Format("{0:0#0000}",b);// 004321
//"."描述：小数点
Label1.Text = string.Format("{0:000.000}",a);//1234.000
Label2.Text = string.Format("{0:000.000}",b);//4321.125
double b = 87654321.12543;
int a = 12345678;
//","描述：数字分组，也用于增倍器
Label1.Text = string.Format("{0:0,00}",a);// 12,345,678
Label2.Text = string.Format("{0:0,00}",b);// 87,654,32
Label1.Text = string.Format("{0:0,}",a);// 12346
Label2.Text = string.Format("{0:0,}",b);// 87654
Label1.Text = string.Format("{0:0,,}",a);// 12
Label2.Text = string.Format("{0:0,,}",b);// 88
Label1.Text = string.Format("{0:0,,,}",a);// 0
Label2.Text = string.Format("{0:0,,,}",b);// 0
//"%"描述：格式为百分数
Label1.Text = string.Format("{ 0:0% }",a);// 1234567800%
Label2.Text = string.Format("{ 0:#% }",b);// 8765432113%
Label1.Text = string.Format("{ 0:0.00% }",a);// 1234567800.00%
Label2.Text = string.Format("{ 0:#.00% }",b);// 8765432112.54%
//"abc"描述：显示单引号内的文本
Label1.Text = string.Format("{0:'文本'0}",a);// 文本12345678
Label2.Text = string.Format("{0:文本0}",b);// 文本87654321
//"\"描述：后跟1要打印字的字符，也用于转移符\n等
Label1.Text = string.Format("\"你好！\"");// "你好！"
Label2.Text = string.Format("[url=file://\\c\\books\\new\\we.asp]\\c\\books\\new\\we.asp");//\c\books\new\we.asp
//"@"描述：后跟要打印字的字符,
Label1.Text = string.Format(@"""你好！"""); // "你好！"要打印"则需要输入两对才可以
Label2.Text = string.Format(@"\c\books\new\we.asp");//\c\books\new\we.asp

这次比赛成绩比预期差

开始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;
}

/**
 * 线性筛法求素数表
 * 复杂度: 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;
        }
    }
}

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

又是我们的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.

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

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

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