标签存档：数据结构

【题目大意】
有N个程序，每个数据有4个测试项。
给出每个程序在这4个测试项里的排名，(排名保证取遍1..N的每个数)，排名越前越牛X。
然后假设对于某一条程序，存在另外一条程序在4项中，有>=3项比它优，那么它就成为了SB程序。
问有多少个SB程序。
【算法分析】
先枚举地移走某一项，然后剩下的三项一起弄。（移走的那项暂时忽略，因为只需>=3个比它优）
这三项又可以按某一项排序，然后问题就变成了将给出N个二元对(Ai,Bi)，然后对于每个二元对，判断有没有出现在它之前的，且满足Ai然后我们可以以Ai为key值作树状数组的下标，然后就可以在lgN的复杂度内维护Ai<=K的点中，Bi最小是多少。然后再标记一下，问题就可以解决了。
【CODE】
#include #include #include const int N=100005;
int n;
int a[N][5],d[N][5],Q[N];
bool bad[N];

inline int cmp(const void *x,const void *y){return ((int *)x)[0]-((int *)y)[0];}

void solve(){
memcpy(d,a,sizeof(int)*5*(n+1));
qsort(d+1,n,sizeof(int)*5,cmp);
memset(Q,50,sizeof(int)*(n+1));
int i,res,j;
for (i=1;i<=n;i++){
res=0x7FFFFFFF;
j=d[i][1]-1;
while (j){
res j-=j&-j;
}
if (res j=d[i][1];
while (j<=n){
Q[j] j+=j&-j;
}
}
}

int main(){
scanf("%d",&n);
int i,j,k,tmp;
for (i=1;i<=n;i++){
a[i][4]=i;
for (j=0;j<4;j++)
scanf("%d",&a[i][j]);
}
for (k=0;k<4;k++){
for (i=1;i<=n;i++){
tmp=a[i][k]; a[i][k]=a[i][3]; a[i][3]=tmp;
}
solve();
for (int i=1;i<=n;i++){
tmp=a[i][k]; a[i][k]=a[i][3]; a[i][3]=tmp;
}
}
int ans=0;
for (int i=1;i<=n;i++)
if (bad[i]) ans++;
printf("%dn",ans);
for (int i=1;i<=n;i++)
if (bad[i]) printf("%dn",i);
}

【题目大意】

定义点与点之间的距离为max(|Xi-Xj|,|Yi-Yj|)

给定N个点，将这N个点中每个点与最近点的距离加起来，输出SUM。

【算法分析】

算法1：

算了下复杂度O(N^2)的话加些优化应该可以卡过。

于是我把他们按x排序，x相等的按y排序。

然后枚举当前点i，并向前和向后枚举点j，如果出现abs(X[j]-X[i])>=now （其它now为当前答案），那么可以break退出循环。（最优化剪枝）

然后这样就可以9000MS左右AC了。

算法2：

同算法1那样排序。

再按X坐标离散化。

然后枚举当前点i，并二分答案（当前最短距离）。

问题转化为看是否存在点(X[j],Y[j])，使得abs(X[j]-X[i])<=ANS 且 abs(Y[j]-Y[i])<=ANS

于是就可以以X轴为线段树所划分的区间建立一棵线段树，线段树上再建立一棵以Y坐标为key值的平衡树。

然后在上面进行查找。每次查找的复杂度是O((lgN)^2)。

加上二分答案，每个点的处理复杂度为O((lgN)^3)。

所以总时间复杂度为O(N (lgN)^3 )。

空间复杂度为O(NlgN)。

因为最同一深度的线段树区间下，一个点只能出现在一个区间内。所以一个点最多出现lgN次。所以空间复杂度不是问题。

但是这个算法编程复杂度可能比较高。如果用STL的

【其它】由于我不会STL，所以算法2就不写了。。。

【CODE】

#include #include #include #include #include using namespace std;
const int N=101111;
const int INF=0x7FFFFFFF;
int n;
struct type{int x,y;}L[N];
long long ans;

inline bool cmp(type x,type y){
    if (x.x    if (x.x>y.x) return false;
    if (x.y    return false;
}   

void input(){
    for (int i=1;i<=n;i++)
      scanf("%d%d",&L[i].x,&L[i].y);
    sort(&L[1],&L[n+1],cmp);
}   

void work(){
    ans=0;
    int i,j,now;
    for (i=1;i<=n;i++){
        now=INF;
       
        j=i-1;
        while (j){
            if (L[i].x-L[j].x>=now) break;
            now            j–;
        }   

        j=i+1;
        while (j<=n){
            if (L[j].x-L[i].x>=now) break;
            now            j++;
        }   
       
        ans+=now;
    }   
    cout << ans << endl;
}   

int main(){
    while (scanf("%d",&n)!=EOF){
        input();
        work();
    }   
}   

【题目大意】

有点已经成一个块了，让你加最少费用的边，使得它整个图成为一个连通块。

【算法分析】

经典最小生成树。

用并差集处理块，然后排序一下搞个kruskal。

但是很容易TLE。于是我加了那个启发式合并。

【其它】

尽管如此，我用G++交还是TLE,C++500多MS。

可能并差集写成非递归会好点。

【CODE】

#include #include #include #include #include #include using namespace std;
const int N=1000000;
int Tc,n,m,k,done,ans;
int f[N],d[N][3];
int num[N];

int gf(int p){
    if (f[p]==p) return p;
    f[p]=gf(f[p]);
    return f[p];
}

void input(){
    done=0; ans=0;
    int i,j,t,one,x;
    scanf("%d%d%d",&n,&m,&k);
    for (i=1;i<=n;i++){
        f[i]=i;
        num[i]=1;
    }
    for (i=1;i<=m;i++)
      scanf("%d%d%d",&d[i][0],&d[i][1],&d[i][2]);
    for (i=1;i<=k;i++){
        scanf("%d%d",&t,&one);
        for (j=1;j          scanf("%d",&x);
          if (gf(x)!=gf(one)){
            if (num[f[x]]                num[f[one]]+=num[f[x]];
                f[f[x]]=f[one];
            }
            else{
                num[f[x]]+=num[f[one]];
                f[f[one]]=f[x];
            }
            done++;
          }
        }
    }
}

int cmp(const void *x,const void *y){
    return ((int *)x)[2]-((int *)y)[2];
}

void work(){
    if (done==n-1) return;
    qsort(d[1],m,sizeof(int)*3,cmp);
    for (int i=1;i<=m;i++){
      int &x=d[i][0],&y=d[i][1];
      if (gf(x)!=gf(y)){
          if (num[f[x]]              num[f[y]]+=num[f[x]];
              f[f[x]]=f[y];
          }
          else{
              num[f[x]]+=num[f[y]];
              f[f[y]]=f[x];
          }

          done++;
          ans+=d[i][2];
          if (done==n-1) return;
      }
    }
}

void output(){
    if (done==n-1) printf("%dn",ans);
              else printf("-1n");
}

int main(){
    cin >> Tc;
    for (int i=1;i<=Tc;i++){
        input();
        work();
        output();
    }
}

【题库地址】https://www.spoj.pl/

进去找685就好，直接发地址的好像没有登录是看不了的。

【题目大意】

给定一个序列Ai，让你把他分成K组，使得每一组的和不超过M，问M最小能是多少？

1<=N<=15000

-30000<=Ai<=30000

【算法分析】

可以用数学归纳法证明：假设已经确定了M，然后设能构成合法分组的最小组数为min，能构成合法分组的最大组数为max，那么对于x∈[min,max]，则x必然存在一个合法分组方式。（即解的连续性）

然后剩下的就是动态规划。

Fmin[i]为A1..Ai这个序列，最少能划分为多少组，使之成为一个合法序列。

然后Fmin[i]=min{Fmin[j]+1} (s[i]-s[j]<=M)

同理Fmax也一样求。

然后转移那个地方用一个平衡树维护一下就好，平衡树以s[i]为key值，然后上面加一个类似线段树的标记，然后随时更新就好。

【其它】1A。

这题一点思路都没有，只能找GXX大神要解题报告了

Orz GXX 大神。。。

【CODE】

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
const int N=15111;
const int INF=1000000000;
int n,part;
int Fmax[N],Fmin[N],a[N],s[N],nowi;
struct SBTtype{
       struct point{int l,r,zz,Min,Max,s;}tr[N];
       int tot,root;
      
       inline void update(int &p){
              if (!p) return;
              tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
              tr[p].Min=Fmin[tr[p].zz];
              if (tr[p].l && tr[tr[p].l].Min<tr[p].min) tr[p].min=”tr[tr[p].l].Min;<br”>              if (tr[p].r && tr[tr[p].r].Min<tr[p].min) tr[p].min=”tr[tr[p].r].Min;<br”>              tr[p].Max=Fmax[tr[p].zz];
              if (tr[p].l && tr[tr[p].l].Max>tr[p].Max) tr[p].Max=tr[tr[p].l].Max;
              if (tr[p].r && tr[tr[p].r].Max>tr[p].Max) tr[p].Max=tr[tr[p].r].Max;
       }
      
       void left(int &p){
            int k=tr[p].r;
            tr[p].r=tr[k].l;
            tr[k].l=p;
            update(p);
            update(k);
            p=k;
       }
      
       void right(int &p){
            int k=tr[p].l;
            tr[p].l=tr[k].r;
            tr[k].r=p;
            update(p);
            update(k);
            p=k;
       }
      
       void repair(int &p){
            if (!p) return;
            bool flag=false;
            if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
              right(p);
              flag=true;
            }
            if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
              left(tr[p].l);
              right(p);
              flag=true;
            }
            if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
              left(p);
              flag=true;
            }
            if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
              right(tr[p].r);
              left(p);
              flag=true;
            }
            if (flag){
              repair(tr[p].l);
              repair(tr[p].r);
              repair(p);
            }
       }
      
       void ins(int &p,int i){
            if (!p){
              p=++tot;
              tr[p].l=0; tr[p].r=0; tr[p].zz=i;
              update(p);
            }
            else{
              tr[p].s++;
              if (s[i]<s[tr[p].zz]) ins(tr[p].l,i);<br=””>                               else ins(tr[p].r,i);
              update(p);
              repair(p);
            }
       }
      
       int Findmin(int &p,int key){
           if (!p) return INF;
           if (s[tr[p].zz]<key) return=”” findmin(tr[p].r,key);<br=””>           int re=Findmin(tr[p].l,key);
           re=min(re,Fmin[tr[p].zz]);
           if (tr[p].r) re=min(re,tr[tr[p].r].Min);
           return re;
       }
      
       int Findmax(int &p,int key){
           if (!p) return -INF;
           if (s[tr[p].zz]<key) return=”” findmax(tr[p].r,key);<br=””>           int re=Findmax(tr[p].l,key);
           re=max(re,Fmax[tr[p].zz]);
           if (tr[p].r) re=max(re,tr[tr[p].r].Max);
           return re;
       }
}sbt;</key)></key)></s[tr[p].zz])></tr[p].min)></tr[p].min)></iostream>
</cstring>
</cstdlib>
</cstdio>

