Jun 24, 2019

[APCS] 2019年六月場實作題詳解

前言

因為想要拼5 + 5，於是又報名了這次的APCS 至於成績如何那就晚點再說吧，算是個小伏筆（？

即便考場在家附近，我還是提早出門了還以為考場一樣在成大的資工系大樓，還在想說為什麼今天進不去，不是有APCS嗎趕快google一下才發現跑錯棚了，應該是在校區的另一邊所以我又趕快跑過去，差一點點遲到好險有提早出門（汗

problem 1

題目

給定兩場籃球賽雙方每一節的比分（每場籃球賽各四節求出主場最終的輸贏

兩場全贏：勝
兩場全敗：敗
一勝一敗：平手

保證輸數皆為正整數且每場比賽不會有雙方比分相同的問題

解法

直接實作一下就好了

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );

    int a = 0, b = 0, ans = 0, swp;
    for ( int i = 0 ; i < 4 ; i++ ){
        cin >> swp;
        a += swp;
    }
    for ( int i = 0 ; i < 4 ; i++ ){
        cin >> swp;
        b += swp;
    }
    ans += ( a > b ? 1 : -1 );


    a = b = 0;
    for ( int i = 1 ; i < 4 ; i++ ){
        cin >> swp;
        a += swp;
    }
    for ( int i = 1 ; i < 4 ; i++ ){
        cin >> swp;
        b += swp;
    }
    ans += ( a > b ? 1 : -1 );

    if ( !ans )
        cout << "Draw";
    else if ( ans > 0 )
        cout << "Win";
    else
        cout << "Lose";
    cout << '\n';
}

problem 2

題目

給定一張圖，起點為整張圖權重最小的點並規定如果可以從點 $A$ 移動到下一個點點 $B$ ，若且唯若點 $B$ 為點 $A$ 的可連接點中，權重最小的點然後路徑上點不能重複求出路徑的總權重

解法

dfs裸題，UVa有類似的題目（題號我忘記了反正就是模擬一次就對了（也沒有其他解法啊(ry

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

const int maxN = 105; // 大小我忘記了
const int INF = 0x3f3f3f3f; // INF大於值域，又可直接memset，方便又實用
typedef long long LL;

int mp[maxN][maxN];

LL dfs ( int x, int y, LL sum ){
    // 先找出最低點
    int mi = min ( min ( mp[x + 1][y], mp[x - 1][y] ), min ( mp[x][y + 1], mp[x][y - 1] ) );
    sum += mp[x][y];
    mp[x][y] = INF;
    if ( mi == INF )
        return sum;
    if ( mp[x + 1][y] == mi )
        return dfs ( x + 1, y, sum );
    if ( mp[x - 1][y] == mi )
        return dfs ( x - 1, y, sum );
    if ( mp[x][y + 1] == mi )
        return dfs ( x, y + 1, sum );
    if ( mp[x][y - 1] == mi )
        return dfs ( x, y - 1, sum );
}

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );

    int n, m, x, y, mi = INF;
    memset ( mp, INF, sizeof mp );
    cin >> n >> m;
    // 1 index，可以直接免去判斷邊界的麻煩
    for ( int i = 1 ; i <= n ; i++ )
        for ( int j = 1 ; j <= m ; j++ ){
            cin >> mp[i][j];
            if ( mi > mp[i][j] )
                mi = mp[i][j], x = i, y = j;
        }

    cout << dfs ( x, y, 0 ) << '\n';
}

problem 3

題目

給定 $N$ 個字串，且這 $N$ 個字串只會由前 $M$ 個字元組成，字元由 $A$ 開始請求出每一對可以組成互補字串的數量且字串是一個集合，也就是說，即便元素有重複還是只算一個，也不計較排列所以 $AAB$ 與 $AB$ 與 $BA$ 都是相同的字串

定義一下互補字串

假設字串 $A$ 中的元素沒有出現在字串 $B$ 中同時，字串 $B$ 的元素也沒有出現在字串 $A$ 中則稱 $A \text& B$ 為互補字串

解法

解法一：硬幹

說明

之所以會稱為是硬幹，是因為在找查互補字串的時候是硬著做的

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>
#define F first
#define S second

using namespace std;

map < string, int > lib;

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );

    int n, m, ans = 0;
    string str, basic;
    char c = 'A';
    cin >> n >> m;
    for ( int i = 0 ; i < m ; i++, c++ )
        basic += c;
    while ( n-- ){
        cin >> str;
        // 這邊為了要把順序都統一，所以先做一下排序
        sort ( str.begin(), str.end() );
        // 這邊則是要把重複的字元壓掉
        str.erase ( unique ( str.begin(), str.end() ), str.end() );
        lib[str]++;
    }

    for ( auto j: lib ){
        str = basic;
        // 把出現過的直接刪掉
        for ( auto i: j.F )
            str.erase ( lower_bound ( str.begin(), str.end(), i ) );
        ans += j.S * lib[str];
    }

    // 因為會重複計算到兩次
    ans /= 2;
    cout << ans << '\n';
}

方法二：Xor

說明

因為原本的方法太智障了（？如果不是因為資料量小可以這樣做，資料量一大直接吃土

出來之後聽到有人是這樣做的，有點類似Hash的做法把字串轉成二進位，如果這個字元有出現過就是 $1$ ，反之，就是 $0$ 然後為了方便運算會把這個二進位reverse

