因为是小高考期间写的代码,所以有浓厚的小高考风格

这一篇里复习了辩证法除了矛盾观以外的几乎所有知识..?

题意:

给你个n*m的区域,你需要回答:

在第d年,经济指数是a的时候,求总收入

收入计算:2^Bits(每一个岛屿的大小&a)

Bits(x)表示x中1的个数

第x年,海拔<=x的沿海的地方全要被淹掉(注意样例中中心地区因为不沿海淹不掉)

//请用唯物辩证法来分析下列程序

分两步

第一步,计算淹没时间,算法为dfs

第二步,计算收入,大概要排序离线乱搞

代码如下,看代码好理解吧:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
int count_one[250005];
struct cell
{
    //联系具有普遍性客观性多样性,我们要用联系的观点看问题 
    int id;
    int height;
    friend bool operator < (const cell &a,const cell &b)
    {
        return a.height<b.height;
    }
    int code(int x,int y)
    {
        return x*m+y;
    }
    int decode_x()
    {
        return id/m;
    }
    int decode_y()
    {
        return id%m;
    }
};
struct query
{
    //整体统帅部分,具有部分所没有的作用,我们要树立全局观念 
    int id;
    int a;
    int d;
    friend bool operator < (const query &a,const query &b)
    {
        return a.d>b.d;
    }
    void input()
    {
        scanf("%d%d",&d,&a);
    }
};
query c[10005];
cell b[250005];
int a[505][505];
int visit[505][505];
int size[250005];
int father[250005];
int ans[10005];
map<int,int> ma;
void delete_size(int x)
{
    //关键部分对整体功能甚至具有决定作用,我们不能忽视部分的作用 
    ma[x]--;
    if (ma[x]==0)
    {
        ma.erase(ma.find(x));
    }
}
int findroot(int x)
{
    //事物发展的道路是曲折的,前途是光明的,我们要坚持曲折性与前进性相统一 
    int root;
    for (root=x;father[root]!=-1;root=father[root]) ;
    for (;father[x]!=-1;)
    {
        int temp=father[x];
        father[x]=root;
        x=temp;
    }
    return root;
}
void u(int x,int y)
{
    //量变引起质变,我们要重视量的积累,抓住时机促成质变 
    x=findroot(x);
    y=findroot(y);
    if (x==y) return;
    if (size[x]>size[y]) swap(x,y);
    delete_size(size[x]);
    delete_size(size[y]);
    father[x]=y;
    size[y]+=size[x];
    ma[size[y]]++;
}
void dfs(int x,int y,int id)
{
    //辩证否定是事物自身的否定,即自己否定自己,自己发展自己 
    if (x<0) return;
    if (y<0) return;
    if (x>=n) return;
    if (y>=m) return;
    if (visit[x][y]!=1) return;
    a[x][y]=id;
    visit[x][y]=2;
    dfs(x+1,y,id);
    dfs(x-1,y,id);
    dfs(x,y+1,id);
    dfs(x,y-1,id);
}
bool unok(int x,int y)
{
    //辩证否定是联系的环节,也是发展的环节 
    if (x<0) return true;
    if (y<0) return true;
    if (x>=n) return true;
    if (y>=m) return true;
    if (visit[x][y]==2) return true;
    return false;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    //辩证否定的实质是"扬弃",我们要树立创新意识 
    int i;
    for (i=0;i<=250000;i++)
    {
        int j;
        for (j=0;j<31;j++)
        {
            if ((1<<j)&i) count_one[i]++;
        }
    }
    for (;;)
    {
        if (scanf("%d%d",&n,&m)==-1) break;
        int i;
        for (i=0;i<n;i++)
        {
            int j;
            for (j=0;j<m;j++)
            {
                scanf("%d",&a[i][j]);
                b[i*m+j].height=a[i][j];
                b[i*m+j].id=i*m+j;
            }
        }
        sort(b,b+n*m);
        memset(visit,0,sizeof(visit));
        for (i=0;i<n*m;i++)
        {
            int x=b[i].decode_x();
            int y=b[i].decode_y();
            int z=b[i].height;
            visit[x][y]=1;
            if ((unok(x-1,y))||(unok(x+1,y))||(unok(x,y-1))||(unok(x,y+1)))
            {
                dfs(x,y,z);
            }
        }
        for (i=0;i<n*m;i++)
        {
            b[i].height=a[b[i].decode_x()][b[i].decode_y()];
            size[i]=1;
            father[i]=-1;
        }
        sort(b,b+n*m);
        #ifdef absi2011
        //矛盾的普遍性是指事事有矛盾,时时有矛盾,我们要敢于揭露矛盾 
        for (i=0;i<n;i++)
        {
            int j;
            for (j=0;j<m;j++)
            {
                printf("%d ",a[i][j]);
            }
            printf("\n");
        }
        //矛盾的特殊性是指事物及其每一个侧面各有其特点,我们要具体问题具体分析 
        #endif
        int q;
        scanf("%d",&q);
        for (i=0;i<q;i++)
        {
            c[i].input();
            c[i].id=i;
        }
        sort(c,c+q);
        int j=n*m-1;
        for (i=0;i<q;i++)
        {
            for (;j>=0&&b[j].height>c[i].d;j--)
            {
                int x=b[j].decode_x();
                int y=b[j].decode_y();
                visit[x][y]=3;
                ma[1]++;
                if (!unok(x,y+1)) u(b[j].id,b[0].code(x,y+1));
                if (!unok(x,y-1)) u(b[j].id,b[0].code(x,y-1));
                if (!unok(x+1,y)) u(b[j].id,b[0].code(x+1,y));
                if (!unok(x-1,y)) u(b[j].id,b[0].code(x-1,y));
            }
            map<int,int>::iterator ii;
            int sum=0;
            for (ii=ma.begin();ii!=ma.end();ii++)
            {
                sum+=(1<<count_one[(*ii).first&c[i].a])*(*ii).second;
            }
            ans[c[i].id]=sum;
        }
        for (i=0;i<q;i++)
        {
            printf("%d\n",ans[i]);
        }
        ma.clear();
    }
    return 0;
}