就是标准的平衡二叉数。。
有insert,delete,rank,select四个操作。。
我用splay就是超时。。。妈呀。。最后用别人的SBT过掉了。。
Code:
#include<cstdio>
using namespace std;
const int inf=~0U>>1;
class splay
{
struct node
{
int k,s;
bool d;
node*c[2],*p;
void sc(node*_c,bool d)
{c[d]=_c;_c->p=this;_c->d=d;}
}*root,*Null,*Now,*stack[100000],Data[200000],*tmp;
int top;
typedef node* Node;
Node new_node(int k)
{
if(top) tmp=stack[–top];
else tmp=Now++;
tmp->k=k;tmp->s=1;
tmp->c[0]=tmp->c[1]=Null;
return tmp;
}
void del_node(Node p)
{
stack[top++]=p;
}
void upd(Node t)
{
t->s=t->c[0]->s+t->c[1]->s+1;
}
void rot(Node t)
{
node*p=t->p;bool d=t->d;
p->sc(t->c[!d],d);
p->p->sc(t,p->d);
t->sc(p,!d);
upd(p);upd(t);
}
void spl(Node x,Node f)
{
while(x->p!=f)
{
if(x->p->p==f) rot(x);
else x->d==x->p->d?( rot(x->p),rot(x) ):( rot(x),rot(x) );
}
}
Node select(int k)
{
int r;
for(Node t=root->c[1];;)
{
r=t->c[0]->s;
if(r==k) return t;
t=t->c[k>r];
if(k>r) k-=r+1;
}
}
Node ser(Node t,int k)
{
for(;t!=Null&&t->k!=k;t=t->c[k>t->k]);
return t;
}
Node insert(int k)
{
bool d;Node t=root;
for(;t->k!=k;)
{
d=k>t->k;
if(t->c[d]==Null)
{
Node p=new_node(k);
t->sc(p,d);
}
t=t->c[d];
}
return t;
}
int rank(int k)
{
int ans=0;
for(Node t=root->c[1];t!=Null;)
{
if(k>t->k) ans+=1+t->c[0]->s;
t=t->c[k>t->k];
}
return ans;
}
public:
splay()
{
top=0;Now=Data;
Null=new_node(0);Null->s=0;
root=new_node(-inf);root->p=root;
}
void ins(int x)
{
Node p=insert(x);
spl(p,root);
}
int sel(int x)
{
if(x>=root->c[1]->s) return inf;
Node p=select(x);
return p->k;
}
int ran(int x)
{
return rank(x);
}
void del(int k)
{
Node tmp=ser(root->c[1],k);if(tmp==Null) return;
while(tmp->c[0]!=Null)
rot(tmp->c[0]);
if(tmp->c[1]==Null)
{
tmp->p->c[tmp->d]=Null;
tmp->p->s–;
spl(tmp->p,root);
del_node(tmp);
return;
}
tmp->p->sc(tmp->c[1],tmp->d);
spl(tmp->c[1],root);
del_node(tmp);
}
}*sp;
int main()
{
int n,t,a;char c;sp=new splay;scanf("%dn",&n);char C[1000];
for(int i=0;i<n;i++)
{
scanf("%c %dn",&c,&t);
switch(c)
{
case ‘I’:sp->ins(t);break;
case ‘D’:sp->del(t);break;
case ‘K’:a=sp->sel(t-1);
if(a==inf) puts("invalid");
else printf("%dn",a);break;
case ‘C’:printf("%dn",sp->ran(t));break;
}
}
}

就是说给你1到n一排数每次把从l到r的数反过来。。让你输出最后的那列数。。
动态表。。明显用splay。。最近刚学了splay，爽阿。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=~0U>>1;
class splay
{
int n;
struct node
{
int k,s;
bool d,rev;
node*c[2],*p;
node(){c[0]=c[1]=p=0;}
void sc(node*_c,bool d)
{c[d]=_c;_c->p=this;_c->d=d;}
}*root,*Null,*Now,Data[130100];
typedef node* Node;
Node new_node(int k)
{
Now->c[0]=Now->c[1]=Null;
Now->rev=false;Now->s=1;
Now->k=k;return Now++;
}
void rev(Node t)
{
if(t==Null) return;
t->rev^=1;
swap(t->c[0],t->c[1]);
t->c[0]->d=0;
t->c[1]->d=1;
}
void pus(Node t)
{
if(t->rev)
rev(t->c[0]),rev(t->c[1]);
t->rev=false;
}
void upd(Node t)
{
t->s=t->c[0]->s+t->c[1]->s+1;
}
void rot(Node t)
{
Node p=t->p;
pus(p);pus(t);bool d=t->d;
p->sc(t->c[!d],d);
p->p->sc(t,p->d);
t->sc(p,!d);
upd(p);upd(t);
if(p==root) root=t;
}
void spl(Node x,Node f)
{
for(pus(x);x->p!=f;)
{
if(x->p->p==f) rot(x);
else x->d==x->p->d?( rot(x->p),rot(x) ):( rot(x),rot(x) );
}
}
Node sel(int k)
{
int r;
for(Node t=root;;)
{
pus(t);
r=t->c[0]->s;
if(r==k) return t;
t=t->c[k>r];
if(k>r) k-=r+1;
}
}
void print(Node t)
{
if(t==Null||!t) return;
pus(t);
print(t->c[0]);
if(t->k)printf("%d ",t->k),fflush(stdout);
print(t->c[1]);
}
public:
void out()
{
print(root);
}
splay(int n):n(n)
{
Now=Data;
Null=new node;Null->s=0;
root=new_node(0);root->p=Null;
Node p,q=root;
for(int i=1;i<=n;i++)
{
p=new_node(i);
q->sc(p,1);
q=p;
}
Node last=new_node(0);
q->sc(last,1);
spl(last,Null);
}
void reverse(int l,int r)
{
Node x,y;
x=sel(l-1);
spl(x,Null);
y=sel(r+1);
spl(y,root);
rev(y->c[0]);
}
}*sp;
int main()
{
int n,m,l,r;cin>>n>>m;
sp=new splay(n);
while(m–)
{
scanf("%d %d",&l,&r);
sp->reverse(l,r);
}
sp->out();
}

PKU 2008 Individual Practice 7
  3666 Problem A Making the Grade 大意。。就是用最小的代价把一群数变成单调的。。变化一个数的代价是变化的绝对值。。
首先很明确是可以离散的，就是说如果一个数不这N个数中，也没有必要把其他的数变成这个数。。
所以实际上有用的数只有N个。。设这些数为A1..N
那么设D[i][j]为1..i,第i个数为Aj让所有数递增的最小代价。。
那么D[i][j]=|Ai-Aj|+min(D[i-1][k])(1<=k<=j)
那么答案就是min(D[N][1..N])。。
实际上这是BOI的原题。。当时N<=100000，所以N^2只能见鬼去，
但这个N只<=2000。。可以过。。。
有一个用左偏树的NLogN的算法。。但是太麻烦了。。
Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<string>
#include<cmath>
using namespace std;
const int maxn=2010,inf=~0U>>1;
int A[maxn],B[maxn],DP[maxn],n;
inline int cost(int i,int j){return i>j?(i-j):(j-i);}
int solve()
{
for(int i=0;i<n;i++)
DP[i]=cost(B[i],A[0]);
int tmp;
for(int i=1;i<n;i++)
{
tmp=inf;
for(int j=0;j<n;j++)
{
tmp=min(tmp,DP[j]);
DP[j]=tmp+cost(B[j],A[i]);
}
}
return *min_element(DP,DP+n);
}
int main()
{
freopen("in","r",stdin);
cin>>n;for(int i=0;i<n;i++) scanf("%d",A+i),B[i]=A[i];
sort(B,B+n);int ans=solve();
for(int l=0,r=n-1;l<r;l++,r–)
swap(A[l],A[r]);
ans=min(ans,solve());
cout<<ans<<endl;
}   3667 Problem B Hotel
用一个线段树维护就OK了。。需要使用懒标记。。
Code：
#include<iostream>
 
