容斥原理专题(更新中……)

首先推荐一篇翻译过来的俄文论文
http://www.cnblogs.com/acSzz/archive/2012/11/18/2775923.html
uva10325
题意:整数区间[1,n],m个数a[1……m],且a[i]<=n,求区间[1,n]中不能被任意一个a[i]整除的数有多少
简单容斥

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef long long ll;
ll a[17];
ll ans;
ll n,m;
ll gcd(ll a,ll b)
{
	if(!b) return a;
	while(b)
	{
		ll t=a;
		a=b;
		b=t%b;
	
	}
	return a;
}
ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}
void dfs(int flag,ll x,ll num)
{
	if(flag&1) ans+=n/num;
	else ans-=n/num;
	for(int i=x+1;i<=m;i++)
		dfs(flag+1,i,lcm(num,a[i]));
	return;
}
int main()
{
	int i;
	while(scanf("%lld %lld",&n,&m)!=EOF)
	{
		for(i=1;i<=m;i++)
			scanf("%lld",&a[i]);
		ans=0;
		for(i=1;i<=m;i++)
			dfs(1,i,a[i]);
		ans=n-ans;
		printf("%lld\n",ans);

	
	
	}

	return 0;
}

uva11806
题意:n*m的格子矩阵,要你涂色其中k个格子,使得第一行、最后一行、第一列、最后一列都至少有一格涂色(角上的格子代表着两行),问有多少种方案,结果mod 1000007
思路:思考它的逆问题,上述四行中至少一行没有被涂色的可能方案数。容斥解之。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int mod=1000007;
int c[510][510],a[5],b[5];
int ans,n,m,k;
void init()
{
    int i,j;
    memset(c,0,sizeof(c));
    for(i=0;i<=500;i++)
        c[i][0]=1;
    for(i=1;i<=500;i++)
        for(j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        }
    return;
}
void dfs(int flag,int x,int row,int col)
{
    if(flag&1)
        ans=(ans+c[row*col][k])%mod;
    else
        ans=(ans-c[row*col][k]+mod)%mod;
    for(int i=x+1;i<=4;i++)
      dfs(flag+1,i,row+a[i],col+b[i]);
    return;

}
int main()
{
    int i,t,cases=0;
    a[1]=-1,a[2]=0,a[3]=-1,a[4]=0;
    b[1]=0,b[2]=-1,b[3]=0,b[4]=-1;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d",&n,&m,&k);
        ans=0;
        for(i=1;i<=4;i++)
            dfs(1,i,n+a[i],m+b[i]);
        ans=(c[n*m][k]-ans+mod)%mod;
        printf("Case %d: %d\n",++cases,ans);
    }
    return 0;
}

TopCoder SRM 477
题意:n个数对应n个位置,其中k个确定的位置错排的方案有多少种
思路:思考反问题,设k个位置分别为pos[1],pos[2],……,pos[k].pos[i]不错排,其他k-1个位置错排的方案,pos[i]、pos[j]错排,其它k-2个位置不错排的方案,and so on……

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef long long ll;
const ll mod=1000000007;
ll n,k;
ll ans;
ll fact[1010];
ll mulmod(ll a,ll n,ll m)
{
    ll y=0;
    a%=m;
    while(n)
    {
        if(n&1) y+=a;
        if(y>=m) y-=m;
        n>>=1;
        a<<=1;
        if(a>=m) a-=m;
    }
    return y;
}
void dfs(int flag,int x,ll num)
{
    if(flag&1)
        ans=(ans+fact[n-num])%mod;
    else
        ans=(ans-fact[n-num]+mod)%mod;
    for(int i=x+1;i<=k;i++)
        dfs(flag+1,i,num+1);

}
int main()
{
    int i;
    fact[0]=1;
    for(i=1;i<=1000;i++)
    fact[i]=mulmod(fact[i-1],i,mod);
    while(scanf("%lld %lld",&n,&k)!=EOF)
    {
        ans=0;
        for(i=1;i<=k;i++)
            dfs(1,i,1);
        ans=(fact[n]-ans+mod)%mod;
        printf("%lld\n",ans);

    }
    return 0;
}

hdoj2204
一直用g++提交,一直wa,后来用c++,终于ac了。。
1.a^k<=n,那么显然对于<=a的数t,t^k<=n
2.若a^(k*t),则(a^k)^t.所以只要考虑指数为素数的情况即可。
3.a^3与t^7可能相同,所以要用容斥

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef __int64 ll;
#define eps 1.0e-8
int a[5];
ll ans,n;
const int N=100;
int pr[N+10],p[N+10],lp;
void gp()
{
    for(int i=2;i<N;i++)
    {
        if(!pr[i])p[++lp]=pr[i]=i;
        for(int j=1;j<=lp && i*p[j]<N;j++)
        {
            pr[i*p[j]]=p[j];
            if(i%p[j]==0) break;
        }
    }
    return;
}
void dfs(int flag,int x,int num)
{
    int i;
    if(num>=60)
        return;
    ll tmp=(ll)pow((double)n+eps,1.0/num);

    if(flag&1)
        ans+=tmp;
    else
        ans-=tmp;
    for(i=x+1;i<=17;i++)
        dfs(flag+1,i,num*p[i]);
    return;
}
int main()
{
    int i;
    gp();
    while(scanf("%I64d",&n)!=EOF)
    {
        ans=0;
        for(i=1;i<=17;i++)
            dfs(1,i,p[i]);
        printf("%I64d\n",ans-1);
    }
    return 0;
}

zoj2836
简单那容斥,注意理解题意,any与every的区别。。

