大衞的筆記

題目大意

打擊腐敗基金會要對 Nlogonia 非法組織做審查，但基金會收到帳本後卻發現帳本並沒有表示交易紀錄是收入還是支出，只剩下數字、結餘多少。
於是我們希望可以透過程式還原每項明細，他是收入還是支出。

如果此結餘跟所有明細都對不上就輸出 *
如果這筆明細確認是收入就輸出 +
如果這筆明細確認是費用就輸出 -
如果這筆明細無法確認就輸出 ?

題目連結

題目大意

有一群人他們在玩 Largest Sum Game，主要就是在一個數列內要找出一個區間的總和最大，並輸出總和最大的數字。

題目連結

題目大意

給你一個數列，請善用 a+b=c, cost += c ，其中 a 與 b 是數列裡面的數字，並將 c 再放入數列
請求出最小的 cost

題目連結

重點觀念

• priority_queue 的應用
  priority_queue 是 heap sort 的應用，理論就是不斷拿出 heap tree 的 root，需要看 heap sort 請看大衞的筆記

分析

• 我們可以知道不斷拿數列中兩個最小的數字相加會使得 cost 最小
  如果你覺得不可信，可以看看題目舉例
• 因此我們使用 priority_queue 每次取出兩個最小的相加即可。

心得

水題，給我自信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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN
#define int long long
using namespace std;
int n, num;
//注意，這是最小遞增 priority_queue 的寫法
priority_queue<int, vector<int>, greater<int> > q; 

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL


    while(cin >> n && n){
        while(!q.empty()) q.pop(); //clear, priority_queue 沒有 clear 的 method  

        for(int i = 0; i < n; i++){  //輸入資料
            cin >> num;
            q.push(num);
        }

        int ans = 0, a, b;
        while(q.size() != 1){ //只要數列中還有兩個以上的數字可以累加
            a = q.top(); q.pop();
            b = q.top(); q.pop();
            q.push(a+b);
            ans += a+b;
        }
        cout << ans << '\n';

    }

    return 0;
}

題目大意

一個古典樂團要進行演奏，通常古典樂團是許多樂器、許多人一起搭配而成，例如：演奏小提琴有 8 個人、中提琴有 4 個、大提琴有 2 個，由於每次演奏的曲譜都不一樣，要帶著走很不方便。
如果每個樂手都有一份譜，古典樂一份樂譜至少要 100 張紙以上，這很不環保、浪費成本，因此我們希望可以讓同個樂器的人可以共同看一份樂譜，但是如果讓一群人只看一張樂譜會讓聽眾視覺觀感不好，因此指揮會讓同個樂器的人拿到很多份樂譜，來降低讓觀眾視覺觀感不好。

因此我們希望給你 p 張譜，n 種樂器、其中每種樂器都有很多人，請告訴我們在以讓最少人一起看樂譜的前提下，最多會有幾個人一起合看一張樂譜。
題目不會有 樂譜 < 樂器種類 的情況

舉例：演奏小提琴有 8 個人、兩張樂譜，那麼小提琴 4 個人一起看一張樂譜。
題目連結

重點觀念

• 這邊可以用兩種做法，其中 Binary Search 最好實現
  • priority_queue
    priority_queue 是 heap sort 的應用，理論就是不斷拿出 heap tree 的 root，需要看 heap sort 請看大衞的筆記
  • Binary Search
    注意，這裡的二分搜尋的區間是 [L,R]，而學習連結是 [L,R)
• Udebug 的第二個測資有誤…。(在我寫這篇文章時他是第二個)

分析

• 通常大家第一個會先想到 priority_queue，但我們要考慮一種情況。
  • 舉例：p = 5, n = 3, 9,1,1
    • 如果用最簡單的做法，大到小 priority_queue 然後不斷除二，會遇到小數點的問題。
      • 9/2= 4.5，這時候就變成我們要 + 1，push(5)
      • 但正確答案其實是 3。
    • 也就是說，如果用 priority_queue 實作，我們必須用一個 struct 實作，參數有。
      • 樂手數量
      • 幾個樂譜
      • 幾個人看一張樂譜
    • 但這樣比較麻煩，因為你必須寫 struct compare。