#include<algorithm>
 
#include<cstring>
 
#include<utility>
 
#include<cstdio>
 
#define Renew(x,c) x=max(x,c)
 
using namespace std;
 
struct Tree
 
{
 
bool sign,e;
 
int max,Lmax,Rmax,size,l,r;
 
Tree*Lch,*Rch;
 
}A[150000],*now,*root;
 
Tree* NewNode(int l,int r)
 
{
 
now->sign=false;
 
now->max=now->Lmax=now->Rmax=r-l+1;
 
now->size=r-l+1;
 
now->l=l;
 
now->r=r;
 
return now++;
 
}
 
void Update(Tree*Fa)
 
{
 
if(Fa->Lch->max==Fa->Lch->size)
 
Fa->Lmax=Fa->Lch->size+Fa->Rch->Lmax;
 
else
 
Fa->Lmax=Fa->Lch->Lmax;
 
if(Fa->Rch->max==Fa->Rch->size)
 
Fa->Rmax=Fa->Rch->size+Fa->Lch->Rmax;
 
else
 
Fa->Rmax=Fa->Rch->Rmax;
 
Fa->max=Fa->Lch->Rmax+Fa->Rch->Lmax;
 
Renew(Fa->max,max(Fa->Lch->max,Fa->Rch->max));
 
}
 
Tree* Build(int l,int r)
 
{
 
if(l==r)return NewNode(l,r);
 
int mid=(l+r)/2;
 
Tree* T=NewNode(l,r);
 
T->Lch=Build(l,mid);
 
T->Rch=Build(mid+1,r);
 
return T;
 
}
 
void Set(Tree*T,bool e)
 
{
 
T->sign=true;
 
T->e=e;
 
T->Lmax=T->Rmax=T->max=e?T->size:0;
 
}
 
void Push(Tree*T)
 
{
 
if(T->sign)
 
{
 
if(T->size>1)
 
{
 
Set(T->Lch,T->e);
 
Set(T->Rch,T->e);
 
}
 
T->sign=false;
 
}
 
}
 
int l,r;
 
void set(Tree*T,bool e)
 
{
 
if(T->l>=l and T->r<=r)
 
{
 
Set(T,e);
 
return;
 
}
 
int mid=T->Lch->r;
 
Push(T);
 
if(mid>=l)
 
set(T->Lch,e);
 
if(r>mid)
 
set(T->Rch,e);
 
Update(T);
 
}
 
int len;
 
int Put(Tree*T)
 
{
 
Push(T);
 
if(T->Lch->max>=len)
 
return Put(T->Lch);
 
if(T->Lch->Rmax+T->Rch->Lmax>=len)
 
return T->Lch->r-T->Lch->Rmax+1;
 
if(T->Rch->max>=len)
 
return Put(T->Rch);
 
return 0;
 
}
 
void In(int D)
 
{
 
len=D;
 
int a=Put(root);
 
printf("%dn",a);
 
if(a)
 
l=a,r=a+D-1,set(root,false);
 
}
 
void Out(int l,int r)
 
{
 
::l=l;::r=r;
 
set(root,true);
 
}
 
int n,m;
 
void init()
 
{
 
cin>>n>>m;
 
now=A;
 
root=Build(1,n);
 
}
 
void work()
 
{
 
int k,l,d;
 
while(m–)
 
{
 
scanf("%d",&k);
 
if(k==1)
 
scanf("%d",&d),In(d);
 
else
 
scanf("%d %d",&l,&d),Out(l,l+d-1);
 
}
 
}
 
int main()
 