#include<stdio.h>
#include<stdlib.h>
typedef long long ll;
ll n,m,ans;
ll a[15];
ll gcd(ll a,ll b)
{
    if(a<b) a=a^b,b=a^b,a=a^b;
    if(!b) return a;
    while(b)
    {
        ll t=a;
        a=b;
        b=t%b;
    }
    return a;
}
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}
void dfs(ll flag,ll x,ll num)
{
    if(flag&1)
        ans+=m/num;
    else
        ans-=m/num;
    for(int i=x+1;i<=n;i++)
        dfs(flag+1,i,lcm(num,a[i]));
    return;
}
int main()
{
    int i,j;
    while(scanf("%lld %lld",&n,&m)!=EOF)
    {
        ans=0;
        for(i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        for(i=1;i<=n;i++)
            dfs(1,i,a[i]);
        printf("%lld\n",ans);

    }
    return 0;
}

zoj3233
题意:分别给你n个正整数a[i],m个正整数b[i],数据范围[1,32767],同时给你两个整数low,up,数据范围[1,10^18],问你[low,up]区间内有多少个数满足:至少能被一个a[i]整除且至少能被一个b[i]不整除。
哈哈,这题独立想出来了特别高兴,应为感觉这题不是直接赤裸裸的容斥,而是要变化下。
思路:
1.[low,up]区间满足的数的个数=[1,up]区间满足的数的个数-[1,low-1]区间满足的数的个数。
2.能被a整除,且能被b整除,等价于能被lcm(a,b)整除
3.至少能被一个a[i]整除且至少能被一个b[i]不整除,转化一下:至少能被一个a[i]整除且不是能被所有b[i]整除。为了是思维清晰,符号化一下:
x:至少能被一个a[i]整除.
y:能被所有b[i]整除
原命题转化为:x && (非y)
发现还是不能直接用容斥,继续转化,最关键的转化:x && (非y)=x-(x && y)
也就是说:(a[1]表示能被a[1]整除的个数)
(能被所有b[i]整除,等价于能被lcm(b[1],b[2],b[3],……,b[m])整除(设为lcm))
(a[1] || a[2] || …… || a[n])-(a[1] || a[2] || …… || a[n]) && lcm就是答案
很显然,减号的前面部分是可以直接用容斥的,后面部分却带了一个 && lcm,肿么办呢?
其实这里考察的就是布尔代数的知识啦。
(a[1] || a[2] || …… || a[n]) && lcm=(a[1] && lcm) || (a[2] && lcm) || …… || (a[n] && lcm)
化成这样就可以使用容斥啦。
最后,分别对[1,up],[1,low-1]求解出满足的个数再相减就可以了。
本题这样就解决了吗?思路上这样确实对了,但是还有一个要注意的地方,这个地方往往被忽略(弱菜表示因为这个提交错了20次。。).
本题的a[i],b[i]是10^4级别,且b序列可能达到500个,这样最坏情况下,这些数的lcm是会llu溢出的,溢出说明区间中没有数能被这个数整除,因为这个数太大了。所以直接返回或continue即可。(可以lcm()函数里判断是否溢出,溢出返回0,这样在dfs等地方就很好判断是否溢出了,当然,也可以在溢出时,让lcm()返回一个>10^18的数,试了一下时间从690 ms升到1190 ms)
—————————————————我是分割线君————————————————
好吧,看了下网上别人的代码,其实可以更严格地考虑当a/gcd>up/b就返回up+1,也就是说当lcm大于up了,能被lcm整除的数一定为0了。

#include<stdio.h>
const unsigned long long inf=(1<<63)-1+(1<<63);
typedef unsigned long long ll;
int n,m;
ll a[20];
ll ans;
bool flag;
ll gcd(ll a,ll b)
{
    if(a<b) a=a^b,b=a^b,a=a^b;
    if(!b) return a;
    while(b)
    {
        ll t=a;
        a=b;
        b=t%b;
    }
    return a;
}
ll lcm(ll a,ll b)
{
    ll tmp=a/gcd(a,b);
    if(tmp>(inf/b))
        return 0;
    return tmp*b;
}
void dfs(ll flag,int x,ll num,ll b)
{
    if(num==0)
        return;
    if(flag&1)
        ans+=b/num;
    else
        ans-=b/num;
    for(int i=x+1;i<=n;i++)
    {
        if(a[i]==0)
            continue;
        dfs(flag+1,i,lcm(num,a[i]),b);
    }
    return;

}
ll solve(ll l,ll r)
{
    int i;
    ll result=0;
    ans=0;
    for(i=1;i<=n;i++)
        dfs(1,i,a[i],l);
    result+=ans;
    ans=0;
    for(i=1;i<=n;i++)
        dfs(1,i,a[i],r);
    result=ans-result;
    if(flag)
    {
        for(i=1;i<=n;i++)
        {
            a[i]=lcm(a[i],a[n+1]);
        }
        ans=0;
        for(i=1;i<=n;i++)
            dfs(1,i,a[i],l);
        result+=ans;
        ans=0;
        for(i=1;i<=n;i++)
            dfs(1,i,a[i],r);
        result-=ans;
    }
    return result;
}
int main()
{
    int i;
    ll l,r;
    scanf("%d %d %llu %llu",&n,&m,&l,&r);
    while(!(n==0 && m==0 && l==0 && r==0))
    {
        flag=1;
        for(i=1;i<=n;i++)
        {
            scanf("%llu",&a[i]);
        }
        a[n+1]=1;
        ll tmp;
        for(i=1;i<=m;i++)
        {
            scanf("%llu",&tmp);
            if(a[n+1]==0)
            {
                flag=0;
                continue;
            }
            a[n+1]=lcm(a[n+1],tmp);
        }
        ll result=solve(l-1,r);
        printf("%llu\n",result);
        scanf("%d %d %llu %llu",&n,&m,&l,&r);
    }
    return 0;
}

hdoj1796
简单容斥

#include<stdio.h>
typedef long long ll;
ll a[15];
ll n;
int m;
ll ans;
ll gcd(ll a,ll b)
{
    if(a>b) a=a^b,b=a^b,a=a^b;
    if(!b) return a;
    while(b)
    {
        ll t=a;
        a=b;
        b=t%b;
    }
    return a;
}
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}
void dfs(int flag,int x,ll num)
{
    if(flag&1)
        ans+=n/num;
    else
        ans-=n/num;
    for(int i=x+1;i<=m;i++)
    {
        if(a[i]==0)
            continue;
        dfs(flag+1,i,lcm(num,a[i]));
    }
    return;
}
int main()
{
    int i;
    while(scanf("%lld %d",&n,&m)!=EOF)
    {
        n--;
        ans=0;
        for(i=1;i<=m;i++)
        {
            scanf("%lld",&a[i]);
        }
        if(n==0)
        {
            printf("0\n");
            continue;
        }
        for(i=1;i<=m;i++)
        {
            if(a[i]==0)
                continue;
            dfs(1,i,a[i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

hdoj2841
开始把这题想的太简单了。
开始的错误思路,如图:

只考虑了和蓝色线共线的点,没考虑紫色线共线的点。
正确思路:可以发现,两个点与(0,0)在一条线上,那么a1/b1=a2/b2,也就是说加入两个点坐标(a,b),a与b不互质,则设a=a1*d,b=b1*d,那么a/b=a1/b1,也就是说(a,b)与(a1,b1)共线。那么本体就转化为找[1,n]、[1,m]有多少个互素对(交换位置算不同的互素对)

#include<stdio.h>
#include<string.h>
const int N=100000;
int pr[N+10],p[N];
int pi[N+5][30],ki[N+5][30];//这里数组大小开成log2(N)左右即可
int cnt,lp;
int ans;
int n,m;
void gp()
{
	for(int i=2;i<=N;i++)
	{
		if(!pr[i])
			p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0)break;
		}
	}
	return;
}
void fenjie(int n,int* pi,int* ki)
{
	cnt=0;
	memset(ki,0,sizeof(ki));
    while(n!=1)
	{
        int t=pr[n];
        pi[++cnt]=t;
        ki[cnt]=0;
        while(n%t==0)
        {
            n/=t;
            ki[cnt]++;
        }
    }
    pi[0]=cnt;
    return;
}
void dfs(int flag,int x,int num,int d)
{
    if(flag&1)
        ans+=m/num;
    else
        ans-=m/num;
    for(int i=x+1;i<=pi[d][0];i++)
        dfs(flag+1,i,num*pi[d][i],d);
    return;
}
int rongchi(int n)
{
    ans=0;
    for(int i=1;i<=pi[n][0];i++)
        dfs(1,i,pi[n][i],n);
    ans=m-ans;
    return ans;
}
__int64 solve()
{
    int i;
    __int64 result=0;
    for(i=1;i<=n;i++)
    {
        result+=(__int64)rongchi(i);
    }

    return result;
}
int main()
{
    int i;
    int t;
    gp();
    for(i=2;i<=N;i++)
        fenjie(i,pi[i],ki[i]);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        if(n==1 || m==1)
        {
            int ans=(n==1?m:n);
            printf("%d\n",ans);
            continue;
        }
        __int64 result=solve();
        printf("%I64d\n",result);






    }

    return 0;
}

ural1091
题意:在[1,s]取k个不同的数,要求,这k个数有>1的公约数,给出k、s,求组数
思路:如果k个数含公因子p[i]、p[j],那么这些组肯定会重复计算。
ans=∑c(s/p[i],k)-∑c(s/(p[i]*p[j]),k)+……(p[i]是素数)

#include<stdio.h>
typedef long long ll;
int p[16]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
int s,k;
ll  ans;
int cc[45][45];
int c(int n,int m)
{
    if(m>n)
        return 0;
    return cc[n][m];
}
void dfs(int flag,int x,int num)
{
    if(num>s)
        return;
    if(flag&1)
        ans+=(ll)c(s/num,k);
    else
        ans-=(ll)c(s/num,k);
    for(int i=x+1;i<=15;i++)
        dfs(flag+1,i,num*p[i]);
    return;
}
int main()
{
    int i,j;
    for(i=0;i<=40;i++)
        cc[i][0]=1;
    for(i=1;i<=40;i++)
        for(j=1;j<=i;j++)
            cc[i][j]=cc[i-1][j-1]+cc[i-1][j];

    while(scanf("%d %d",&k,&s)!=EOF)
    {
        ans=0;
        for(i=1;i<=15;i++)
            dfs(1,i,p[i]);
        if(ans<10000)
            printf("%lld\n",ans);
        else
            printf("10000\n");

    }
    return 0;
}

URAL 1114
题意:a个相同的红球和b个相同的篮球放入n个不同的盒子,每个盒子可以为空,球可以不放。问有几种放球方案。
思路:
1.对于没放的球,可以抽象出一个盒子,这个盒子用于放没放的球,这样就解决了球可以不放的问题。
2.对于球的颜色,可以分别计算放红球的方法数,放篮球的方法数,乘法原理即可,可以这样做的原因在于:对于不同的红球方法,必有至少一个盒子里面的红球数不同,而对于每种红球方法,加上不同的篮球放法必然形成不同的放法。这样就解决了颜色问题
3.最后就是插板法计算每种球的方法了:c(n+a,n)、c(n+b,n)。最后答案两者相乘
4.注意要用高精度。。(尼玛,这次这个大数模板没出错,看来刚才wa的几题不是大数部分出错。。)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 9999
#define MAXSIZE 1000
#define DLEN 4
using namespace std;
class BigNum;
istream& operator>>(istream&,  BigNum&);
ostream& operator<<(ostream&,  BigNum&);
class BigNum
{
public:
	int a[MAXSIZE];
	int len;
public:
	BigNum(){len = 1;memset(a,0,sizeof(a));}
	BigNum(const int);
	BigNum(const char*);
	BigNum(const BigNum &);
	BigNum &operator=(const BigNum &);
	friend istream& operator>>(istream&,  BigNum&);
	friend ostream& operator<<(ostream&,  BigNum&);
	BigNum operator+(const BigNum &) const;
	BigNum operator-(const BigNum &) const;
	BigNum operator*(const BigNum &) const;
	BigNum operator/(const int  &) const;
	BigNum operator^(const int  &) const;
	int    operator%(const int  &) const;
	bool   operator>(const BigNum & T)const;
	bool   operator==(const BigNum & T)const;
	bool   operator==(const int & t)const;
	bool   operator>(const int & t)const;
};
istream& operator>>(istream & in,  BigNum & b)
{
	char ch[MAXSIZE*4];
	int i = -1;
	in>>ch;
	int l=strlen(ch);
	int count=0,sum=0;
	for(i=l-1;i>=0;)
	{
		sum = 0;
		int t=1;
		for(int j=0;j<4&&i>=0;j++,i--,t*=10)
		{
			sum+=(ch[i]-'0')*t;
		}
		b.a[count]=sum;
		count++;
	}
	b.len =count++;
	return in;

}
ostream& operator<<(ostream& out,  BigNum& b)
{
	int i;
	cout << b.a[b.len - 1];
	for(i = b.len - 2 ; i >= 0 ; i--)
	{
		cout.width(DLEN);
		cout.fill('0');
		cout << b.a[i];
	}
	return out;
}
BigNum::BigNum(const int b)
{
	int c,d = b;
	len = 0;
	memset(a,0,sizeof(a));
	while(d > MAXN)
	{
		c = d - (d / (MAXN + 1)) * (MAXN + 1);
		d = d / (MAXN + 1);  a[len++] = c;
	}
	a[len++] = d;
}
BigNum::BigNum(const char*s)
{
	int t,k,index,l;
	memset(a,0,sizeof(a));
	l=strlen(s);
	len=l/DLEN;
	if(l%DLEN)len++;
	index=0;
	for(int i=l-1;i>=0;i-=DLEN)
	{
		t=0;k=i-DLEN+1;
		if(k<0)k=0;
		for(int j=k;j<=i;j++)
			t=t*10+s[j]-'0';
		a[index++]=t;
	}
}
BigNum::BigNum(const BigNum & T) : len(T.len)
{
	int i;
	memset(a,0,sizeof(a));
	for(i = 0 ; i < len ; i++)  a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n)
{
	len = n.len;
	memset(a,0,sizeof(a));
	for(int i = 0 ; i < len ; i++)
		a[i] = n.a[i];
	return *this;
}
BigNum BigNum::operator+(const BigNum & T) const
{
	BigNum t(*this);
	int i,big;
	big = T.len > len ? T.len : len;
	for(i = 0 ; i < big ; i++)
	{
		t.a[i] +=T.a[i];
		if(t.a[i] > MAXN)
		{
			t.a[i + 1]++;
			t.a[i] -=MAXN+1;
		}
	}
	if(t.a[big] != 0) t.len = big + 1;
	else t.len = big;
	return t;
}
BigNum BigNum::operator-(const BigNum & T) const
{
	int i,j,big;
	bool flag;
	BigNum t1,t2;
	if(*this>T)
	{
		t1=*this;
		t2=T;
		flag=0;
	}
	else
	{
		t1=T;
		t2=*this;
		flag=1;
	}
	big=t1.len;
	for(i = 0 ; i < big ; i++)
	{
		if(t1.a[i] < t2.a[i])
		{
			j = i + 1;
			while(t1.a[j] == 0) j++;
			t1.a[j--]--;
			while(j > i) t1.a[j--] += MAXN;
			t1.a[i] += MAXN + 1 - t2.a[i];
		}
		else t1.a[i] -= t2.a[i];
	}
	t1.len = big;
	while(t1.a[len - 1] == 0 && t1.len > 1)
	{
		t1.len--;
		big--;
	}
	if(flag)t1.a[big-1]=0-t1.a[big-1];
	return t1;
}
BigNum BigNum::operator*(const BigNum & T) const
{
	BigNum ret;
	int i,j,up;
	int temp,temp1;
	for(i = 0 ; i < len ; i++)
	{
		up = 0;
		for(j = 0 ; j < T.len ; j++)
		{
			temp = a[i] * T.a[j] + ret.a[i + j] + up;
			if(temp > MAXN)
			{
				temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
				up = temp / (MAXN + 1);
				ret.a[i + j] = temp1;
			}
			else
			{
				up = 0;
				ret.a[i + j] = temp;
			}
		}
		if(up != 0)
			ret.a[i + j] = up;
	}
	ret.len = i + j;
	while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
	return ret;
}
BigNum BigNum::operator/(const int & b) const
{
	BigNum ret;
	int i,down = 0;
	for(i = len - 1 ; i >= 0 ; i--)
	{
		ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
		down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
	}
	ret.len = len;
	while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
	return ret;
}
int BigNum::operator %(const int & b) const
{
	int i,d=0;
	for (i = len-1; i>=0; i--)
	{
		d = ((d * (MAXN+1))% b + a[i])% b;
	}
	return d;
}
BigNum BigNum::operator^(const int & n) const
{
	BigNum t,ret(1);
	int i;
	if(n<0)exit(-1);
	if(n==0)return 1;
	if(n==1)return *this;
	int m=n;
	while(m>1)
	{
		t=*this;
		for( i=1;i<<1<=m;i<<=1){
			t=t*t;
		}
		m-=i;
		ret=ret*t;
		if(m==1)ret=ret*(*this);
	}
	return ret;
}
bool BigNum::operator>(const BigNum & T) const
{
	int ln;
	if(len > T.len) return true;
	else if(len == T.len)
	{
		ln = len - 1;
		while(a[ln] == T.a[ln] && ln >= 0) ln--;
		if(ln >= 0 && a[ln] > T.a[ln]) return true;
		else return false;
	}
	else return false;
}
bool BigNum::operator==(const BigNum & T) const
{
	int ln;
	if(len != T.len) return false;
	else
	{
		ln = len - 1;
		while(a[ln] == T.a[ln] && ln-- );
		if(ln < 0) return true;
		else return false;
	}
}
bool BigNum::operator >(const int & t) const
{
	BigNum b(t);
	return *this>b;
}
bool BigNum::operator==(const int & t) const
{
	BigNum b(t);
	return *this==b;
}
typedef BigNum ll;
ll cc[45][45];
ll c(int n,int m)
{
    if(m>n)
        return 0;
    return cc[n][m];
}
int main()
{
    int i,j;
    for(i=0;i<=40;i++)
        cc[i][0]=1;
    for(i=1;i<=40;i++)
        for(j=1;j<=i;j++)
            cc[i][j]=cc[i-1][j-1]+cc[i-1][j];
    int n,a,b;
    while(scanf("%d%d%d",&n,&a,&b)!=EOF)
    {
        ll ans=c(n+a,n)*c(n+b,n);
        cout<<ans<<endl;
    }
    return 0;
}

poj1091
关键是要知道最大公约数相关定理,本博客中已转载

#include<stdio.h>
typedef long long ll;
ll n,m;
const ll N=1000000;
ll pr[N+10],p[(N+10)/10],lp;
void gp()
{
	for(ll i=2;i<=N;i++)
	{
		if(!pr[i]) p[++lp]=pr[i]=i;
		for(ll j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
	return;
}
ll cnt;//b数组用来存放n分解后的素因子
ll b[50];
void gn(ll n)
{
	ll i,t;
	cnt=0;
	while(n>1)
	{
		if(n<=N) //判断n是否小于等于10^6,当大于10^6时,它肯定含有p[1—lp]范围内的素数(如果不含,那么必然是素数,否则它含有大于10^6的素数,则它>10^12)
			t=pr[n];//小于的时候直接log级别分解
		else
		{
			t=n;
			for(i=1;i<=lp && p[i]<=n/p[i];i++)
				if(n%p[i]==0)
				{
					t=p[i];
					break;
				}
		}
		while(n%t==0) n/=t;
			b[++cnt]=t;
	}
	return;
}
ll ans;
ll cal(ll x)
{
    ll result=1;
    for(ll i=1;i<=n;i++)
    {
        result*=x;
    }
    return result;

}
void dfs(int flag,ll x,ll num)
{
    ll tmp=cal(m/num);
    if(flag&1)
        ans+=tmp;
    else
        ans-=tmp;
    for(ll i=x+1;i<=cnt;i++)
    {
        dfs(flag+1,i,num*b[i]);
    }
    return;
}
int main()
{
    ll i;
    gp();
    while(scanf("%lld %lld",&n,&m)!=EOF)
    {
        ans=0;
        gn(m);
        for(i=1;i<=cnt;i++)
            dfs(1,i,b[i]);
        ans=cal(m)-ans;
        printf("%lld\n",ans);
    }
    return 0;
}

hdoj4135
简单容斥

#include<stdio.h>
typedef __int64 ll;
ll n,a,b;
const int N=1000000;
ll pr[N+10],p[(N+10)/10],lp;
void gp()
{
	for(int i=2;i<=N;i++)
	{
		if(!pr[i]) p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
	return;
}
int cnt;
ll pp[30];//b数组用来存放n分解后的素因子
void gn(ll n)
{
	int i,t;
	cnt=0;
	while(n>1)
	{
		if(n<=N) //判断n是否小于等于10^6,当大于10^6时,它肯定含有p[1—lp]范围内的素数(如果不含,那么必然是素数,否则它含有大于10^6的素数,则它>10^12)
			t=pr[n];//小于的时候直接log级别分解
		else
		{
			t=n;
			for(i=1;i<=lp && p[i]<=n/p[i];i++)
				if(n%p[i]==0)
				{
					t=p[i];
					break;
				}
		}
		while(n%t==0) n/=t;
			pp[++cnt]=t;
	}
	return;
}
ll ans;
void dfs(int flag,int x,ll num,ll n)
{
    if(num>n)
        return;
    if(flag&1)
        ans+=n/num;
    else
        ans-=n/num;
    for(int i=x+1;i<=cnt;i++)
    {
        if(num*pp[i]<=n)
            dfs(flag+1,i,num*pp[i],n);
    }
    return;
}
int main()
{
    int t,i,cases=0;
    gp();
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%lld %lld %lld",&a,&b,&n);
        gn(n);
        for(i=1;i<=cnt;i++)
            dfs(1,i,pp[i],a-1);
        ll tmp=ans;
        ans=0;
        for(i=1;i<=cnt;i++)
            dfs(1,i,pp[i],b);
        ans=ans-tmp;
        ans=b-a+1-ans;
        printf("Case #%d: %lld\n",++cases,ans);
     }
    return 0;
}

poj2773
二分+容斥
一开始以为二分完就可以了,其实还要判断当前答案是否与m互质,如果不互质,还要继续减下去。

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll inf=100000000000000000;
const int N=1000000;
ll pr[N+10],p[N];
ll pi[N],ki[N];//这里数组大小开成log2(N)左右即可
int cnt,lp;
ll m,k;
ll gcd(ll a,ll b)
{
    if(a<b) a=a^b,b=a^b,a=a^b;
    if(!b) return a;
    while(b)
    {
        ll t=a;
        a=b;
        b=t%b;
    }
    return a;
}
void gp()
{
	for(int i=2;i<=N;i++)
	{
		if(!pr[i])
			p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0)break;
		}
	}
	return;
}
void fenjie(ll n)
{
	cnt=0;
	memset(ki,0,sizeof(ki));
	while(n!=1)
	{
		ll t=pr[n];
        pi[++cnt]=t;ki[cnt]=0;
        while(n%t==0)
        {
            n/=t;ki[cnt]++;
        }
    }
    return;
}
ll ans;
void dfs(int flag,int x,ll num,ll n)
{
    if(flag&1)
        ans+=n/num;
    else
        ans-=n/num;
    for(int i=x+1;i<=cnt;i++)
    {
        if(num*pi[i]<=n)
            dfs(flag+1,i,num*pi[i],n);
    }
    return;
}
int main()
{
    int i,j;
    gp();
    while(scanf("%lld %lld",&m,&k)!=EOF)
    {
        ans=0;
        ll result=0;
        fenjie(m);
        ll l=1,r=inf,mid;
        while(l<=r)
        {
            ans=0;
            mid=l+(r-l)/2;
            for(i=1;i<=cnt;i++)
                dfs(1,i,pi[i],mid);
            ans=mid-ans;
            if(ans==k)
            {
                result=mid;
                break;
            }
            else if(ans>k)
                r=mid-1;
            else
                l=mid+1;
        }
        result=mid;

        while(gcd(result,m)!=1)
        {
            result--;
        }

        printf("%lld\n",result);




    }

    return 0;
}

zoj3687
终于ac了,纠结了好一阵子,居然是变量名错了。
关键点:冲突的条件不可能同时成立,所以要判断这种情况。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mod 55566677
using namespace std;
bool day[55],cha[55];
bool hash[55][55];
typedef long long ll;
typedef struct node{
    int d,c;
}node;
node a[30];
ll fact[55];
int n,m;
ll ans;
void dfs(int flag,int x,int num)
{
    day[a[x].d]=1;cha[a[x].c]=1;
    if(flag&1)
    {
        ans=((ans-fact[n-num])%mod+mod)%mod;
    }
    else
    {
        ans=(ans+fact[n-num])%mod;
    }
    for(int i=x+1;i<=m;i++)
    {
        if((day[a[i].d]==1) || (cha[a[i].c]==1)) continue;
        dfs(flag+1,i,num+1);
        day[a[i].d]=0;cha[a[i].c]=0;
    }
    return;
}
int main()
{
    int i;
    fact[0]=1;fact[1]=1;
    for(i=2;i<=50;i++)
        fact[i]=fact[i-1]*(ll)i%mod;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(day,0,sizeof(day));
        memset(cha,0,sizeof(cha));
        memset(hash,0,sizeof(hash));
        int cnt=0;
        for(i=1;i<=m;i++)
        {
            int d,c;
            scanf("%d%d",&d,&c);
            if(hash[d]1) continue;
            a[++cnt].d=d;a[cnt].c=c;
            hash[d]1=1;
        }
        m=cnt;
        ans=fact[n];
        for(i=1;i<=m;i++)
        {
            dfs(1,i,1);
            day[a[i].d]=0;cha[a[i].c]=0;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

hdoj1025

LIS+单调队列优化

#include<stdio.h>
#include<algorithm>
#define N 100000+10
#define inf 1000000000
using namespace std;
typedef struct Node{
	int p,r;
}Node;
Node node[N];
int b[N];
bool cmp(Node a,Node b)
{
	return a.p<b.p;
}
int main()
{
	int i,j;
	int n,cases=0;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++)
		{
			int p,r;
			scanf("%d %d",&p,&r);
			node[i].p=p;
			node[i].r=r;
			b[i]=inf;
		}
		sort(node+1,node+1+n,cmp);
		for(i=1;i<=n;i++)
		{
			int* index=lower_bound(b+1,b+1+n,node[i].r);
			b[index-b]=node[i].r;
		}
		for(i=n;i>=1;i--)
			if(b[i]!=inf)
				break;
		printf("Case %d:\nMy king, at most %d %s can be built.\n\n",++cases,i,i==1?"road":"roads");

	
	}

	//system("pause");
	return 0;
}

数论专题

基础应用:
hdoj3501

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define ll __int64
#define mod 1000000007
ll phi(int n)
{
    int m = floor(sqrt(n+0.5));
    ll ans = n;
    for(int i = 2; i <= m; i++)
		if(n%i == 0)
		{
			ans = ans / i * (i-1);
			while(n%i == 0)
			{
				n /= i;
			}
		}
    if(n > 1)
		ans = ans / n *(n-1);
    return ans;
}
ll mulmod(ll a,ll n,ll m){
    ll y=0;
    a%=m;
    while(n){ 
        if(n&1) y+=a;
        if(y>=m) y-=m;
        n>>=1;
        a<<=1;
        if(a>=m) a-=m;
    }
    return y;
}

int main()
{
	int n,i;
	scanf("%d",&n);
	while(n!=0)
	{
		ll tmp=n-1-phi(n);
		if(tmp&1)
			n/=2;
		else
			tmp/=2;
		ll	ans=mulmod(tmp,(ll)n,(ll)mod);
		printf("%I64d\n",ans);
		
		

		scanf("%d",&n);
	}
	system("pause");
	return 0;
}

hdoj1215

#include<stdio.h>
#include<string.h>
#define N 500000
int sum[N+10];
void yueshu()
{
	int i,j;
	for(i=1;i<=N/2;i++)
	{
		for(j=2*i;j<=N;j+=i)
		{
			if(j>N) break;
			sum[j]+=i;
		}
	}
	return;

}
int main()
{
	int t;
	memset(sum,0,sizeof(sum));
	yueshu();
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		printf("%d\n",sum[n]);
		
	
	
	
	}
	return 0;
}

hdoj2136
用普通的筛选法筛出素数,然后记录每个素数在素数表里的位置,pr[]数组记录的是每个数的最大素因子
注意:这里的筛选素数不能写成

for(i=2;i*i<=N;i++)
{	
    if(!pr[i])
    {
	p[++lp]=i;
	pos[i]=lp;
	for(j=i*i;j<=N;j+=i)
	pr[j]=i;
    }
}

这样会出错,对于sqrt(N)的素数没有用来更新它的倍数,这样它的倍数的pr[]也没有更新,另外若i是素数,也没更新pr[i]

#include<stdio.h>
const int N=1000000;
int pr[N+10],p[N/10+10],lp;
int pos[N+10];
void gp(){
	int i,j;
    for(i=2;i<=N;i++)
	{	
		if(!pr[i])
		{
			p[++lp]=i;
			pos[i]=lp;
			for(j=i;j<=N;j+=i)
				pr[j]=i;
		}
    }
	return;
}
int main()
{
	int i,j;
	int n;
	gp();
	while(scanf("%d",&n)!=EOF)
	{
		if(n==1)
		{
			printf("0\n");
			continue;
		}
		
		printf("%d\n",pos[pr[n]]);
	
	
	}
	return 0;

}

poj2689
筛两次,注意细节

#include<stdio.h>
#include<string.h>
bool p[50010];
bool pr[1000000+10];
int prime[1000000+10];
void gp()
{
	int i,j;
	p[1]=0;
	memset(p,1,sizeof(p));
	for(i=2;i*i<=50000;i++)
	{
		if(p[i])
		{
			for(j=i*i;j<=50000;j+=i)
			{
				p[j]=0;
			}
		}
	}
	return;
}
void gp2(__int64 l,__int64 r)
{
	__int64 i,j;
	memset(pr,1,sizeof(pr));
	if(l==1)
		pr[1]=0;
	for(i=2;i*i<=r;i++)
	{
		if(i*i>r)
			break;
		if(p[i])
		{
			j=i*i;
			if(j<l)
			{
				j=(l/i)*i;
				if(j<l)
					j+=i;
			}
			for(;j<=r;j+=i)
			{
				if(j>r) break;
				pr[j-l+1]=0;
			}
		}
	}
	return;
}
int main()
{
	__int64 i;
	__int64 l,r;
	gp();
	while(scanf("%I64d %I64d",&l,&r)!=EOF)
	{
		gp2(l,r);
		int cnt=0;
		for(i=l;i<=r;i++)
		{
			if(pr[i-l+1])
				prime[++cnt]=i;
		}
		if(cnt<=1)
		{
			printf("There are no adjacent primes.\n");
			continue;
		}
		int min=1000000+10,max=-1,minx,miny,maxx,maxy;
		for(i=1;i<=cnt-1;i++)
		{
			if(prime[i+1]-prime[i]<min)
			{
				min=prime[i+1]-prime[i];
				minx=prime[i];
				miny=prime[i+1];
			
			}
			if(prime[i+1]-prime[i]>max)
			{
				max=prime[i+1]-prime[i];
				maxx=prime[i];
				maxy=prime[i+1];
			}
		
		}
		printf("%d,%d are closest, %d,%d are most distant.\n",minx,miny,maxx,maxy);
	
	}


	return 0;
}

hdoj4474
这题思路很巧妙,如果枚举n的倍数显然超时,而且这个答案可能非常大,无法用long long存储。
正确方法是用可用的数字bfs,如果当前状态下除以n的余数前面状态得到过,那么这个就不用进队了,因为显然由前面的那个状态进行搜索更优,这样队列中最多10000左右的元素,状态间要记录前驱。开始没有记录前驱,而是直接每个状态都开个字符串,最后MLE。。
然后又是被一个小错误弄的RE好多次。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 10010
char use[11];
typedef struct node{
	char num;
	short mod;
	short pre;
}node;
bool has[maxn];
short n,m;
char cnt;
char ans[maxn];
node q[maxn];
short anscnt;
bool bfs()
{
	short i,j;
	memset(has,0,sizeof(has));
	int iq=0;
	node sr;
	for(i=1;i<=cnt;i++)
	{

		if(use[i]==0)
			continue;
		sr.mod=use[i]%n;
		if(has[sr.mod]==1) continue;
		has[sr.mod]=1;
		sr.pre=-1;
		sr.num=use[i];
		if(sr.mod==0)
		{
			ans[++anscnt]=use[i];
			return 1;
		}
		q[iq++]=sr;
	}
	for(i=0;i<=iq-1;i++)
	{
		int mod=q[i].mod;
		for(j=1;j<=cnt;j++)
		{
			int yushu=((mod*(10%n))%n+use[j]%n)%n;
			if(has[yushu]) continue;
			has[yushu]=1;
			node tmp;
			tmp.mod=yushu;
			tmp.pre=i;
			tmp.num=use[j];
			if(tmp.mod==0)
			{
				ans[++anscnt]=tmp.num;
				int cur=tmp.pre;
					while(cur!=-1)
					{
						ans[++anscnt]=q[cur].num;
						cur=q[cur].pre;
					}
				return 1;
			
			}
			q[iq++]=tmp;

		}
	}
	return 0;
}
int main()
{
	short i,j;
	int cases=0;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		if(m==10)
		{
			for(i=1;i<=m;i++)
			{
				char tmp;
				scanf("%d",&tmp);
			}
			printf("Case %d: ",++cases);
			printf("-1\n");

			continue;
		}
		bool digit[12];
		anscnt=0;
		memset(digit,1,sizeof(digit));
		for(i=1;i<=m;i++)
		{
			int tmp;
			scanf("%d",&tmp);
			digit[tmp]=0;
		}
		cnt=0;
		for(i=0;i<=9;i++)
		{
			if(digit[i]==1)
				use[++cnt]=i;
		}
		bool flag=bfs();
		printf("Case %d: ",++cases);
		if(flag)
		{
			for(int tt=anscnt;tt>=1;tt--)
				printf("%d",ans[tt]);
			printf("\n");
		}
		else
			printf("-1\n");


	
	
	}
	return 0;
}

