SPOJ QTREE2

阿阿阿阿阿阿阿阿。。。总算做出来了。。错误这一个那一个的,调试的快疯了。。
大意:
一棵带权树,有两种询问:
(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

赞赞阿。。
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位。。。

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

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

PKU 2008 Individual Practice 1 (1)

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

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

mipt 006

水题。。直接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;
}

mipt 004

很经典的题目了。。
一堆人。。有重量和力量之两个属性。。
要堆个塔,一个人头上的所有人重量之和不大于其力量。。
求塔最多能有几个人。。
很明显将人按重量+力量排序。。就可以满足无后效性。。
那么用树状数组维护一下DP的答案就OK了。。
#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cstdlib>
#define low(x) (x&(-x))
using namespace std;
typedef pair<int,int> pi;
const int maxs=2000000,maxn=100000;
int n;
pi C[maxs+100];
pi A[maxn];
inline void Renew(pi&x,pi c)
{
if(x.first>c.first) return;
if(x.first<c.first) {x=c;return;}
if(x.second>c.second) x=c;
}
void change(int l,pi d)
{
for(;l<=maxs;l+=low(l))
Renew(C[l],d);
}
pi Max(int l)
{
pi ans=pi(0,0);
for(;l>0;l-=low(l))
Renew(ans,C[l]);
return ans;
}
inline bool cmp(const pi&x,const pi&y)
{return x.first+x.second<y.first+y.second;}
int main()
{
cin>>n;
for(int i=1;i<=maxs;i++)
C[i].second=i,C[i].first=0;
for(int i=0;i<n;i++)
cin>>A[i].first>>A[i].second;
sort(A,A+n,cmp);pi get;int pos;int ans=0;
for(int i=0;i<n;i++)
{
get=Max(A[i].second);
pos=get.second+A[i].first;ans=max(ans,get.first+1);
change(pos,pi(get.first+1,pos));
}
cout<<ans<<endl;
}

mipt 005

没什么好说的。。直接模拟。。
(:加深1层,
):降低1层
数字: 叶子
直接算就OK了。。
注意一下cin.peek()可能会有用,它的作用是读下一个但不删除,
可以用来判断是否是'(‘和’)’。。
#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cstdlib>
using namespace std;
double pow[1000];
int main()
{
pow[0]=1;
for(int i=1;i<1000;i++)
pow[i]=pow[i-1]/2;
int cnt=0;double ans=0,x;
while(true)
{
while(cin.peek()==’ ‘)
cin.get();
if(cin.peek()=='(‘)
cnt++,cin.get();
else
{
if(cin.peek()==’)’)
cnt–,cin.get();
else
cin>>x,ans+=x*pow[cnt];
}
if(!cnt) break;
}
cout.setf(ios::fixed);
cout.precision(2);
cout<<ans<<endl;
}

mipt 003

开始作mipt了
大意:
给一个竞赛图(有向图,x和y要么x到y有边,要么y到x有边)。。
求哈密顿回路。。
图很密。。暴力dfs2.00s。。
我直接随机了。。0.02s。。
就是说随机一个序列,然后如果其中有两个相邻的没边的话,
交换一下位置就有边了。。但是可能导致其他的没边。。
但多随机调整几次就OK了。。
#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cstdlib>
using namespace std;
int n;const int maxn=200;
bool beat[maxn][maxn]={0};
void init()
{
cin>>n;char c;bool w;scanf("n");
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
cin>>c;w=(c==’+’);
beat[i][j]=w;
beat[j][i]=!w;
}
scanf("#n");
}
}
int t;
inline void swap(int&x,int&y)
{t=x;x=y;y=t;}
void print(int A[])
{
for(int i=0;i<n;i++)
cout<<A[i]+1<<" ";
cout<<endl;
exit(0);
}
void solve()
{
int A[maxn];
for(int i=0;i<n;i++)
A[i]=i;
int test=100;
while(test–)
{
random_shuffle(A,A+n);
int ti=100;
while(ti–)
{
bool can=true;
for(int i=0;i<n-1;i++)
if(!beat[A[i]][A[i+1]])
swap(A[i],A[i+1]),can=false;
if(can)
print(A);
}
}
}
int main()
{
srand(199581);
init();
solve();
}

Page 1 of 212