{
 
init();
 
work();
 
}   3668 Problem C Game of Lines 就是所有直线中不同斜率的个数。。直接set就可以了。。
Code:
#include<iostream>
#include<cstdio>
#include<utility>
#include<set>
using namespace std;
typedef pair<int,int> pi;
int n;
pi A[300];
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
pi operator-(pi x,pi y)
{
return pi(x.first-y.first,x.second-y.second);
}
int main()
{
freopen("in","r",stdin);
cin>>n;
for(int i=0;i<n;i++)
cin>>A[i].first>>A[i].second;
set<pi> S;pi get;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
get=A[j]-A[i];
int d=gcd(get.first,get.second);
get.first/=d;
get.second/=d;
S.insert(get);
}
cout<<S.size()<<endl;
}   3669 Problem D Meteor Shower BFS…
Code:
#include<iostream>
#include<cstdio>
#include<utility>
#include<queue>
#define Renew(x,c) x=min(x,c)
using namespace std;
typedef pair<int,int> pi;
const int maxn=310,inf=~0U>>1;
int T[maxn][maxn],D[maxn][maxn];
queue<pi> Q;
inline bool inarea(int x,int y)
{return x>=0 and y>=0 and x<maxn and y<maxn;}
int main()
{
freopen("in","r",stdin);
int m,x,y,t;cin>>m;
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
T[i][j]=D[i][j]=inf;
const int di[]={-1,0,1,0},dj[]={0,1,0,-1};
while(m–)
{
scanf("%d %d %d",&x,&y,&t);
Renew(T[x][y],t);
for(int ii,jj,d=0;d<4;d++)
{
ii=x+di[d];jj=y+dj[d];
if(inarea(ii,jj))
Renew(T[ii][jj],t);
}
}
D[0][0]=0;Q.push(pi(0,0));int c;
while(Q.size())
{
pi t=Q.front();Q.pop();c=D[t.first][t.second];
if(T[t.first][t.second]==inf)
{
cout<<c<<endl;
return 0;
}
for(int ii,jj,d=0;d<4;d++)
{
ii=t.first+di[d];jj=t.second+dj[d];
if(inarea(ii,jj) and D[ii][jj]==inf and T[ii][jj]>c+1)
D[ii][jj]=c+1,Q.push(pi(ii,jj));
}
}
cout<<-1<<endl;
}

阿阿阿阿阿阿阿阿。。。总算做出来了。。错误这一个那一个的，调试的快疯了。。
大意：
一棵带权树，有两种询问：
（1）：Dist（a，b）询问a到b的距离
（2）：Kth（a，b，k）询问a到b的路径上的第一k个点。。
分析：
用传统的RMQ+对每个节点记录第2^i个(i=0、1、2…)祖先的在线做法，
时间是NlogN。。比较慢。。。
我的办法是首先Tarjan求出所有询问中a和b的lca。。然后dist可以直接算，
kth就需要看第k个节点是在a的祖先还是b的祖先，可以归结为求一个节点的第几个祖先的问题，
可以再dfs一遍。。用一个deque储存根到当前节点的路径。就可以离线KO了。。。
不过在码代码的时候我精神失常。。错误一箩筐。。。
Code：http://ideone.com/p9PZ8PvR

