C. Bipartize

枚舉每個(gè)點(diǎn)的顏色，然后統(tǒng)計(jì)有多少條邊的端點(diǎn)顏色相同，這就是要?jiǎng)h除的點(diǎn)，取最小值即可

代碼實(shí)現(xiàn) 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using P = pair<int, int>;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<P> es;
    rep(i, m) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        es.emplace_back(u, v);
    }
    
    int ans = m;
    rep(s, 1<<n) {
        vector<int> col(n);
        rep(i, n) col[i] = s>>i&1;
        int now = 0;
        for (auto [u, v] : es) {
            if (col[u] == col[v]) now++;
        }
        ans = min(ans, now);
    }
    
    cout << ans << '\n';
    
    return 0;
}

D. The Simple Game

博弈型dp
記 dp[i][v] 表示從第 \(i\) 輪時(shí)棋子位于點(diǎn) \(v\) 這個(gè)狀態(tài)開(kāi)始時(shí)的贏家是否是 \(\mathrm{Alice}\)

轉(zhuǎn)移順序：從后往前

轉(zhuǎn)移需要用到以下性質(zhì)：

一個(gè)狀態(tài)是必勝狀態(tài)，當(dāng)且僅當(dāng)它至少有一個(gè)后繼是必?cái)顟B(tài)

代碼實(shí)現(xiàn) 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

void solve() {
    int n, m, k;
    string s;
    cin >> n >> m >> k >> s;
    
    vector<vector<int>> to(n);
    rep(i, m) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        to[u].push_back(v);
    }
    
    vector dp(k*2+1, vector<int>(n));
    rep(v, n) {
        dp[k*2][v] = s[v] == 'A';
    }
    
    for (int i = k*2-1; i >= 0; --i) {
        rep(v, n) {
            dp[i][v] = 0;
            for (int u : to[v]) {
                if (!dp[i+1][u]) dp[i][v] = 1;
            }
        }
    }
    
    if (dp[0][0]) puts("Alice");
    else puts("Bob");
}

int main() {
    int t;
    cin >> t;
    
    while (t--) solve();
    
    return 0;
}

E. Wind Cleaning

把“同時(shí)把所有垃圾平移一格”的動(dòng)態(tài)，用一個(gè) \(\mathrm{bfs}\) 在狀態(tài)空間上跑最短路。每個(gè)狀態(tài)由一個(gè)矩形區(qū)域（表示“仍然可能留在棋盤上的初始格子下標(biāo)范圍”）和當(dāng)前 \(T\) 的位置共同描述。\(\mathrm{bfs}\) 在這些狀態(tài)中按步數(shù)擴(kuò)展（每一步相當(dāng)于把所有垃圾朝某個(gè)方向移動(dòng)一次，等價(jià)于改變 T 的相對(duì)偏移），一旦“矩形中沒(méi)有任何 # 原始格”就說(shuō)明所有垃圾都已經(jīng)消失，此時(shí)的步數(shù)就是最終答案。

簡(jiǎn)單來(lái)說(shuō)就是不斷裁剪包含所有垃圾的最小矩形框，然后利用運(yùn)動(dòng)的是相互，保持垃圾不動(dòng)，移動(dòng)高橋的位置

代碼實(shí)現(xiàn) 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int h, w;
    cin >> h >> w;
    
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    
    int si = 0, sj = 0;
    rep(i, h)rep(j, w) if (s[i][j] == 'T') si = i, sj = j;
    
    using S = tuple<int, int, int, int, int, int>;
    map<S, int> dist;
    queue<S> q;
    
    auto push = [&](int li, int ri, int lj, int rj, int ti, int tj, int d) {
        li = max(li, ti-si); ri = min(ri, h+(ti-si));
        lj = max(lj, tj-sj); rj = min(rj, w+(tj-sj));
        if (li <= ti and ti < ri and lj <= tj and tj < rj) {
            if (s[ti][tj] == '#') return;
        }
        S st(li, ri, lj, rj, ti, tj);
        if (dist.count(st)) return;
        dist[st] = d;
        q.emplace(st);
    };
    
    push(0, h, 0, w, si, sj, 0);
    while (q.size()) {
        int d = dist[q.front()];
        auto [li, ri, lj, rj, ti, tj] = q.front(); q.pop();
        
        {
            int cnt = 0;
            for (int i = li; i < ri; ++i) {
                for (int j = lj; j < rj; ++j) {
                    if (s[i][j] == '#') cnt++;
                }
            }
            if (cnt == 0) {
                cout << d << '\n';
                return 0;
            }
        }
        
        push(li, ri, lj, rj, ti-1, tj, d+1);
        push(li, ri, lj, rj, ti+1, tj, d+1);
        push(li, ri, lj, rj, ti, tj-1, d+1);
        push(li, ri, lj, rj, ti, tj+1, d+1);
    }
    
    puts("-1");
    
    return 0;
}

F. Not Adjacent

折半搜索
發(fā)現(xiàn)兩邊還是有 \(30\) 個(gè)數(shù)，但注意到每邊最多取到 \(15\) 個(gè)數(shù)，所以直接搜就行

代碼實(shí)現(xiàn) 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    auto enumerate = [&](int l, int r) {
        vector<int> d0 = {0}, d1 = {0};
        for (int i = l; i < r; ++i) {
            vector<int> d2 = d1;
            for (int x : d0) d2.push_back((x+a[i])%m);
            swap(d0, d1);
            swap(d1, d2);
        }
        return d1;
    };
    
    ll ans = 0;
    int c = n/2;
    rep(ci, 2) {
        auto dl = enumerate(0, c-ci);
        auto dr = enumerate(c+1+ci, n);
        sort(dr.begin(), dr.end());
        for (int x : dl) {
            if (ci) x += a[c], x %= m;
            int y = (m-x)%m;
            int l = lower_bound(dr.begin(), dr.end(), y) - dr.begin();
            int r = upper_bound(dr.begin(), dr.end(), y) - dr.begin();
            ans += r-l;
        }
    }
    
    cout << ans << '\n';
    
    return 0;
}

另外，不相鄰子序列的數(shù)量其實(shí)是斐波那契數(shù)列（雖然用了這個(gè)也沒(méi)有變的很快）

代碼實(shí)現(xiàn) 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    vector<int> fib(n+1, 1);
    for (int i = 2; i <= n; ++i) fib[i] = fib[i-1]+fib[i-2];
    
    auto enumerate = [&](int l, int r) -> vector<int> {
        if (l >= r) return {0};
        int w = r-l;
        vector<int> res(fib[w+1]);
        for (int s = 1, fi = 1; s < fib[w+1]; ++s) {
            if (fib[fi+1] <= s) fi++;
            res[s] = (a[r-fi]+res[s-fib[fi]])%m;
        }
        return res;
    };
    
    ll ans = 0;
    int c = n/2;
    rep(ci, 2) {
        auto dl = enumerate(0, c-ci);
        auto dr = enumerate(c+1+ci, n);
        sort(dr.begin(), dr.end());
        for (int x : dl) {
            if (ci) x += a[c], x %= m;
            int y = (m-x)%m;
            int l = lower_bound(dr.begin(), dr.end(), y) - dr.begin();
            int r = upper_bound(dr.begin(), dr.end(), y) - dr.begin();
            ans += r-l;
        }
    }
    
    cout << ans << '\n';
    
    return 0;
}

G. Takahashi's Expectation 2

二進(jìn)制分組+塊間合并

直接看StarSilk的題解