UVa13095 - Tobby and Query(貪心、動態規劃)

題目大意

Tobby and Query 對一些事情很感興趣,Tobby 對一些問題很有興趣
題目會給你一組數列,其中數列的數字只會是 0~9,之後會給你一個區間 [l,r],想問妳這裡面有幾個不重複的數字

題目連結

重點觀念

  • 使用動態規劃
  • 題目的數字只有 10 個,是不是可以用些笨拙的方法快速解決這題?

分析

  • 應該會有些人像我一樣,第一個想法是使用 set or segment tree 嗎?
    • 使用 set 不好,我們只能夠確認區間裡面有那些數字,在大量查詢時沒辦法
    • 使用 Segment tree 呢?在判斷左子樹、右子樹 [l,r] 有哪些數字時會比較難處理些
  • 動態規劃
    • 我們可以發現題目的數列是不需要修改的,也就是我們只要做到區間查詢就好,不需要做到區間修改。
    • 此時動態規劃就很適合我們解決此問題,先算出 [0,0~r] 中有哪些數字、有幾個,之後透過區間相減的方式來進行區間查詢
    • 注意:區間查詢不能用在需要區間修改的問題

參考連結

Uva11264 - Coin Collector by morris821028

心得

嗚嗚,我處理這種問題還是需要再聰明點,雖然一開始就想到區間查詢 => Segment tree,確定後再試著找一些網路上的詳解,驗證我的答案是不是對的XD。

看來我想得不夠乾淨,理應可以把題目變得更簡單。
能夠盡量把題目變得更簡單,就應該要變得簡單,我還要在訓練這方面的思考。

題目程式碼

會在下面放一些簡單註解,供大家學習時參考。

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
#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define DEBUG
#define MAXN 100020
using namespace std;
int n, q, l, r, idx; //var index error => https://blog.csdn.net/cyril_ki/article/details/109668100
int a[MAXN][12];

int32_t main()
{
#ifdef LOCAL
freopen("in1.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif // LOCAL
while(cin >> n){
memset(a, 0, sizeof(a));
for(int i = 1; i <= n; i++){ //輸入資料
cin >> idx;
a[i][idx]++;
//狀態轉移,區間 [0,i-1] => [0,i]
for(int j = 0; j < 10; j++) a[i][j] += a[i-1][j];
}

cin >> q;
for(int i = 0; i < q; i++){
cin >> l >> r;
int ans = 0;
for(int j = 0; j < 10; j++){
//如果區間 [0,r] - [0,l) = [l,r] 裡面如果有 0~9 就 ans +1
if(a[r][j] - a[l-1][j] > 0) ans++;
}
cout << ans << '\n';
}
}

return 0;
}
  • 版權聲明: 本部落格所有文章除有特別聲明外,均採用 Apache License 2.0 許可協議。轉載請註明出處!
  • © 2020-2024 John Doe
  • Powered by Hexo Theme Ayer
  • PV: UV: