Star 的档案库

Appearance

2026夏组队训练赛第一场 ​

A. Find the Strongest Card ​

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

void solve(int n) {
	vector<int> a(14);
	for (int i = 1; i <= n; i ++) {
		int x;
		cin >> x;
		a[x] = 1;
	}
	if (a[2]) {
		cout << 2 << '\n';
	} else if (a[1]) cout << 1 << '\n';
	else {
		for (int i = 13; i >= 1; i --) {
			if (a[i]) {
				cout << i << '\n';
				return;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt", "r", stdin); 
	int n;
	while (cin >> n && n) solve(n);
}

B. Vending Machines ​

  • 二分查找
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';

void solve(int n, int d) {
	vector<int> a(n);
	for (int i = 0; i < n; i ++) cin >> a[i];

	auto calc = [&](int x) -> bool {
		int last = -1e9;
		int need = 0;
		for (auto i : a) {
			if (i - last > d) {
				need ++;
				last = i + d;
			}
		}
		return need <= x;
	};

	int l = 0, r = 200;
	while (l < r) {
		int mid = (l + r) >> 1;
		//debug(calc(mid))
		if (calc(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt", "r", stdin); 
	int n, d;
	while (cin >> n >> d && n && d) solve(n, d);
}

C. Water Remaining ​

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

#define int long long
#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';

void solve(int n) {
	vector<int> a(n + 1), l(n + 1), r(n + 1);
	for (int i = 1; i <= n; i ++) cin >> a[i];

	ll ans = 0;

	int t = 1e9;
	for (int i = 1; i <= n; i ++) {
		l[i] = t;
		t = min(t, a[i]);
	}
	t = 1e9;
	for (int i = n; i >= 1; i --) {
		r[i] = t;
		t = min(t, a[i]);
	}

	//for (int i = 1; i <= n; i ++) cout << l[i] << ' '; DL
	//for (int i = 1; i <= n; i ++) cout << r[i] << ' '; DL

	for (int i = 1; i <= n; i ++) {
		int x = a[i] - max(l[i], r[i]);
		x = max(0ll, x);
		ans += x;
	}
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt", "r", stdin); 
	int n;
	while (cin >> n && n) solve(n);
}

D. Frequency Sequence ​

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

#define int long long
#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';

void solve(int s, int k) {
	if (k == 1) {
		cout << s << '\n';
		return;
	}
	k --;

	if (k <= s * s) {
		int l = 1, r = s;

		auto calc = [&](int x) {
			int a1 = s * 2 - 1;
			int cnt = (__int128)x * a1 - x * (x - 1);
			return cnt >= k;
		};

		while (l < r) {
			int mid = (l + r) >> 1;
			if (calc(mid)) r = mid;
			else l = mid + 1;
		}

		l --;
		int a1 = s * 2 - 1;
		int cnt = (__int128)l * a1 - l * (l - 1);
		l ++;
		k -= cnt;
		if (k == 1) cout << l << '\n';
		else {
			k --;
			int b = k / 2;
			if (k & 1) cout << l << '\n';
			else cout << l + b << '\n';
		}
		return;
	}
	k -= s * s;
	int b = k / (s * 2);
	int p = k % (s * 2);
	//debug(b) debug(p)
	if (p % 2) cout << s + b + 1 << '\n';
	else {
		if (p / 2 == 0) cout << s << '\n';
		else cout << p / 2 << '\n';
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt", "r", stdin); 
	

	//freopen("out1.txt", "w", stdout);
	//for (int i = 1; i <= 400; i ++) solve(7, i);


	//return 0;

	int s, k;
	while (cin >> s >> k && s && k) solve(s, k);
}

E. Shopping Master ​

  • 贪心
  • 优先队列
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';
#define int long long 

void solve(int n) {
	vector<int> a(n + 1), b(n + 1);
	for (int i = 1; i <= n; i ++) cin >> a[i] >> b[i];

	ll ans = 0;
	ll have_f = 0, mn = 1e18, p = 0;
	for (int i = 1; i <= n; i ++) {
		if (b[i]) {
			have_f = 1;
			if (a[i] < mn)  {
				mn = a[i];
				p = i;
			}
		}
	}

	// spe
	if (have_f == 0) {
		ll ans = 0;
		for (int i = 1; i <= n; i ++) ans += a[i];
		cout << ans << '\n';
		return;
	}
	ll k = b[p];

	priority_queue<ll, vector<ll>, greater<ll>> pq;
	for (int i = 1; i <= n; i ++) if (i != p) {
		if (b[i]) {
			pq.push(a[i]);
			k += b[i] - 1;			
		}
	}
	ans = mn;
	vector<ll> v;
	for (int i = 1; i <= n; i ++) if (b[i] == 0) v.push_back(a[i]);

	sort(v.begin(), v.end(), greater<ll>());

	//cout << size(v) << '\n';
	
	for (auto i : v) {
		//cout << i << ' ';
		if (k > 0) {
			k --;
			pq.push(i);
		} else if (pq.empty()) {
			ans += i;
		}
		else if (i > pq.top()) {
			ans += pq.top();
			pq.pop();	
		} else {
			ans += i;
		}
	}
	//DL
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt", "r", stdin); 
	int n;
	while (cin >> n && n) solve(n);
}

F. Optimizing a Map Application ​

  • Dijkstra
  • 离散化
cpp
#include <bits/stdc++.h>
using namespace std;

const long long INF = 2e18;

void solve() {
    int n, u, v;
    while (cin >> n >> u >> v && (n != 0 || u != 0 || v != 0)) {
        int m;
        cin >> m;
        vector<int> a(m), b(m), c(m), d(m);
        
        vector<int> R, C;
        R.push_back(1); R.push_back(n); R.push_back(u);
        C.push_back(1); C.push_back(n); C.push_back(v);

        for (int i = 0; i < m; ++i) {
            cin >> a[i] >> b[i] >> c[i] >> d[i];
            R.push_back(a[i]); R.push_back(b[i]);
            if (a[i] > 1) R.push_back(a[i] - 1);
            if (b[i] < n) R.push_back(b[i] + 1);

            C.push_back(c[i]); C.push_back(d[i]);
            if (c[i] > 1) C.push_back(c[i] - 1);
            if (d[i] < n) C.push_back(d[i] + 1);
        }
        sort(R.begin(), R.end());
        R.erase(unique(R.begin(), R.end()), R.end());
        sort(C.begin(), C.end());
        C.erase(unique(C.begin(), C.end()), C.end());

        int r_sz = R.size(), c_sz = C.size();
        vector<vector<bool>> blocked(r_sz, vector<bool>(c_sz, false));
        for (int k = 0; k < m; ++k) {
            int r1 = lower_bound(R.begin(), R.end(), a[k]) - R.begin();
            int r2 = lower_bound(R.begin(), R.end(), b[k]) - R.begin();
            int c1 = lower_bound(C.begin(), C.end(), c[k]) - C.begin();
            int c2 = lower_bound(C.begin(), C.end(), d[k]) - C.begin();
            for (int i = r1; i <= r2; ++i) {
                for (int j = c1; j <= c2; ++j) {
                    blocked[i][j] = true;
                }
            }
        }
        int u_idx = lower_bound(R.begin(), R.end(), u) - R.begin();
        int v_idx = lower_bound(C.begin(), C.end(), v) - C.begin();
        vector<vector<long long>> dist(r_sz, vector<long long>(c_sz, INF));
        using State = pair<long long, pair<int, int>>;
        priority_queue<State, vector<State>, greater<State>> pq;

        dist[u_idx][v_idx] = 0;
        pq.push({0, {u_idx, v_idx}});

        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};

        while (!pq.empty()) {
            auto top_elem = pq.top();
            pq.pop();
            long long d_curr = top_elem.first;
            int r_idx = top_elem.second.first;
            int c_idx = top_elem.second.second;

            if (d_curr > dist[r_idx][c_idx]) continue;

            for (int dir = 0; dir < 4; ++dir) {
                int nr = r_idx + dr[dir];
                int nc = c_idx + dc[dir];
                if (nr >= 0 && nr < r_sz && nc >= 0 && nc < c_sz && !blocked[nr][nc]) {
                    long long weight = abs(R[nr] - R[r_idx]) + abs(C[nc] - C[c_idx]);
                    if (dist[r_idx][c_idx] + weight < dist[nr][nc]) {
                        dist[nr][nc] = dist[r_idx][c_idx] + weight;
                        pq.push({dist[nr][nc], {nr, nc}});
                    }
                }
            }
        }
        int q;
        cin >> q;
        while (q--) {
            int s, t;
            cin >> s >> t;
            
            int i2 = lower_bound(R.begin(), R.end(), s) - R.begin();
            int i1 = i2;
            if (R[i2] > s) i1 = i2 - 1; 

            int j2 = lower_bound(C.begin(), C.end(), t) - C.begin();
            int j1 = j2;
            if (C[j2] > t) j1 = j2 - 1; 
            long long ans = INF;
            int r_cands[] = {i1, i2};
            int c_cands[] = {j1, j2};

            for (int rx : {0, 1}) {
                for (int cx : {0, 1}) {
                    int rr = r_cands[rx];
                    int cc = c_cands[cx];
                    if (dist[rr][cc] != INF) {
                        long long cost = dist[rr][cc] + abs(R[rr] - s) + abs(C[cc] - t);
                        ans = min(ans, cost);
                    }
                }
            }
            if (ans == INF) cout << "no\n";
            else cout << ans << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
}

其他没做的题

  • Avoid Collision
  • Sorting Swim Rings
  • Speed Limit
  • Maximum Scaling