某島

… : "…アッカリ~ン . .. . " .. .
October 21, 2021

Facebook Hacker Cup 2021 Round 1

A1.
給定一個 ’01-‘ 組成的字元串 s,設 f(s) 為忽略掉 s 中所有 ‘-‘ 字元後,相鄰字元發生變換的次數。
求 f(s)。
掃一遍即可。

A2
統計所有 s 的子串的 f 值。
統計相鄰的 ’01’ pair 的貢獻即可。

const int N = int(1e6) + 9;
char s[N];
int n;

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif

    Rush {
        RD(n); RS(s);
        Int z = 0;
        char lc = '?'; // 上一個字元
        int lp = 0; // 上一個字元的位置

        REP(i, n) {
            char c = s[i];
            if(c != 'F') {
                if (lc != c) {
                    if(lc != '?') z += Int(lp) * (n-i);
                    lc = c;
                }
                lp = i+1;
            }
        }
        OT(z);
    }
}

A3
s 中還包含 ‘.’ 字元,如果出現 ‘.’ 字元,則用此前的字元串替換 ‘.’ 位置,詢問 A2。

延續 A2 的思路,我們需要對每個 pair 統計出左邊和右邊分別有多少字元。
這個比較簡單,但是每個 ‘.’ 內部還會出現很多 pair,我們需要對這些內部的 pair 也 O(1) 時間統計。
這樣首先我們需要改進 A2 的演算法,再開一個 ls 變數記錄前面所有 pair 的貢獻,這樣就可以不支持後續長度的情況下 incremental 的維護答案。

const int N = int(1e6) + 9;
char s[N];
int n;

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif

    Rush {
        RD(n); RS(s);
        Int z = 0;
        char lc = '?'; // 上一個字元
        int lp = 0; // 上一個字元的位置
        Int ls = 0; // 右邊新增加一個字元時答案的增量。

        REP(i, n) {
            z += ls;
            char c = s[i];
            if (c != 'F') {
                if (lc != '?' && lc != c) {
                    z += lp;
                    ls += lp;
                }
                lp = i+1;
                lc = c;
            }
        }
        OT(z);
    }
}

進一步考慮 ‘.’ 的影響,我們不僅需要知道當右邊新增加一個字元時的增量 ls,還需要對稱的,知道當左邊新增加一個字元時的增量 rs,
那麼新的答案就是 2z + len(ls+rs),還要考慮合併的位置會不會產生一組新的 pair。
因此還需要維護左右第一個字元是什麼和所在位置以及一共有多少 pair。各種維護即可。

const int N = int(1e6) + 9;
char s[N];
int n;

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif

    Rush {
        RD(n); RS(s);
        Int z = 0;
        char lc = '?', rc = '?'; //
        Int lp = 0, rp = 0, ct = 0;
        Int ls = 0, rs = 0;
        Int len = 0;

        REP(i, n) {
            char c = s[i];
            if (c == '.') {

                z = z*2 + len*(ls+rs);
                ls = ls*2 + len*ct;
                rs = rs*2 + len*ct;
                ct *= 2;

                if (lc != rc) {
                    ct += 1; ls += lp; rs += (len-rp+1);
                    z += lp * (len-rp+1);
                }
                if (lc != '?') lp += len;
                len *= 2;

            } else {

                z += ls;
                len += 1;

                if (c != 'F') {

                    if (rc == '?') {
                        rc = c, rp = len;
                    }

                    if (lc != '?' && lc != c) {
                        z += lp;
                        ls += lp;
                        ct += 1;
                    }
                    lp = len;
                    lc = c;
                }

                rs += ct;
            }
        }
        OT(z);
    }
}

C.
感覺是樹形 dp 基本功題,最簡單的方法應該是 dfs() 兩次,
一次得到子樹的 dp 狀態,一次得到子樹外的 dp 狀態,但是比賽時思路比較混亂。

賽後讀了一下 nhb 的代碼,發現忽略了一個重要得條件,就是邊權 <= 20。。。
然後就可以直接暴力加維了。。囧。

當然邊分治也可以,參考 neal wu 的代碼

不知道沒有邊權的限制還能不能做。