Star 的档案库

Appearance

2026夏组队训练赛第十场 ​

A. Take It or Double It ​

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

void solve() {
    ll a, b;
    cin >> a >> b;
    if (a * 2 <= b) cout << "double it";
    else cout << "take it";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    t = 1;
    while (t --) solve();
}

B. Twin Guardians ​

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

const int N = 1e6 + 5;
bool isp[N];

void init() {
    for (int i = 2; i <= 1e6; i ++) isp[i] = 1;
    for (int i = 2; i * i <= 1e6; i ++) {
        if (isp[i]) {
            for (int j = i * i; j <= 1e6; j += i) isp[j] = 0;
        }
    }
}
void solve() {
    int a, b;
    cin >> a >> b;
    if (b == a + 2 && isp[a] && isp[b]) cout << "Y\n";
    else cout << "N\n";
}

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

    init();

    int t;
    cin >> t;
    while (t --) solve();
}

C. One-Way Abyss ​

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

using ll = long long;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<ll> dp(n + 1);
    for (int i = 1; i <= m; i ++) {
        ll u, v, val;
        cin >> u >> v >> val;
        ll nu = dp[v] + val;
        ll nv = dp[u] + val;
        dp[u] = nu;
        dp[v] = nv;
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';
}

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

    int t;
    cin >> t;
    while (t --) solve();
}

D. Palindromic Distance ​

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

void solve() {
    string s;
    cin >> s;
    int n = size(s);

    vector<vector<int>> dp(n, vector<int>(n));

    for (int len = 2; len <= n; len ++) {
        for (int l = 0, r = l + len - 1; r < n; l ++, r ++) {
            dp[l][r] = min({dp[l + 1][r] + 1, dp[l][r - 1] + 1, dp[l + 1][r - 1] + (s[l] != s[r])});
        }
    }
    cout << dp[0][n - 1] << '\n';
}

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

    int t;
    cin >> t;
    while (t --) solve();
}

E. Explosive Slabstones Rearrangement ​

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

int a[505][505], vis[505][505], id;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

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

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

    for (int i = 1; i <= k; i ++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = i;
    }

    int u1, v1, u2, v2;
    cin >> u1 >> v1 >> u2 >> v2;

    auto fill = [&](int x) -> bool {
        for (int i = u1; i <= u2; i ++) {
            for (int j = v1; j <= v2; j ++) {
                if (a[i][j] > x) return 0;
            }
        }

        ++id;
        queue<pair<int, int>> q;

        for (int i = u1; i <= u2; i ++) {
            for (int j = v1; j <= v2; j ++) {
                if (vis[i][j] == id) continue;
                vis[i][j] = id;
                q.push({i, j});
            }
        }

        int emp = 0;
        while (!q.empty()) {
            auto [u, v] = q.front();
            q.pop();

            for (int d = 0; d < 4; d ++) {
                int nu = u + dx[d];
                int nv = v + dy[d];

                if (nu < 1 || nu > n || nv < 1 || nv > m) continue;
                if (a[nu][nv] > x || vis[nu][nv] == id) continue;

                vis[nu][nv] = id;
                q.push({nu, nv});
                if (!(nu >= u1 && nu <= u2 && nv >= v1 && nv <= v2)) {
                    emp += (a[nu][nv] == 0);
                }
            }
        }
        int cnt = 0;
        for (int i = u1; i <= u2; i ++) {
            for (int j = v1; j <= v2; j ++) {
                cnt += (a[i][j] != 0);
            }
        }
        return emp >= cnt;
    };
    int l = 0, r = k;

    while (l < r) {
        int mid = (l + r) >> 1;
        if (fill(mid)) r = mid;
        else l = mid + 1;
    }
    if (fill(l)) cout << l << '\n';
    else cout << -1 << '\n';
}

J. Gas Station ​

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

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

    int n, k;
    cin >> n >> k;

    vector<vector<pair<int, int>>> g(n + 1);

    ll L = 0, R = 0;
    for (int i = 1; i < n; i ++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        L = max(L, (ll)w);
        R += w;
    }

    int need;
    auto dfs = [&](auto self, int u, int fa, ll pe, ll x) -> ll {
        ll mx1 = 0, mx2 = 0, mxx = 0;
        int leaf = 1;

        for (auto [v, w] : g[u]) {
            if (v == fa) continue;
            leaf = 0;
            ll d = self(self, v, u, w, x);
            mxx = max(mxx, d + pe);
            if (d >= mx1) {
                mx2 = mx1;
                mx1 = d;
            }
            else if (d > mx2) {
                mx2 = d;
            }
        }
        if (leaf) return pe;
        if (mxx > x || mx1 + mx2 > x) {
            need ++;
            return pe;
        }
        return mxx;
    };

    auto valid = [&](ll x) -> bool {
        need = 0;
        dfs(dfs, 1, 0, 0, x);
        return need <= k;
    };

    while (L < R) {
        ll mid = (L + R) >> 1;
        if (valid(mid)) R = mid;
        else L = mid + 1;
    }

    cout << L;
}

K. Move Stone ​

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

const int N = 1e6 + 5, M = 1e6 + 5;
const ll INF = 1e18;

struct Dinic {
	int cnt = 1;
	int hd[N], nxt[M << 1], to[M << 1];
	ll cap[M << 1];