poj1845
对a进行分解质因数,但是由于是a^b,所以a^b的质因子指数非常大,所以构造矩阵快速计算pi^1+pi^2+……+pi^ki %mod
矩阵为:
pi pi
0 1
开始的思路是O(n)时间预处理出2——50000000每个数的最小质因数,然后常数时间对a分解质因数,结果无情的MLE了。。
改成sqrt(n)时间分解质因数就能AC了

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int maxn=3100000;
const int mod=9901;
int cnt;
__int64 p[maxn],k[maxn];
void fenjie(int n)
{
	cnt=0;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i == 0)
		{
			p[++cnt]=i;
			k[cnt]=0;
			while(n%i==0)
			{
				n/=i;
				k[cnt]++;
			}
		}
	}
	if(n > 1)
	{
		p[++cnt]=n;
		k[cnt]=1;
	}
	return;
}
typedef struct Mat{
	__int64 m[3][3];
}Mat;
Mat per;
Mat multi(Mat a,Mat b)
{
	int i,j,k;
	Mat ans;
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
		{
			__int64 tmp=0;
			for(k=1;k<=2;k++)
				tmp=(tmp+a.m[i][k]*b.m[k][j])%mod;
			ans.m[i][j]=tmp;	
		}
	return ans;

}
Mat pow(Mat a,__int64 k)
{
	Mat ans=per,p=a;
	while(k)
	{
		if(k&1)
		{
			k--;
			ans=multi(ans,p);
		}
		else
		{
			k/=2;
			p=multi(p,p);
		}
	}
	return ans;
}
int main()
{
	int i,j;
	int a,b;
	Mat aa;
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
			per.m[i][j]=(i==j);
	while(scanf("%d %d",&a,&b)!=EOF)
	{
		fenjie(a);
		__int64 ans=1;
		for(i=1;i<=cnt;i++)
		{
			k[i]*=b;
			aa.m[1][1]=p[i];aa.m[1][2]=p[i];aa.m[2][1]=0;aa.m[2][2]=1;
			Mat tmp=pow(aa,k[i]);
			__int64 tt=(tmp.m[1][2]+1)%mod;
			ans=(ans*tt)%mod;
		}
		printf("%I64d\n",ans);
	
	
	
	
	
	}

	return 0;
}

poj1061
在zxs大神的帮助下终于ac了,orz一下^_^
wa的关键点在于自己对求方程通解的原理原来并不理解深刻,只是生搬硬套,导致错误。理解很重要啊
设d=gcd(a,b)
ax+by=d的初解是(x,y),那么ax0-by0=0加到该方程上一定还是成立的(因为加了0嘛。。)得到:
a(x+x0)+b(y-y0)=d。ax0=by0,可见a是ax0的约数,b是ax0的约数,所以ax0=by0一定是a和b的公倍数,那么要不漏掉任何解的话ax0自然要取最小,即ax0=by0=lcm(a,b)(设为lcm).如此可见,通解为(x+k*(lcm/a),y-k*(lcm/b))
再来考虑ax+by=c与ax+by=d的关系,显然在后面那个方程两边乘上c/d就得到了方程ax+by=c.所以得到ax+by=c的初解是(x*c/d,y*c/d)。那么它的通解呢。我们可以用分析ax+by=d的通解的方法来分析。
在ax+by=c基础上加上ax0-by0=0方程仍然成立。由于从ax+by=d到ax+by=c,系数a、b没有变,所以x0,y0也没变。这样,就得到ax+by=c的通解为(x*(c/d)+k*(lcm/a),y*(c/d)-k*(lcm/b))

#include<stdio.h>
#include<stdlib.h>
void exgcd(__int64 a,__int64 b,__int64 &d,__int64 &x,__int64 &y)
{
	if (!b) d=a,x=1,y=0;
	else
	{
		exgcd(b,a%b,d,y,x);
		y-=a/b*x;
	}
	return;
}
int main()
{
	__int64 x,y,m,n,L;
	while(scanf("%I64d %I64d %I64d %I64d %I64d",&x,&y,&m,&n,&L)!=EOF)
	{
		x=x%L;
		y=y%L;
		__int64 a=n-m;
		__int64 b=L;
		__int64 c=x-y;
		if(a==0)
		{
			printf("Impossible\n");
			continue;
		}
		if(c<0)
		{
			c=-c;
			a=-a;
		}
		__int64 xx,yy,d;
		if(a>0)
		{
			exgcd(a,b,d,xx,yy);
			if(c%d!=0)
			{
				printf("Impossible\n");
				continue;
			}
			xx*=c/d;
			xx=xx%(b/d);
			if(xx<0)
				xx=b/d+xx;
			printf("%I64d\n",xx);
		
		}
		else
		{
			a=-a;
			exgcd(a,b,d,xx,yy);
			if(c%d!=0)
			{
				printf("Impossible\n");
				continue;
			}
			xx*=c/d;
			xx=xx%(b/d);
			if(xx>0)
				xx-=b/d;
			
			printf("%I64d\n",-xx);				
		
		}
	}
	//system("pause");
	return 0;
}

