2140: 学无止境

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 100  Solved: 23
[Submit] [Status] [Web Board] [Creator:admin]

Description

“别人总说我瓜，其实我一点也不瓜，大多数时候我都机智的一批“
ACM程序设计竞赛是一个团体项目。宝儿姐作为其中优秀的一份子，每天好好学习天天向上。曾经宝儿姐给自
己定了一个计划，刷穿bzoj。于是她每天把oj上连续的几道题给写一遍，这样持续了n天。现在宝儿姐想知道有多少天自己
是处于特别强的状态。某一天，如果宝儿姐那天刷的所有题目，n天后已经都刷过了至少3遍，那么那天就是很强的状。
给你宝儿姐n天的刷题状况，请你帮她算算吧。

Input

第一行一个case代表测试实例（case<=3）
第二行两个数n和m，分别代表宝儿姐刷题的天数和最大题号。（1<=n,m<=1e5）
接下来n行每行两个数字l, r，代表宝儿姐在那天刷题号的起点和终点。（l,r<=m）

Output

一个数字，代表宝儿姐处于很强的状态的天数。

Sample Input

1 6 5 1 5 2 4 3 4 2 3 4 5 1 1

Sample Output

3

HINT

宝儿姐的第2,3,4天处于很强的状态

前面有一篇博客说过前缀和和差分：

https://blog.csdn.net/qq_42217376/article/details/81301468

这道题我们先用差分把n天后每道题做了几次算出来，然后遍历每天的区间，看看是否每道题都做了三遍以上。

这个题我刚开始我做成了做了三遍以上的题有几道.....

AC代码：

#include<bits/stdc++.h> #include<algorithm> using namespace std; int b[100010],a[100010]; struct A {int l,r; }c[100010]; int main() {int t;scanf("%d",&t);while(t--){memset(a,0,sizeof(a));memset(b,0,sizeof(b));int n,m,j=1;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d%d",&c[i].l,&c[i].r);b[c[i].l]++;b[c[i].r+1]--;}int sum=0;for(int i=1;i<=m;i++){b[i]+=b[i-1];a[i]+=b[i];}for(int i=1;i<=n;i++){int b=1;for(int j=c[i].l;j<=c[i].r;j++){if(a[j]<3){b=0;break;} }if(b)sum++;}printf("%d\n",sum);}return 0; }

 

转载于:https://www.cnblogs.com/zut-syp/p/10543720.html

总结

以上是生活随笔为你收集整理的2140: 学无止境（差分）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。