题解

8 条题解

  • 2
    @ 2015-04-19 15:51:39

    4.琵琶湖
    对于T次讯问,倒叙考察之。则问题变成了水面不断下降的情况。这个时候,每一单位时间,会有额外的格子露出水平,并有可能合并原有的不相连的区域。这样的问题可以被描述为对若干集合进行合并,用并查集是最高效的处理方案。总的时间复杂度为O(TlogT+nm)。
    暴力的方法可以在这一题中得到20分。而对于n<=1的情况,我们知道任意时间每一个连通块总是单连通的。所以可以利用链表来维护,从而得到这额外的40分部分分。

  • 1
    @ 2017-05-28 07:52:23
  • 1
    @ 2015-10-23 18:31:04

    #include<cstdio>
    #include<cctype>
    #include<algorithm>
    using namespace std;
    const int maxn = 1000*1000+5;
    int n, m, T, u, c = 1, v, t, x[maxn], y[maxn], a[maxn], pa[maxn], M[1000+5][1000+5];
    int e[maxn];
    pair<int, int>P[maxn];
    int findset(int x){return pa[x] == x ? x : pa[x] = findset(pa[x]);}
    int read(){
    char t = getchar();
    while(!isdigit(t))t = getchar();
    int r = 0;
    while(isdigit(t)){
    r = r*10+t-'0';
    t = getchar();
    }
    return r;
    }
    int main()
    {
    n = read(), m = read();
    for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
    u = read();
    M[i][j] = u;
    P[c] = make_pair(u, c);
    x[c] = i, y[c] = j;
    c++;
    }
    }
    for(int i = 1; i < c; i++)pa[i] = i;
    T = read(); t = T;
    for(int i = 1; i <= T; i++)a[i] = read();
    sort(P, P+c), c--;
    int count = c, co = 0;
    while(T > 0 && c > 0){
    while(T > 0&&P[c].first <= a[T]){e[T] = count-c-co; T--;}
    while(c > 0&&P[c].first > a[T]){
    int k = P[c].second;
    int X = x[k], Y = y[k];
    if(X - 1 >= 0 && M[X-1][Y] > a[T]){
    u = findset(k), v = findset(k-m);
    if(u != v){pa[u] = v; co++; }
    }
    if(Y - 1 >= 0 && M[X][Y-1] > a[T]){
    u = findset(k), v = findset(k-1);
    if(u != v){pa[u] = v; co++; }
    }
    if(X + 1 < n && M[X+1][Y] > a[T]){
    u = findset(k), v = findset(k+m);
    if(u != v){pa[u] = v; co++; }
    }
    if(Y + 1 < m && M[X][Y+1] > a[T]){
    u = findset(k), v = findset(k+1);
    if(u != v){pa[u] = v; co++; }
    }
    c--;
    }
    }
    while(T)e[T--] = 1;
    for(int i = 1; i <= t; i++){
    printf("%d", e[i]);
    if(i != t)printf(" ");
    }
    return 0;
    }

  • 1
    @ 2015-10-17 21:19:20

    #include<algorithm>
    #include<iostream>
    #include<stdio.h>
    using namespace std;

    int dir[2][5]={{1,-1,0,0},{0,0,1,-1}};

    int n,m;
    int h[1005][1005];
    int father[1000005];
    typedef pair<int,int> nodexy;
    inline nodexy getxy(int t){
    return make_pair((t-1)/m+1,(t-1)%m+1);
    }
    inline int getrl(int x,int y){
    return (x-1)*m+y;
    }
    int T,t[100005];
    int ans[100005];
    int head[100005];
    int NEXT[1000005];

    int find(int x){
    if(father[x]==x) return x;
    father[x]=find(father[x]);
    return father[x];
    }

    int main(){
    cin>>n>>m;
    int i,j;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    { scanf("%d",&h[i][j]);}
    cin>>T;
    for(i=1;i<=T;i++)
    { scanf("%d",&t[i]);}
    int x,y,k;
    nodexy xy;
    for(i=1;i<=n*m;i++)
    { x=(i-1)/m+1; y=(i-1)%m+1;
    int bot=0,top=T,mid=T/2;
    while(bot<top)
    { if(t[mid]<h[x][y])
    { bot=mid;}
    else
    { top=mid-1;}
    mid=(bot+top+1)/2;
    }
    h[x][y]=mid;
    NEXT[i]=head[mid];
    head[mid]=i;
    }
    for(i=T;i>=1;i--)
    { k=head[i];
    ans[i]=ans[i+1];
    while(k)
    { ans[i]++;
    father[k]=k;
    k=NEXT[k];}
    k=head[i];
    int x1,y1,f0,f1;
    while(k)
    { xy=getxy(k);
    x=xy.first;
    y=xy.second;
    for(j=0;j<4;j++)
    { x1=x+dir[0][j];
    y1=y+dir[1][j];
    if(x1>=1&&x1<=n&&y1>=1&&y1<=m){
    f0=find(getrl(x,y));
    f1=find(getrl(x1,y1));
    if(f0!=f1&&f0&&f1){
    ans[i]--;
    father[f0]=f1;
    }}
    }
    k=NEXT[k];
    }
    }
    for(i=1;i<=T;i++)
    printf("%d ",ans[i]);
    return 0;
    }

  • 1
    @ 2015-08-25 10:40:57

    请联系我,,,数据,,dllp555@163.com

  • 1
    @ 2015-08-25 10:40:17

    有没有测试数据啊。。。

  • 0
    @ 2017-09-17 20:47:27

    肯定是要引用 “doc小姐姐” 的题解啦 (快去上面赞她!)

    “ 对于T次讯问,倒叙考察之。 则问题变成了水面不断下降的情况 。这个时候,每一单位时间,会有额外的格子露出水平,并有可能合并原有的不相连的区域。这样的问题可以被描述为 对若干集合进行合并 ,用 并查集 是最高效的处理方案。总的时间复杂度为O(TlogT+nm)。 ”

    细节一下 ,可知,倒叙操作时,假如新出现的小方格周围全是海洋,那么它就能提供一个答案值(当成一个小块)。
    接着,我们易知, 每次的方格更新最多只会联通它四个方向上的块 ,所以我们 不需要对整个方格整体进行扫描 ,只需要让当前格 与四个方向上块依次进行合并(还没出现的块不合并) 。当发现他们在同一个块上时,不操作。但他们分别属于不同块时,将其合并,并将答案值减一即可。

    #include <vector>
    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    struct QUESTION {
        int id, h;
    };
    struct POINT {
        int x, y, h;    
    };
    int N, M, T;
    vector<POINT> A;
    vector<QUESTION> B;
    int Cnt, Ans[100005], Fa[1000005], Vis[1000005], Dx[5]={0, 0, 1, 0, -1}, Dy[5]={0, -1, 0, 1, 0};
    int ID (int x, int y) {
        if (x<1||x>N||y<1||y>M) return 0;
        return (x-1)*M+y;
    }
    bool QUESTIONCMP (QUESTION a, QUESTION b) {
        return a.h>b.h;
    }
    bool POINTCMP (POINT a, POINT b) {
        return a.h>b.h;
    }
    void INIT () {
        for(int i=1; i<=N*M; i++) Fa[i]=i;
    }
    int FIND (int x) {
        return x==Fa[x]?x:Fa[x]=FIND(Fa[x]); 
    } 
    void UNION (int a, int b) {
        int fa=FIND(a), fb=FIND(b); 
        if (fa==fb) return;
        Fa[fa]=fb;
        Cnt--;
    }
    int main () {
    
        ios::sync_with_stdio(false);
        cin >> N >> M;
        for(int i=1; i<=N; i++)
            for(int j=1, h; j<=M; j++) {
                cin >> h;
                A.push_back((POINT){i, j, h}); 
            }
        cin >> T;
        for(int i=1, h; i<=T; i++) {
            cin >> h;   
            B.push_back((QUESTION){i, h});
        }
        sort(A.begin(), A.end(), POINTCMP);
        sort(B.begin(), B.end(), QUESTIONCMP);
        INIT();
        int k=0;
        for(int i=0; i<T; i++) {
            while(k<A.size()&&A[k].h>B[i].h) {
                int id1=ID(A[k].x, A[k].y);
                if (!Vis[id1]) {
                    Vis[id1]=1;
                    Cnt++;
                    for(int j=1; j<=4; j++) {
                        int id2=ID(A[k].x+Dx[j], A[k].y+Dy[j]);
                        if (Vis[id2]) UNION(id1, id2);
                    }
                }
                k++;
            }
            Ans[B[i].id]=Cnt;   
        }
        for(int i=1; i<=T; i++) cout << Ans[i] << " ";
        return  0;
        
    }
    
  • 1

信息

ID
1944
难度
7
分类
(无)
标签
递交数
502
已通过
81
通过率
16%
上传者