【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