赞赞阿。。
Splay绝对是最完美的平衡树。。除了时间比较慢。。其他绝对是最NB的。。
想出这玩意的人绝对是天才中的天才。。。
写了个Code。。贴一下。。
#include<cstdio>
#include<iostream>
using namespace std;
const int inf=~0U>>1;
class splay
{
struct node
{
int k,s;//k是值,s是子树大小
bool d;//d是该节点是父亲的那种节点
node*c[2],*p;//c[0]、c[1]分别是左，右孩子，p是父亲
node(int _k,node*_c):k(_k),s(1){c[0]=c[1]=_c;}
void sc(node*_c,bool d) //sc means set child
{c[d]=_c;_c->p=this;_c->d=d;}
}*root,*Null,*Now;
typedef node* Node;
void upd(Node t)
{
t->s=t->c[0]->s+t->c[1]->s+1;
}
void rot(Node t)
{
node*p=t->p;bool d=t->d;
p->sc(t->c[!d],d);
p->p->sc(t,p->d);
t->sc(p,!d);
upd(p);upd(t);
}
void spl(Node x,Node f)
{
while(x->p!=f)
{
if(x->p->p==f) rot(x);
else x->d==x->p->d?( rot(x->p),rot(x) ):( rot(x),rot(x) );
}
}
Node select(Node t,int k)
{
int r;
for(;;)
{
r=t->c[0]->s;
if(r==k) return t;
t=t->c[k>r];
if(k>r) k-=r+1;
}
}
Node insert(Node t,int k)
{
bool d=k>t->k;
if(t->c[d]==Null)
{
Node p=new node(k,Null);
t->sc(p,d);
return p;
}
return insert(t->c[d],k);
}
public:
splay()
{
Null=new node(0,0);Null->s=0;
root=new node(-inf,Null);
}
void ins(int x)
{
Node p=insert(root,x);
spl(p,root);
}
int sel(int x)
{
Node p=select(root->c[1],x);
spl(p,root);
return p->k;
}
}*sp;
int main()
{
freopen("in","r",stdin);
int n;int k,a;sp=new splay;cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d %d",&k,&a);
if(k==0)
sp->ins(a);
else
printf("%dn",sp->sel(a));
}
}

今天出去喝酒。。无聊灵机一动，想到一道挺有意思的题目。。

一个N个顶点的完全图，每条边的长度是0-1之间的随机实数，

那么这个图最小生成树的期望长度和是多少？

N<=10000,答案要求精确到4位。。。

其实很容易。。。如果你会积分的话。。。

打算A光PKU Individual Practice。。。
已经A了2008的1-3了。。
由于题目比较多。。
做个索引好看题。。
PKU 2008 Individual Practice 1
(1): http://wjmzbmr.com/archives/pku_2008_individual_practice_1_1/
(2): http://wjmzbmr.com/archives/pku_2008_individual_practice_1_2/

3615 Problem D Cow Hurdles

大意：

N（1<=300）个顶点的图，有T（<=40000）个询问，

每次询问从s到e的所有路径中，最大边最小是多少。。

分析：

很明显N很小T很大暴力不可行。。

于是想到floyd。。发现扩展一下没有问题，不过是改成了。。

D[i,j]=min(D[i,j],max(D[i,k],D[k,j]) );而已

启示：

很多时候floyd是很有用的。。

Code：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=300,inf=~0U>>1;
int d[maxn][maxn];
int n,m,ti;
int main()
{
freopen("in","r",stdin);
cin>>n>>m>>ti;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
d[i][j]=inf;
int s,t,c;
while(m–)
{
scanf("%d %d %d",&s,&t,&c);s–;t–;
d[s][t]=min(d[s][t],c);
}
for(int k=n-1;k>=0;k–)
for(int i=n-1;i>=0;i–)if(i!=k&&d[i][k]!=inf)
for(int j=n-1;j>=0;j–)
d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));
while(ti–)
{
scanf("%d %d",&s,&t);s–;t–;
printf("%dn",(d[s][t]==inf?-1:d[s][t]));
}
}

3616 Problem E Milking Time

大意：M个区间，每个有个效率值，取一些区间，让所有区间不重叠并前相邻的两个中空开R格以上。。

分析：设P[n]为最后一个区间在n结束时最大效率和，则P[n]=max(P[k])(k<=n-R)。。

那么用数状数组维护一下就OK了。。

启示：

区间问题如果长度不是太大的化鬼才离散化。。。