hdoj2588
题意:给出n、m,求1<=x<=n,且gcd(x,n)>=m的这样的x有多少个
思路来自网上。。悲剧,想不到啊,以下是自己的一些总结
假设k是n的约数且k>=m,并设b与n/k互质,那么b和n/k都乘上k之后,得到n与bk,他们的最大公约数是k>=m。这里用到的关键一点就是:如果a与b互质,那么a*t与b*t的最大公约数是t。
那么只要找出所有phi(n/k)就可以了。(k是>=m的n的约数),答案就是所有phi(n/k)之和。
一个问题:设b1是与n/k1互质的数,b2是与n/k2互质的数,是否可能b1k1、b2k2相等?如果可能的话,就会造成重复计算
答:其实是不可能的。因为b1与n/k1互质,所以b1k1与最大公约数为k1,同理:b2k2与最大公约数为k2
证:假设b1k1=b2k2。
(1) 如果b1=b2,因为k1、k2是n的不同的约数,所以b1k1!=b2k2。
(2) 如果b1!=b2。
假设k1>k2,那么显然b2k2的最大真约数是k1,而k1又是n的约约数,可见b2k2与n的最大公约数是k1,这与b2k2与n的最大公约数是k2矛盾。
k1

#include<stdio.h>
__int64 phi(__int64 n)
{
	__int64 ans = n;
	for(__int64 i = 2; i*i<= n; i++)
		if(n%i == 0)
		{
			ans = ans / i * (i-1);
			while(n%i == 0)
			{
				n /= i;
			}
		}
	if(n > 1)
		ans = ans / n *(n-1);
	return ans;
}
int main()
{
	int t,i,j;
	__int64 n,m;
	scanf("%d",&t);
	while(t–)
	{
		scanf("%I64d %I64d",&n,&m);
		if(m==1)
		{
			printf("%I64d\n",n);
			continue;
		
		}
		__int64 result=0;
		for(i=1;i*i<=n;i++)
		{
			if(n%i!=0) continue;
			if(i<m)
			{
				if(n/i>=m)
					result+=phi(i);
			}
			else if(i>=m)
			{
				result+=phi(n/i);
				if(n/i>=m && i*i!=n)
					result+=phi(i);
			
			}
		}
		
			
		printf("%I64d\n",result);


	}
	return 0;
}

hdoj1788
解模线性方程组

#include<stdio.h>
typedef __int64 ll;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
	if (!b) d=a,x=1,y=0;
	else
	{
		exgcd(b,a%b,d,y,x);y-=a/b*x;
	}
	return;
}
int main()
{
	int n,i,aa;
	while(scanf("%d %d",&n,&aa)!=EOF && !(n==0 && aa==0))
	{
		ll a1,r1,a2,r2;
		scanf("%I64d",&a1);
		r1=a1-aa;
		for(i=2;i<=n;i++)
		{
			scanf("%I64d",&a2);
			r2=a2-aa;
			ll a=a1,b=a2,c=r2-r1;
			ll d,x,y;
			exgcd(a,b,d,x,y);
			ll t=b/d;
			x=((x*c/d)%t+t)%t;
			r1=a1*x+r1;
			a1=a1/d*a2;
		}
		printf("%I64d\n",r1);
	}
	return 0;
}

hdoj1299
题意:对于1/x+1/y=1/n。(1<=x<=y,x、y为整数,n已知)。求满足方程的x、y有多少对。
尼玛。。。想不出来,看了别人思路。。罪过。。
思路:显然x>=n,y>=n。那么可以假设y=x+k。代入方程得到x=n+((n^2)/k)。那么显然必须(n^2)/k是整数。
则k必然是(n^2)的因子。解的个数其实就是k的个数。而且因为x<=y,所以k>=n,k的个数就是n^2的因子数,但是n^2可能达到2^18,很大。其实只要对n分解素因素即可,假设n分解后为n=p1^k1+p2^k2+……+pm^km.那么n的因子个数为(k1+1)(k2+1)……(km+1)。而n^2的因子个数很显然是(2*k1+1)(2*k2+1)……(2*km+1).那么满足k>=n的k的可能个数就是(ans+1)/2(为什么呢?因为因子是对称的嘛。。对于n^2来说,有一个小于n的因子k,必有一个大于n的因子(n^2)/k)

#include<stdio.h>
#include<string.h>
typedef __int64 ll;
const int N=1000000;
ll pr[N+10],p[(N+10)/10],lp;
void gp()
{
	for(ll i=2;i<=N;i++)
	{
		if(!pr[i]) p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
	return;
}
ll b[30],k[30];
int cnt;
void gn(ll n)
{
	int i;
	ll t;
	cnt=0;
	memset(k,0,sizeof(k));
	while(n>1)
	{
		if(n<=N)
		{
			t=pr[n];
		}
		else
		{
			t=n;
			for(i=1;i<=lp && p[i]<=n/p[i];i++)
				if(n%p[i]==0)
				{
					t=p[i];
					break;
				}
		}
		b[++cnt]=t;
		while(n%t==0)
		{
			n/=t;
			k[cnt]++;
		}
	}
	return;
}
int main()
{
	int t,cases=0;
	int i;
	gp();
	scanf("%d",&t);
	while(t--)
	{
		ll n;
		ll ans=1;
		scanf("%I64d",&n);
		gn(n);
		for(i=1;i<=cnt;i++)
			ans*=(2*k[i]+1);
		ans=(ans+1)/2;
		printf("Scenario #%d:\n%I64d\n\n",++cases,ans);
		
	}
	return 0;
}

hdoj1695
题意:给你两个区间[1,a],[1,b],问你两个区间各选一个整数x,y,gcd(x,y)=k的有多少对(无序对).
思路:gcd(x,y)=d,说明x/d、y/d互质。因为是无序的,所以先给定次序x<=y,问题转化为[1,a/d][1,b/d]两个区间各选x、y,满足x、y互质的对数有多少。设b=a/d,d=b/d,假设b是小区间,那么:
对于<=b的y,显然结果就是[1,b]每个数的欧拉函数值之和。
对于>b的y,要找到与y互质的且<=b的x有多少,这时欧拉函数失效了。可以用容斥求出[1,b]区间与y不互质的数有多少,然后b减去不互质的数的数量就是与y互质且<=b的x的数量。当然先要对y分解素因素。因为y<=10^5,所以可以预处理素数,log时间分解素因素。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef __int64 ll;
const int N=100000;
ll pr[N+10],p[N+10];
ll phi[N+10];
int cnt,lp;
void gp(){
	for(int i=2;i<=N;i++)
	{
		if(!pr[i]) p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
	return;
}
void oula()
{
	int i,j;
	for(i=1;i<=N;i++)
		phi[i]=i;
	for(i=1;i<=lp;i++)
	{
		for(j=p[i];j<=N;j+=p[i])
		{
			phi[j]=phi[j]/p[i]*(p[i]-1);
		}
	}
	return;
}
ll pi[30],ki[30];
void fenjie(int n)
{
	cnt=0;
	memset(ki,0,sizeof(ki));
	while(n!=1)
	{
		ll t=pr[n];
		pi[++cnt]=t;
		ki[cnt]=0;
		while(n%t==0)
		{
			n/=t;
			ki[cnt]++;
		}
	}
	return;
}
ll sum[N+10];
ll ans;
void dfs(int flag,int x,ll p,ll a)
{
	if(flag&1)
		ans+=a/p;
	else
		ans-=a/p;
	for(int i=x+1;i<=cnt;i++)
		dfs(flag+1,i,p*pi[i],a);
	return;
}
int main()
{
	int i,j;
	int t,cases=0;
	ll a,b,c,d,k;
	gp();
	oula();
	sum[1]=phi[1];
	for(i=2;i<=N;i++)
		sum[i]=sum[i-1]+phi[i];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%I64d %I64d %I64d %I64d %I64d",&a,&b,&c,&d,&k);
		if(k==0 || (k>b && k>d))
		{
			printf("Case %d: 0\n",++cases);
			continue;
		}
		a=b/k;b=d/k;
		if(a>b){a=a^b;b=a^b;a=a^b;}
		if(a==b)
		{
			printf("Case %d: %I64d\n",++cases,sum[b]);
			continue;
		}
		ll result=sum[a];
		for(i=a+1;i<=b;i++)
		{
			fenjie(i);
			ans=0;
			for(j=1;j<=cnt;j++)
				dfs(1,j,pi[j],a);
			ans=a-ans;
			result+=ans;
		}
		printf("Case %d: %I64d\n",++cases,result);
	}
	return 0;
}

Codeforces 264B (Good Sequences)
题意:给你序列a1,a2,a3,……,an。n<=10^5,1<=ai<=10^5,严格升序给出。要你求出任意相邻数不互质的严格升序子序列最大长度。
O(n^2)的dp是很好想到的,方程:dp[i]=max{dp[j]|1<=j 需要换一种dp的形式。可以用dp[i]表示以序列中含素因子i的最后一个数结尾的子序列最大长度,显然:每次读入一个数,他都可以加在含它的素因子的数结尾的子序列后面,所以每次读入a[i]的时候,只需找出含它的素因子的数结尾的最长长度,并在这个长度上+1根新他的素因子即可

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef __int64 ll;
const int N=100000;
int pr[N+10],p[N+10];
int cnt,lp;
int max(int a,int b)
{
	return a>b?a:b;
}
void gp(){
	for(int i=2;i<=N;i++)
	{
		if(!pr[i]) p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
	return;
}
void fenjie(int n,int *pp)
{
	cnt=0;
	while(n!=1)
	{
		int t=pr[n];
		pp[++cnt]=t;
		while(n%t==0)
			n/=t;
	}
	pp[0]=cnt;
	return;
}
int a[N+10],dp[N+10];
int pp[N+10][30];
int main()
{
	int i,j;
	int n;
	gp();
	for(i=2;i<=N;i++)
		fenjie(i,pp[i]);
	pp[1][0]=0;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==1)
		{
			scanf("%d",&a[1]);
			printf("1\n");
			continue;
		}
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]==1)
				continue;
			int tmp=-1;
			for(j=1;j<=pp[a[i]][0];j++)
			{
				tmp=max(tmp,dp[pp[a[i]][j]]);
			}
			for(j=1;j<=pp[a[i]][0];j++)
			{
				dp[pp[a[i]][j]]=tmp+1;
			}
		}
		int max=-1;
		for(i=2;i<=N;i++)
			if(dp[i]>max)
				max=dp[i];
		printf("%d\n",max);
	}


	return 0;
}

hdoj4483
好难,还没理清楚。。
先放上pick定理:pick定理:在一个平面直角坐标系内,以整点为顶点的简单多边形(任两边不交叉),它内部整点数为a,它的边上(包括顶点)的整点数为b,则它的面积S = a+b/2-1
pick定理及其证明
一个结论:对于长a,宽b的整点矩形,它的一条对角线上的整点数为gcd(a,b)-1

lca && rmq 专题

hdoj2586

    选一个根,lca的同时出每个点到根的距离,u,v间的距离是dist[u]+dist[v]-2*dist[anc];

小技巧:

    以前做过这道题,那个时候q[]数组开成int型的,然后开一个保存询问的结构体数组(struct{int u,v,anc;})然后每次回答一个询问,都要遍历一下该询问数组,看看对上哪一个询问,然后写入答案,这样效率不好(每次保存一个询问的答案要O(q),q是询问数)

  其实只需要把q数组开成node类型,node中记录该询问的id,这样每次解答了一个询问就可以O(1)时间写入一个一维数组ans[]。(ans[i]表示第i个询问的答案)

ps:题目中每个case后输出一个空行是骗人的~~~

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
#define maxn 40010
#define maxe 80010
#define maxm 210
using namespace std;
typedef struct Edge{
	int to;
	int w;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int cnt;
int bin[maxn];
bool visit[maxn];
typedef struct node{
	int to;
	int id;
}node;
int ans[maxm],dist[maxn];
vector<node> q[maxn];
void init(int n)
{
	int i;
	dist[0]=dist[1]=0;
	for(i=1;i<=n;i++)
		if(!q[i].empty())
			q[i].clear();
	cnt=0;
	memset(visit,0,sizeof(visit));
	memset(head,-1,sizeof(head));
	return;
}
void add(int a,int b,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=b;
	edge[cnt].next=head[a];
	head[a]=cnt++;
	return;
}
int find(int x)
{
	int r=x;
	while(bin[r]!=r)
		r=bin[r];
	int t=x,tmp;
	while(t!=r)
	{
		tmp=bin[t];
		bin[t]=r;
		t=tmp;
	}
	return r;
}
void merge(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		bin[fx]=fy;
	return;
}
void lca(int cur,int fa,int w)
{
	int i,j;
	dist[cur]=dist[fa]+w;
	bin[cur]=cur;
	visit[cur]=1;
	int d=q[cur].size();
	for(i=0;i<=d-1;i++)
	{
		int v=q[cur][i].to;
		if(visit[v])
		{
			int anc=find(v);
			ans[q[cur][i].id]=dist[cur]+dist[v]-2*dist[anc];
		}
	}
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		int w=edge[i].w;
		if(visit[v])
			continue;
		lca(v,cur,w);
		merge(v,cur);
	}
	return;
}
int main()
{
	int t;
	int i,j;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		int a,b,k;
		scanf("%d%d",&n,&m);
		init(n);
		for(i=1;i<=n-1;i++)
		{
			scanf("%d %d %d",&a,&b,&k);
			add(a,b,k);
			add(b,a,k);
		}
		for(i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d %d",&u,&v);
			node tmp;
			tmp.to=v;tmp.id=i;
			q[u].push_back(tmp);
			tmp.to=u;
			q[v].push_back(tmp);
		}
		lca(1,0,0);
		for(i=1;i<=m;i++)
			printf("%d\n",ans[i]);

	
	}



	//system("pause");
	return 0;
}

