The 2020 ICPC Asia Taipei-Hsinchu Site Programming Contest

A Right-Coupled Numbers

暴力

int main() {
    for (read(_); _; --_) {
        read(n); bool f = 0; 
        per (i, sqrt(n), 1) if (n % i == 0 && i * 2 >= n / i) f = 1;
        write(f); puts("");
    }
    return 0;
}

B Make Numbers

枚举去重

int main() {
    IOS; rep (i, 0, 3) cin >> a[i]; sort(a, a + 4);
    st.insert(a[0] + a[1] + a[2] + a[3]);
    st.insert(a[0] * a[1] * a[2] * a[3]);
    do {
        st.insert(abs(a[0] + a[1] + a[2] - a[3]));
        st.insert(abs(a[0] + a[1] - a[2] - a[3]));
        st.insert(a[0] * a[1] + a[2] + a[3]);
        st.insert(a[0] * a[1] + a[2] * a[3]);
        st.insert(abs(a[0] * a[1] - a[2] - a[3]));
        st.insert(abs(a[0] * a[1] - a[2] + a[3]));
        st.insert(abs(a[0] * a[1] - a[2] * a[3]));
        st.insert(a[0] + a[1] * a[2] * a[3]);
        st.insert(abs(a[0] - a[1] * a[2] * a[3]));
        st.insert(a[0] * 10 + a[1] + a[2] + a[3]);
        st.insert(a[0] * 10 + a[1] + a[2] * a[3]);
        st.insert(abs(a[0] * 10 + a[1] - a[2] - a[3]));
        st.insert(abs(a[0] * 10 + a[1] - a[2] + a[3]));
        st.insert(abs(a[0] * 10 + a[1] - a[2] * a[3]));
        st.insert((a[0] * 10 + a[1]) * a[2] + a[3]);
        st.insert((a[0] * 10 + a[1]) * a[2] - a[3]);
        st.insert((a[0] * 10 + a[1]) * a[2] * a[3]);
        st.insert(a[0] * 100 + a[1] * 10 + a[2] + a[3]);
        st.insert(a[0] * 100 + a[1] * 10 + a[2] - a[3]);
        st.insert((a[0] * 100 + a[1] * 10 + a[2]) * a[3]);
        st.insert((a[0] * 10 + a[1]) + (a[2] * 10 + a[3]));
        st.insert(abs((a[0] * 10 + a[1]) - (a[2] * 10 + a[3])));
        st.insert((a[0] * 10 + a[1]) * (a[2] * 10 + a[3]));
    } while (next_permutation(a, a + 4));
    cout << st.size();
    return 0;
}

C Pyramid

根据前 k - 1 个小球确定每个开关的状态, 顺便转移第 k 个小球就好

空间复杂度不够, 用滚动数组优化 f[i&1][j] 表示当前 第i层 第j个节点 经过 的小球的数量

int f[2][N];
 
int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n >> m; int ans = 0;
        if (n == 1) { cout << "0\n"; continue; }
        f[0][0] = m - 1;
        if (f[0][0] & 1) ++ans;
        rep (i, 1, n - 2) {
            int las = 0, cur = -1;
            rep (j, 0, i - 1) {
                f[i & 1][++cur] = las + (f[(i + 1) & 1][j] + 1 >> 1);
                las = f[(i + 1) & 1][j] >> 1;
            }
            f[i & 1][++cur] = las;
            if (f[i & 1][ans] & 1) ++ans;
        }
        cout << ans << '\n';
    }
    return 0;
}

D Quality Monitoring

E A Color Game

祖玛, 明显的区间dp, 共7种颜色,

故设状态 f[l][r][k] 表示区间 [l, r] 其他颜色消除之后剩下颜色k的小球的数量(如果不存在将其他颜色全部消除, 设-inf)

所以目标状态就是 存在 f[1][n][k] >= m, 即整个学列能消除到最后只剩 f[1][n][k] 个颜色k的小球, 且能消除完

特判一个就可以消除的情况