也就是說， $ACD$ 會轉成 $(1101)_2$ ，而 $ABD$ 會轉成 $(1011)_2$ ， $BD$ 會轉成 $(1010)_2$ 然後再把二進位轉成十進位這樣就可以很輕鬆的用一個 $int$ 來作儲存了，而且可以直接用 $Xor$ 來取互補字串

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>
#define F first
#define S second

using namespace std;

map < int, int > lib;

inline int translate ( string str ){
    int res = 0;
    for ( auto i: str )
        res |= ( 1 << ( i - 'A' ) );

    return res;
}

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );

    int n, m, ans = 0, ori = 0;
    string str;
    cin >> n >> m;
    for ( int i = 0 ; i < m ; i++ )
        ori |= ( 1 << i );
    while ( n-- ){
        cin >> str;
        // 這邊為了要把順序都統一，所以先做一下排序
        sort ( str.begin(), str.end() );
        // 這邊則是要把重複的字元壓掉
        str.erase ( unique ( str.begin(), str.end() ), str.end() );
        lib[translate ( str )]++;
    }

    for ( auto j: lib )
        ans += ( j.S * lib[ori ^ j.F] );

    // 因為會重複計算到兩次
    ans >>= 1;
    cout << ans << '\n';
}

注意，這份code並沒有經過詳細測試，可能有誤

problem 4

題目

給定一個長度為 $N$ 的序列，求給定數字 $M$ 長度，且其中所有數字都不重複的連續子序列數量

解法

Slide Window裸題，不過關於實作又有兩種做法

方法一：固定Window大小

把window大小固定為 $M$ ，並且開一個set紀錄這個window的數字要把數字從前端pop掉時，記得檢查這個數字在後頭是否出現過然後不想要用map，所以離散化一下，這樣就可以用陣列儲存了

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

const int maxN = 100005;

int cnt[maxN];

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );

    int n, m, ans = 0;
    cin >> n >> m;
    vector < int > data ( n ), lib;
    for ( auto &i: data )
        cin >> i;
    // 離散化
    lib = data;
    sort ( lib.begin(), lib.end() );
    lib.erase ( unique ( lib.begin(), lib.end() ), lib.end() );
    for ( auto &i: data )
        i = lower_bound ( lib.begin(), lib.end(), i ) - lib.begin();

    queue < int > q;
    set < int > s;
    for ( int i = 0 ; i < n ; i++ ){
        q.push ( data[i] );
        s.insert ( data[i] );
        cnt[data[i]]++;
        if ( q.size() >= m ){
            cnt[q.front()]--;
            if ( !cnt[q.front()] )
                s.erase ( q.front() );
            q.pop();
        }
        if ( s.size() == m )
            ans++;
    }

    cout << ans << '\n';
}

方法二：不固定的window大小

此方法由吳邦一教授提出（原文連結）由左往右把數字push進window，如果遇到已經在window裡面的數字，則一路pop到該數字離開window為止

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

const int maxN = 100005;

int cnt[maxN];

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );

    int n, m, ans = 0;
    cin >> n >> m;
    vector < int > data ( n ), lib;
    for ( auto &i: data )
        cin >> i;
    // 離散化
    lib = data;
    sort ( lib.begin(), lib.end() );
    lib.erase ( unique ( lib.begin(), lib.end() ), lib.end() );
    for ( auto &i: data )
        i = lower_bound ( lib.begin(), lib.end(), i ) - lib.begin();

    // 這邊的話就不用set了
    queue < int > q;
    for ( int i = 0 ; i < n ; i++ ){
        // 不斷pop直到這個數字前面沒有出現過
        while ( !q.empty() && cnt[data[i]] ){
            cnt[q.front()]--;
            q.pop();
        }
        q.push ( data[i] );
        cnt[data[i]]++;
        if ( q.size() == m )
            ans++;
    }

    cout << ans << '\n';
}

後記

其實我把所有題目寫完之後，大概才過41分鐘然後為了要確定code都沒有爛，還特地多花一個小時半左右吧，在寫對拍，想要抓抓看bug 接著我就發現我在裡面多花快一個半小時，然後一個字元都沒有改到也就是說，我在裡面燒機燒了一個半小時然後產量是零抓到，澪人桐是燒機大師早就知道出來玩手機算了 = =

看到這邊多多少少都會對我的成績有點興趣吧（？（不然如果他成績跟垃圾一樣，到底浪費時間看這篇文章幹嘛話不多說我直接上圖好了

差一題觀念5+5 搞什麼 = =

以前我有過觀念五，但是那次實作沒有考好，這次換觀念沒有五，我該注意什麼（欸，差不多是一年前的六月場欸OAO

雖然按照官方的說法這樣也算是5+5啦，不過沒有單場5+5真的有點可惜那麼今天就到這邊了，謝謝各位今天的閱讀如果需要更多的說明（無論是否是這次的題目，或是該如何準備APCS）的話，都歡迎寫email給我我的email可以在我的個人頁面找到 p.s. 我今天寫好長的文章喔，到這邊已經430行了

本來用Typora編輯，那個md編輯軟體好像會自動幫我加上一大堆的空行，大概就是打完一行就會有一行空行所以原本的文章看起來很很空還需要自己手動調整，有點小麻煩不過他可以即時顯示md的渲染結果，真的讓人難以抉擇

更新（2019/07/04 10:28）

之前可以查詢成績好像是bug，官方是說今天早上十點才可以查剛剛查了一下，發現級距出來了，在這邊附上（上次查的沒有級距可以看）

圖片出處

紅色鳥居：神奈川縣蘆之湖kaji_nori06
成績單。。。等等，這張就我的成績單啊，沒有什麼出處問題吧
級距。。。啊就從成績單上截圖截下來的啊 = =