hdoj3078
题意:给你一棵树,每个顶点都有一个权值,然后给你两种操作,k a b,k=0的时候表示把a的权值变成b,k>0的时候表示求解a到b的路径上第k大的权值是多少。
朴素的深度比较法求lca即可,求解lca的同时记录途中经过的点的权值,排序一下即可,注意两个点相同时的处理。
粗粗估计一下平均情况时间复杂度:dfs标上深度:O(n),对于每个询问:O(logn+(logn)*(loglogn)),所以复杂度为O(n)-O(q*(logn+(logn)*(loglogn))),计算器算一下最坏情况下大概是4992786次运算(10^6级别),可以过。
如果数据变态,树是一条链,那么复杂度变成O(n)-O(q*(n+nlogn)),大概是10^10数量级的,那就悲催了。。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#define maxn 80010
#define maxe 170010
#define maxq 40010
using namespace std;
typedef struct Edge{
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int lay[maxn];
bool visit[maxn];
int cnt;
int fa[maxn],depth[maxn];
void dfs(int cur,int f,int dep)
{
	fa[cur]=f;
	visit[cur]=1;
	depth[cur]=dep+1;
	for(int i=head[cur];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(visit[v]) continue;
		dfs(v,cur,depth[cur]);
	}
	return;
}
void init()
{
	cnt=0;
	fa[1]=-1;
	memset(head,-1,sizeof(head));
	memset(visit,0,sizeof(visit));
	return;
}
bool cmp(int a,int b)
{
	return a>b;
}

void add(int u,int v)
{
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	return;
}
int lca(int u,int v,int k)
{
	if(u==v)
	{
		if(k==1)
			return lay[u];
		else
			return -1;
	}
	int i;
	int road[maxn];
	int iq=0;
	int x=u,y=v;
	while(x!=y)
	{
		if(depth[x]>depth[y])
		{
			road[++iq]=lay[x];
			x=fa[x];

		}
		else if(depth[y]>depth[x])
		{
			road[++iq]=lay[y];
			y=fa[y];

		}
		else
		{
			road[++iq]=lay[x];road[++iq]=lay[y];
			x=fa[x],y=fa[y];

		}
	}
	road[++iq]=lay[x];
	if(k<=0 || k>iq)
		return -1;
	sort(road+1,road+1+iq,cmp);
	return road[k];
}
int main()
{
	int i,j;
	int n,Q;
	scanf("%d %d",&n,&Q);
	init();
	for(i=1;i<=n;i++)
		scanf("%d",&lay[i]);
	for(i=1;i<=n-1;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dfs(1,-1,0);
	for(i=1;i<=Q;i++)
	{
		int k,a,b;
		scanf("%d %d %d",&k,&a,&b);
		if(k==0)
			lay[a]=b;
		else
		{
			int ans=lca(a,b,k);
			if(ans==-1)
				printf("invalid request!\n");
			else
				printf("%d\n",ans);

		}
	}
	//system("pause");
	return 0;
}

poj1470
简单的lca,注意输入格式,用getchar()就行,一个case结束前可能有空格,不要用getchar()处理掉这一行剩余字符,因为下一个case的n可能和前一个case的最后一行在同一行上。

#include<stdio.h>
#include<string.h>
#include<vector>
#define maxn 1000
#define maxq 300000
using namespace std;
typedef struct Edge{
	int to;
	int next;
}Edge;
Edge edge[maxn];
int head[maxn];
vector<int> q[maxq];
int time[maxn];
bool visit[maxn];
bool root[maxn];
int cnt;
int bin[maxn];
int find(int x)
{
	int r=x;
	while(r!=bin[r])
		r=bin[r];
	int t=x,tmp;
	while(t!=r)
	{
		tmp=bin[t];
		bin[t]=r;
		t=tmp;
	}
	return r;
}
void merge(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx!=fy)
		bin[fx]=fy;
	return;
}
void init(int n)
{
	cnt=0;
	int i;
	for(i=1;i<=n;i++)
		if(!q[i].empty())
			q[i].clear();
	memset(visit,0,sizeof(visit));
	memset(root,1,sizeof(root));
	memset(head,-1,sizeof(head));
	memset(time,0,sizeof(time));
	return;
}
void lca(int cur)
{
	int i;
	visit[cur]=1;
	bin[cur]=cur;
	int d=q[cur].size();
	for(i=0;i<=d-1;i++)
	{
		int v=q[cur][i];
		if(!visit[v]) continue;
		time[find(v)]++;
	}
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		lca(v);
		merge(v,cur);
	}
	return;
}
void add(int u,int v)
{
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	return;
}
void getdata()
{
	int p,num;
	scanf("%d",&p);
	char c;
	c=getchar();
	while(c!=':')
		c=getchar();
	c=getchar();
	while(c!='(')
		c=getchar();
	scanf("%d",&num);
	c=getchar();
	while(c!=')')
		c=getchar();
	for(int i=1;i<=num;i++)
	{
		int to;
		scanf("%d",&to);
		add(p,to);
		root[to]=0;
	}
	return;	
}
void getquery()
{
	int u,v;
	char c=getchar();
	while(c!='(')
		c=getchar();
	scanf("%d %d",&u,&v);
	c=getchar();
	while(c!=')')
		c=getchar();
	q[u].push_back(v);
	q[v].push_back(u);
	return;

}
int main()
{
	int n;
	int i,j;
	while(scanf("%d",&n)!=EOF)
	{
		init(n);

		for(i=1;i<=n;i++)
		{
			getdata();
		}
		int Q;
		scanf("%d",&Q);
		for(i=1;i<=Q;i++)
		{
			getquery();
		
		}
		for(i=1;i<=n;i++)
			if(root[i]==1)
				break;
		lca(i);
		for(i=1;i<=n;i++)
		{
			if(time[i]!=0)
				printf("%d:%d\n",i,time[i]);
		
		}
		
	}
	return 0;
}

poj2763
思路很清晰,但是无限WA中。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
#define maxn 400010
#define maxe 500010
#define maxq 400100
using namespace std;
typedef struct Edge{
	int to;
	int w;
	int next;
}Edge;
typedef struct node{
	int to;
	int id;
}node;
typedef struct Ans{
	int type;
	int now;
	int dest;
	int edge_id;
	int w;
	int anc;
}Ans;
typedef struct Sub{
	int begin,end;
}Sub;
Sub sub[maxn];
Ans ans[maxq];
Edge edge[maxe];
int head[maxn];
vector<node> q[maxn];
int visit[maxn];
int dist[maxn];
int bin[maxn];
int cnt;
int d[maxn];
int cc[maxn];
int n;
int lowbit(int x)
{
	return x & -x;

}
void add(int id,int x)
{
	for(int i=id;i<=n;i+=lowbit(i))
		cc[i]+=x;
	return;
}
int getsum(int x)
{
	int sum=0;
	for(int i=x;i>=1;i-=lowbit(i))
	{
		sum+=cc[i];

	}
	return sum;
}
int find(int x)
{
	int r=x;
	while(bin[r]!=r)
		r=bin[r];
	int t=x,tmp;
	while(t!=r)
	{
		tmp=bin[t];
		bin[t]=r;
		t=tmp;
	}
	return r;

}
void merge(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		bin[fx]=bin[fy];
	return;
}
void init()
{
	int i;
	cnt=0;
	dist[1]=0;
	for(i=1;i<=n;i++)
		if(!q[i].empty())
			q[i].clear();
	memset(head,-1,sizeof(head));
	memset(visit,0,sizeof(visit));
	memset(cc,0,sizeof(cc));
	memset(d,0,sizeof(d));
	return;
}
void dfs(int cur,int fa,int w)
{
	int i;
	sub[cur].begin=++cnt;
	visit[cur]=1;
	dist[cur]=dist[fa]+w;
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		int w=edge[i].w;
		if(!visit[v])
		{
			edge[i^1].w=-1;
			dfs(v,cur,w);
		}
	}
	sub[cur].end=cnt;
	return;

}
void lca(int cur)
{
	int i;
	bin[cur]=cur;
	visit[cur]=1;
	int d=q[cur].size();
	for(i=0;i<=d-1;i++)
	{
		int v=q[cur][i].to;
		int id=q[cur][i].id;
		if(!visit[v]) continue;
		ans[id].anc=find(v);
	
	}
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		if(edge[i].w<0) continue;
		int v=edge[i].to;
		if(visit[v]) continue;
		lca(v);
		merge(v,cur);
	
	}
	return;


}
void addedge(int u,int v,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	return;
}
int main()
{
	int Q,s;
	int i;
	while(scanf("%d %d %d",&n,&Q,&s)!=EOF)
	{
		init();
		int a,b,w;
		for(i=1;i<=n-1;i++)
		{
			scanf("%d %d %d",&a,&b,&w);
			addedge(a,b,w);
			addedge(b,a,w);
		}
		int com;
		int vex,num,neww;
		int pass=s;
		for(i=1;i<=Q;i++)
		{
			scanf("%d",&com);
			if(com==0)
			{
				scanf("%d",&vex);
				ans[i].type=com;
				ans[i].now=pass;
				ans[i].dest=vex;
				pass=vex;
				node tmp;
				tmp.to=ans[i].dest;tmp.id=i;
				q[ans[i].now].push_back(tmp);
				tmp.to=ans[i].now;
				q[ans[i].dest].push_back(tmp);
			}
			else
			{
				scanf("%d %d",&num,&neww);
				ans[i].type=com;
				ans[i].edge_id=num;
				ans[i].w=neww;
			}
		}
		cnt=0;
		dfs(1,1,0);
		memset(visit,0,sizeof(visit));
		lca(1);
		int aa[maxn];
		for(i=1;i<=n;i++)
		{
			int pos=sub[i].begin;
			aa[pos]=dist[i];
		}
		d[1]=aa[1];
		for(i=2;i<=n;i++)
			d[i]=aa[i]-aa[i-1];
		for(i=1;i<=n;i++)
		{
			add(i,d[i]);
		
		}
		
		for(i=1;i<=Q;i++)
		{
			int com=ans[i].type;
			if(com==0)
			{
				int anc=ans[i].anc;
				int u=ans[i].now;
				int v=ans[i].dest;
				int idu=sub[u].begin,idv=sub[v].begin,idanc=sub[anc].begin;
				dist[u]=getsum(idu);dist[v]=getsum(idv);dist[anc]=getsum(idanc);
				int ans=dist[u]+dist[v]-2*dist[anc];
		
				printf("%d\n",ans);
	
			}
			else
			{
				int w=ans[i].w;
				int id=ans[i].edge_id;
				id=(id-1)*2;
				id=edge[id].w>=0?id:id+1;
				int val=w-edge[id].w;
				int node=edge[id].to;
				int l=sub[node].begin,r=sub[node].end;
				add(l,val);add(r+1,-val);
			}
		}
	}

	return 0;
}

用在线倍增法改写了lca,还是wa。。待查

#include<stdio.h>
#include<string.h>
#define maxn 100011
#define maxj 20
typedef struct Edge{
	int to;
	int w;
	int next;
}Edge;
typedef struct Sub{
	int begin;
	int end;
}Sub;
Sub sub[maxn];
int head[maxn];
Edge edge[5*maxn];
int dep[maxn];
int f[maxn][maxj+5];
bool visit[maxn];
int dist[maxn];
int n;
int cnt;
int d[maxn],c[maxn];
int lowbit(int x)
{
	return x & -x;
}
void add(int id,int x)
{
	for(int i=id;i<=n;i+=lowbit(i))
		c[i]+=x;
	return;
}
int getsum(int x)
{
	int sum=0;
	for(int i=x;i>=1;i-=lowbit(i))
		sum+=c[i];
	return sum;
}
void addedge(int u,int v,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	return;
}
void init()
{
	cnt=0;
	dep[1]=0;
	dist[1]=0;
	memset(visit,0,sizeof(visit));
	memset(head,-1,sizeof(head));
	memset(f,1,sizeof(f));
	memset(c,0,sizeof(c));
	return;
}
void dfs(int cur,int fa,int w)
{
	int i,j;
	sub[cur].begin=++cnt;
	visit[cur]=1;
	dep[cur]=dep[fa]+1;
	dist[cur]=dist[fa]+w;
	f[cur][0]=fa;
	for(j=1;j<=maxj;j++)
		f[cur][j]=f[f[cur][j-1]][j-1];
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		int w=edge[i].w;
		if(visit[v]) continue;
		edge[i^1].w=-1;
		dfs(v,cur,w);
	}
	sub[cur].end=cnt;
	return;
}
int lca(int a,int b)
{
	int i;
	if(a==b)
		return a;
	if(dep[a]<dep[b])
	{
		a=a^b;b=a^b;a=a^b;
	}
	int cha=dep[a]-dep[b];
	for(i=0;(1<<i)<=cha;i++)
		if(cha & (1<<i))
			a=f[a][i];
	if(a!=b)
	{
		for(i=maxj;i>=0;i--)
		{
			if(f[a][i]!=f[b][i])
			{
				a=f[a][i];b=f[b][i];
			}
		}
		a=f[a][0],b=f[b][0];
	}
	return a;
}
int main()
{
	int q,s;
	int i,j;
	while(scanf("%d %d %d",&n,&q,&s)!=EOF)
	{
		init();
		for(i=1;i<=n-1;i++)
		{
			int a,b,w;
			scanf("%d %d %d",&a,&b,&w);
			addedge(a,b,w);
			addedge(b,a,w);
		
		}
		cnt=0;
		dfs(1,1,0);
		int a[maxn];
		for(i=1;i<=n;i++)
			a[sub[i].begin]=dist[i];
		d[1]=a[1];
		for(i=2;i<=n;i++)
			d[i]=a[i]-a[i-1];
		for(i=1;i<=n;i++)
			add(i,d[i]);
		for(i=1;i<=q;i++)
		{
			int com;
			scanf("%d",&com);
			if(com==1)
			{
				int id,w;
				scanf("%d %d",&id,&w);
				id=2*(id-1);
				id=edge[id].w<0?id+1:id;
				int node=edge[id].to;
				int l=sub[node].begin,r=sub[node].end;
				int val=w-edge[id].w;
				add(l,val);add(r+1,-val);
			}
			else
			{
				int dest;
				scanf("%d",&dest);
				int anc=lca(s,dest);
				dist[s]=getsum(sub[s].begin);
				dist[dest]=getsum(sub[dest].begin);
				dist[anc]=getsum(sub[anc].begin);
				int ans=dist[s]+dist[dest]-2*dist[anc];
				printf("%d\n",ans);
				s=dest;
			}
		}
	}


return 0;
}

hdoj2888
裸的二维rmq,顺便写个模板,其实原理和一维rmq一样,理解了一维的话,可以很快写出二维的来

#include<stdio.h>
#include<math.h>
#define maxn 310
#define maxm 310
int n,m;
int f[maxn][9][maxm][9];
int map[maxn][maxm];
int log2[maxn+maxm+20];
int cal_log2(int x)
{
	return log((double)x)/(log(2.0));
}
int max(int a,int b)
{
	return a>b?a:b;
}
void init()
{
	int x,y,i,j;


	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			f[i][0][j][0]=map[i][j];
	for(i=0;i<=log2[n];i++)
		for(j=0;j<=log2[m];j++)
		{
			if(i==0 && j==0) continue;
			for(x=1;x+(1<<i)-1<=n;x++)
				for(y=1;y+(1<<j)-1<=m;y++)
				{
					if(i==0)
						f[x][0][y][j]=max(f[x][0][y][j-1],f[x][0][y+(1<<(j-1))][j-1]);
					else if(j==0)
						f[x][i][y][0]=max(f[x][i-1][y][0],f[x+(1<<(i-1))][i-1][y][0]);
					else
						f[x][i][y][j]=max(max(f[x][i-1][y][j-1],f[x+(1<<(i-1))][i-1][y+(1<<(j-1))][j-1]),max(f[x][i-1][y+(1<<(j-1))][j-1],f[x+(1<<(i-1))][i-1][y][j-1]));		
				}
		}
	return;
}
int query(int upleft_x,int upleft_y,int bottomright_x,int bottomright_y)
{
	int x1=upleft_x,x2=bottomright_x;
	int y1=upleft_y,y2=bottomright_y;
	if(x1>x2){x1=x1^x2;x2=x1^x2;x1=x1^x2;y1=y1^y2;y2=y1^y2;y1=y1^y2;}
	if(y1>y2){x1=x1^x2;x2=x1^x2;x1=x1^x2;y1=y1^y2;y2=y1^y2;y1=y1^y2;}
	
	int ki=log2[x2-x1+1],kj=log2[y2-y1+1];
	return max(max(f[x1][ki][y1][kj],f[x2-(1<<ki)+1][ki][y2-(1<<kj)+1][kj]),max(f[x1][ki][y2-(1<<kj)+1][kj],f[x2-(1<<ki)+1][ki][y1][kj]));
}
int main()
{
	int i,j;
	for(i=1;i<=310;i++)
		log2[i]=cal_log2(i);
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				scanf("%d",&map[i][j]);
		init();
		int q;
		scanf("%d",&q);
		for(i=1;i<=q;i++)
		{
			int r1,c1,r2,c2;
			scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
			int ans=query(r1,c1,r2,c2);
			printf("%d ",ans);
			int num1=map[r1][c1],num2=map[r1][c2],num3=map[r2][c1],num4=map[r2][c2];
			if(num1==ans || num2==ans || num3==ans ||num4==ans)
				printf("yes\n");
			else
				printf("no\n");
		}
	}
	return 0;
}

