【AtCoder-4244】解题报告（暴力，DP）

原始题目

D - AtCoder Express 2

  • Time limit : 3sec / Memory limit : 1000MB
  • Score: 400 points

Problem Statement

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 M trains, 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

题目大意

在一条东西向的铁路上有 \(1,2,3 \cdots N\) 个城市，列车公司有\(M\)列火车，每列火车从\(L_i\)行驶到 \(R_i( L_i \le R_i)\)，现在有\(Q\)个询问 每次询问\(p_i,q_i\) 两个城市间有多少躺列车的行驶路程恰好再在两城市之间（包括端点）。

解题思路

  • 暴力：由于只需要计数，那么以每个城市为集合，统计该城市出发的列车的行使距离，对于每次询问，遍历pi到qi城市的集合判断距离是否小于终点到遍历点的距离即可。

  • DP：
    • 把列车行驶看作线段，很明显大的线段包含小的线段。由此联想可以由内向外扩展，考虑DP
    • 以终点作为集合，元素为起始点，预处理后对每个集合排序（代码实际应用vector而非set，因为set不支持迭代器随机访问而且可能会有重复线路）
    • \(dp[i][j]\)表示从i城市到j城市包含的火车线路。
    • 则状态转移方程为\(dp[i][j]=dp[i][j-1]+num[i][j]\) ，\(num[i][j]\)表示到达j城市且起点不在i城市之前的列车线路数。
    • 求\(num[i][j]\)，用二分查找lower_bound找到j城市集合中第一个大于等于i的位置，\(num[i][j]\)即为size减去前缀。
    • 预处理后直接可以输出答案

解题代码

  • 暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define mp make_pair
#define np next_permutation
#define pb push_back
#define all(x) (x.begin(),x.end())
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
using namespace std; 
const int maxn=500+5;

vector <int> v[maxn]; 
bool vis[maxn];
 
void init(){
	rep(i,0,maxn) v[i].clear();
	memset(vis,0,sizeof(vis));
}
 
 
void addedge(int l,int r){
	int len=r-l;
	v[l].pb(len);
}
 
int  checkedge(int l,int len){
//	if(v[l].begin()!=v[l].end()) 
//		 cout<<*v[l].begin()<<endl; 
	int ans=upper_bound(v[l].begin(),v[l].end(),len)-v[l].begin();
//	cout<<"ans="<<ans<<endl;
	return ans;
}
int n,m,q,li,ri,pi,qi;
 
int main(){
	ios::sync_with_stdio(false);
	while(cin>>n>>m>>q){
		init(); 
		rep(i,0,m){
			cin>>li>>ri;
			addedge(li,ri);
			vis[li]=1;
		}
		rep(i,0,maxn){
			if(vis[i])	sort(v[i].begin(),v[i].end()); 
		} 
		rep(i,0,q){
			cin>>pi>>qi;
			int cnt=0;
			for(int i=pi;i<=qi;i++){
				int plen=qi-i;
//				cout<<"plen="<<plen<<endl;
				cnt+=checkedge(i,plen);
			}
			cout<<cnt<<endl;
		}
	} 
}
  • DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define mp make_pair
#define np next_permutation
#define pb push_back
#define all(x) x.begin(),x.end()
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
using namespace std; 
const int maxn=500+5;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
 
vi v[maxn];
int dp[maxn][maxn];
int n,m,q,li,ri,pi,qi;
void solve(){
	rep(i,1,n+1) sort(v[i].begin(),v[i].end());
	memset(dp,0,sizeof(dp));
	rep(l,1,n+1){
		for(int r=l;r<=n;r++){
			dp[l][r]=dp[l][r-1];
//			if(r-1<l) continue;
			dp[l][r]+=(v[r].size()-(lower_bound(v[r].begin(),v[r].end(),l)-v[r].begin()));
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	while(cin>>n>>m>>q){
		rep(i,0,m){
			cin>>li>>ri;
			v[ri].pb(li);
		}
		solve();
		rep(i,0,q){
			cin>>pi>>qi;
			cout<<dp[pi][qi]<<endl;
		}
	}
}

收获与反思

  • 脑子里别老想着暴力，有重复计算又没有修改为什么不考虑记忆化搜索？不考虑DP？思维训练还不够
  • 很明显的时间差异。
1.jpg
1.jpg