Code：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#define low(x) (x&(-x))
#define Renew(x,c) x=max(x,c)
using namespace std;
typedef pair<int,int> pi;
typedef pair<pi,int> inter;
const int maxn=1000000+100,maxm=1000+100,inf=~0U>>2;
int N,M,R,A[maxn];
int Max(int l)
{
int ans=0;
for(;l>0;l-=low(l))
Renew(ans,A[l]);
return ans;
}
void Change(int l,int d)
{
for(;l<=N;l+=low(l))
Renew(A[l],d);
}
inter I[maxm];
void init()
{
cin>>N>>M>>R;N++;
for(int i=1;i<=N;i++) A[i]=-inf;
int s,t,e;
for(int i=0;i<M;i++)
{
scanf("%d %d %d",&s,&t,&e);
I[i]=inter(pi(s,t),e);
}
sort(I,I+M);
}
void solve()
{
int ans=-inf,get;
for(inter*i=I;i!=I+M;i++)
{
get=Max(i->first.first-R);
get+=i->second;
Change(i->first.second,get);
}
ans=Max(N);
cout<<ans<<endl;
}
int main()
{
init();
solve();
}

3617 Problem F Best Cow Line

大意：

长度为N的一串字符，每次从两端取一个，放入新的字符串尾部，那么N次后字符串序最小的字符串是什么？

分析：

如果两端不一样的话就取小点的。。如果一样的话可以忽略看再里面一个么？

不是很清楚为什么。。不过A掉了。。就是说如果字符串正过来看比较小，就选左边的，如果倒过来看比较小，就选右边的。。

启示：

直觉阿。。不证明。。

Code：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<string>
using namespace std;
typedef string::iterator it;
typedef string::reverse_iterator rit;
const int maxn=2000;
int n,limit=5000000;
string a,ans;
bool cmp(it a,it b,rit c,rit d)
{
for(;a!=b;a++,c++)
{
if(*a<*c) return true;
if(*a>*c) return false;
}
return false;
}
int main()
{
scanf("%d",&n);char c;
for(int i=0;i<n;i++)
scanf("n%c",&c),a+=c;
it l=a.begin(),r=a.end();
rit rl=a.rbegin(),rr=a.rend();
while(l!=r)
{
if(cmp(l,r,rl,rr))
{
ans+=*l;
l++;rr–;
}
else
{
r–;rl++;
ans+=*r;
}
}
int now=0;
for(int i=0;i<n;i++)
{
now++;
printf("%c",ans[i]);
if(now==80) printf("n"),now=0;
}
if(now) printf("n");
}

3618 Problem G Exploration

水题。。不分析。。

Code：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<string>
using namespace std;
const int maxn=50000;
typedef pair<int,int> pi;
inline int abs(int x){return x>0?x:-x;}
int t,n,x;
pi X[maxn];
int main()
{
cin>>t>>n;
for(int i=0;i<n;i++)
{
scanf("%d",&x);
X[i]=pi(abs(x),x);
}
sort(X,X+n);int last=0;
for(int i=0;i<n;i++)
{
t-=abs(last-X[i].second);
if(t<0){cout<<i<<endl;return 0;}
last=X[i].second;
}
cout<<n<<endl;
}

3619 Problem H Speed Reading

水题。。直接数学计算。。

Code：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<utility>
using namespace std;
const int maxk=1000;
int n,k;
int time(int s,int t,int r)
{
int p=n/(s*t),ans;
if(p*s*t==n)
return (p-1)*(t+r)+t;
ans=p*(t+r);
int e=n-p*s*t;
ans+=((e-1)/s)+1;
return ans;
}
int main()
{
cin>>n>>k;
int s,t,r;
while(k–)
{
cin>>s>>t>>r;
cout<<time(s,t,r)<<endl;
}
}

3620 Problem I Avoid The Lakes

一个网格。。求最大的连续空格块的大小

直接DFS。。。