hdoj2874
询问森林中两点是否连通,若连通则最短距离是多少。
思路:关键一点是添加虚拟根结点,如果两个点的lca是这个虚拟根结点,那这两点肯定在两棵树中。
哈哈,这道题我嫌lca-tarjan太麻烦,于是学了下lca的在线倍增算法,开心。
注意重边的情况,当然测试数据中没有重边,因为我的代码没有考虑重边也AC了。如果有重边的话,是会WA的。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 10010
#define maxj 15//开成log2(maxn)大小
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
Edge edge[4*maxn];
int head[maxn];
bool visit[maxn];
int f[maxn][maxj+5];
int dep[maxn];
int dist[maxn];
int bin[maxn];
int n,cnt;
int find(int x)
{
	int r=x;
	while(r!=bin[r])
		r=bin[r];
	int t=x,tmp;
	while(t!=r)
	{
		tmp=bin[t];
		bin[t]=r;
		t=tmp;
	}
	return r;
}
void merge(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		bin[fx]=fy;
	return;

}
void init()
{
	cnt=0;
	dep[1]=1;
	memset(head,-1,sizeof(head));
	memset(visit,0,sizeof(visit));
	memset(f,n+1,sizeof(f));
	for(int i=1;i<=n;i++)
		bin[i]=i;
	return;

}
void init_dfs(int cur,int fa)
{
	int i;
	visit[cur]=1;
	merge(cur,fa);
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(!visit[v])
			init_dfs(v,cur);
	
	}
	return;
}
void dfs(int cur,int fa,int w)//f[i][j]的求解可以用dfs也可以两层for循环搞定
{
	int i,j;
	visit[cur]=1;
	dep[cur]=dep[fa]+1;
	dist[cur]=dist[fa]+w;
	f[cur][0]=fa;
	for(j=1;j<=maxj;j++)
		f[cur][j]=f[f[cur][j-1]][j-1];
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		int w=edge[i].w;
		if(visit[v]) continue;
		dfs(v,cur,w);
	}
	return;
}
int lca(int u,int v)
{
	int i;
	if(dep[u]<dep[v])
	{
		u=u^v;v=u^v;u=u^v;
	}
	int cha=dep[u]-dep[v];
	for(i=0;(1<<i)<=cha;i++)//不是用每次u上升1的方法来使u到达v所在层,而是以2的i次方上升,直到上升cha,效率高
		if(cha & (1<<i))
			u=f[u][i];
	if(u!=v)
	{
		for(i=maxj;i>=0;i--)
			if(f[u][i]!=f[v][i])
			{
				u=f[u][i];
				v=f[v][i];
			}
		u=f[u][0],v=f[v][0];
	}
	return u;

}
void add(int u,int v,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	return;

}
int main()
{
	int m,q;
	int i,j;
	while(scanf("%d %d %d",&n,&m,&q)!=EOF)
	{
		init();
		for(i=1;i<=m;i++)
		{
			int a,b,w;
			scanf("%d%d%d",&a,&b,&w);
			add(a,b,w);
			add(b,a,w);
		}
		for(i=1;i<=n;i++)
			init_dfs(i,i);
		for(i=1;i<=n;i++)
		{
			if(bin[i]==i)
				add(n+1,i,0);
		}
		n=n+1;
		memset(visit,0,sizeof(visit));
		dfs(n,n,0);
		for(i=1;i<=q;i++)
		{
			int u,v;
			scanf("%d %d",&u,&v);
			int ans=lca(u,v);
			if(ans==n)
				printf("Not connected\n");
			else
				printf("%d\n",dist[u]+dist[v]-2*dist[ans]);
		
		}

	
	
	}
	return 0;
}

hdoj3830
这题真心没看出来是lca。。。无奈看了网上的解题报告,发现原来这么巧妙
关键在于要想到一点:对于任意状态a,b,c;经过合法操作”两侧向内翻”最终一定对应一个状态x,y,z;其中x=y=z,此时无法由两侧元素向内翻转。所以可以把这个稳定状态看成根。那么显然这是一棵二叉树。
判断两个状态是否可以相互得到只要判断两者的根状态是否相同即可。
如果根相同,那么只要将两个状态调到同一深度(深度大的往小的调),然后用二分法求解lca,步数=2*深度较小的状态与lca深度差+两个状态深度差。

#include<stdio.h>
#include<stdlib.h>
typedef struct State{
	__int64 x,y,z;
	__int64 d;
}State;
void adj(State& s)
{
	__int64 t;
	if(s.x>s.y)
	{
		t=s.x;s.x=s.y;s.y=t;
	}
	if(s.y>s.z)
	{
		t=s.y;s.y=s.z;s.z=t;
	}
	if(s.x>s.y)
	{
		t=s.x;s.x=s.y;s.y=t;
	
	}
	return;
}
bool equ(State a,State b)
{
	return a.x==b.x && a.y==b.y && a.z==b.z;


}
State Root(State& s)
{

	s.d=0;
	State root;root.x=s.x;root.y=s.y;root.z=s.z;root.d=s.d;
	__int64 p=root.y-root.x,q=root.z-root.y;
	__int64 t;
	while(p!=q)
	{
		if(p<q)
		{

			t=(q-1)/p;//t表示向内翻转的次数
			__int64 t1=t/2,t2=t-t1;//t1表示y动了几次,t2表示x动了几次
			t1*=2;t2*=2;
			root.x+=t2*p;
			root.y+=t1*p;
		}
		else
		{
			t=(p-1)/q;
			__int64 t1=t/2,t2=t-t1;
			t1*=2;t2*=2;
			root.y-=t1*q;
			root.z-=t2*q;
		}
		adj(root);
		s.d+=t;
		p=root.y-root.x;q=root.z-root.y;
	}
	return root;
}
State up(State s,__int64 setup)
{
	__int64 p=s.y-s.x,q=s.z-s.y;
	State tmp;tmp.x=s.x;tmp.y=s.y;tmp.z=s.z;tmp.d=s.d;
	__int64 t;
	while(setup>0)
	{
		if(p<q)
		{

			t=(q-1)/p;
			if(t>setup) t=setup;
			__int64 t1=t/2,t2=t-t1;
			t1*=2;t2*=2;
			tmp.x+=t2*p;
			tmp.y+=t1*p;
		}
		else
		{
			t=(p-1)/q;
			if(t>setup) t=setup;			
			__int64 t1=t/2,t2=t-t1;
			t1*=2;t2*=2;
			tmp.y-=t1*q;
			tmp.z-=t2*q;
		
		}
		adj(tmp);
		p=tmp.y-tmp.x;q=tmp.z-tmp.y;
		setup-=t;
	}
	return tmp;
}
int main()
{
	__int64 a,b,c,x,y,z;
	while(scanf("%I64d %I64d %I64d %I64d %I64d %I64d",&a,&b,&c,&x,&y,&z)!=EOF)
	{
		State begin,end;
		begin.x=a;begin.y=b;begin.z=c;
		end.x=x;end.y=y;end.z=z;
		adj(begin);adj(end);
		State root1=Root(begin);
		State root2=Root(end);
		if(!equ(root1,root2))
			printf("NO\n");
		else
		{
			__int64 d1=begin.d,d2=end.d;
			__int64 cha=0;
			if(d1>d2)
			{
				cha=d1-d2;
				begin=up(begin,cha);
			}
			else if(d1<d2)
			{
				cha=d2-d1;
				end=up(end,cha);
			}
			__int64 mid,l=0,r=d1>d2?d2:d1;
			while(l<=r)
			{
				mid=(l+r)/2;
				if(equ(up(begin,mid),up(end,mid)))
					r=mid-1;
				else
					l=mid+1;
			}
			printf("YES\n%I64d\n",2*l+cha);
		
		
		
		
		}
	
	}



//system("pause");
return 0;
}

hdoj3183
题意:给出一个长度为n的整数(n<=1000,不含前导0),让你去掉m(m<=n)个数字,使新形成的整数最小。(不能该改变原次序)
思路:
1.贪心可解,每次去掉从高位到低位第一个后面相邻的数字比它小的数字,具体思路请百度(希望不要百度。。)
2.rmq解法:
去掉m个数字可以看成取n-m个数字。那么取的第一个数字一定在区间[1,m+1],为什么呢?是 想[m+2,n]一共多少数字呢,显然是n-m-1个,如果第一个数字是在[m+2,n]上,那么如论如 何也取不出n-m个数字,因为第二个取的数字一定在第一个之后,而[m+2,n]一共只有n-m-1个数字。
继续想,那么取的第二个数字一定在区间[x+1,m+2],其中x是取的第一个数字在数组中的位置。为什么呢?思考下吧
注意:
1.写st算法的时候要用结构体,不然不知道对应的最小值的下标
2.在比较函数min里面<要改成<=,也就是说两部分最小值相等时,要选前面那部分的最小值,这样才能给后面留出尽量大的可选区间

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define maxn 1000+10
char a[maxn];
int b[maxn];
int n;
typedef struct Node{
    int v;
    int pos;
}Node;
Node f[maxn][20];
Node min(Node a,Node b)
{
    return a.v<=b.v?a:b;
}
int log2(int x)
{
    return log10((double)x)/log10(2.0);
}
void init()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        f[i][0].v=a[i]-’0′;
        f[i][0].pos=i;
    }
    for(j=1;(1<<j)<=n;j++)
        for(i=1;i+(1<<j)-1<=n;i++)
        {
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    return;
}
Node query(int l,int r)
{
    int k=log2(r-l+1);
    return min(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
    int m,i;
    while(scanf("%s %d",a,&m)!=EOF)
    {
        getchar();
        n=strlen(a);
        for(i=n;i>=1;i–)
            a[i]=a[i-1];
        init();
        int t=n-m;
        int l=1,r=m+1;
        for(i=1;i<=t;i++)
        {
            Node x=query(l,r);
            b[i]=x.v;
            l=x.pos+1;
            r++;
        }
        int cur;
        for(cur=1;cur<=t;cur++)
            if(b[cur]!=0)
                break;
        if(cur>t)
        {
            printf("0\n");
            continue;
        }
        for(i=cur;i<=t;i++)
            printf("%d",b[i]);
        printf("\n");
    }
    return 0;
}

hdoj部分最短路题

hdoj1245
简单题,spfa二维最短路,也可以用dij来做,注意:如果用spfa来做,那么开始建图的时候,对于距离>d的两个点不要连边,如果这里连了而在松弛的时候判断w与d的关系会超时。
这里其他点到起点不用连边,因为显然不会回到源点(如果中途回到原点再到其他点何不开始时就直接到那个点呢,对吧),因为图中边权均为正的,所以不用判环,算法一定可以结束。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<queue>
#define maxn 110
#define maxe 50000
#define inf 1.0e10
#define eps 1.0e-6
using namespace std;
typedef struct Edge{
	double w;
	int to;
	int next;
}Edge;
typedef struct Point{
	double x,y;
}Point;
typedef struct node{
	int p;
	int num;
}node;
Point p[maxn];
Edge edge[maxe];
int head[maxn];
int inque[maxn][maxn];
double dist[maxn][maxn];
int n;
double d;
int cnt;
double max(double a,double b)
{
	return a>b?a:b;
}
void spfa(int s)
{
	int i,j;
	queue<node> q;
	memset(inque,0,sizeof(inque));
	for(i=0;i<=n+1;i++)
		for(j=0;j<=n+1;j++)
		dist[i][j]=inf;
	dist[s][0]=0;
	inque[s][0]=1;
	node sr;sr.p=s;sr.num=0;
	q.push(sr);
	while(!q.empty())
	{
		int u=q.front().p,num=q.front().num;q.pop();
		inque[u][num]=0;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			double w=edge[i].w;
			if(dist[u][num]+w+eps<dist[v][num+1])
			{
				dist[v][num+1]=dist[u][num]+w;
				if(!inque[v][num+1])
				{
					inque[v][num+1]=1;
					node tmp;tmp.p=v;tmp.num=num+1;
					q.push(tmp);
				
				}
			
			}
		
		}

	}
	return;
}
void init()
{
	memset(head,-1,sizeof(head));
	cnt=0;
	p[0].x=p[0].y=0.0;
	return;

}
void add(int u,int v,double w)
{
	int i;
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	return;
}

double cal_dist(Point a,Point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}
double to_bank(Point a)
{
	double tmp=max(fabs(a.x),fabs(a.y));
	return 50.0-tmp;

}
int main()
{
	int i,j;
	while(scanf("%d %lf",&n,&d)!=EOF)
	{
		init();
		double w;
		for(i=1;i<=n;i++)
		{
			scanf("%lf %lf",&p[i].x,&p[i].y);
		}
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				if(i==j)
					continue;
				w=cal_dist(p[i],p[j]);
				if(w>d)
					continue;
				add(i,j,w);
				add(j,i,w);
			}
		for(i=1;i<=n;i++)
		{
			w=cal_dist(p[0],p[i])-15.0/2.0;
			if(w>d)
				continue;
			add(0,i,w);
		}
		for(i=1;i<=n;i++)
		{
			w=to_bank(p[i]);
			if(w>d)
				continue;
			add(i,n+1,w);
		}
		w=50.0-15.0/2.0;
		if(w-eps<d)
			add(0,n+1,w);

		spfa(0);
		double ans=inf;
		int num=0;
		for(i=1;i<=n+1;i++)
			if(dist[n+1][i]+eps<ans)
			{
				ans=dist[n+1][i];
				num=i;
			}
		if(ans>inf-eps)
			printf("can't be saved\n");
		else
			printf("%.2lf %d\n",ans,num);



	}
	system("pause");
	return 0;
}

呵呵,好吧,又看了下题目,好像自己做复杂了。。直接spfa求下最短路就行了,spfa是bellman ford的优化,考察bellman ford可以发现,如果存在多条最短路,bellman ford总是会先找到经过顶点少的那个。举一反三,如果要求经过结点最多的那条最短路,那么只要松弛的时候,dist[u]+w<=dist[v]则更新就行了,其实很好理解

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<queue>
#define maxn 110
#define maxe 50000
#define inf 1.0e10
#define eps 1.0e-6
using namespace std;
typedef struct Edge{
    double w;
    int to;
    int next;
}Edge;
typedef struct Point{
    double x,y;
}Point;
typedef struct node{
    int p;
    int num;
}node;
Point p[maxn];
Edge edge[maxe];
int head[maxn];
int inque[maxn];
double dist[maxn];
int pre[maxn];
int n;
double d;
int cnt;
double max(double a,double b)
{
    return a>b?a:b;
}
void spfa(int s)
{
    int i,j;
    queue<int> q;
    memset(inque,0,sizeof(inque));
	memset(pre,-1,sizeof(pre));
    for(i=0;i<=n+1;i++)
        dist[i]=inf;
    dist[s]=0;
    inque[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        inque[u]=0;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            double w=edge[i].w;
            if(dist[u]+w+eps<dist[v])
            {
                dist[v]=dist[u]+w;
				pre[v]=u;
                if(!inque[v])
                {
                    inque[v]=1;
                    q.push(v);
                
                }
            
            }
        
        }

    }
    return;
}
void init()
{
    memset(head,-1,sizeof(head));
    cnt=0;
    p[0].x=p[0].y=0.0;
    return;

}
void add(int u,int v,double w)
{
    int i;
    edge[cnt].w=w;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}

