题解 P1047 【校门外的树】

#### 校门外的树下，是曾经纯真少年的懵懂模拟，今日再遇，又是何处思绪涌上心头，愿不朽如AC图标般万年长青。 ~~这种区间问题啊，普通暴力不行，那就简洁分块吧（逃~~ #### 详情看代码，一边看代码，一边看注释，效果好一点 ```cpp #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; } ```