void init(){
     scanf(“%d%d”,&n,&part);
     for (int i=1;i<=n;i++) scanf(“%d”,&a[i]);
     for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
}

bool can(int M){
     sbt.root=0; sbt.tot=0;
     sbt.ins(sbt.root,0);
     for (nowi=1;nowi<=n;nowi++){
         Fmin[nowi]=sbt.Findmin(sbt.root,s[nowi]-M)+1;
         Fmax[nowi]=sbt.Findmax(sbt.root,s[nowi]-M)+1;
         sbt.ins(sbt.root,nowi);
     }
     if (Fmin[n]<=part && part<=Fmax[n]) return true;
     return false;
}

void work(){
     int l=-INF,r=INF,mid;
     while (l<r){
           mid=(l+r)>>1;
           if (can(mid)) r=mid;
                    else l=mid+1;
     }
     printf(“%dn”,l);
}</r){

int main(){
//    freopen(“input.txt”,”r”,stdin);
//    freopen(“output.txt”,”w”,stdout);
    int Tc;
    cin >> Tc;
    for (int i=0;i<tc;i++){
        init();
        work();
    }
    return 0;
}</tc;i++){

 

【题目大意】

同银河英雄传说。。。

【算法分析】

并差集之~

这题更简单，直接输出s[i]即可。

【其它】1A

。。。无意水，是在找银河英雄传说的提交网站时无意碰到的。。。

【CODE】

#include #include #include const int n=30000;
int T;
int f[31111],s[31111],tail[31111];
char c;

int gf(int x){
    if (f[x]==x) return x;
    int tf=gf(f[x]);
    s[x]+=s[f[x]];
    f[x]=tf;
    return tf;
}   

void Union(){
    int x,y;
    scanf("%d%d",&y,&x);
    gf(x); gf(y);
    s[f[y]]=1;
    int fy=f[y];
    f[f[y]]=tail[f[x]];
    tail[f[x]]=tail[fy];
}   

void Count(){
    int x;
    scanf("%d%d",&x);
    gf(x);
    printf("%dn",s[x]);
}   

int main(){
    for (int i=1;i<=n;i++){
        f[i]=i;
        s[i]=0;
        tail[i]=i;
    }   
    scanf("%d",&T);
    for (int i=1;i<=T;i++){
        c=getchar();
        while (c==’ ‘ || c==’n’) c=getchar();
        if (c==’M’) Union();
               else Count();
    }   
}