double cal_dist(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}
double to_bank(Point a)
{
    double tmp=max(fabs(a.x),fabs(a.y));
    return 50.0-tmp;

}
int main()
{
    int i,j;
    while(scanf("%d %lf",&n,&d)!=EOF)
    {
        init();
        double w;
        for(i=1;i<=n;i++)
        {
            scanf("%lf %lf",&p[i].x,&p[i].y);
        }
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(i==j)
                    continue;
                w=cal_dist(p[i],p[j]);
                if(w>d)
                    continue;
                add(i,j,w);
                add(j,i,w);
            }
        for(i=1;i<=n;i++)
        {
            w=cal_dist(p[0],p[i])-15.0/2.0;
            if(w>d)
                continue;
            add(0,i,w);
        }
        bool flag=0;
        for(i=1;i<=n;i++)
        {
            w=to_bank(p[i]);
            if(w>d)
                continue;
            add(i,n+1,w);
            flag=1;
        }
        if(!flag)
        {
            printf("can’t be saved\n");
            continue;
        }

        w=50.0-15.0/2.0;
        if(w-eps<d)
            add(0,n+1,w);

        spfa(0);
		int num=0;
		int x=n+1;
		while(pre[x]!=-1)
		{
			x=pre[x];
			num++;
		
		}
        double ans=inf;
        if(dist[n+1]+eps<ans)
			ans=dist[n+1];
        if(ans>inf-eps)
            printf("can’t be saved\n");
        else
            printf("%.2lf %d\n",ans,num);



    }
	//system("pause");
    return 0;
}

关于spfa快速找环

注意一点:在找环前务必保证从原点出发可达任一点。(spfa只能判断出从源点可达的环)

记下要点,详细论证见《spfa的优化及应用》一文

1.无论使用bfs的spfa还是dfs的spfa,如果只是找环,可以把dist全部初始化为0,这样要快很多

2.对于bfs的spfa,当元素进入队列的总次数超过T*(M+N)时,就判断图中存在正环。T可以根据题目特点自由选取,一般取2。(这是一个非常重要的流氓优化)

3.有些题目可以用outque[u]>(int)sqrt((doubel)*(1.0*n))水过去。。

4.使用dfs的spfa找环非常高效。

Johnson算法介绍

   鉴于大家对Johnson算法了解不多,而且Johnson的预处理正需要SPFA,所以这里作简要介绍。

  Johnson算法主要用于求稀疏图上的全源最短路径。其主体思想是利用重赋 权值的方法把一个原问题带负权的图转化为权值非负的图。然后再使用N次Dijkstra算法以求出全源最短路。

  下面先介绍其重赋权值的主体步骤:

  1. 增设一点S,由S往各点连一条权值为0的边。

   2. 使用SPFA求出S到各点I的最短路径h(i)。

  3. 对于每条边w(u,v),将其重赋权为w’(u,v)=w(u,v)+h(u)-h(v)。  这一步的最坏理论时间复杂度为O(NM)。那么这样赋值以后会产生什么效果呢?

  对于任意一对点(s,t)的任意一条路径s,x1,x2,….xk,t,其原路径长度为

  f(s,t)=w(s,x1)+w(x1,x2)+……+w(xk,t)  而重赋值后,其路径长度为  f’(s,t)=h(s)+w(s,x1)-h(x1)+h(x1)+w(x1,x2)-h(x2)+……+h(xk)+w(xk,t)-h(t) = h(s)+w(s,x1)+w(x1,x2)+……+w(xk,t)-h(t) =h(s)+f(s,t)-h(t) 

则显然其最短路径f’(s,t)= fminmin(s,t)+h(s)-h(t)。h(s)-h(t)为定值,由此得出重赋权值后不会改变原图的最短路径。

  其次,由于h(i)是S到i的最短路径,由三角不等式知,对于每条边w(u,v)有,h(u)+w(u,v)>=h(v),即w(u,v) +h(u)-h(v)>=0,w’(u,v)>=0,由此知转化后的图权值非负。

  这样我们就把问题转化为在一非负权图上求全源最短路径,可以很方便地使用Dijkstra算法进行求解。 

差分约束专题

希望读者把思路和代码先当成空气,不到万不得已不要看思路,代码最好不要看,可以用来对拍。
首先,对于a-b>=w建模:b->(w)->a
一句经典的话:最短路求出的是最大解,最长路求出的是最小解。
因为求最短路时dist赋的初值是inf,它在松弛变小过程中,一旦满足约束条件就退出,所以是最大值,最长路的情况也是一个道理。(注意,这里的最大值最小值是相对inf和-inf而言的,数学上,差分约束的解是没有最大值和最小值的)
关于求dist[1]和dist[n]之间差最大。
其实我认为求最短路和求最长路都能解决这个问题,对于最短路,新建超级源点,向每个点连边,权0。这相当于增加约束条件dist[i]<=0,因为dist[i]初始化为inf,所以不断松弛直到dist[i]<=0,这是求出的是差距最小的。求最长路的过程也可以这样分析。


hdoj1384
给你一些闭区间[ai,bi],0<=ai<=bi<=50000,以及ci,表示区间[ai,bi]上至少有ci个整数,求满足这些条件的整数最少是几个。
第一次做差分约束,对约束条件思考不全面,sum[i]表示小于i的整数个数,那么必须满足约束条件:
sum[bi+1]-sum[ai]>=ci
sum[i+1]-sum[i]>=0
sum[i]-sum[i+1]>=-1(sum[i+1]-sum[i]<=1)
设超级源点,到每个点连边,权为0,这样相当于增加了约束条件sum[i]>=0,这样求最长路求出来的必然全>=0.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#define maxn 50010
#define maxe 5000100
#define inf 1000000000
using namespace std;
typedef struct Edge{
	int to;
	int w;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
bool inque[maxn];
int dist[maxn];
int n,m;
void spfa(int s)
{
	int i;
	queue<int> q;
	memset(inque,0,sizeof(inque));
	for(i=0;i<=n;i++)
		dist[i]=-inf;
	dist[s]=0;
	inque[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		inque[u]=0;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int w=edge[i].w;
			if(dist[u]+w>dist[v])
			{
				dist[v]=dist[u]+w;
				if(!inque[v])
				{
					inque[v]=1;
					q.push(v);
				}
			}
		}
	}
	return;
}
int main()
{
	int i,j;
	while(scanf("%d",&m)!=EOF)
	{
		memset(head,-1,sizeof(head));
		int a,b,c;
		int cnt=0;
		int max=-1;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&c);
			if(b+1>max)
				max=b+1;
			edge[cnt].w=c;
			edge[cnt].to=b+1;
			edge[cnt].next=head[a];
			head[a]=cnt++;
		}
		for(i=1;i<=max;i++)
		{
			edge[cnt].w=0;
			edge[cnt].to=i;
			edge[cnt].next=head[i-1];
			head[i-1]=cnt++;

			edge[cnt].w=-1;
			edge[cnt].to=i-1;
			edge[cnt].next=head[i];
			head[i]=cnt++;
		}
		for(i=0;i<=max;i++)
		{
			edge[cnt].w=0;
			edge[cnt].to=i;
			edge[cnt].next=head[max+1];
			head[max+1]=cnt++;
		}
		n=max+1;
		spfa(max+1);
		printf("%d\n",dist[max]);
	
	
	
	
	}
	return 0;
}

hdoj3592
简单的差分约束,根据题意间不等式即可

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<string.h>
#define maxn 1010
#define maxe 6000000
#define inf 1000000000
using namespace std;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int outque[maxn];
int inque[maxn];
int dist[maxn];
int n;
bool spfa(int s)
{
	int i;
	memset(inque,0,sizeof(inque));
	memset(outque,0,sizeof(outque));
	queue<int> q;
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	inque[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		inque[u]=0;
		outque[u]++;
		if(outque[u]>n-1) return false;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int w=edge[i].w;
			if(dist[u]+w<dist[v])
			{
				dist[v]=dist[u]+w;
				if(!inque[v])
				{
					inque[v]=1;
					q.push(v);
				}
			}
		
		}
	}

	return true;
}
int main()
{	
	int t;
	int i;
	scanf("%d",&t);
	while(t--)
	{
		int x,y;
		int cnt=0;
		memset(head,-1,sizeof(head));
		scanf("%d %d %d",&n,&x,&y);
		for(i=2;i<=n;i++)
		{
			edge[cnt].w=0;
			edge[cnt].to=i-1;
			edge[cnt].next=head[i];
			head[i]=cnt++;
		
		}
		for(i=1;i<=x;i++)
		{
			int a,b,c;
			scanf("%d %d %d",&a,&b,&c);
			edge[cnt].w=c;
			edge[cnt].to=b;
			edge[cnt].next=head[a];
			head[a]=cnt++;

		}
		for(i=1;i<=y;i++)
		{
			int a,b,c;
			scanf("%d %d %d",&a,&b,&c);
			edge[cnt].w=-c;
			edge[cnt].to=a;
			edge[cnt].next=head[b];
			head[b]=cnt++;
		}
		if(spfa(1))
		{
			if(dist[n]>=inf)
				printf("-2\n");
			else
				printf("%d\n",dist[n]);
		
		}
		else
			printf("-1\n");



	}
	//system("pause");
	return 0;
}

poj1716
依然是整数区间问题,还是那句话,不等式要找齐全,这里有三种不等式组。

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<string.h>
#define maxn 10010
#define maxe 6000000
#define inf 2000000000
using namespace std;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int outque[maxn];
int inque[maxn];
int dist[maxn];
int n;
bool spfa(int s)
{
	int i;
	memset(inque,0,sizeof(inque));
	memset(outque,0,sizeof(outque));
	queue<int> q;
	for(i=0;i<=n;i++)
		dist[i]=-inf;
	dist[s]=0;
	inque[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		inque[u]=0;
		outque[u]++;
		if(outque[u]>n-1) return false;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int w=edge[i].w;
			if(dist[u]+w>dist[v])
			{
				dist[v]=dist[u]+w;
				if(!inque[v])
				{
					inque[v]=1;
					q.push(v);
				}
			}
		
		}
	}

	return true;
}
int main()
{
	int i;
	while(scanf("%d",&n)!=EOF)
	{
		int a,b;
		int cnt=0;
		memset(head,-1,sizeof(head));
		int max=-1;
		for(i=1;i<=n;i++)
		{
			scanf("%d %d",&a,&b);
			if(b>max)
				max=b;
			edge[cnt].w=2;
			edge[cnt].to=b+1;
			edge[cnt].next=head[a];
			head[a]=cnt++;
		}
		max++;
		for(i=1;i<=max;i++)
		{
			edge[cnt].w=-1;
			edge[cnt].to=i-1;
			edge[cnt].next=head[i];
			head[i]=cnt++;
		}
		for(i=0;i<=max-1;i++)
		{
			edge[cnt].w=0;
			edge[cnt].to=i+1;
			edge[cnt].next=head[i];
			head[i]=cnt++;
		
		}
		for(i=0;i<=max;i++)
		{
			edge[cnt].w=0;
			edge[cnt].to=i;
			edge[cnt].next=head[max+1];
			head[max+1]=cnt++;
		}
		n=max+1;
		spfa(max+1);
		printf("%d\n",dist[max]);


	}
	//system("pause");
	return 0;
}

poj2949
题意:给你一些单词,如果单词a的后两个字母和单词b的前两个字母相同,那么b可以接在a的后面,给你的单词中很可能形成一个环(可以一个单词形成自环)。求出平均长度最小的环。如果不存在环,输出No solution.
思路:将两个字母抽象成一个状态(顶点),如果一个单词以’aa’开始,以’ab’结束,那么两个顶点间连一条有向边,权为单词长度。题目转化为求有向图的平均权值最小的正环。有经典的二分法,还可以用专门的Karp算法(不懂。。)
poj提交了几十次,终于c++A了,G++居然是WA。。(补充:G++终于也ac了,原来在G++中最好用%f而不是%lf..)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 1000+10
#define maxe 5000000
#define inf 1e10
#define eps 1.0e-6
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int hash[maxn];
int outque[maxn];
int inque[maxn];
double dist[maxn];
int q[100000000];
int map[maxn][maxn];
int n,m,cnt;
bool spfa(int s,double mid)
{
	int i,j;
	int iq=0;
	memset(outque,0,sizeof(outque));
	memset(inque,0,sizeof(inque));
	for(i=0;i<=n;i++)
		dist[i]=-inf;
	dist[s]=0;
	inque[s]=1;
	q[iq++]=s;
	for(i=0;i<=iq-1;i++)
	{
		int u=q[i];
		inque[u]=0;
		outque[u]++;
		if(outque[u]>n) return false;
		for(j=head[u];j!=-1;j=edge[j].next)
		{
			int v=edge[j].to;
			double w=(double)edge[j].w-mid;
			if(dist[u]+w>dist[v])
			{
				dist[v]=dist[u]+w;
				if(!inque[v])
				{
					inque[v]=1;
					q[iq++]=v;
				}
			
			}
		
			
		}
	
	
	}

return true;

}
void addedge(int u,int v,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	return;
}
int main()
{
	int m;
	int i,j;
	char str[1010];
	while(scanf("%d",&m)!=EOF && m!=0)
	{
		getchar();
		memset(head,-1,sizeof(head));
		memset(hash,0,sizeof(hash));
		for(i=0;i<=1000;i++)
			for(j=0;j<=1000;j++)
				map[i][j]=0;
		int count=0;
		cnt=0;
		double max=-1,min=inf;
		n=0;
		for(i=1;i<=m;i++)
		{
			scanf("%s",str);
			getchar();
			int len=strlen(str);
			if(len<2)
			{
				count++;
				continue;
			}
			int u=(str[0]-'a'+1)*27+(str[1]-'a'+1);
			int v=(str[len-2]-'a'+1)*27+(str[len-1]-'a'+1);
			if(!hash[u])
				hash[u]=++n;
			if(!hash[v])
				hash[v]=++n;
			if(len>map[hash[u]][hash[v]])
				map[hash[u]][hash[v]]=len;//重要优化,不然TLE。如果有重边,保留长的那条
			if((double)len<min)
				min=(double)len;
			if((double)len>max)
				max=(double)len;

		}
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				if(map[i][j])
				{
					addedge(i,j,map[i][j]);
				}
			
			}
		for(i=1;i<=n;i++)
		{
			addedge(0,i,0);
		
		
		}
		hash[0]=0;
		if(count==m)
		{
			printf("No solution.\n");
			continue;
		}
		
		if(spfa(0,0))
			printf("No solution.\n");
		else
		{
			double l=min,r=max,mid;
			while(r-l>eps)
			{
				mid=(l+r)/2;
				if(spfa(0,mid))
					r=mid;
				else
					l=mid;
			}
			printf("%.2lf\n",l-0.005);
		
		
		
		}
			

	
	
	
	}



	//system("pause");
	return 0;
}

