SMU Summer 2024 Contest Round 5

A Robot Takahashi

思路：

将所有数排序，枚举孩子成人的分解点X，同时根据s的标识维护正真的孩子成人的个数

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int sum = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '1') sum ++;
    }
    vector<PII> w(n);
    for (int i = 0; i < n; ++i) {
        cin >> w[i].first;
        w[i].second = i;
    }
    sort(w.begin(), w.end());
    int a1 = sum, a0 = 0, ans = a1;
    for (int i = 0; i < w.size(); ++i) {
        int j = i;
        while (j < w.size() && w[j].first == w[i].first) {
            if (s[w[j ++].second] == '1') a1 --;
            else a0 ++;
        }
        i = j - 1;
        ans = max(ans, a1 + a0);
    }
    cout << ans;
}

B Connect 6

思路：

暴力枚举，注意对角线有两种\和/

void solve() {
    int n;
    cin >> n;
    vector<string> ve(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> ve[i];
        ve[i] = ' ' + ve[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int a = 0, b = 0, c = 0, d = 0;
            for (int k = 0; k < 6; ++k) {
                if (i >= 6 && j >= 6 && ve[i - k][j - k] == '#') a++;
                if (i >= 6 && j + 5 <= n && ve[i - k][j + k] == '#') d++;
                if (j >= 6 && ve[i][j - k] == '#') b++;
                if (i >= 6 && ve[i - k][j] == '#') c++;
            }
            if (a >= 4 || b >= 4 || c >= 4 || d >= 4) {
                cout << "Yes";
                return ;
            }
        }
    }
    cout << "No";
    return ;
}

C Strange Balls

思路：

用栈维护连续相同的数字及其个数，若满足数字等于个数就取出，同时记录总个数即为答案

void solve() {
    int n;
    cin >> n;
    vector<int> cnt (n + 1);
    vector<PII> ve;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (ve.size() && ve.back().first == x) {
            ve.back().second ++, ans ++;
        } else {
            ve.push_back({x, 1}), ans ++;
        }
        if (ve.size() && ve.back().first == ve.back().second) {
            ans -= ve.back().second;
            ve.pop_back();
        }
        cout << ans << '\n';
    }
}

D Linear Probing

思路：

用类似路径压缩的方式找到下一个空的位置

数组不是很大，也可以直接用set存所有空的位置，每次赋值时二分找位置，找到后从set中删掉该位置，注意的是可能位置太靠后以至于后面没有空位置，那就手动把位置调到0即可

void solve() {
    int q;
    cin >> q;
    int n = pow(2, 20);
    vector<int> val(n, -1);
    set<int> se;
    for (int i = 0; i < n; ++i) {
        se.insert(i);
    }
    while (q --) {
        int t, x;
        cin >> t >> x;
        int s = x;
        x %= n;
        if (t == 2) {
            cout << val[x] << '\n';
        } else {
            auto p = se.lower_bound(x);
            if (p == se.end()) {
                x = 0;
                p = se.lower_bound(x);
            }
            val[*p] = s;
            se.erase(p);
        }
    }

}

F Stronger Takahashi

题目链接

思路：01bfs，优先做0步的操作，再做1步的操作，用双端队列维护

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int dxx[20] = {-2, -2, -2, -1, -1,
               -1, -1, -1, 0, 0,
               0, 0, 1, 1, 1,
               1 ,1, 2, 2, 2};
int dyy[20] = {-1, 0, 1, -2, -1,
               0, 1, 2, -2, -1,
               1, 2, -2, -1, 0,
               1, 2, -1, 0, 1};

void solve() {
    int h, w;
    cin >> h >> w;
    vector<string> ve(h + 1);
    for (int i = 1; i <= h; ++i) {
        cin >> ve[i];
        ve[i] = ' ' + ve[i];
    }
    deque<pair<PII, int> > q;
    vector<vector<int> > dis(h + 1, vector<int> (w + 1, -1));
    q.push_back({{1, 1}, 0});
    while (q.size()) {
        auto [u, ww] = q.front();
        q.pop_front();
        int x = u.first, y = u.second;
        if (dis[x][y] != -1) continue;
        dis[x][y] = ww;
        for (int i = 0; i < 4; ++i) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx < 1 || xx > h || yy < 1 || yy > w || ve[xx][yy] != '.') continue;
            q.push_front({{xx, yy}, ww});
        }
        for (int i = 0; i < 20; ++i) {
            int xx = x + dxx[i], yy = y + dyy[i];
            if (xx < 1 || xx > h || yy < 1 || yy > w) continue;
            q.push_back({{xx, yy}, ww + 1});
        }
    }
    cout << dis[h][w];
}

E Red Polyomino

题目链接

思路：暴力dfs+剪枝，枚举下一步改颜色的位置

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void solve() {
    int n, k;
    cin >> n >> k;
    vector<string> s(n);
    for (int i = 0; i < n; ++i) cin >> s[i];
    map<vector<string>, int> st;
    int ans = 0;
    auto dfs = [&] (int cnt, auto dfs) -> void {
        if (st.count(s)) return ;
        st[s] = 1;
        if (cnt == 0) {
            ans ++;
            return ;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (s[i][j] == '.') {
                    for (int k = 0; k < 4; ++k) {
                        int xx = i + dx[k], yy = j + dy[k];
                        if (xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
                        if (s[xx][yy] == 'j') {
                            s[i][j] = 'j';
                            dfs(cnt - 1, dfs);
                            s[i][j] = '.';
                            break;
                        }
                    }
                }
            }
        }
    };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (s[i][j] == '.') {
                s[i][j] = 'j';
                dfs(k - 1, dfs);
                s[i][j] = '.';
            }
        }
    }
    cout << ans;
}

G Predilection

题目链接

思路：

递推，相邻的数才进行合并，用f[i]表示前i个数的答案

第i个数没合并前，与f[i - 1]个序列构成一种序列，贡献为f[i - 1]

第i个数合并后，与f[i - 1]个序列的最后一个数进行合并，贡献为f[i - 1]

但是存在0的话会有重复的情况，就需要消去加入a[i]后出现的0带来的贡献，即找到后缀和为0的最大下标j，消去的贡献为f[j - 1]

为啥只消最大的下标j呢，因为之前的已经f[j]消掉了

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), r(n + 5);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = n; i >= 1; --i) {
        r[i] = a[i] + r[i + 1];
    }
    map<int, int> pre;
    vector<int> f(n + 1);
    f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        f[i] = f[i - 1] * 2 % mod;
        f[i] = (f[i] - pre[r[i]] + mod) % mod;
        pre[r[i]] = f[i - 1];
    }
    cout << f[n];
}