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

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

很经典的题目了。。
一堆人。。有重量和力量之两个属性。。
要堆个塔，一个人头上的所有人重量之和不大于其力量。。
求塔最多能有几个人。。
很明显将人按重量+力量排序。。就可以满足无后效性。。
那么用树状数组维护一下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;
}

没什么好说的。。直接模拟。。
(：加深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了
大意:
给一个竞赛图(有向图，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();
}

BT阿。。这明明就是IMO1996年的竞赛题阿。。
设A={1..p},B={p+1..2*p}
那么A和B是一种选法。。
然后对于其他的每一种选法。必然有A也有B。。
那么把它的全体B中的数+1、+2、+3、。。、+p-1由于p是素数。。
所以必有p-1个和模p不为0的选法与其对应。。
于是答案就是(C(2n,n)-2)/p+2。。。
高精写次了。。用Java算了答案后交了个表。。

1986.Distance Queries
大意：
给一颗树。。每次询问两点之间的距离。。
很明显是要求lca的。。又不是要求在线算法。。于是我就用tarjan了。。
#include<cstdio>
#include<utility>
#include<vector>
using namespace std;
const int maxn=40000;
typedef pair<int,int> pi;
int F[maxn];
inline void makeset(int x)
{
F[x]=x;
}
int find(int x)
{
if(x!=F[x]) F[x]=find(F[x]);
return F[x];
}
void Union(int x,int y)
{
x=find(x);y=find(y);
F[y]=x;
}
int cnt=0;
vector<pi> Ask[maxn],E[maxn];
int Ans[maxn],Dep[maxn];
bool vis[maxn]={0};
void addQuery(int x,int y)
{
Ask[x].push_back(pi(y,cnt));
Ask[y].push_back(pi(x,cnt));
cnt++;
}
void addEdge(int s,int t,int c)
{
E[s].push_back(pi(t,c));
E[t].push_back(pi(s,c));
}
int n,m,k;
void dfs(int x,int dep)
{
vis[x]=true;
Dep[x]=dep;
makeset(x);
for(int v,i=0;i<E[x].size();i++)
if(!vis[v=E[x][i].first])
{
dfs(v,dep+E[x][i].second);
Union(x,v);
}
for(int lca,v,i=0;i<Ask[x].size();i++)
if(vis[v=Ask[x][i].first])
{
lca=find(v);
Ans[Ask[x][i].second]=Dep[x]+Dep[v]-2*Dep[lca];
}
}
int main()
{
scanf("%d %d",&n,&m);
int s,t,l;char c;
while(m–)
{
scanf("%d %d %d %c",&s,&t,&l,&c);s–;t–;
addEdge(s,t,l);
}
scanf("%d",&k);
for(int i=0;i<k;i++)
{
scanf("%d %d",&s,&t);s–;t–;
addQuery(s,t);
}
dfs(0,0);
for(int i=0;i<k;i++)
{
printf("%dn",Ans[i]);
}
}1987.Distance Statistics
这道有点意思：
给一颗树。。求出其中距离不超过K的点有多少对。。
明显是要用分治。。首先多叉转二叉。。所有点到兄弟的边长度都为0。。
之所以要多叉转二叉是因为如果不转的话。。有些情况（例如星形树。。）你就悲剧了。。
这样两点之间的距离还是不变的。。
然后用基于边的分支。。每次找出中心边。。再分成两棵子树。。
然后两个点都在子树内部的可以递归解决。。需要算的是两个点在不同子树的。。
两个子树所有节点都按到根的距离排序。。然后就可以扫描了。。
可惜我的Code写次了。。时间超了1倍。。需要去改改。。
没AC就不发了。。