int id[100], f[N][N][8];
string t = "ARGBCMYK";
char s[N];
 
int main() {
    IOS; cin >> s + 1 >> m; n = strlen(s + 1);
    if (m == 1) return cout << "Yes", 0;
    rep (i, 1, t.size() - 1) id[t[i]] = i;
    memset(f, 0xcf, sizeof f);
    rep (i, 1, n) f[i][i][id[s[i]]] = 1;
    rep (len, 2, n) rep (l, 1, n + 1 - len) {
        int r = l + len - 1; bool g = 0;
        rep (i, l, r - 1) rep (k, 1, 7) {
            umax(f[l][r][k], f[l][i][k] + f[i + 1][r][k]);
            if (f[l][r][k] >= m) g = 1;
        }
        rep (k, 1, 7) if (f[l][r][k] < 0 && g) f[l][r][k] = 0;
    }
    rep (i, 1, 7) if (f[1][n][i] >= m) return cout << "Yes", 0;
    return cout << "No", 0;
}

F Cable Protection

最小点覆盖, 基环树拆环s, t, 分两种情况当成普通的树的最小点覆盖即可

一种以 s 为根, 一种以 t 为根

VI h[N << 1];
int f[N << 1], d[N << 1], s, t, ans;
 
void dfs(int x, int fa) {
    f[x] = 1; d[x] = 0;
    for (auto y : h[x]) if (y != fa)
        dfs(y, x), f[x] += min(f[y], d[y]), d[x] += f[y];
}
 
int main() {
    IOS; cin >> n >> m;
    rep (i, 1, n + m) {
        int x, y; cin >> x >> y; ++x, ++y;
        if (!s && x <= n && y <= n) { s = x, t = y; continue; }
        h[x].pb(y); h[y].pb(x);
    }
    dfs(s, 0); ans = f[s]; dfs(t, 0); umin(ans, f[t]);
    cout << ans;
    return 0;
}

G Graph Cards

H Optimization for UltraNet

明显的最小生成树, 却要最小的权值最大, 这不就是二分的套路吗?

直接二分最小权值, 再跑最小生成树判断是否存在即可

最后再跑一遍树上路径和即可

pair<int, PII> e[M];
int f[N], sz[N];
ll ans; bool a[M];
 
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
 
bool check(int mid) {
    rep(i, 1, n) f[i] = i; int k = 0;
    rep(i, lower_bound(e + 1, e + 1 + m, pair<int, PII>{mid, { 0, 0 }}) - e, m) {
        int x = find(e[i].se.fi), y = find(e[i].se.se);
        if (x == y) { a[i] = 0; continue; } ++k; f[y] = x; a[i] = 1;
    }
    return k == n - 1;
}
 
int main() {
    IOS; cin >> n >> m;
    rep(i, 1, m) cin >> e[i].se.fi >> e[i].se.se >> e[i].fi;
    sort(e + 1, e + 1 + m);
    int l = 0, r = 1e7 - 1;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    rep(i, 1, n) sz[i] = 1, f[i] = i;
    per(i, m, 1) if (a[i]) {
        if (e[i].fi < l) break;
        int x = find(e[i].se.fi), y = find(e[i].se.se);
        ans += (ll)sz[x] * sz[y] * e[i].fi;
        sz[x] += sz[y]; f[y] = x;
    }
    cout << ans;
    return 0;
}

I Optimization for UltraNet

J Puzzle Game

K Number with Bachelors

L Save lives or money

M Keystroke

按照题意状压枚举即可

int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n >> m; set<int> x, y;
        rep (i, 1, n) cin >> k, x.insert(k);
        rep (j, 1, m) cin >> k, y.insert(k); k = 0;
        rep (i, 0, 1 << 4) {
            set<int> a, b;
            rep (j, 0, 3) if (i >> j & 1) a.insert(j >> 1), b.insert(j % 2);
            if (a == x && y == b) ++k;
        }
        cout << k << '\n';
    }
    return 0;
}