首页 > 代码库 > 洛谷 P1276 校门外的树（增强版） 题解
洛谷 P1276 校门外的树（增强版） 题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目链接：https://www.luogu.org/problem/show?pid=1276
题目描述
校门外马路上本来从编号0到L，每一编号的位置都有1棵树。有砍树者每次从编号A到B处连续砍掉每1棵树，就连树 苗也不放过（记 0 A B ，含A和B）；幸运的是还有植树者每次从编号C到D 中凡是空穴（树被砍且还没种上树苗或树苗又被砍掉）的地方都补种上树苗（记 1 C D，含C和D）；问最终校门外留下的树苗多少棵？植树者种上又被砍掉的树苗有多少棵？
输入输出格式
输入格式：第一行L和N,表示校园外原来有L+1棵树，并有N次砍树或种树的操作。
以下N行，砍树或植树的标记和范围，每行3个整数。
L（1 <= L <= 10000）和 N（1 <= N <= 100）
输出格式：共两行。第1行校门外留下的树苗数目，第2行种上又被拔掉的树苗数目。
输入输出样例
输入样例#1：
10 30 2 61 1 80 5 7
输出样例#1：
32
分析：
[被标签坑]系列
虽然出题者费了半天力气增强了一下...这特么还是一个模拟啊qwq
向线段树dalao低头
AC代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 #include<iostream> 5 int road[10005]; 6 int tot,ans; 7 int main() 8 { 9 int n,m,a,b,c;10 scanf("%d%d",&n,&m);11 for(int i = 0;i <= n;++ i)12 road[i] = 1;13 //0表示没有树，1表示原有的树，2表示树苗 14 for(int i = 1;i <= m;++ i)15 {16 scanf("%d%d%d",&a,&b,&c);17 if(a == 0)18 {19 for(int j = b;j <= c;++ j)20 {21 if(road[j] == 2)22 tot ++;23 road[j] = 0;24 }25 }26 else27 {28 for(int j = b;j <= c;++ j)29 {30 if(road[j] == 0)31 road[j] = 2;32 }33 }34 }35 for(int i = 0;i <= n;++ i)36 {37 if(road[i] == 2)38 ans ++;39 }40 printf("%d\n%d",ans,tot);41 return 0;42 }
洛谷 P1276 校门外的树（增强版） 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。