hiho的每周一题都不会很难，基本上就是一些很裸和经典的问题，这一次写了几道分冶专题的题，做个总结。
分冶最简单的就是二分，二分说简单，很简单，不过7,8行代码，不过也常常写挂，写成无限循环。
直接看题1128
http://hihocoder.com/problemset/problem/1128
很裸的直接二分查找，但是其中的第二种写法，事实上是很不实用的，未排序数组的二分查找，有一丝手写快排的味道，当然这道题直接可以在O（N）的复杂度便历得出结果。每次在2分过程中通过把比x小的数放x左边，把x大的数放x右边的方式，在边排序中边二分查找，效率不比直接排序二分高多少，但思想不错。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
int n,k;
int a[1000005];
int p(int l,int r)
{
int k=a[r];
for(int i=l;i<r;i++)
{
if(a[i]<=a[r])
{
swap(a[i],a[l]);
l++;
}
}
swap(a[l],a[r]);
return l;
} int bs(int *a,int n,int k)
{
int l=0;
int r=n-1;
while(l<=r)
{
int mid=p(l,r);
if(a[mid]==k)
return mid;
else if(a[mid]<k)
l=mid+1;
else
r=mid-1;
}
return -1;
}
int main()
{
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
int t=bs(a,n,k);
if(t==-1)
printf("%d\n",t);
else
printf("%d\n",t+1);
}
1133这道题http://hihocoder.com/problemset/problem/1133
找第k小的数
滚动数组，也算是手排加二分吧。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
int n,k,c;
int a[2][1000005];
int p(int l,int r,int c)
{
int k=a[1-c][r];
int lf=l;
int rf=r;
for(int i=l;i<r;i++)
{
if(a[1-c][i]<k)
{
a[c][lf++]=a[1-c][i];
}
else if(a[1-c][i]>k)
{
a[c][rf--]=a[1-c][i];
}
a[c][lf]=k;
}
return lf;
} int bs(int n,int k)
{
int l=0;
int r=n-1;
c=1;
while(l<=r)
{
int mid=p(l,r,c);
if(l==r)
c=1-c;
if(mid==k)
return a[c][mid];
else if(mid<k)
l=mid+1;
else
r=mid-1;
c=1-c;
}
return -1;
} int main()
{
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&a[0][i]);
}
int t=bs(n,k-1);
printf("%d\n",t);
}
1139http://hihocoder.com/problemset/problem/1139
二分判断，每次二分判断是否能符合题目的要求，这道题让我重新回忆了如何链式前向星建图，由于bfs O（N+E）的复杂度完全可以接受，就直接bfs搞起，写的很不熟练，也码了很长时间。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define ll long long
int n,m,k,kk,u,v,w;
int head[10005];
int vis[10005];
int cnt=0;
struct edge
{
int v,w,next;
edge() {};
edge(int x,int y,int ww):v(x),w(y),next(ww){};
}e[200005]; struct node
{
int u,cc;
node() {};
node(int x,int y):u(x),cc(y){};
};
queue<node> q;
void add_edge(int u,int v,int w)
{
e[cnt]=edge(v,w,head[u]);
head[u]=cnt++;
} bool bfs(int key)
{
// printf("cas %d\n",key);
memset(vis,0,sizeof(vis));
while(!q.empty())
q.pop();
q.push(node(1,0));
vis[1]=1;
while(!q.empty())
{
node t=q.front();
q.pop();
for(int xx=head[t.u];xx!=-1;xx=e[xx].next)
{
int v=e[xx].v;
if(e[xx].w<=key&&t.cc+1<=k)
{
if(v==kk)
return 1;
if(vis[v])
continue;
q.push(node(v,t.cc+1));
vis[v]=1;
}
}
}
return 0;
} int main()
{
// freopen("input.txt","r",stdin);
memset(head,-1,sizeof(head));
scanf("%d%d%d%d",&n,&m,&k,&kk);
int mm=-1;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,w);
mm=max(w,mm);
}
if(n==1)
{
printf("0\n");
return 0;
}
int l=0,r=mm;
while(l<r)
{
int mid=(r+l)/2;
if(bfs(mid))
{
r=mid;
}
else
l=mid+1;
}
printf("%d\n",l);
}
1141http://hihocoder.com/problemset/problem/1141
逆序对，老问题，常用方法就归并排序和树状数组，这两个方法都写一次。
并归排序就是先通过递归二分，再合并，类似后序便历，然后在合并的过程中求出逆序对的个数。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define ll long long
int n;
int a[100005];
int temp[100005];
ll res=0;
void pp(int l,int mid,int r)
{
int lf=l,rf=mid,ls=mid+1,rs=r;
int ans=0;
while(lf<=rf&&ls<=rs)
{
if(a[lf]<=a[ls])
{
temp[ans++]=a[lf++];
res+=(ls-mid-1);
}
else
{
temp[ans++]=a[ls++];
}
}
while(lf<=rf)
{
temp[ans++]=a[lf++];
res+=(ls-mid-1);
}
while(ls<=rs)
{
temp[ans++]=a[ls++];
}
for(int i=0;i<ans;i++)
a[l+i]=temp[i];
} void merge_sort(int l,int r)
{
if(l<r)
{
int mid=(l+r)/2;
merge_sort(l,mid);
merge_sort(mid+1,r);
pp(l,mid,r);
}
} int main()
{
//freopen("input.txt","r",stdin);
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
merge_sort(0,n-1);
cout<<res<<endl;
}
树状数组：
树状数组就是这样的一种数据结构,原理类似多重背包的二进制做法，都把O（N)的复杂度简化到log的复杂度。
目前只会单点修改，查询区间。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<queue>
#include<set>
using namespace std;
#define ll long long
int n; struct node
{
int pos,val,cc;
}a[100005];
int r[100005];
int c[100005];
bool cmp(node a,node b)
{
return a.val<b.val;
} int lowbit(int x)
{
return x&(-x);
} void add(int i,int v)
{
while(i<=n)
{
c[i]+=v;
i+=lowbit(i);
}
} ll getsum(int x)
{
ll sum=0;
while(x)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
//freopen("a+b.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].val);
a[i].pos=i;
}
sort(a+1,a+n+1,cmp);
r[a[1].pos]=1;
for(int i=2;i<=n;i++)
{
if(a[i].val==a[i-1].val)
r[a[i].pos]=r[a[i-1].pos];
else
r[a[i].pos]=r[a[i-1].pos]+1;
}
ll ans=0;
for(int i=1;i<=n;i++)
{
add(r[i],1);
ans+=i-getsum(r[i]);
}
cout<<ans<<endl;
}
注意离散化的时候同样大的数值一样。
1142 三分
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define ll long long
int a,b,c,x,y;
const double eps=1e-8;
double dis(double xx)
{
double yy=(a*xx*xx+b*xx+c);
return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
} int main()
{
//freopen("input.txt","r",stdin);
scanf("%d%d%d%d%d",&a,&b,&c,&x,&y);
double lf=-200,rf=200,midf,midr;
while(rf-lf>eps){
midf=(lf*2+rf)/3;
midr=(lf+rf*2)/3;
if(dis(midf)<dis(midr))
rf=midr;
else
lf=midf;
}
printf("%.3f\n",dis(lf));
}
简单的说啊，首尾a,b;取两个三分点，然后如果求最小值，答案肯定包括小的那一段，求最大值，包括大的那一段。