【AtCoder - 4244 】AtCoder Express 2 （区间dp 或 暴力枚举，思维）

题干：

In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east. A company called AtCoder Express possesses Mtrains, and the train i runs from City Li to City Ri (it is possible that Li=Ri). Takahashi the king is interested in the following Q matters:

• The number of the trains that runs strictly within the section from City pi to City qi, that is, the number of trains j such that pi≤Lj and Rj≤qi.

Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

Constraints

 

• N is an integer between 1 and 500 (inclusive).
• M is an integer between 1 and 200 000 (inclusive).
• Q is an integer between 1 and 100 000 (inclusive).
• 1≤Li≤Ri≤N (1≤i≤M)
• 1≤pi≤qi≤N (1≤i≤Q)

Input

 

Input is given from Standard Input in the following format:

N M Q L1 R1 L2 R2 : LM RM p1 q1 p2 q2 : pQ qQ

Output

 

Print Q lines. The i-th line should contain the number of the trains that runs strictly within the section from City pi to City qi.

Sample Input 1

 

2 3 1 1 1 1 2 2 2 1 2

Sample Output 1

 

3

As all the trains runs within the section from City 1 to City 2, the answer to the only query is 3.

Sample Input 2

 

10 3 2 1 5 2 8 7 10 1 7 3 10

Sample Output 2

 

1 1

The first query is on the section from City 1 to 7. There is only one train that runs strictly within that section: Train 1. The second query is on the section from City 3 to 10. There is only one train that runs strictly within that section: Train 3.

Sample Input 3

 

10 10 10 1 6 2 9 4 5 4 7 4 7 5 8 6 6 6 7 7 9 10 10 1 8 1 9 1 10 2 8 2 9 2 10 3 8 3 9 3 10 1 10

Sample Output 3

 

7 9 10 6 8 9 6 7 8 10

解题报告：

     这题区间dp乱搞一下就可以了。

AC代码1：（区间dp）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 500 + 5; int a[MAX][MAX],n,m,q; ll dp[MAX][MAX]; int main() {cin>>n>>m>>q;int l,r;while(m--) {scanf("%d%d",&l,&r);a[l][r]++;}for(int len = 1; len<=n; len++) {for(int l = 1; l+len-1<=n; l++) {//每一个起点 int r = l+len-1;if(l == r) dp[l][r]=a[l][r];else if(r-l==1) dp[l][r] = dp[l][l] + dp[r][r] + a[l][r];else dp[l][r] = dp[l][r-1] + dp[l+1][r] - dp[l+1][r-1]+a[l][r];}}while(q--) {ll ans = 0;scanf("%d%d",&l,&r);printf("%lld\n",dp[l][r]);}return 0 ;}

AC代码2：（区间dp）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 500 + 5; int a[MAX][MAX],n,m,q; ll dp[MAX][MAX]; int main() {cin>>n>>m>>q;int l,r;while(m--) {scanf("%d%d",&l,&r);a[l][r]++;}for(int l = n; l>0; l--) {for(int r = 1; r<=n; r++) {dp[l][r] = a[l][r] + dp[l+1][r] + dp[l][r-1] - dp[l+1][r-1];}}while(q--) {ll ans = 0;scanf("%d%d",&l,&r);printf("%lld\n",dp[l][r]);}return 0 ;}

AC代码3：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 500 + 5; int a[MAX][MAX],n,m,q; int main() {cin>>n>>m>>q;int maxx = -1,l,r;while(m--) {scanf("%d%d",&l,&r);maxx = max(maxx,r);a[l][r]++;}for(int i = 1; i<=maxx; i++) {for(int j = 1; j<=maxx; j++) {a[i][j] += a[i][j-1];}}while(q--) {ll ans = 0;scanf("%d%d",&l,&r);for(int i = l; i<=r; i++) {ans += a[i][r];}printf("%lld\n",ans);}return 0 ;}

 

总结

以上是生活随笔为你收集整理的【AtCoder - 4244 】AtCoder Express 2 （区间dp 或 暴力枚举，思维）的全部内容，希望文章能够帮你解决所遇到的问题。

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