Code：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<utility>
#define Renew(x,c) x=max(x,c)
using namespace std;
const int maxn=100+10;
const int di[]={-1,0,1,0},dj[]={0,1,0,-1};
bool map[maxn][maxn]={0};
int n,m,k;
int dfs(int i,int j)
{
map[i][j]=false;int ans=1;
for(int ii,jj,d=0;d<4;d++)
{
ii=i+di[d];jj=j+dj[d];
if(map[ii][jj])
ans+=dfs(ii,jj);
}
return ans;
}
int main()
{
freopen("in","r",stdin);
cin>>n>>m>>k;int s,t;
while(k–)
{
cin>>s>>t;
map[s][t]=true;
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(map[i][j])
Renew(ans,dfs(i,j));
cout<<ans<<endl;
}

  3612 Problem A Telephone Wire   3613 Problem B Cow Relays   3614 Problem C Sunscreen   3615 Problem D Cow Hurdles   3616 Problem E Milking Time   3617 Problem F Best Cow Line   3618 Problem G Exploration   3619 Problem H Speed Reading   3620 Problem I Avoid The Lakes
这个什么Individual Practice的感觉还不错,确实满可以prrctice的。。
3612 Problem A Telephone Wire
大意：
一排N(1<N<100000)跟电线杆,每根的高Hi<=100,相邻两个接线的钱是他们高度差*C,
为了省钱，可以把一些电线杆变高，一根电线杆变高X要花X^2的钱。。求最少花多少钱。。
分析：
设DP[i][H]为1..i第i个长为H时的最小价格。。
那么DP[i][H](H>=Hi)=(H-Hi)^2+min(DP[i-1][k]+C*abs(k-H))
(k<=100)
是O(N*maxH^2)的。。必超。。
优化一下，DP[i][H]=(H-Hi)^2+
min( min(DP[i-1][k]+C*k-C*H)(k>=H),min(DP[i-1][k]+C*H-C*k)(k<H) )
故设A[i]=min(DP[i-1][k]-C*k)(k<i)
B[i]=min(DP[i-1]+C*k)(k>=i)
A和B可以线性推出来。。
从而复杂度就降到。。
O(N*maxH)了。。
启示：
有abs这种分段函数的时候可以分队考虑最优值。。。
Code:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Renew(x,c) x=min(x,c)
using namespace std;
const int maxh=100,maxn=100000,inf=~0U>>2;
int n,c,x,best[2][maxh+1],now,old,low[maxh+2],up[maxh+2];
inline int abs(int x){return x<0?-x:x;}
int main()
{
freopen("in","r",stdin);
cin>>n>>c>>x;
for(int i=1;i<x;i++)
best[0][i]=inf;
for(int i=x;i<=maxh;i++)
best[0][i]=(x-i)*(x-i);
for(int t=1;t<n;t++)
{
now=t%2;old=1-now;
int get;scanf("%d",&x);
for(int i=1;i<=maxh;i++) best[now][i]=inf;
memset(low,127,sizeof(low));
memset(up,127,sizeof(up));
for(int i=1;i<=maxh;i++)
low[i]=min(low[i-1],best[old][i]-c*i);
for(int i=maxh;i>=1;i–)
up[i]=min(up[i+1],best[old][i]+c*i);
for(int i=x;i<=maxh;i++)
{
best[now][i]=(i-x)*(i-x);
best[now][i]+=min(low[i]+c*i,up[i]-c*i);
}
}
int ans=inf;
for(int i=1;i<=maxh;i++) Renew(ans,best[now][i]);
cout<<ans<<endl;
}3613 Problem B Cow Relays
大意：
一个图，边数小于100，求S到E的经过N条边的最短路。。
分析：
这是很经典的矩阵乘法的题目，
大家都知道距离矩阵自乘N次就是长度为N的最短路，那么只要用二分算矩阵的N次方就OK了。。
启示：
矩阵乘法非常NB阿。。
Code：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<utility>
#include<stack>
#define Renew(x,c) x=min(x,c)
#define x first
#define y second
#define ss x.x
#define tt x.y
#define cc y
using namespace std;
const int maxt=1000+10,maxn=100+1,inf=~0U>>1;
typedef long long Board[maxn][maxn];
typedef pair<int,int> pi;
typedef pair<pi,int> edge;
struct Matrix
{
    Board M;int n;
    Matrix(int n):n(n)
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                M[i][j]=inf;
    }
    Matrix operator*(const Matrix&o)
    {
        Matrix ans(n);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                    Renew(ans.M[i][j],M[i][k]+o.M[k][j]);
        return ans;
    }
    void operator=(const Matrix&o)
    {
        memmove(M,o.M,sizeof(M));
        n=o.n;
    }
}*dist;
int Map[maxt]={0},N,s,t,cnt;
inline int get(int a)
{
    if(Map[a]==-1) Map[a]=cnt++;
    return Map[a];
}
void init()
{
    for(int i=1;i<maxt;i++)
        Map[i]=-1;
    int m;
    cin>>N>>m>>s>>t;cnt=0;
    stack<edge> S;
    while(m--)
    {
        int a,b,c;cin>>c>>a>>b;
        a=get(a);b=get(b);
        S.push(edge(pi(a,b),c));
    }
    dist=new Matrix(cnt);
    while(S.size())
    {
        edge i=S.top();S.pop();
        dist->M[i.ss][i.tt]=dist->M[i.tt][i.ss]=i.cc;
    }
    s=get(s);t=get(t);
}
Matrix Power(int n)
{ 
    if(n==1){return *dist;}
    Matrix ans=Power(n/2);
    ans=ans*ans;
    if(n%2==1)
        ans=ans*(*dist);
    return ans;
}
void solve()
{
    Matrix ans=Power(N);
    cout<<ans.M[s][t]<<endl;
}
int main()
{
    init();
    solve();
}

