Star 的档案库

Appearance

2026夏组队训练赛第十六场 ​

C. Distributing Candies ​

cpp
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;
        if (n & 1) cout << "No\n";
        else cout << "Yes\n" << n / 2 << ' ' << n / 2 << '\n';
    }
    return 0;
}

F. Bitwise And Path ​

cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

struct dsu {
    int fa[N], n;

    void init(int n) {
        this->n = n;
        for (int i = 1; i <= n; ++i) fa[i] = i;
    }

    int getfa(int x) {
        return x == fa[x] ? x : fa[x] = getfa(fa[x]);
    }

    void merge(int x, int y) {
        x = getfa(x), y = getfa(y);
        fa[y] = x;
    }

    bool check(int x, int y) {
        return getfa(x) == getfa(y);
    }
} a[1 << 12];
int que[(1 << 12) + 10], hh, tt;
bool vis[1 << 12];

void upd(int x, int y, int z) {
    hh = 0, tt = -1;
    if (a[z].check(x, y)) return;
    a[z].merge(x, y);
    que[++tt] = z;
    vis[z] = true;
    while (hh <= tt) {
        int cur = que[hh++];
        for (int i = 0; i < 12; ++i) {
            if (cur >> i & 1) {
                int nxt = cur ^ 1 << i;
                if (!vis[nxt] && a[nxt].check(x, y) == 0) que[++tt] = nxt, a[nxt].merge(x, y), vis[nxt] = true;
            }
        }
    }
    for (int i = 0; i <= tt; ++i) vis[que[i]] = 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, q;
        cin >> n >> q;
        long long ans = 0;
        for (int i = 0; i < (1 << 12); ++i) a[i].init(n);
        while (q--) {
            char op;
            cin >> op;
            if (op == '+') {
                int x, y, z;
                cin >> x >> y >> z;
                upd(x, y, z);
            }
            else {
                int x, y;
                cin >> x >> y;
                int res = 0;
                for (int i = 11; i >= 0; --i) {
                    if (a[res | 1 << i].check(x, y)) res |= 1 << i;
                }
                // cout << res << '\n';
                if (a[res].check(x, y)) ans += res;
                else ans--;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

G. Bucket Bonanza ​

cpp
#include <bits/stdc++.h>
#define vi vector<int>
#define int long long
using namespace std;

void solve(){
    int n;
    cin>>n;
    vector<int>v(n), l(n);
    set<pair<int, int>> sv;
    set<pair<int, int>, greater<pair<int, int>>> sl;
    int id=n;
    int sumv = 0, suml = 0;
    for(int i=0;i<n;i++)cin>>v[i], sv.emplace(v[i], i), sumv += v[i];
    for(int i=0;i<n;i++)cin>>l[i], sl.emplace(l[i], i), suml += l[i];
    
    int q;
    cin >> q;
    vector<pair<int, int>> qs(q);
    vector<int> res(q);
    for (int i = 0; i < q; ++i) cin >> qs[i].first, qs[i].second = i;
    sort(qs.begin(), qs.end());
    for (int i = 0; i < q; ++i) {
        int t = qs[i].first;
        while (!sv.empty() && sv.begin()->first - t * sl.begin()->first < 0) {
            auto p = sv.begin(), q = sl.begin();
            int x = p->second, y = q->second;
            if (sv.begin()->second == sl.begin()->second) {
                sumv -= v[x];
                suml -= l[x];
                sv.erase(p), sl.erase(q);
            }
            else {
                sumv -= v[x] + v[y];
                suml -= l[x] + l[y];
                sv.erase({v[x], x}), sv.erase({v[y], y});
                sl.erase({l[x], x}), sl.erase({l[y], y});
                v[x] = max(v[x], v[y]);
                l[x] = min(l[x], l[y]);
                sv.insert({v[x], x}), sl.insert({l[x], x});
                sumv += v[x], suml += l[x];
            }
        }
        res[qs[i].second] = sumv - suml * t;
    }
    for (int i : res) cout << i << ' ';
    cout << '\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
}

I. Chi Fan ​

cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 2e3 + 5, M = 5e3 + 5;
const ld INF = 1e100;

ll a[N], c[N];
ll b[N], d[N], e[N], p[N];
ld dp[2][M][2][2];

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

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) cin >> a[i] >> b[i] >> c[i] >> d[i] >> e[i] >> p[i];

    int cur = 0, nxt = 1;

    for (int i = n; i >= 1; i --) {
        for (int j = 0; j <= m; j ++)
            for (int x = 0; x < 2; x ++)
                for (int y = 0; y < 2; y ++)
                    dp[nxt][j][x][y] = -INF;

        ld P = (ld)p[i] / 100;

        for (int j = 0; j <= m; j ++) {
            for (int x = 0; x < 2; x ++) {
                for (int y = 0; y < 2; y ++) {
                    if (j >= b[i]) {
                        int k = j - b[i];
                        ld v = a[i] + P * dp[cur][k][1][y] + (1 - P) * dp[cur][k][x][1];
                        dp[nxt][j][x][y] = max(dp[nxt][j][x][y], v);
                    }

                    if (x && y) {
                        if (j >= d[i] + e[i]) {
                            int k = j - d[i] - e[i];
                            ld v = c[i] + dp[cur][k][0][0];
                            dp[nxt][j][x][y] = max(dp[nxt][j][x][y], v);
                        }
                    } else {
                        if (j >= d[i]) {
                            int k = j - d[i];
                            ld v = c[i] + P * dp[cur][k][1][y] + (1 - P) * dp[cur][k][x][1];
                            dp[nxt][j][x][y] = max(dp[nxt][j][x][y], v);
                        }
                    }
                }
            }
        }

        swap(cur, nxt);
    }

    ld ans = dp[cur][m][0][0];

    if (ans < 0) cout << -1 << '\n';
    else cout << fixed << setprecision(10) << ans << '\n';
}

K. Xiangqi ​

发现搜两步移动就能判断出来。

cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 11;
bool f[N][N][N][N][2];
int vis[N][N][N][N][2];

bool dfs(int x1, int y1, int x2, int y2, int flg, int d) {
    // if (vis[x1][y1][x2][y2][flg]) return;
    // vis[x1][y1][x2][y2][flg] = 1;
    if (x1 == x2 && y1 == y2) return false;
    if (d == 0) {
        if (x1 == x2 && y1 == y2) {
            // f[x1][y1][x2][y2][flg] = 0;
            return false;
        }
        return true;
    }
    if (flg == 0) {
        if (x1 + 1 != x2 || y1 != y2) {
            if (x1 + 2 <= 9 && y1 + 1 <= 10) {
                if (!dfs(x1 + 2, y1 + 1, x2, y2, 1, d - 1)) return true;
                // if (!f[x1 + 2][y1 + 1][x2][y2][1]) f[x1][y1][x2][y2][0] = true;
            }
            if (x1 + 2 <= 9 && y1 - 1 > 0) {
                if (!dfs(x1 + 2, y1 - 1, x2, y2, 1, d - 1)) return true;
                // if (!f[x1 + 2][y1 - 1][x2][y2][1]) f[x1][y1][x2][y2][0] = true;
            }
        }

        if (x1 - 1 != x2 || y1 != y2) {
            if (x1 - 2 > 0 && y1 + 1 <= 10) {
                if (!dfs(x1 - 2, y1 + 1, x2, y2, 1, d - 1)) return true;
                // if (!f[x1 - 2][y1 + 1][x2][y2][1]) f[x1][y1][x2][y2][0] = true;
            }
            if (x1 - 2 > 0 && y1 - 1 > 0) {
                if (!dfs(x1 - 2, y1 - 1, x2, y2, 1, d - 1)) return true;
                // if (!f[x1 - 2][y1 - 1][x2][y2][1]) f[x1][y1][x2][y2][0] = true;
            }
        }

        if (x1 != x2 || y1 + 1 != y2) {
            if (x1 + 1 <= 9 && y1 + 2 <= 10) {
                if (!dfs(x1 + 1, y1 + 2, x2, y2, 1, d - 1)) return true;
                // if (!f[x1 + 1][y1 + 2][x2][y2][1]) f[x1][y1][x2][y2][0] = true;
            }
            if (x1 - 1 > 0 && y1 + 2 <= 10) {
                if (!dfs(x1 - 1, y1 + 2, x2, y2, 1, d - 1)) return true;
                // if (!f[x1 - 1][y1 + 2][x2][y2][1]) f[x1][y1][x2][y2][0] = true;
            }
        }

        if (x1 != x2 || y1 - 1 != y2) {
            if (x1 + 1 <= 9 && y1 - 2 > 0) {
                if (!dfs(x1 + 1, y1 - 2, x2, y2, 1, d - 1)) return true;
                // if (!f[x1 + 1][y1 - 2][x2][y2][1]) f[x1][y1][x2][y2][0] = true;
            }
            if (x1 - 1 > 0 && y1 - 2 > 0) {
                if (!dfs(x1 - 1, y1 - 2, x2, y2, 1, d - 1)) return true;
                // if (!f[x1 - 1][y1 - 2][x2][y2][1]) f[x1][y1][x2][y2][0] = true;
            }
        }
        
    } else {
        if (x1 == x2 || y1 == y2) return true;
        else {
            for (int i = 1; i <= 9; ++i) {
                if (x2 != i) {
                    if (!dfs(x1, y1, i, y2, 0, d - 1)) return true;
                    // if (!f[x1][y1][i][y2][0]) f[x1][y1][x2][y2][1] = true;
                }
            }
            for (int i = 1; i <= 10; ++i) {
                if (y2 != i) {
                    if (!dfs(x1, y1, x2, i, 0, d - 1)) return true;
                    // if (!f[x1][y1][x2][i][0]) f[x1][y1][x2][y2][1] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (dfs(x1, y1, x2, y2, 0, 2)) cout << "NO\n";
        else cout << "YES\n";
        // cout << (f[x1][y1][x2][y2][0] ? "NO\n" : "YES\n");
    }
    return 0;
}

其他没做的题

  • Wow, It’s Yesterday Six Times More
  • What, More Kangaroos?
  • Fallleaves01 and Golf
  • Cyan White Tree
  • Pen Pineapple Apple Pen
  • Trajan Algorithm
  • Regional Champion
  • Many Convex Polygons