题解 P1047 【校门外的树】

2018-05-23 20:12:12


校门外的树下,是曾经纯真少年的懵懂模拟,今日再遇,又是何处思绪涌上心头,愿不朽如AC图标般万年长青。

这种区间问题啊,普通暴力不行,那就简洁分块吧(逃

详情看代码,一边看代码,一边看注释,效果好一点

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,ll,rr,block,num,tot;
bool alive[10003];
int l[103],r[103],belong[10003],sum[103];
int main()
{
  scanf("%d%d",&n,&m);//读入
  tot=n+1;//tot表示目前还存在几棵树,由于包括0端点,所以n要加1
  block=sqrt(n);//表示需要分成几块,至于为什么分成根号n块,我也不知道……
  for (int i=1;i<=block;i++)
  {
    l[i]=block*(i-1);//表示第i块的左端点
    r[i]=block*i-1;//表示第i块的右端点
    sum[i]=block;//表示第i块拥有树的个数
    for (int j=block*(i-1);j<=block*i-1;j++)
     belong[j]=i;
  }
  for (int i=block*block;i<=n;i++)//由于可能存在最后一块所拥有树的个数
  //不一定和前面每一块一样,所以需要单独处理。比如5课被分成两块:2棵和2棵,那么
  //最后一块就只有1棵了,所以需要单独处理一下。
  {
   belong[i]=block;
   sum[block]++; 
  }
  r[block]=n;//显然最后一块的右端点应该是n
  for (int i=1;i<=m;i++)
   {
     scanf("%d%d",&ll,&rr);//读入需要移树的区间
     for (int j=ll;j<=rr;j++)
      if (ll<=l[belong[j]]&&r[belong[j]]<=rr) {if (sum[belong[j]]>0) {tot-=sum[belong[j]];sum[belong[j]]=0;}j=r[belong[j]];}
      //如果当前区间包含某一块,并且这一块里还有树没有被移除(sum[belong[j]]>0)
      //那么就移除这个块里的所有树,并且把j指向这一块的右端点+1的位置
      //(程序里之所以是写把j移到右端点的位置,是因为for循环的下一次循环
      //会把j又加上1)。
      else {if (sum[belong[j]]>0 && !alive[j]){sum[belong[j]]--;tot--;alive[j]=true;}} 
      //如果只是包含某一块的一部分,那么就直接暴力处理,
      //同样如果这一块中还有树,并且我们要移除的这棵树还在这一块中,那么就移除这棵树
      //然后tot减去一棵树(程序中的alive的意思搞反了,False代表存在,True代表
      //不存在)      
   }
   printf("%d\n",tot);
  return 0;
}