3614 Problem C Sunscreen
大意：改的XX点算了。。
每个男生的帅气值在1到1000之间，，
N个女生（N<=2500）第i个喜欢帅气值Lowi到Upi之间的男生。。
M种男生（M<=2500）第i个有Numi人，帅气值为Handsomei。。
这时男生得知WJMZBMR来了，为了不让帅帅的WJMZBMR（帅气值>2^128）
抢走女生的心。。他们马上开始行动了。。
问最多有多少个女生可以有男朋友呢？（不包括WJMZBMR。。。）
分析：
把男生按handsomei排序。。
一个个扫描过去，每个男生尽量匹配Upi小的女生（太小的先踢掉）。。
用一个heap维护就可以了。。
启示：
很多时候想贪心也是有方法的。。最重要的是降维和替代法。。
Code：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<utility>
#include<queue>
using namespace std;
typedef pair<int,int> pi;
int Cover[1000+1]={0},C;
pi Cs[2500],Bs[2500];
priority_queue<int> Q;
inline void ins(int x)
{ Q.push(-x); }
inline int top()
{ return -Q.top(); }
inline void pop()
{ Q.pop(); }
int main()
{
int L;cin>>C>>L;
for(int i=0;i<C;i++)
{
cin>>Cs[i].first>>Cs[i].second;
}
for(int i=0;i<L;i++)
{
cin>>Bs[i].first>>Bs[i].second;
}
sort(Cs,Cs+C);
sort(Bs,Bs+L);
pi*s=Cs;int ans=0;
for(pi*i=Bs;i!=Bs+L;i++)
{
while(s!=Cs+C&&s->first<=i->first)
ins(s->second),s++;
while(Q.size()&&top()<i->first)
pop();
while(i->second&&Q.size())
{
pop(),i->second–,ans++;
}
}
cout<<ans<<endl;
}

由于百度篇幅问题
只能开很多章了。。

水题。。直接DP。。

#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cstdlib>
using namespace std;
const int maxn=10000;
bool F[maxn]={0};
int main()
{
int n,x;F[0]=true;
for(int i=0;i<3;i++)
{
for(int t=maxn-1;t>=0;t–)
if(!F[t])
{
for(int j=0;j<100;j++)
{
x=j*j;if(x>t) break;
if(F[t-x]) {F[t]=true;break;}
}
}
}
cin>>n;
cout<<count(F,F+n+1,false)<<endl;
}