2140: 學無止境

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

Description

“別人總說我瓜，其實我一點也不瓜，大多數(shù)時候我都機智的一批“
ACM程序設(shè)計競賽是一個團體項目。寶兒姐作為其中優(yōu)秀的一份子，每天好好學習天天向上。曾經(jīng)寶兒姐給自
己定了一個計劃，刷穿bzoj。于是她每天把oj上連續(xù)的幾道題給寫一遍，這樣持續(xù)了n天。現(xiàn)在寶兒姐想知道有多少天自己
是處于特別強的狀態(tài)。某一天，如果寶兒姐那天刷的所有題目，n天后已經(jīng)都刷過了至少3遍，那么那天就是很強的狀。
給你寶兒姐n天的刷題狀況，請你幫她算算吧。

Input

第一行一個case代表測試實例（case<=3）
第二行兩個數(shù)n和m，分別代表寶兒姐刷題的天數(shù)和最大題號。（1<=n,m<=1e5）
接下來n行每行兩個數(shù)字l, r，代表寶兒姐在那天刷題號的起點和終點。（l,r<=m）

Output

一個數(shù)字，代表寶兒姐處于很強的狀態(tài)的天數(shù)。

Sample Input

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

Sample Output

3

HINT

寶兒姐的第2,3,4天處于很強的狀態(tài)

前面有一篇博客說過前綴和和差分：

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

這道題我們先用差分把n天后每道題做了幾次算出來，然后遍歷每天的區(qū)間，看看是否每道題都做了三遍以上。

這個題我剛開始我做成了做了三遍以上的題有幾道.....

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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zut-syp/p/10543720.html

總結(jié)

以上是生活随笔為你收集整理的2140: 学无止境（差分）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。