• 二分搜尋，這個大家比較不會想到，原因是因為不直觀。
  • 想想，其實我們是要找出一種狀況是最多會有幾個人一起合看一張樂譜。
  • 題目詢問我們的是x 個人一起合看一張樂譜
  • 我們把題目想深一點，可以想成這個樂團最多 x 個人看一張樂譜，樂譜總數量有沒有超過 p
  • 這時候就可以轉化成二分搜尋，降低複雜度。我們只要找到最低的 x 就可以了！此時就不會被 p 影響，複雜度就可以降至 \(O(n \log n\)
  • 作法
    • 左邊界設為 1 個人看一張、右邊界設為樂器中最多人的一團看一張。
    • 如果再 x 個人的情況下需要 y 張樂譜
      • y 比 p 小，可以讓更多人看因此把 R 邊界降低，讓 (L+R)/2 變小，讓更少人看一張
      • y 比 p 大，把 L 邊界提高，讓更少人看一張
    • 不斷二分搜尋，找出一種最佳答案。

參考連結

Uva13177 - Orchestral scores by txya900619

心得

其實我原本是要用 priority_queue 的寫法的，只是在我想好做法後，先翻了翻解答XD。
不然假如自己程式碼寫錯還要重改很嘔嘛，又不是比賽，深思熟慮完成後對答案來改進也不差。

畢竟紙上談兵都錯了的話，那做下去也不會對。

看了後發現這題還可以用另一種方式去詮釋，覺得很棒。就寫這種做法了。

後來有在網路上看到有人用 priority_queue 這種作法，點此連結

總之，這次讓我看到了一種做法是並不是以題目給的答案為主要思考方向，而是在往上推一層，找出一個可以決定題目答案的變數，並推敲此變數已獲得答案。
這想法很不賴阿，100分。

題目程式碼

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

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
//#define DEBUG
#define int long long
#define MAXN 100020
using namespace std;
int p, n;
int num[MAXN];

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // LOCAL

    while(cin >> p >> n){
        //注意：這裡我們的 m 就是分析中的 x，是要看最多 x 人拿一張樂譜的情況下，每個樂器部門需要幾張
        //左邊界設定一個人一張
        int L=1, R=0; // L 
        for(int i = 0; i < n; i++){
            cin >> num[i];
            //L = min(num[i], L);
            R = max(num[i], R); //右邊界設定以最大團的樂器部門人數數量，以此做標準拿一張
        }

        int ans = 0;
        while(L <= R){
            int mid = (L+R) / 2, required = 0; //required 總共需要幾張樂譜
            //計算每張樂譜需要的數量
            //因為每個樂團至少要一張，因此先將 mid，以避免計算出來的數字為 0
            //EX: 2 / 10 = 0，但理論上要是 1
            for(int i = 0; i < n; i++) required += (num[i] + mid - 1) / mid;
            #ifdef DEBUG
                cout << "L R required " << L << ' ' << R << ' ' << required << '\n';
            #endif // DEBUG
            if(required <= p){ //如果 required 小於等於 p，表示還可以讓更少人拿一張
                ans = mid; //以最多 mid 人為一個單位，剛好符合答案
                R = mid-1; //由於我們的邊界是 [L,R]，因此 R-1
            }
            else L = mid+1; //由於我們的邊界是 [L,R]，因此 L+1
        }
        cout << ans << '\n';
    }

    return 0;
}

題目大意

給你一個只有加減的多元方程式與一些數字，EX: \(-(-(x-x))\)，\(x = 2,3\)，請將這些 x 帶入方程式內，並找出一種方程式帶入 x 後可以輸出最大的數字。
每一個 x 只能夠使用一次

題目連結

題目大意

我們發現外星人的 DNA 片段了！但我們必須要將這些 DNA 的片段組裝成一組 DNA。(注意：一組 DNA 是我定義的名詞)
而組裝的方式則是只要 DNA 片段中有一個小寫字母與另一個 DNA 片段小寫字母組在一起即可。
P.S. 如果想要讓一組 DNA 有三個或以上的片段組成時，則新進來的 DNA 必須都跟其他 DNA 片斷有一個以上的小寫字母連接。

其中一組 DNA 是連續的，因此不可以拿第一個片段 DNA 與第三個片段 DNA 組成一個新的 DNA。
而題目要求則是，我們最少需要切幾次可以讓裡面的片段 DNA 們都是一組 DNA。

UVa 11583 Alien DNA

重點觀念

• 英文閱讀
  • 對很重要 least one common base. 我看不出來他是指說組裝的方式則是只要 DNA 片段中有一個小寫字母與另一個 DNA 片段小寫字母組在一起即可。
  • 然後我也看不出來一組 DNA 是連續的，這個題目要求…