	int dis[N], cur[N], T;

	void add(int u, int v, ll w) {
		cap[++cnt] = w, to[cnt] = v, nxt[cnt] = hd[u], hd[u] = cnt;
		cap[++cnt] = 0, to[cnt] = u, nxt[cnt] = hd[v], hd[v] = cnt;
	}

	bool bfs(int s, int t) {
		memset(dis, -1, sizeof(dis));
		queue<int> q;
		dis[s] = 0;
		q.push(s);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int i = hd[u]; i; i = nxt[i]) {
				int v = to[i];
				if (dis[v] == -1 && cap[i] > 0) {
					dis[v] = dis[u] + 1;
					q.push(v);
				}
			}
		}
		return dis[t] != -1;
	}

	ll dfs(int u, ll flow) {
		if (u == T) return flow;
		ll used = 0;
		for (int &i = cur[u]; i && flow; i = nxt[i]) {
			int v = to[i];

			if (dis[v] == dis[u] + 1 && cap[i] > 0) {
				ll pushed = dfs(v, min(flow, cap[i]));

				if (pushed > 0) {
					cap[i] -= pushed;
					cap[i ^ 1] += pushed;

					used += pushed;
					flow -= pushed;
				}
			}
		}
		if (used == 0) dis[u] = -1;
		return used;
	}

	ll maxflow(int s, int t) {
		T = t;
		ll ans = 0;
		while (bfs(s, t)) {
			memcpy(cur, hd, sizeof(hd));
			ans += dfs(s, INF);
		}
		return ans;
	}
};

Dinic f;

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

	int n;
	cin >> n;

    int s = 0, p = 1;
 	ll sum = 0;

	for (int i = 0; i < n; i ++) {
		for (int j = 0; j < n; j ++) {
			int x;
			cin >> x;

			if (x > 1) {
				sum += x - 1;
				int u = p + i * n + j;
				f.add(0, u, x - 1);
				f.add(u, 1 + 2 * n * n + i, INF);
				f.add(u, 1 + 2 * n * n + n + j, INF);
			}
			else if (x == 0) {
				int u = 1 + n * n + i * n + j;
				f.add(1 + 2 * n * n + i, u, 1);
				f.add(1 + 2 * n * n + n + j, u, 1);
				f.add(u, 1 + 2 * n * n + 2 * n, 1);
			}
		}
	}
	int z = f.maxflow(s, 1 + 2 * n * n + 2 * n);
	cout << 2 * sum - z << '\n';
}

L. Stapler ​

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

struct Point {
    ll x, y;
    Point(ll x = 0, ll y = 0) : x(x), y(y){}
    friend istream& operator >> (istream& is, Point &p) {
        is >> p.x >> p.y;
        return is;
    }
};
struct Line {
    ll x1, y1, x2, y2;
    Line(Point a, Point b) {
        x1 = a.x, y1 = a.y, x2 = b.x, y2 = b.y;
    }
};

bool f(Line &l1, Line &l2) {
    if ((l1.x1 > l1.x2 ? l1.x1 : l1.x2) < (l2.x1 < l2.x2 ? l2.x1 : l2.x2) ||
        (l1.y1 > l1.y2 ? l1.y1 : l1.y2) < (l2.y1 < l2.y2 ? l2.y1 : l2.y2) ||
        (l2.x1 > l2.x2 ? l2.x1 : l2.x2) < (l1.x1 < l1.x2 ? l1.x1 : l1.x2) ||
        (l2.y1 > l2.y2 ? l2.y1 : l2.y2) < (l1.y1 < l1.y2 ? l1.y1 : l1.y2)) {
        return 0;
    }

    if ((((l1.x1 - l2.x1)*(l2.y2 - l2.y1) - (l1.y1 - l2.y1)*(l2.x2 - l2.x1))*
        ((l1.x2 - l2.x1)*(l2.y2 - l2.y1) - (l1.y2 - l2.y1)*(l2.x2 - l2.x1))) > 0 ||
        (((l2.x1 - l1.x1)*(l1.y2 - l1.y1) - (l2.y1 - l1.y1)*(l1.x2 - l1.x1))*
        ((l2.x2 - l1.x1)*(l1.y2 - l1.y1) - (l2.y2 - l1.y1)*(l1.x2 - l1.x1))) > 0) {
        return 0;
    }
    return 1;
}


void solve() {
    ll l, u, r, d;
    cin >> l >> d >> r >> u;

    Line L(Point(l, u), Point(l, d)), U(Point(l, u), Point(r, u)), R(Point(r, u), Point(r, d)), D(Point(l, d), Point(r, d));

    Point t1, t2;
    cin >> t1 >> t2;
    Line X(t1, t2);

    if (f(X, L) || f(X, U) || f(X, R) || f(X, D)) cout << "STOP\n";
    else if (t1.x >= l && t1.x <= r && t1.y >= d && t1.y <= u) cout << "STOP\n";
    else if (t2.x >= l && t2.x <= r && t2.y >= d && t2.y <= u) cout << "STOP\n";
    else cout << "OK\n";
}

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

    int t;
    cin >> t;
    while (t --) solve();
}

其他没做的题

  • Fruitful Compression
  • Gamer Bafuko
  • Chopsticks
  • Reactor