用dfs版本的spfa判环会使效率飙升到300多MS。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 1000+10
#define maxe 5000000
#define inf 1e10
#define eps 1.0e-6
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int hash[maxn];
double dist[maxn];
int map[maxn][maxn];
int n,m,cnt;
bool in[maxn],flag;
void init()
{
	int i;
	flag=0;
	memset(in,0,sizeof(in));
	for(i=0;i<=n;i++)
		dist[i]=0;
	return;

}
void spfa(int u,double mid)
{
	int i;
	in[u]=1;
	for(i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		double w=(double)edge[i].w-mid;
		if(dist[u]+w>dist[v])
		{
			dist[v]=dist[u]+w;
			if(in[v])
			{
				flag=1;
				return;
			}
			else
				spfa(v,mid);
			if(flag) return;
		}

	}
	in[u]=0;
	return;

}
bool judge(double mid)
{
	for(int i=1;i<=n;i++)
	{
		spfa(i,mid);
		if(flag)
			return 1;
	}
	return 0;
}
void addedge(int u,int v,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	return;
}
int main()
{
	int m;
	int i,j;
	char str[1010];
	while(scanf("%d",&m)!=EOF && m!=0)
	{
		getchar();
		memset(head,-1,sizeof(head));
		memset(hash,0,sizeof(hash));
		for(i=0;i<=1000;i++)
			for(j=0;j<=1000;j++)
				map[i][j]=0;
		int count=0;
		cnt=0;
		double max=-1,min=inf;
		n=0;
		for(i=1;i<=m;i++)
		{
			scanf("%s",str);
			getchar();
			int len=strlen(str);
			if(len<2)
			{
				count++;
				continue;
			}
			int u=(str[0]-'a'+1)*27+(str[1]-'a'+1);
			int v=(str[len-2]-'a'+1)*27+(str[len-1]-'a'+1);
			if(!hash[u])
				hash[u]=++n;
			if(!hash[v])
				hash[v]=++n;
			if(len>map[hash[u]][hash[v]])
				map[hash[u]][hash[v]]=len;
			if((double)len<min)
				min=(double)len;
			if((double)len>max)
				max=(double)len;

		}
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				if(map[i][j])
				{
					addedge(i,j,map[i][j]);
				}
			
			}

		hash[0]=0;
		if(count==m)
		{
			printf("No solution.\n");
			continue;
		}
		init();
		if(!judge(0))
			printf("No solution.\n");
		else
		{
			double l=min,r=max,mid;
			while(r-l>eps)
			{
				mid=(l+r)/2;
				init();
				if(!judge(mid))
					r=mid;
				else
					l=mid;
			}
			printf("%.2f\n",l);
		
		
		
		}
			

	
	
	
	}




	return 0;
}

hdoj3666
题意:给你一个矩阵,以及两个数组a[1……n],b[1……m]。要求所有map[i][j]*a[i]/b[j]之后其值在[L,U]区间,求解这样的a数组和b数组是否存在。
思路:不等式是乘除形式的,取对数转化成加减形式即可
数据比较水,用出队次数>sqrt(nn)来判断是否有负环,否则TLE

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<string.h>
#include<math.h>
#define maxn 2000
#define maxe 6000000
#define inf 1.0e10
#define eps 1.0e-6
using namespace std;
typedef struct Edge{
	double w;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int outque[maxn];
int inque[maxn];
double dist[maxn];
int nn;
bool spfa(int s)
{
	int i;
	memset(inque,0,sizeof(inque));
	memset(outque,0,sizeof(outque));
	queue<int> q;
	for(i=1;i<=nn;i++)
		dist[i]=inf;
	dist[s]=0;
	inque[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		inque[u]=0;
		outque[u]++;
		if(outque[u]>(double)(sqrt(1.0*nn))) return false;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			double w=edge[i].w;
			if(dist[u]+w-dist[v]<=0)
			{
				dist[v]=dist[u]+w;
				if(!inque[v])
				{
					inque[v]=1;
					q.push(v);
				}
			}
		
		}
	}

	return true;
}
double map[500][500];
int main()
{
	int i,j;
	int n,m;
	double l,u;
	while(scanf("%d %d %lf %lf",&n,&m,&l,&u)!=EOF)
	{
		l=log10(l);
		u=log10(u);
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				scanf("%lf",&map[i][j]);
				map[i][j]=log10(map[i][j]);
			
			}
		int cnt=0;
		memset(head,-1,sizeof(head));
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				int uu=i;
				int vv=j+n;
				double tmpu=u-map[i][j],tmpl=l-map[i][j];
				edge[cnt].w=tmpu;
				edge[cnt].to=uu;
				edge[cnt].next=head[vv];
				head[vv]=cnt++;

				edge[cnt].w=-tmpl;
				edge[cnt].to=vv;
				edge[cnt].next=head[uu];
				head[uu]=cnt++;
			}
			/*
		for(i=1;i<=n+m;i++)
		{
			edge[cnt].w=0;
			edge[cnt].to=i;
			edge[cnt].next=head[0];
			head[0]=cnt++;
		}
		*/
		nn=n+m;
		if(spfa(1))
			printf("YES\n");
		else
			printf("NO\n");
	}

	//system("pause");
	return 0;
}

poj2983
还是区间判合法问题,对于确定性的约束条件a-b=x可以分成a-b>=x和a-b<=x两个不等式

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<string.h>
#define maxn 1010
#define maxe 1000000
#define inf 100000
using namespace std;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dist[maxn];
int outque[maxn];
int inque[maxn];
int n,m,cnt;
bool spfa(int s)
{
	int i;
	queue<int> q;
	memset(outque,0,sizeof(outque));
	memset(inque,0,sizeof(inque));
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	inque[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		inque[u]=0;
		outque[u]++;
		if(outque[u]>n) return false;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int w=edge[i].w;
			if(dist[u]+w<dist[v])
			{
				dist[v]=dist[u]+w;
				if(!inque[v])
				{
					inque[v]=1;
					q.push(v);
				}
			}
		
		
		}	
	
	}

return true;

}
void add(int u,int v,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	return;
}
int main()
{
	int i,j;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		getchar();
		cnt=0;
		memset(head,-1,sizeof(head));
		char com;
		for(i=1;i<=m;i++)
		{
			scanf("%c",&com);
			if(com==’P')
			{
				int a,b,x;
				scanf("%d %d %d",&a,&b,&x);
				getchar();
				add(b,a,x);
				add(a,b,-x);
			
			}
			else
			{
				int a,b;
				scanf("%d %d",&a,&b);
				getchar();
				add(a,b,-1);
			}
		}
		for(i=1;i<=n;i++)
			add(0,i,0);
		if(spfa(0))
			printf("Reliable\n");
		else
			printf("Unreliable\n");
	
	
	
	}

	//system("pause");
	return 0;
}

poj3159
题意不说了,很明确,要求dist[1]和dist[n]之差最大,题目保证差分约束方程组一定有解。
思路:因为要之差最大,所以求最短路。附加超级源点0,o到点2——n引边,边权都为inf,源点0向点1引边,边权为0,这样求出的dist[u]-dist[1]是最大的
注意:这题卡spfa,用堆优化的dij即可

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<string.h>
#define maxn 30000+10
#define maxe 1500000+10
#define inf 1000000000
using namespace std;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dist[maxn];
bool visit[maxn];
int n,m,cnt;
typedef struct node{
	int p;
	int dist;
	bool operator <(const node & a) const
	{
		return dist>a.dist;
	}
}node;
void dij(int s)
{
	int i;
	memset(visit,0,sizeof(visit));
	priority_queue<node> q;
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	node sr;
	sr.p=s;sr.dist=0;
	q.push(sr);
	while(!q.empty())
	{
		int u=q.top().p;q.pop();
		if(visit[u]) continue;
		visit[u]=1;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int w=edge[i].w;
			if(dist[u]+w<dist[v])
			{
				dist[v]=dist[u]+w;
				node tmp;
				tmp.p=v;tmp.dist=dist[v];
				q.push(tmp);
			}
		
		}
	
	
	
	}
	return;
}
void add(int u,int v,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	return;
}
int main()
{
	int i;
	scanf("%d %d",&n,&m);
	cnt=0;
	memset(head,-1,sizeof(head));
	for(i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		add(a,b,c);
	}
	for(i=2;i<=n;i++)
		add(0,i,inf);
	add(0,1,0);
	dij(0);
	printf("%d\n",dist[n]-dist[1]);
	

	//system("pause");
	return 0;
}

poj3169
水题,区间问题

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<string.h>
#define maxn 1000+10
#define maxe 500000
#define inf 1000000000
using namespace std;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dist[maxn];
int outque[maxn];
int inque[maxn];
int n,m;
int cnt;
bool spfa(int s)
{
	int i;
	queue<int> q;
	memset(outque,0,sizeof(outque));
	memset(inque,0,sizeof(inque));
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	inque[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		inque[u]=0;
		outque[u]++;
		if(outque[u]>n-1) return false;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int w=edge[i].w;
			if(dist[u]+w<dist[v])
			{
				dist[v]=dist[u]+w;
				if(!inque[v])
				{
					inque[v]=1;
					q.push(v);
				}
			}
		
		}
	
	
	}

return true;
}
void add(int u,int v,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	return;
}
int main()
{
	int m1,m2;
	int i,j;
	while(scanf("%d %d %d",&n,&m1,&m2)!=EOF)
	{
		int a,b,d;
		cnt=0;
		memset(head,-1,sizeof(head));
		for(i=1;i<=m1;i++)
		{
			scanf("%d %d %d",&a,&b,&d);
			add(a,b,d);

		
		}
		for(i=1;i<=m2;i++)
		{
			scanf("%d %d %d",&a,&b,&d);
			add(b,a,-d);
		}
		for(i=2;i<=n;i++)
			add(i,i-1,0);
		if(spfa(1))
		{
			if(dist[n]>=inf)
				printf("-2\n");
			else
				printf("%d\n",dist[n]);
		
		}
		else
			printf("-1\n");

	}
//system("pause");
return 0;
}

hdoj4274
好题,先求出欧拉序列,然后就是普通的区间差分约束了。注意读题,每个结点>=1.
用队列的spfa会TLE,所幸数据比较水,if(outque[u]>(int)sqrt(1.0*(n+1))) return false;可以水过。。dfs版的spfa应该可以过,没试过。。

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<math.h>
#include<string.h>
#define maxn 10000+10
#define maxe 70000+10
#define inf 1000000000
using namespace std;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dist[maxn];
int outque[maxn];
int inque[maxn];
int n,m;
int cnt;
bool spfa(int s)
{
	int i;
	queue<int> q;
	memset(outque,0,sizeof(outque));
	memset(inque,0,sizeof(inque));
	for(i=1;i<=n+1;i++)
		dist[i]=inf;
	dist[s]=0;
	inque[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		inque[u]=0;
		outque[u]++;
		if(outque[u]>(int)sqrt(1.0*(n+1))) return false;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int w=edge[i].w;
			if(dist[u]+w<dist[v])
			{
				dist[v]=dist[u]+w;
				if(!inque[v])
				{
					inque[v]=1;
					q.push(v);
				}
			}
		
		}
	
	
	}

return true;
}
void add(int u,int v,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	return;
}
Edge edge2[maxn];
int head2[maxn];
typedef struct Sub{
	int begin;
	int end;
}Sub;
Sub sub[maxn];
void dfs(int cur)
{
	sub[cur].begin=++cnt;
	for(int i=head2[cur];i!=-1;i=edge2[i].next)
	{
		int v=edge2[i].to;
		dfs(v);
	}
	sub[cur].end=cnt;
	return;
}
int main()
{
	int i,j;
	while(scanf("%d",&n)!=EOF)
	{
		memset(head,-1,sizeof(head));
		memset(head2,-1,sizeof(head2));
		cnt=0;
		for(i=2;i<=n;i++)
		{
			int fa;
			scanf("%d",&fa);
			edge2[cnt].to=i;
			edge2[cnt].next=head2[fa];
			head2[fa]=cnt++;
		}
		cnt=0;
		dfs(1);
		cnt=0;
		char c;
		int a,w;
		scanf("%d",&m);
		for(i=1;i<=m;i++)
		{
			scanf("%d %c %d",&a,&c,&w);
			int u=sub[a].begin;
			int v=sub[a].end;
			if(c=='<')
			{
				add(u,v+1,w-1);
			
			}
			else if(c=='>')
			{
				add(v+1,u,-(w+1));
			}
			else
			{
				add(u,v+1,w);
				add(v+1,u,-w);
			}
		}
		for(i=2;i<=n+1;i++)
		{
			add(i,i-1,-1);
		
		}
		for(i=1;i<=n+1;i++)
			add(0,i,0);

		if(spfa(0))
			printf("True\n");
		else
			printf("Lie\n");
	
	
	}
//system("pause");
return 0;
}

集训队热身赛3——小结

认真对待每场比赛,及时总结
   √  10 / 26     Problem A     HUST 1607     Problem A        Triangles

        7 / 22       Problem B     HUST 1608     Problem B    Dating With Girls

        4 / 44       Problem C     HUST 1609     Problem C      AntiVirus

                         Problem D     HUST 1610     Problem D     CardGame

  √  15 / 23      Problem E     HUST 1611     Problem E   The mell hell

       5 / 18        Problem F     HUST 1612     Problem F      A new tree game

       0 / 1          Problem G     HUST 1613     Problem G    Minimum Planar Graph

  √  15 / 50      Problem H     HUST 1614     Problem H      Little Sheep and a paper

   √ 14 / 38      Problem I     HUST 1615     Problem I      Matrix

       4 / 27       Problem J     HUST 1616     Problem J     Lexicographically Maximum Subsequence

                        Problem K     HUST 1617     Problem K    GluLookAt and hidden point elimination

太累了,先说下比赛时情况,总结明天再写。

A           hash好题,需要特殊处理平行情况

B          本质最长路,点权转成边权,删去一些边,spfa求最长路即可(时间不够,这道大水题没做出来,对不住队友啊)

C        ac自动机或者Trie图,主串很长,比赛时没想到解决方法。。

D       没看过

E       排序,队友A的,虽然不明白排序的规则为什么是那样,但是感觉很吊。。。

F       听队友说是树的删边博弈,虽然他也不会。。   

G      没看。。

H    推推题,想了好久,终于被我找到递推式(折了好多纸),小问题折磨了一个多小时,gets改成scanf,ac(ps:个人感觉这题不算简单吧。。为毛全场都过了。。(场外的孩子有人找题解?!。。难道真的是我太笨了==!))

I       没看,队友A的   

J      没看

K      没看

很多题目没看,好吧,本队是跟风队,只能A别人AC了的题。。hdu_casual前进———

________________________明日待续___________________