• 程式編寫
  有效率、簡潔的程式碼

分析

這個問題如果有理解英文後就很好解。

• 我們用 int 的 2 進位位數來表示每個字母是否在這組 DNA 中
  • 這組 DNA 預設情況 000...0
  • 這組 DNA 有了 Z 之後 100...0
• 上面這種方式透過數字表達的 DNA 我稱為數字 DNA
• 之後我們讓片段 DNA 先產生出數字 DNA
• 判斷片段數字 DNA 是否跟現在這組數字 DNA 有共同的地方，如果有就讓 (片段數字 DNA & 這組數字 DNA
  • 如果沒有就讓當前這組 DNA 升級成一組 DNA
• 輸出共有幾組 DNA

因為題目有說明片段 DNA 只能夠跟左右片段連接，因此如果是不同種的組裝方式，組合數量也不會不一樣。
一組內的片段 DNA 都必須有一個數字相同，所以往往切斷點就是無法組合的片段 DNA

參考連結

【題解】ZeroJudge d272: 11583 – Alien DNA by YUI HUANG 演算法學習筆記

心得

這題的英文不知道是不是我邏輯差，我怎麼一直看不懂RRRRR。

知道了邏輯後，稍微學習了優秀大神的程式碼編寫方法，太棒了太棒了。又被教到了一課
用二進位來編寫真的很不賴。

不愧是竹女阿太秀了

題目程式碼

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

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

#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define LOCAL
#define DEBUG
#define MAXN 10020
using namespace std;
int t, n ;
int segment, dna;
string s;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n;
        segment = (1 << 27) - 1; //產生出一組 A~Z 都是 1 的數字 DNA，才一定能跟第一組做組合 
        int ans = 0;
        for(int i = 0; i < n; i++){
            cin >> s;
            dna = 0; //片段數字 DNA
            for(int j = 0; j < s.size(); j++){
                dna |= (1 << (s[j] - 'a'));
                //數字 DNA 表達方式 0 表示沒有 1 表示有
                //a 是 個位數、b 是十位數... 以此類推
            }

            //如果可以成為一組，那就一組八!
            //注意必須用 and，因為要每個片段 DNA 都有一個小寫字母相同
            if(dna & segment ) segment &= dna; 
            else{
                segment = dna; //與前面的一組 DNA 不同，這個片段 DNA 升級成一組 DNA 
                ans++; //找到切斷點了! 
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

筆記說明

此筆記用途在於台北科技大學資訊工程系大二下多媒體技術與應用作業紀錄
並非所有人都適用，部分對我而言稍加容易的內容並不會寫在此內。
這是學習後心得的筆記，可能不太適用會未來的學生

由於我沒有學習過裡面的理論，因此這是資工大二學生透過網路與自身理解的筆記，學習價值並不高、且可能擁有大量錯誤。

筆記說明

此筆記用途在於台北科技大學資訊工程系大二下多媒體技術與應用作業紀錄
並非所有人都適用，部分對我而言稍加容易的內容並不會寫在此內。
這是學習後心得的筆記，可能不太適用會未來的學生

由於我沒有學習過裡面的理論，因此這是資工大二學生透過網路與自身理解的筆記，學習價值並不高、且可能擁有大量錯誤。

訓練的資料從 KITTI 資料集產生出來，後面會留下的成果。

如果需要點選某些特定章節，請善用右上的章節列

題目大意

有位愛好蒐集銅板的人想要透過銀行換錢的方式蒐集各式各樣的錢幣。但礙於銀行永遠都只會先給面額較大的錢幣，因此想請問你他最多可以蒐集多少錢幣。

假如有 1,5,10 這三種錢幣，如果我現在有 31 元，那我就會收到 2 個 10 元硬幣、1 個 1 元硬幣。

假如他身上有任意的錢，請告訴她，透過銀行匯款的方式他能夠收集到幾種貨幣。

題目連結

題目大意

在一條主要幹道上，有許多加油站，其中每一個加油站都會影響主要幹道上的某個區段，用 \([x+r, x-r])\) 表示，x 是道路位置、r 是影像長度，其中幹道上的每一個點都有被加油站區斷給覆蓋到，現在加油站公司想要把一些加油站刪除，前提是幹道上的每一個點都還是必須有一個加油站覆蓋到。
請問總共可以刪掉幾個加油站？
如果不行，輸出 -1

題目連結