[Dr.Lib]Note:Data Structures – 数据结构那些事

树状数组

[Dr.Lib]Note:Algorithms – 树状数组
树状数组是个简单高效的数据结构，实质上是省掉一半空间后的线段树加上中序遍历{Via ZKW《统计的力量》}

一般情况下，他可以做到单点更新，区间求和。

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include <cstring>
using namespace std;
int c[100020]={0},n=0,tmp=0,i=1,p=0,q=0,m=0;
inline int lowbit(int x){
    return x&(-x);
}
int sum(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void upd(int x,int v){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
    cin>>n;
    while(i<=n){cin>>tmp;upd(i,tmp);++i;}
    cin>>m;
    while(m--){
    	cin>>tmp;
		if(tmp==2){cin>>p>>q;cout<<(sum(q)-sum(p-1))<<endl;}
        else{cin>>p>>q;upd(p,q);}
    }
    return 0;
}

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include <cstring>

using namespace std;

int c[100020]={0},n=0,tmp=0,i=1,p=0,q=0,m=0;

inline int lowbit(int x){

return x&(-x);

}

int sum(int x){

int sum=0;

while(x>0){

sum+=c[x];

x-=lowbit(x);

}

return sum;

}

void upd(int x,int v){

while(x<=n){

c[x]+=v;

x+=lowbit(x);

}

int main()

{

cin>>n;

while(i<=n){cin>>tmp;upd(i,tmp);++i;}

cin>>m;

while(m--){

cin>>tmp;

if(tmp==2){cin>>p>>q;cout<<(sum(q)-sum(p-1))<<endl;}

else{cin>>p>>q;upd(p,q);}

}

return 0;

}

小小的差分一下，就可以做到区间更新单点值

http://wikioi.com/problem/1081/

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include <cstring>
using namespace std;
int c[100020]={0},n=0,tmp=0,i=1,p=0,q=0,r=0,m=0;
inline int lowbit(int x){
    return x&(-x);
}
int sum(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void upd(int x,int v){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
	cin>>n;
    int pre=0;
    while(i<=n){cin>>tmp;upd(i,tmp-pre);++i;pre=tmp;}
    cin>>m;
    while(m--){
    	cin>>tmp;
		if(tmp==2){cin>>p;cout<<sum(p)<<endl;}
        else{cin>>p>>q>>r;upd(p,r);upd(q+1,-r);}
    }
    return 0;

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include <cstring>

using namespace std;

int c[100020]={0},n=0,tmp=0,i=1,p=0,q=0,r=0,m=0;

inline int lowbit(int x){

return x&(-x);

}

int sum(int x){

int sum=0;

while(x>0){

sum+=c[x];

x-=lowbit(x);

}

return sum;

}

void upd(int x,int v){

while(x<=n){

c[x]+=v;

x+=lowbit(x);

}

int main()

{

cin>>n;

int pre=0;

while(i<=n){cin>>tmp;upd(i,tmp-pre);++i;pre=tmp;}

cin>>m;

while(m--){

cin>>tmp;

if(tmp==2){cin>>p;cout<<sum(p)<<endl;}

else{cin>>p>>q>>r;upd(p,r);upd(q+1,-r);}

}

return 0;

问题是区间更新区间和呢？

只能上线段树了吗？

NO！

http://wikioi.com/problem/1082/

#include<iostream>
#include<algorithm>
#include<cstring>
#include <cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
#define MAXN 200020
int n,q;
int l,r,k,x;
long long c[MAXN],s[MAXN],t[MAXN];
inline int lowbit(int x){return x&(-x);}
long long ssum(int x){
    long long ans=0;
    while(x>0){
        ans+=s[x];
        x-=lowbit(x);
    }
    return ans;
}
long long tsum(int x){
    long long ans=0;
    while(x>0){
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
void sadd(int xx,long long val){while(xx<=n)s[xx]+=val,xx+=lowbit(xx);}
void tadd(int xx,long long val){while(xx<=n)t[xx]+=val,xx+=lowbit(xx);}
int main(){
    memset(c,0,sizeof(c));
    memset(s,0,sizeof(s));
    memset(t,0,sizeof(t));
    scanf("%d",&n);
    for (int i=a;i<=b;i++) scanf("%d",&x),c[i]=c[i-1]+x;
    scanf("%d",&q);
    while(q--){
        scanf("%d%d%d",&x,&l,&r);
        if(x==1){
            scanf("%d",&k);
            sadd(l,k);sadd(r+1,-k);
            tadd(l,(l-1)*k);tadd(r+1,-r*k);
        }else{
           printf("%lld\n",((c[r]-c[l-1])+(1-l)*ssum(l)+r*ssum(r)-(tsum(r)-tsum(l))));
        }
    }
    return 0;
}

#include<iostream>

#include<algorithm>

#include<cstring>

#include <cstdio>

#include<cstdlib>

#include<vector>

using namespace std;

#define MAXN 200020

int n,q;

int l,r,k,x;

long long c[MAXN],s[MAXN],t[MAXN];

inline int lowbit(int x){return x&(-x);}

long long ssum(int x){

long long ans=0;

while(x>0){

ans+=s[x];

x-=lowbit(x);

}

return ans;

}

long long tsum(int x){

long long ans=0;

while(x>0){

ans+=t[x];

x-=lowbit(x);

}

return ans;

}

void sadd(int xx,long long val){while(xx<=n)s[xx]+=val,xx+=lowbit(xx);}

void tadd(int xx,long long val){while(xx<=n)t[xx]+=val,xx+=lowbit(xx);}

int main(){

memset(c,0,sizeof(c));

memset(s,0,sizeof(s));

memset(t,0,sizeof(t));

scanf("%d",&n);

for (int i=a;i<=b;i++) scanf("%d",&x),c[i]=c[i-1]+x;

scanf("%d",&q);

while(q--){

scanf("%d%d%d",&x,&l,&r);

if(x==1){

scanf("%d",&k);

sadd(l,k);sadd(r+1,-k);

tadd(l,(l-1)*k);tadd(r+1,-r*k);

}else{

printf("%lld\n",((c[r]-c[l-1])+(1-l)*ssum(l)+r*ssum(r)-(tsum(r)-tsum(l))));

}

return 0;

}

朴素线段树

[Dr.Lib]Note:Algorithms – 线段树

*计算几何在长期的发展中，
诞生了许多实用的数据结构。

*区间查询，穿刺查询都是计算几何解决的问题

*作为特例中的特例，线段树解决的问题是：

*一维空间上的几何统计

Via 《统计的力量》

线段树（Segment Tree）是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

对于线段树中的每一个非叶子节点[a,b]，它的左子树表示的区间为[a,(a+b)/2]，右子树表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树。叶节点数目为N，即整个线段区间的长度。

http://wikioi.com/problem/1191

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m;
int ls[800100];
int rs[800100];
int ts[800100];
void build(int l,int r,int p) {
	ls[p]=l;
	rs[p]=r;
	ts[p]=1;
	if(l<r) {
		build(l,((l+r)>>1),(p<<1));
		build(((l+r)>>1)+1,r,(p<<1)+1);
	}
	if(l!=r)
	ts[p]=ts[p<<1]+ts[(p<<1)+1];
}
void inst(int l,int r,int p){if(ts[p]){
	if(l<=ls[p]&&rs[p]<=r){ts[p]=0;return;}
	if(ls[p]==rs[p])return;
	if(!(l>rs[p<<1]||r<ls[p<<1])){inst(l,r,(p<<1));}
	if(!(l>rs[(p<<1)+1]||r<ls[(p<<1)+1])){inst(l,r,(p<<1)+1);}
	ts[p]=ts[p<<1]+ts[(p<<1)+1];
}}

int main() {
    int lp,rp;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&lp,&rp);
        inst(lp,rp,1);
        printf("%d\n",ts[1]);
    }
    return 0;
}

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

int n,m;

int ls[800100];

int rs[800100];

int ts[800100];

void build(int l,int r,int p) {

ls[p]=l;

rs[p]=r;

ts[p]=1;

if(l<r) {

build(l,((l+r)>>1),(p<<1));

build(((l+r)>>1)+1,r,(p<<1)+1);

}

if(l!=r)

ts[p]=ts[p<<1]+ts[(p<<1)+1];

}

void inst(int l,int r,int p){if(ts[p]){

if(l<=ls[p]&&rs[p]<=r){ts[p]=0;return;}

if(ls[p]==rs[p])return;

if(!(l>rs[p<<1]||r<ls[p<<1])){inst(l,r,(p<<1));}

if(!(l>rs[(p<<1)+1]||r<ls[(p<<1)+1])){inst(l,r,(p<<1)+1);}

ts[p]=ts[p<<1]+ts[(p<<1)+1];

}}

int main() {

int lp,rp;

scanf("%d%d",&n,&m);

build(1,n,1);

for(int i=1;i<=m;i++)

{

scanf("%d%d",&lp,&rp);

inst(lp,rp,1);

printf("%d\n",ts[1]);

}

return 0;

}

ZKW线段树

参见《统计的力量》

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define N 50005
bool U[4*N];
int T[4*N],M;
void update(int n,int V){
	n+=M;
	T[n]=V;U[n]=1;
	for(n>>=1;n;n>>=1){
	T[n]=T[n<<1]+T[(n<<1)+1];U[n]=1;}
}
int query(int ss,int tt){
	int ans=0;
	for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;ss>>=1,tt>>=1) {
		if (~ss&1) ans=+T[ss^1];
		if ( tt&1) ans=+T[tt^1];
	}
	return ans;
}
int n,s,t,k;
int main (){
	cin>>n;
	for(M=1;M<=n+1;M*=2);
	while(n--){
		cin>>k>>s>>t;
		if(k)
		update(s,t);
		else
		cout<<query(s,t)<<endl;
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define N 50005

bool U[4*N];

int T[4*N],M;

void update(int n,int V){

n+=M;

T[n]=V;U[n]=1;

for(n>>=1;n;n>>=1){

T[n]=T[n<<1]+T[(n<<1)+1];U[n]=1;}

}

int query(int ss,int tt){

int ans=0;

for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;ss>>=1,tt>>=1) {

if (~ss&1) ans=+T[ss^1];

if ( tt&1) ans=+T[tt^1];

}

return ans;

}

int n,s,t,k;

int main (){

cin>>n;

for(M=1;M<=n+1;M*=2);

while(n--){

cin>>k>>s>>t;

if(k)

update(s,t);

else

cout<<query(s,t)<<endl;

}

return 0;

}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define N 50005
bool U[4*N];
int T[4*N],S[4*N],M;
int count(int n){
	int h=1;
	while((n<<=1)<(M*2))h<<=1;
	return h;
}
int query(int ss,int tt){//查询[ss,tt]
	int ans=0,tlc=0,trc=0;
	for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;) {
		if (~ss&1){ans+=T[ss^1];tlc+=count(ss^1);}//左端点是左孩子
		if ( tt&1){ans+=T[tt^1];trc+=count(tt^1);}//右端点是右孩子 
		ss>>=1;tt>>=1;
		ans+=tlc*S[ss]+trc*S[tt];
	}
	for (ss >>= 1;ss > 0; ss >>= 1) {  
        ans += S[ss]*(tlc+trc);  
    }
	return ans;
}
void inc(int ss,int tt,int vv){//[ss,tt]全部加上一个数
	int tlc=0,trc=0;
	for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;) {
		if (~ss&1){S[ss^1]+=vv;T[ss^1]+=vv*count(ss^1);tlc+=count(ss^1);}//左端点是左孩子 
		if ( tt&1){S[tt^1]+=vv;T[tt^1]+=vv*count(tt^1);trc+=count(tt^1);}//右端点是右孩子
		ss>>=1;tt>>=1;
		T[ss]+=tlc*vv;T[tt]+=trc*vv;
	}
	for (ss >>= 1;ss > 0; ss >>= 1) {  
		T[ss] += vv*(tlc+trc);  
	}
}
void update(int n,int V){//置[n,n]为V [problem spec
	int per=query(n,n);
	inc(n,n,-per);
	inc(n,n,V);
}
int n,s,t,k;
int main (){
	cin>>n;
    for(M=1;M<=n+1;M*=2);
	while(1){
		cin>>k>>s>>t;
		if(k==2)
		{cin>>k;inc(s,t,k);}
		else if(k==1)
		update(s,t);
		else if(k==0)
		cout<<query(s,t)<<endl;
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define N 50005

bool U[4*N];

int T[4*N],S[4*N],M;

int count(int n){

int h=1;

while((n<<=1)<(M*2))h<<=1;

return h;

}

int query(int ss,int tt){//查询[ss,tt]

int ans=0,tlc=0,trc=0;

for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;) {

if (~ss&1){ans+=T[ss^1];tlc+=count(ss^1);}//左端点是左孩子

if ( tt&1){ans+=T[tt^1];trc+=count(tt^1);}//右端点是右孩子

ss>>=1;tt>>=1;

ans+=tlc*S[ss]+trc*S[tt];

}

for (ss >>= 1;ss > 0; ss >>= 1) {

ans += S[ss]*(tlc+trc);

}

return ans;

}

void inc(int ss,int tt,int vv){//[ss,tt]全部加上一个数

int tlc=0,trc=0;

for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;) {

if (~ss&1){S[ss^1]+=vv;T[ss^1]+=vv*count(ss^1);tlc+=count(ss^1);}//左端点是左孩子

if ( tt&1){S[tt^1]+=vv;T[tt^1]+=vv*count(tt^1);trc+=count(tt^1);}//右端点是右孩子

ss>>=1;tt>>=1;

T[ss]+=tlc*vv;T[tt]+=trc*vv;

}

for (ss >>= 1;ss > 0; ss >>= 1) {

T[ss] += vv*(tlc+trc);

}

void update(int n,int V){//置[n,n]为V [problem spec

int per=query(n,n);

inc(n,n,-per);

inc(n,n,V);

}

int n,s,t,k;

int main (){

cin>>n;

for(M=1;M<=n+1;M*=2);

while(1){

cin>>k>>s>>t;

if(k==2)

{cin>>k;inc(s,t,k);}

else if(k==1)

update(s,t);

else if(k==0)

cout<<query(s,t)<<endl;

}

return 0;

}

[Dr.Lib]Note:Math – 欧拉函数

正在纠结要不要码一篇欧拉函数……IvyEnd神犇的大作就已经出炉了……

Via http://www.ivy-end.com/archives/1021

欧拉函数\(\varphi \left ( N \right )\)表示小于或等于\(N\)的正整数中与\(N\)互质的数的个数。又称\(\varphi\)函数、欧拉商数。

下面介绍欧拉函数的几个性质：

\(\displaystyle\varphi\left ( 1 \right )=1\)。
\(\displaystyle\varphi \left( N\right )=N\cdot\prod_{p\mid N}\left ( \frac{p-1}{p} \right )\)。
\(\displaystyle\varphi \left ( p^{k} \right ) = p^{k}-p^{k-1}=\left(p-1 \right )\cdot p^{k-1}\)，其中\(p\)为质数。
\(\displaystyle\varphi \left(mn \right )=\varphi \left(m \right )\cdot \varphi \left(n \right )\)，其中\(\gcd \left ( m,n \right )=1\)。

我们根据这几个性质就可以求出欧拉函数。

基本思路是首先置\(\varphi \left ( N \right )=N\)，然后再枚举素数\(p\)，将\(p\)的整数倍的欧拉函数\(\varphi \left ( kp \right )\)进行操作\(\varphi \left ( kp \right )=\varphi \left ( kp \right )\cdot \frac{p-1}{p}\)即可。

#include <iostream>
using namespace std;
const int MAX = 1024;
int N;
int p[MAX], phi[MAX];

int main()
{
    cin >> N;
    for(int i = 1; i <= N; i++)    // 初始化
    { p[i] = 1; phi[i] = i; }
    p[1] = 0;    // 1不是素数
    for(int i = 2; i <= N; i++)    // 筛素数
    {
        if(p[i])
        {
            for(int j = i * i; j <= N; j += i)
            { p[j] = 0; }
        }
    }
    for(int i = 2; i <= N; i++)    // 求欧拉函数
    {
        if(p[i])
        {
            for(int j = i; j <= N; j += i)    // 处理素因子p[i]
            {
                phi[j] = phi[j] / i * (i - 1);    // 先除后乘，防止中间过程超出范围
            }
        }
    }
    cout << "Primes: " << endl;
    for(int i = 1; i <= N; i++)
    { if(p[i]) { cout << i << " "; } }
    cout << endl;
    cout << "Euler Phi Function: " << endl;
    for(int i = 1; i <= N; i++)
    { cout << phi[i] << " "; }
    return 0;
}

#include <iostream>

using namespace std;

const int MAX = 1024;

int N;

int p[MAX], phi[MAX];

int main()

{

cin >> N;

for(int i = 1; i <= N; i++) // 初始化

{ p[i] = 1; phi[i] = i; }

p[1] = 0; // 1不是素数

for(int i = 2; i <= N; i++) // 筛素数

{

if(p[i])

{

for(int j = i * i; j <= N; j += i)

{ p[j] = 0; }

}

for(int i = 2; i <= N; i++) // 求欧拉函数

{

if(p[i])

{

for(int j = i; j <= N; j += i) // 处理素因子p[i]

{

phi[j] = phi[j] / i * (i - 1); // 先除后乘，防止中间过程超出范围

}

cout << "Primes: " << endl;

for(int i = 1; i <= N; i++)

{ if(p[i]) { cout << i << " "; } }

cout << endl;

cout << "Euler Phi Function: " << endl;

for(int i = 1; i <= N; i++)

{ cout << phi[i] << " "; }

return 0;

}

以及求单点的函数值

ull phi(ull x)
{
    ull ans = x;
    ull m = (ull)sqrt(x);
    for(ull i = 2; i <= m; i++)
    {
        if(x % i == 0)    // 求素因子
        {
            ans = ans / i * (i - 1);    // 运用通项求解欧拉函数
            while(x % i == 0)    // 每个素因子只计算一次
            { x /= i; }
        }
    }
    if(x > 1)    // 防质数
    { ans = ans / x * (x - 1); }
    return ans;
}

ull phi(ull x)

{

ull ans = x;

ull m = (ull)sqrt(x);

for(ull i = 2; i <= m; i++)

{

if(x % i == 0) // 求素因子

{

ans = ans / i * (i - 1); // 运用通项求解欧拉函数

while(x % i == 0) // 每个素因子只计算一次

{ x /= i; }

}

if(x > 1) // 防质数

{ ans = ans / x * (x - 1); }

return ans;

}

应用：

欧拉定理

\(a^{\varphi(n)}=1 \mod {n}\)

原根个数

\(\varphi \left ( \varphi \left ( N \right ) \right )\)

对于原根的定义，我们可以这样来叙述：

若存在一个实数\(a\)，使得\(a^{i}\mod{N},a\in\left \{ 1,2,3,\cdots ,N \right \}\)的结果各不相同，我们就成实数\(a\)为\(N\)的一个原根。

原根的个数等于\(\varphi \left ( \varphi \left ( N \right ) \right )\)。这样我们就可以很方便的求出原根的个数。（参考题目）

指数循环节

Via http://hi.baidu.com/aekdycoin/item/e493adc9a7c0870bad092fd9

\( A^{x}=A^{x\%\varphi(C) + \varphi(C)} \mod{C} (x \ge \varphi(C))\)

[Dr.Lib]Note:解题报告 – 上网（DP）

题4 上网

【问题描述】

假设有n个人要上网，却只有1台电脑可以上网。上网的时间是从1 szw 至 T szw ，szw是sxc,zsx,wl自创的时间单位，至于 szw怎么换算成s,min或h，没有人清楚。依次给出每个人在某个时间段内上网的快乐程度C（必须这个人在整个时间段内都在上网，才能获得快乐程度C，否则，快乐程度是0），请你得到使总的快乐程度达到最大的方案。

【输入格式】

第1行2个整数 n和T，含义如题目所述；

接下来有n个这样的结构（每两个相邻的结构之间有一空行，且第1个结构和第一行间有一空行）：

第1行一个整数Mi，表示第i个人的时间段的个数；

接下来有Mi行，每行3个整数Xj,Yj,C，表示第i个人在[Xj，Yj]内上网的快乐程度为C，

因此有Xj-Yj-1=1，X1=1，Ymi=T，Xj<=Yj。

【输出格式】

仅输出一行，为总的最大的快乐程度。

【输入样例】

3 10

1 3 6

4 7 9

8 10 3

1 3 5

4 7 10

8 10 1

1 3 2

4 8 2

9 9 6

10 10 3

【输出样例】

【样例说明】

在[1，3]内，安排1上网，快乐程度为6；

在[4，7]内，安排2上网，快乐程度为10；

在[8，8]内，不安排；

在[9，9]内，安排3上网，快乐程度为6；

在[10，10]内，安排3上网，快乐程度为3；

这是使总的快乐程度达到最大的方案，对应的值是25。

【数据范围】

对于30%的数据，n<=4，所有的Mi<=5，T<=20；

对于60%的数据，n<=100，所有的Mi<=100，T<=2000；

对于100%的数据，n<=500，所有的Mi<=500，T<=500000，所有的0<C<=10^9，并保证最终解Max<=10^9。

【标程】

很明显,前30%的数据可以用暴力过，直接枚举每一个区间即可，时间复杂度是2^(n*m)。

其实，拿到这到题，就很容易想到DP，用max[i]表示第i szw后，所能达到的最大快乐程度，状态转移方程如下：max[i]=max{max[i-1]，max[x-1]+C[x,i]}，边界情况max[0]=0，其中C[x,i]表示从x时刻开始玩到i时刻的快乐程度。具体操作时，枚举所有结束时刻是i的区间，比较这些区间的初始时刻x对应的max[x-1]+C[x,i]与当前max[i]的大小，如果max[x-1]+C[x,i]更大，就替换max[i]。可能对于很多选手来说，拿出状态转移方程并不难，问题在于怎么存每个区间。如果直接开2维数组，c:array[1..maxT,1..maxT] of longint，空间复杂度是T^2，可以过60%的数据。我们应该如何存区间呢？

我们开一个一维数组，g:array[1..maxn*maxm] of record x,y,c,l:longint; end，空间约4M，其中x,y表示对应区间的初始时刻和结束时刻，c表示快乐程度，l表示上一个和这个区间y值相同的区间所对应的位置。再开一个一维数组，l:array[1..maxT] of longint，l[y]表示以y为结束时刻的最后一个区间所对应的位置。这样，我们就可以很轻松的找到以某个值y为结束时刻的区间了。DP的时间复杂度降到 O(maxn*maxm+T)。但事实上由于读入大数据文件比较耗时,所以标程过最后一个数据也要约0.4秒，因此把时限定为1.5s。(我们同样可以用x做为标准)

此题主要考察动态规划和链表，拿60分相对容易，拿满分比较困难。

数据范围和类型:

数据	1	2	3	4	5	6	7	8	9	10
N值	3	4	4	65	78	98	400	450	498	500
M值	4	4	5	62	92	98	384	462	498	500
T值	10	16	19	1234	1674	98	25*10^4	35*10^4	45*10^4	5*10^5
平均分	3.81	2.90	3.24	2.33	2.33	2.84	1.19	1.19	1.14	1.08
类型	手工	随机	特殊	随机	随机	特殊	随机	随机	随机	随机

program hh;
var f:array[0..500010] of longint;
    first:array[1..500000] of longint;
    e:array[1..250000] of record x,y,next,v:longint; end;
    i,j,k,n,t,s,x,y,v:Longint;
function max(x,y:Longint):Longint;
begin
 if x>y then exit(x) else exit(y);
end;

begin
 assign(input,'net.in');
 reset(input);
 assign(output,'net.out');
 rewrite(output);
 readln(n,t);
 s:=0;
 for i:=1 to n do
  begin
   readln;
   readln(k);
   for j:=1 to k do
    begin
     inc(s);
     readln(x,y,v);
     e[s].x:=x;e[s].y:=y;e[s].v:=v;e[s].next:=first[y];first[y]:=s;
    end;
   end;
 for i:=1 to t do
  begin
   f[i]:=f[i-1]; k:=first[i];
   while k<>0 do
    begin
     f[i]:=max(f[e[k].x-1]+e[k].v,f[i]);
     k:=e[k].next;
    end;
  end;
 writeln(f[t]);
 close(input);close(output);
end.

program hh;

var f:array[0..500010] of longint;

first:array[1..500000] of longint;

e:array[1..250000] of record x,y,next,v:longint; end;

i,j,k,n,t,s,x,y,v:Longint;

function max(x,y:Longint):Longint;

begin

if x>y then exit(x) else exit(y);

end;

begin

assign(input,'net.in');

reset(input);

assign(output,'net.out');

rewrite(output);

readln(n,t);

s:=0;

for i:=1 to n do

begin

readln;

readln(k);

for j:=1 to k do

begin

inc(s);

readln(x,y,v);

e[s].x:=x;e[s].y:=y;e[s].v:=v;e[s].next:=first[y];first[y]:=s;

end;

for i:=1 to t do

begin

f[i]:=f[i-1]; k:=first[i];

while k<>0 do

begin

f[i]:=max(f[e[k].x-1]+e[k].v,f[i]);

k:=e[k].next;

end;

writeln(f[t]);

close(input);close(output);

end.

【个人报告】

赛场上前几题耗时太多没来得及打这题。妥妥的DP阿……

但确实没想那么多……

看了题解才知道确实有坑。

抽象的模型大概就是m条带权线段求不相交区间最大权值和……几个几个人是考你读入的……

果断读进来按终点排序，一条一条来DP。

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
int n,t,mt,m,px,py,pc;
struct net{
	int x;int y;int c;
};
struct p{
	int y;int c;
};
struct dqueue{
	dqueue(){head=-1;}
	p S[250000];
	int head;
	bool ins(p i){
		if(head==-1){head++;S[head]=i;return 1;}
		if(S[head].c>=i.c)return 0;
		head++;S[head]=i;return 1;
	}
	int get(int i){
		if(head==-1){return 0;}
		int t=head;
		while(t>=0&&S[t].y>i){--t;}
		if(t==-1)return 0;
		return S[t].c;//二分查找我不会= =
	}
};
int cmp(net a,net b){
	return a.y<b.y;
}
vector<net> Q;
dqueue D;
int scanfd(){
	int p=0;
	char c;
	while(c=getchar()){
		if(c-'0'<=9&&c-'0'>=0){break;}
	}
	p=c-'0';
	while(c=getchar()){
		if(c-'0'<=9&&c-'0'>=0){p=p*10+c-'0';}else{break;}
	}
	return p;
}
int main(){
    freopen("net.in","r",stdin);
    freopen("net.out","w",stdout);
	scanf("%d%d",&n,&t);
	while(n--){
		scanf("%d",&m);
		mt+=m;
		while(m--){
			px=scanfd();py=scanfd();pc=scanfd();
			net pn;
			pn.x=px;pn.y=py;pn.c=pc;
			Q.push_back(pn);
		}
	}
	sort(Q.begin(),Q.end(),cmp);
	for(int i=0;i<mt;++i){
		pc=Q[i].c;px=Q[i].x;py=Q[i].y;
		int tmc=D.get(px-1);
		p pyc;
		pyc.c=tmc+pc;pyc.y=py;
		D.ins(pyc);
	}
	cout<<D.get(t)<<endl;
	return 0;
}

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<cmath>

#include<queue>

#include<stack>

using namespace std;

typedef long long ll;

int n,t,mt,m,px,py,pc;

struct net{

int x;int y;int c;

};

struct p{

int y;int c;

};

struct dqueue{

dqueue(){head=-1;}

p S[250000];

int head;

bool ins(p i){

if(head==-1){head++;S[head]=i;return 1;}

if(S[head].c>=i.c)return 0;

head++;S[head]=i;return 1;

}

int get(int i){

if(head==-1){return 0;}

int t=head;

while(t>=0&&S[t].y>i){--t;}

if(t==-1)return 0;

return S[t].c;//二分查找我不会= =

}

};

int cmp(net a,net b){

return a.y<b.y;

}

vector<net> Q;

dqueue D;

int scanfd(){

int p=0;

char c;

while(c=getchar()){

if(c-'0'<=9&&c-'0'>=0){break;}

}

p=c-'0';

while(c=getchar()){

if(c-'0'<=9&&c-'0'>=0){p=p*10+c-'0';}else{break;}

}

return p;

}

int main(){

freopen("net.in","r",stdin);

freopen("net.out","w",stdout);

scanf("%d%d",&n,&t);

while(n--){

scanf("%d",&m);

mt+=m;

while(m--){

px=scanfd();py=scanfd();pc=scanfd();

net pn;

pn.x=px;pn.y=py;pn.c=pc;

Q.push_back(pn);

}

sort(Q.begin(),Q.end(),cmp);

for(int i=0;i<mt;++i){

pc=Q[i].c;px=Q[i].x;py=Q[i].y;

int tmc=D.get(px-1);

p pyc;

pyc.c=tmc+pc;pyc.y=py;

D.ins(pyc);

}

cout<<D.get(t)<<endl;

return 0;

}

[Dr.Lib]Note:Math – 不定方程

Via Ivy-Endhttp://www.ivy-end.com/archives/1010
关于这个算法，主要是参考NOIP2012 Day2 T1。即这里所讲的是求解这样一个线性模方程：\[ax\equiv 1\mod{p}\]的最小正整数解。

去年我是暴搜做的(PS+1)，当时什么都不会。今天在这里介绍两种算法，一种是我国古代数学家秦九韶发明的「大衍求一术」，还一种是著名的「扩展欧几里德算法」。

大衍求一术

首先来看一下大衍求一术。这里只介绍它的计算方法，至于证明可以参考扩展欧几里德算法。

例1：求解方程\(23x\equiv 1\mod{97}\)。

解：我们只需要列出下面这张表就可以得到求解\[\begin{matrix}23^{1} & 23^{1} & 3^{17} & 3^{17} & 1^{38}\\ 97^{0} & 5^{4} & 5^{4} & 2^{21} & 2^{21}\end{matrix}\]结果就是38。

接下来我们来理论化的表述一下这个算法的过程：

假设输入\(a,b\)满足\(a>b\)。那么我们用\(a_{n},A_{n}\)分别表示第一行的底数和奇数，\(b_{n},B_{n}\)分别表示第二行的底数和奇数，如果\(a_{i}>b_{i}\)，那么\(a_{i+1}=a_{i}\mod{b_{i}},A_{i+1}=A_{i}+B_{i}\cdot \left [ \frac{a_{i}}{b_{i}} \right ],b_{i+1}=b_{i},B_{i+1}=B_{i}\)；如果\(a_{i}<b_{i}\)则上面的结论倒过来即可。

算法结束当且仅当\(a_{i}=1\)，此时\(A_{i}\)即为所求的最小正整数解。

例2：求解方程\(97x\equiv 1\mod{23}\)。

解：我们只需要列出下面这张表就可以得到求解\[\begin{matrix}97^{1} & 5^{1} & 5^{1} & 2^{5} & 2^{5} & \\ 23^{0} & 23^{0} & 3^{4} & 3^{4} & 1^{9} & 1^{14}\end{matrix}\]结果就是14。

对于这个结果，如果1最先出现在下面一行，则需要再计算一次，而且这次计算必须使得余数是1。

假设输入\(a,b\)满足\(a<b\)。中间的步骤和之前一行，在计算过程中必然存在一个\(i\)使得\(b_{i}=1\)，此时我们只需计算\(B_{i+1}\)即可得到结果。其中\(B_{i+1}=A_{i}+B_{i}\cdot \left(a_{i} – 1\right)\)。

#include <iostream>

using namespace std;

struct Num
{
    int nBase, nIndex;    // 分别表示底数和奇数
};

Num x, y;

int main()
{
    cin >> x.nBase >> y.nBase;
    x.nIndex = 1; y.nIndex = 0;    // 初始化
    if(x.nBase < y.nBase)
    {
        while(1)
        {
            if(x.nBase == 1 || x.nBase == 0)    // 循环出口
            { cout << x.nIndex << endl; break; }
            if(x.nBase < y.nBase)    // 模拟计算过程
            {
                int nDiv = y.nBase / x.nBase;
                if(y.nBase % x.nBase == 0)
                { nDiv--; }
                y.nBase %= x.nBase;
                y.nIndex += nDiv * x.nIndex;
            }
            else
            {
                int nDiv = x.nBase / y.nBase;
                if(x.nBase % y.nBase == 0)
                { nDiv--; }
                x.nBase %= y.nBase;
                x.nIndex += nDiv * y.nIndex;
            }
        }
    }
    else
    {
        while(1)
        {
            if(y.nBase == 1)    // 出口
            {
                int nDiv = x.nBase - 1;
                cout << nDiv * y.nIndex + x.nIndex << endl;    // 求出结果
                break;
            }
            if(x.nBase < y.nBase)    // 模拟计算过程
            {
                int nDiv = y.nBase / x.nBase;
                if(y.nBase % x.nBase == 0)
                { nDiv--; }
                y.nBase %= x.nBase;
                y.nIndex += nDiv * x.nIndex;
            }
            else
            {
                int nDiv = x.nBase / y.nBase;
                if(x.nBase % y.nBase == 0)
                { nDiv--; }
                x.nBase %= y.nBase;
                x.nIndex += nDiv * y.nIndex;
            }
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

struct Num

{

int nBase, nIndex; // 分别表示底数和奇数

};

Num x, y;

int main()

{

cin >> x.nBase >> y.nBase;

x.nIndex = 1; y.nIndex = 0; // 初始化

if(x.nBase < y.nBase)

{

while(1)

{

if(x.nBase == 1 || x.nBase == 0) // 循环出口

{ cout << x.nIndex << endl; break; }

if(x.nBase < y.nBase) // 模拟计算过程

{

int nDiv = y.nBase / x.nBase;

if(y.nBase % x.nBase == 0)

{ nDiv--; }

y.nBase %= x.nBase;

y.nIndex += nDiv * x.nIndex;

}

else

{

int nDiv = x.nBase / y.nBase;

if(x.nBase % y.nBase == 0)

{ nDiv--; }

x.nBase %= y.nBase;

x.nIndex += nDiv * y.nIndex;

}

else

{

while(1)

{

if(y.nBase == 1) // 出口

{

int nDiv = x.nBase - 1;

cout << nDiv * y.nIndex + x.nIndex << endl; // 求出结果

break;

}

if(x.nBase < y.nBase) // 模拟计算过程

{

int nDiv = y.nBase / x.nBase;

if(y.nBase % x.nBase == 0)

{ nDiv--; }

y.nBase %= x.nBase;

y.nIndex += nDiv * x.nIndex;

}

else

{

int nDiv = x.nBase / y.nBase;

if(x.nBase % y.nBase == 0)

{ nDiv--; }

x.nBase %= y.nBase;

x.nIndex += nDiv * y.nIndex;

}

return 0;

}

扩展欧几里德算法

可能上面的算法对于某些人来说比较晦涩，我们下面来介绍一下扩展欧几里德算法。首先介绍一个定理：

方程\(ax+by=\gcd\left ( a,b \right )\)一定有解。

这样我们的问题就可以转化为求方程\(ax+b\cdot \left ( -y \right )=1\)，在这里，我们先求出方程\(ax+b\cdot \left ( -y \right )=\gcd\left(a,b\right)\)的解，然后只要将结果除以\(\gcd\left(a,b\right)\)就行了。

下面来推导一下扩展欧几里德算法。

我们已知\[ax+by=\gcd\left ( a,b \right )\]，且\(\gcd\left ( a,b \right )=\gcd\left(b,a\mod b \right )\)。不妨设\[bx{}'+\left ( a\mod b \right )y{}'=\gcd\left ( b,a\mod b \right )\]。此时就有\[bx{}'+\left ( a\mod b \right )y{}'=ax+by\]，展开得到\[bx{}'+\left ( a-\left [ \frac{a}{b} \right ]\cdot b \right )y{}’=ax+by\]，化简得\[ay{}'+b\left (x{}'-\left [ \frac{a}{b} \right ]\cdot y{}’ \right )=ax+by\]。因此可以得到\[x=y{}',y=x{}'-\left [ \frac{a}{b} \right ]\cdot y{}’\]。

这样我们就可以用递归来实现扩展欧几里德算法了。

#include <iostream>

using namespace std;

typedef long long LL;

LL A, B, C, X = 0, Y = 0;

LL gcd(LL a, LL b);
void exgcd(LL a, LL b, LL &x, LL &y);

int main()
{
    cin >> A >> B;
    C = gcd(A, B);
    exgcd(A, -B, X, Y);
    while(X < 0) { X += B; }    // 找最小正整数
    cout << X << endl;
    return 0;
}

void exgcd(LL a, LL b, LL &x, LL &y)
{
    if(a == 0)
    {
        x = 0; y = C / b;    // 边界
    }
    else
    {
        exgcd(b % a, a, x, y);
        y = x;        // 递推公式
        x = (C - b * y) / a;
    }
}

LL gcd(LL a, LL b)    // 求解最大公倍数
{
    if(b == 0) { return a; }
    else
    {
        return gcd(b, a % b);
    }
}

#include <iostream>

using namespace std;

typedef long long LL;

LL A, B, C, X = 0, Y = 0;

LL gcd(LL a, LL b);

void exgcd(LL a, LL b, LL &x, LL &y);

int main()

{

cin >> A >> B;

C = gcd(A, B);

exgcd(A, -B, X, Y);

while(X < 0) { X += B; } // 找最小正整数

cout << X << endl;

return 0;

}

void exgcd(LL a, LL b, LL &x, LL &y)

{

if(a == 0)

{

x = 0; y = C / b; // 边界

}

else

{

exgcd(b % a, a, x, y);

y = x; // 递推公式

x = (C - b * y) / a;

}

LL gcd(LL a, LL b) // 求解最大公倍数

{

if(b == 0) { return a; }

else

{

return gcd(b, a % b);

}

欧拉定理

\(a^{phi(n)}=1 \mod {n}\)
令\(x=a^{phi(n) -1}\mod{n}\)有\(ax=1 \mod{n}\)则x即为答案。
只需求出phi(n)就可以了。

#include<iostream>
#include<cmath>
using namespace std;
typedef unsigned int ll;
typedef long long lll;
lll qkpow(lll a,  lll b,  lll  c){
    lll  ret=1%c;
   while(b) {
      if(b&1) ret=ret*a%c;a=a*a%c;b>>=1;
   }
   return ret;
}
ll a,b,n;lll rsts;
ll phi(){
    ll rst=1;
    double x=sqrt(b);
    for(int i=2;i<=x;++i){
        if(b%i==0){
            rst*=i-1;
            while(b%i==0){
                rst*=i;
                b/=i;
            }
            rst/=i;
        }
    }
    if(b>1){rst*=(b-1);}
    return rst;
}
int main(){
    cin>>a>>b;n=b;
    rsts=qkpow(a,phi()-1,n);
    cout<<rsts<<endl;
    return 0;
}

#include<iostream>

#include<cmath>

using namespace std;

typedef unsigned int ll;

typedef long long lll;

lll qkpow(lll a, lll b, lll c){

lll ret=1%c;

while(b) {

if(b&1) ret=ret*a%c;a=a*a%c;b>>=1;

}

return ret;

}

ll a,b,n;lll rsts;

ll phi(){

ll rst=1;

double x=sqrt(b);

for(int i=2;i<=x;++i){

if(b%i==0){

rst*=i-1;

while(b%i==0){

rst*=i;

b/=i;

}

rst/=i;

}

if(b>1){rst*=(b-1);}

return rst;

}

int main(){

cin>>a>>b;n=b;

rsts=qkpow(a,phi()-1,n);

cout<<rsts<<endl;

return 0;

}

[Dr.Lib]Note:Algorithms – 矩阵乘法

矩阵乘法在很多题目中都有显著的应用，在一些递推、计算几何和其他可以用矩阵表示元素操作的题目中，可以借助快速幂的思想优化不少时间。

1.加速递推

最著名的递推当属Fibonacci数列了。
\(
f[0]=f[1]=1
f[n]=f[n-1]+f[n-2]
\)

朴素的递推需要O(n)的时间（应该没人写递归吧……

如果采用矩阵快速幂

\(
\begin{bmatrix}
f(n+1) \\
f(n)
\end{bmatrix}
=
(\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix})^{n}
\cdot
\begin{bmatrix}
1 \\
1
\end{bmatrix}
\)
其中矩阵乘法可以采用快速幂的思想加速运算（矩阵乘法满足结合律）

稍稍复杂的例子还有

http://wikioi.com/problem/1281/

http://acm.buaa.edu.cn/problem/653/

……等等很多

2.计算几何

example：via http://www.matrix67.com/blog/archives/276/

给定n个点，m个操作，构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转
这里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转（两种情况），旋转则以原点为中心。如果对每个点分别进行模拟，那么m个操作总共耗时O(mn)。利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵，然后每个点与该矩阵相乘即可直接得出最终该点的位置，总共耗时O(m+n)。假设初始时某个点的坐标为x和y，下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵全部乘起来，再乘以(x,y,1)，即可一步得出最终点的位置。

3.……以及其他

example：黑书p205细菌、VOJ1049序列置换、有向图方案数……

顺次给出m个置换，反复使用这m个置换对初始序列进行操作，问k次置换后的序列。m<=10, k<2^31。
首先将这m个置换“合并”起来（算出这m个置换的乘积），然后接下来我们需要执行这个置换k/m次（取整，若有余数则剩下几步模拟即可）。注意任意一个置换都可以表示成矩阵的形式。例如，将1 2 3 4置换为3 1 2 4，相当于下面的矩阵乘法：

置换k/m次就相当于在前面乘以k/m个这样的矩阵。我们可以二分计算出该矩阵的k/m次方，再乘以初始序列即可。做出来了别忙着高兴，得意之时就是你灭亡之日，别忘了最后可能还有几个置换需要模拟。

给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。

4.模版

模版代码来源于http://blog.csdn.net/u010153200/article/details/8974369

template <int A, int B>
struct matrix
{
	long long v[A][B];
	matrix(long long r = 0)
	{
		memset(v, 0, sizeof(v));
		for (int i = 0; i < A && i < B; i++)
			v[i][i]	= r;
	}
	matrix(long long a[A][B])
	{
		memcpy(v, a, sizeof(a));
	}	
};
inline long long quickadd(long long a, long long b)
{
	long long ans = 0;
	for (; b; b >>= 1)
	{
		if (b & 1) ans = (ans + a) % m;
		a = (a + a) % m;
	}
	return ans;
}
template <int A, int B, int C>
matrix <A, C> operator * (const matrix <A, B> &a, const matrix <B, C> &b)
{
	matrix <A, C> ans;
	for (int i = 0; i < A; i++)
		for (int j = 0; j < C; j++)
		{
			long long v = 0;
			for (int k = 0; k < B; k++)
				v += quickadd(a.v[i][k], b.v[k][j]);
			ans.v[i][j] = (v % m + m) % m;
		}
	return ans;
}
template <int A>
matrix <A, A> power(const matrix<A, A> &a, long long b)
{
	matrix <A, A> ans = 1;
	for (matrix<A, A> i = a; b; b >>= 1)
	{
		if (b & 1) ans = ans * i;
		i = i * i;
	}
	return ans;
}

template <int A, int B>

struct matrix

{

long long v[A][B];

matrix(long long r = 0)

{

memset(v, 0, sizeof(v));

for (int i = 0; i < A && i < B; i++)

v[i][i] = r;

}

matrix(long long a[A][B])

{

memcpy(v, a, sizeof(a));

}

};

inline long long quickadd(long long a, long long b)

{

long long ans = 0;

for (; b; b >>= 1)

{

if (b & 1) ans = (ans + a) % m;

a = (a + a) % m;

}

return ans;

}

template <int A, int B, int C>

matrix <A, C> operator * (const matrix <A, B> &a, const matrix <B, C> &b)

{

matrix <A, C> ans;

for (int i = 0; i < A; i++)

for (int j = 0; j < C; j++)

{

long long v = 0;

for (int k = 0; k < B; k++)

v += quickadd(a.v[i][k], b.v[k][j]);

ans.v[i][j] = (v % m + m) % m;

}

return ans;

}

template <int A>

matrix <A, A> power(const matrix<A, A> &a, long long b)

{

matrix <A, A> ans = 1;

for (matrix<A, A> i = a; b; b >>= 1)

{

if (b & 1) ans = ans * i;

i = i * i;

}

return ans;

}

Category Archives: Algorithm

[Dr.Lib]Note:Data Structures – 数据结构那些事

树状数组

朴素线段树

ZKW线段树

[Dr.Lib]Note:Math – 欧拉函数

欧拉定理

原根个数

指数循环节

[Dr.Lib]Note:解题报告 – 上网（DP）

[Dr.Lib]Note:Math – 不定方程

大衍求一术

扩展欧几里德算法

欧拉定理

[Dr.Lib]Note:Algorithms – 矩阵乘法

1.加速递推

2.计算几何

3.……以及其他

朋友们

TAG CLOUD