2026 TOI 初選

先講結果：223 / 500 分，rk.48

1. 快樂數

題目 PDF

上傳紀錄

當時上傳的程式碼

100 / 100 分

#include<bits/stdc++.h>
using namespace std;
int f(int x) {
    int sum = 0;
    do{
        sum += (x % 10) * (x % 10);
    } while (x /= 10);
    return sum;
}
int main() {
    int n;
    cin >> n;
    unordered_map<int, int> mp;
    int ans = 0;
    mp[n]++;
    while (n != 1) {
        n = f(n);
        ans++;
        if (mp[n]++) {
            cout << n;
            return 0;
        }
    }
    cout << ans;
}

2. 河內塔

題目 PDF

上傳紀錄

當時上傳的程式碼

忘記河內塔咋寫了，啥都沒上傳。

3. 大中括

題目 PDF

上傳紀錄

當時上傳的程式碼

19 / 100 分

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> v(m);
    for (auto &[x, y] : v) cin >> x >> y;
    for (int i = 0;i < m;i++) for (int j = i + 1;j < m;j++) {
        if (v[i].first < v[j].first and v[j].first <= v[i].second and v[i].second < v[j].second) {
            cout << m - 1;
            return 0;
        }
        if (v[j].first < v[i].first and v[i].first <= v[j].second and v[j].second < v[i].second) {
            cout << m - 1;
            return 0;
        }
    }
    cout << m;
}

4. 新高價

題目 PDF

上傳紀錄

當時上傳的程式碼

17 / 100 分

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (auto &x : v) cin >> x;
    int l = 0, r = n - 1;
    int ans = 0;
    while (l <= r) {
        int m = (l + r) / 2, cnt = 0;
        for (int i = 0;i < n;i++) {
            int now = v[i];
            for (int j = i + 1;j <= min(i + m, n - 1);j++) if (v[j] > now) {
                cnt += v[j];
                now = v[j];
            }
        }
        if (cnt <= k) l = m + 1, ans = m;
        else r = m - 1;
    }
    cout << ans;
}

---

34 / 100 分

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (auto &x : v) cin >> x;
    int l = 0, r = n - 1;
    int ans = 0;
    while (l <= r) {
        int m = (l + r) / 2, cnt = 0;
        for (int i = 1;i < n;i++) {
            cnt += v[i] * min(i, m);
        }
        if (cnt <= k) l = m + 1, ans = m;
        else r = m - 1;
    }
    cout << ans;
}

---

100 / 100 分

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> v(n), left(n, 1000000);
    for (auto &x : v) cin >> x;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    for (int i = n - 1;i >= 0;i--) {
        while (!q.empty() and v[i] >= q.top().first) {
            left[q.top().second] = q.top().second - i;
            q.pop();
        }
        q.push({v[i], i});
    }
    // for (int i = 0;i < n;i++) cout << left[i] << ' ';
    int l = 0, r = n - 1;
    int ans = 0;
    while (l <= r) {
        int m = (l + r) / 2, cnt = 0;
        for (int i = 1;i < n;i++) cnt += v[i] * min({i, m, left[i] - 1});
        if (cnt <= k) l = m + 1, ans = m;
        else r = m - 1;
    }
    cout << ans;
}

5. 幾乎獨立的分店

題目 PDF

上傳紀錄

當時上傳的程式碼

4 / 100 分

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n + 1);
	vector<vector<int>> v(n + 1);
	for (int i = 0;i < n;i++) cin >> a[i];
	for (int i = 1;i < n;i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int ans = 0;
	for (int j = 0;j < (1 << n);j++) {
		bool flag = 1;
		for (int i = 0;i < n;i++) {
			if (!((1 << i) & j)) continue;
			int cnt = 0;
			for (auto ni : v[i]) if ((1 << ni) & j) cnt++;
			if (cnt > k) {
				flag = 0;
				break;
			}
		}
		if (flag) {
			int sum = 0;
			for (int i = 0;i < n;i++) if ((1 << i) & j) sum += a[i];
			ans = max(ans, sum);
		}
	}
	cout << ans;
}