Star 的档案库

Appearance

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

B. Brickwork ​

扫描线，第一行和最后一行必须是整块，且相等剩下的每一行进来的和出去的必须完全一样。

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

using namespace std;

map<int, vector<tuple<int, int, int>>> mp;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x, y, w, h;
        cin >> x >> y >> h >> w;
        mp[x].emplace_back(y, y + w - 1, 1);
        mp[x + h].emplace_back(y, y + w - 1, -1);
    }
    auto check = [](vector<pair<int, int>> &v) -> vector<pair<int, int>> {
        if (v.empty()) return {};
        sort(v.begin(), v.end());
        vector<pair<int, int>> res = {v[0]};
        for (int i = 1; i < v.size(); ++i) {
            // cout << v[i].first << ' ' << res.back().second << '\n';
            if (v[i].first == res.back().second + 1) res.back().second = v[i].second;
            else if (v[i].first > res.back().second + 1) res.emplace_back(v[i]);
            else return {{-1, -1}};
        }
        return res;
    };
    vector<pair<int, int>> tmp1, tmp2;
    vector<pair<int, int>> t = {{-1, -1}};
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        // cout << "row " << it->first << '\n';
        vector<pair<int, int>> v1, v2;
        for (auto [l, r, f] : it->second)  {
            if (f == 1) v1.emplace_back(l, r);
            else v2.emplace_back(l, r);
            // cout << l << ' ' << r << ' ' << f << '\n';
        }
        auto p1 = check(v1), p2 = check(v2);
        // for (auto [l, r] : p1) cout << "[" << l << ',' << r << "] ";
        // cout << '\n';
        // for (auto [l, r] : p2) cout << "[" << l << ',' << r << "] ";
        // cout << '\n';
        if (p1 == t || p2 == t) {
            cout << "no\n";
            return 0;
        }
        else if (it == mp.begin()) {
            tmp1 = p1;
            continue;
        }
        else if (it == --mp.end()) {
            tmp2 = p2;
            continue;
        }
        else if (p1 == p2) continue;
        else {
            cout << "no\n";
            return 0;
        }
    }
    cout << (tmp1 == tmp2 && tmp1.size() == 1 ? "yes\n" : "no\n");
    return 0;
}

C. Colourful Captcha ​

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

char a[11][101];
map<char, int> mp;

void put(int x, int y, int len, int type) {
    if (type == 0) {
        for (int i = 0; i < len; i ++) a[x][y + i] = 'A';
    } else if (type == 1) {
        for (int i = 0; i < len; i ++) a[x][y + i] = 'A';
        a[x + 1][y] = a[x + 1][y + len - 1] = 'A';
        for (int i = 0; i < len; i ++) a[x + 2][y + i] = 'A';
    } else {
        for (int i = 0; i < len; i ++) a[x][y + i] = 'A';
        a[x + 1][y] = a[x + 1][y + len - 1] = 'A';
        for (int i = 0; i < len; i ++) a[x + 2][y + i] = 'A';
        a[x + 3][y] = a[x + 3][y + len - 1] = 'A';
        for (int i = 0; i < len; i ++) a[x + 4][y + i] = 'A';
    }
}

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

    //freopen("out.txt", "w", stdout);

    for (int i = 1; i <= 10; i ++) {
        for (int j = 1; j <= 100; j ++) {
            a[i][j] = '.';
        }
    }
    mp['B'] = 2;
    string tmp = "ADOPQR";
    for (auto c : tmp) mp[c] = 1;

    string s1, s2;
    cin >> s1 >> s2;

    int x = 1, y = 1;

    for (auto c : s1) {
        put(x, y, size(s2), mp[c]);
        y += 11;
    }

   
    
    y = 1;
    for (int i = 0; i < size(s1); i ++) {
        for (int j = 0; j < size(s2); j ++) {
            a[1][y + j] = s2[j];
        }
        y += 11;
    } 

	for (int i = 1; i <= 10; i ++) {
        for (int j = 1; j <= 100; j ++) {
            cout << a[i][j];
        }
        cout << '\n';
    }
}

D. Depot ​

背包 dp。

cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <complex>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
void pr(vector<int> a) {
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
const int mod = 998244353;
const int INF = 1e18;
const int N = 1e6 + 5;

void init() {}
void solve() {
    int n, m;
    cin >> n >> m;
    int s, k;
    cin >> s >> k;
    vvpii a(n);
    for (int i = 0; i < m; i++) {
        int it, mi, mo;
        cin >> it >> mi >> mo;
        a[it].pb({mi,mo});
    }
    int res=s;
    for(int i=1;i<n;i++){
        vi dp(res+1,0);
        for(int j=res;j>=0;j--){
            for(auto [w1,w2]:a[i]){
                if(j<w1)continue;
                if(j-w1+w2>k)continue;
                dp[j-w1]=max(dp[j-w1],min(dp[j]+w2,k-(j-w1)));
            }
        }
        res=dp[0];
        // cout<<res<<endl;
    }
    cout<<res<<endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    // cin>>t;
    while (t--) {
        solve();
    }
    return 0;
}

E. Enclosure ​

三分峰值。

cpp
#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef long double LD;
const LD PI = acosl(-1);

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int m, t;
        cin >> m >> t;
        int l = 3, r = t / m;
        auto calc = [&](int n) -> LD {
            return tanl(((LD)n - 2) * PI / (n * 2)) * (t - (LD)n * m) / n * (t - (LD)n * m) / n / 4 * n;
        };
        while (l + 1000 < r) {
            int m1 = (l * 2 + r) / 3, m2 = (l + r * 2) / 3;
            LD v1 = calc(m1), v2 = calc(m2);
            if (v1 > v2)
                r = m2;
            else
                l = m1;
        }
        LD res = 0;
        // cout << t / m << '\n';
        for (int i = l; i <= r; ++i) {
            res = max(res, calc(i));
        }
        cout << fixed << setprecision(10) << res << '\n';
    }
    return 0;
}

F. Fell Walking ​

枚举最小值，然后不断往后枚举最大值用 dsu 维护可行性。

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

using namespace std;

const int N = 5010;
vector<int> adj[N];
int h[N], pos[N];
int fa[N];

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);
    if (x != y) fa[y] = x;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].emplace_back(y);
        adj[y].emplace_back(x);
    }
    for (int i = 1; i <= n; ++i) pos[i] = i;
    sort(pos + 1, pos + n + 1, [&](int x, int y) {
        return h[x] < h[y]; 
    });
    int res = INT_MAX;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) fa[j] = j;
        for (int j = i; j <= n; ++j) {
            for (int y : adj[pos[j]]) {
                if (h[y] <= h[pos[j]] && h[y] >= h[pos[i]]) merge(pos[j], y);
            }
            if (getfa(1) == getfa(2)) {
                res = min(res, h[pos[j]] - h[pos[i]]);
                break;
            }
        }
    }
    cout << res << '\n';
    return 0;
}

G. Get Good ​

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

void solve() {
    ll n, a, b, x, y;
    cin >> n >> a >> b >> x >> y;

    ll need = min(n, x);
    ll ans = need * a;

    n -= need;

    ll T = (x + y);
    ll k = n / T;
    ll left = n % T;

    ll val1 = x * a;
    ll val2 = (x + y) * b;

    ans += k * max(val1, val2);

    ll work = max(0ll, left - y);
    val1 = work * a;
    val2 = left * b;
    ans += max(val1, val2);

    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

预处理 dfn 和深度

  • 对于第一个直接 bfs，过程中用 dfn 更新答案
  • 对于第二个遍历 dfs 序，用主席树维护子树中深度的区间和，查询深度严格小于目标点的和 dfn 小于等于目标点且深度等于目标点的，求和更新答案。
cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
vector<int> adj[N];
int dep[N], dfn[N], cnt[N], rk[N], t;

struct Node {
    int val, ls, rs;
} tr[N * 20];
int rt[N], tot;

void modify(int &u, int v, int l, int r, int p, int d) {
    u = ++tot;
    tr[u] = tr[v];
    if (l == r) tr[u].val += d;
    else {
        int mid = l + r >> 1;
        if (p <= mid) modify(tr[u].ls, tr[v].ls, l, mid, p, d);
        else modify(tr[u].rs, tr[v].rs, mid + 1, r, p, d);
        tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
    }
}

int query(int u, int v, int l, int r, int ql, int qr) {
    if (!u && !v) return 0;
    else if (ql <= l && r <= qr) return tr[u].val - tr[v].val;
    else {
        int mid = l + r >> 1, res = 0;
        if (ql <= mid) res += query(tr[u].ls, tr[v].ls, l, mid, ql, qr);
        if (qr > mid) res += query(tr[u].rs, tr[v].rs, mid + 1, r, ql, qr);
        return res;
    }
}

void dfs(int x, int fa) {
    dfn[x] = ++t;
    rk[t] = x;
    cnt[x] = 1;
    for (int y : adj[x]) {
        if (y == fa) continue;
        dep[y] = dep[x] + 1;
        dfs(y, x);
        cnt[x] += cnt[y];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, s;
    cin >> n >> s;
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].emplace_back(y);
        adj[y].emplace_back(x);
    }
    dep[1] = 1;
    dfs(1, 0);


    queue<pair<int, int>> q;
    q.emplace(1, 0);
    t = 0;
    int res = n;
    while (!q.empty()) {
        auto [x, fa] = q.front();
        q.pop();
        t++;

        if (dfn[x] <= dfn[s] && dfn[s] <= dfn[x] + cnt[x] - 1) {
            res = min(res, t + dfn[s] - dfn[x]);
        }

        for (int y : adj[x]) {
            if (y == fa) continue;
            q.emplace(y, x);
        }
    }
    cout << res << '\n';


    res = n;
    for (int i = 1; i <= n; ++i) {
        modify(rt[i], rt[i - 1], 1, n, dep[rk[i]], 1);
    }
    auto qsum = [&](int l, int r, int d1, int d2) -> int {
        return query(rt[r], rt[l], 1, n, d1, d2);
    };
    for (int i = 1; i <= n; ++i) {
        int x = rk[i];
        if (dfn[x] <= dfn[s] && dfn[s] <= dfn[x] + cnt[x] - 1) {
            res = min(res, i + qsum(i, i + cnt[x] - 1, 1, dep[s] - 1) + qsum(i, dfn[s], dep[s], dep[s]));
        }
    }
    cout << res << '\n';
    return 0;
}

I. Itsy Bits ​

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

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    long long x;
    cin >> x;
    for (int i = 0; i < 10; ++i) {
        if ((__int128_t)(1) << (1LL << i) > x) {
            if (i == 0) cout << "1 bit\n";
            else cout << (1LL << i) << " bits\n";
            return 0;
        }
    }
    return 0;
}

J. Joust Sort ​

拓扑排序。

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

using namespace std;

vector<int> adj[128];
int deg[128], cnt[128];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        char a, b, c;
        cin >> a >> b >> c;
        if (b == '>') {
            adj[c].emplace_back(a);
            deg[a]++;
        }
        else {
            adj[a].emplace_back(c);
            deg[c]++;
        }
    }
    string s;
    cin >> s;
    for (char c : s) cnt[c]++;
    queue<int> q;
    for (int i = 0; i < 128; ++i) if (!deg[i]) q.emplace(i);
    string t;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < cnt[x]; ++i) t += x;
        for (int y : adj[x]) {
            if (--deg[y] == 0) q.emplace(y);
        }
    }
    if (t.length() == s.length()) cout << t << '\n';
    else cout << "IMPOSSIBLE\n";
    return 0;
}

L. Last Orders ​

分层图最短路。

cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <complex>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
void pr(vector<int> a) {
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
const int mod = 998244353;
const int INF = 1e10;
const int N = 1e6 + 5;

void init() {}
void solve() {
    int n;
    cin>>n;
    vi a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    int m;
    cin>>m;
    vi t(m);
    for(int i=0;i<m;i++)cin>>t[i];
    vvi dis(m,vi(m,INF));
    for(int i=0;i<m;i++)dis[i][i]=0;
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int u,v,w;
        cin>>u>>v>>w;
        u--,v--;
        dis[u][v]=w;
        dis[v][u]=w;
    }
    for(int k=0;k<m;k++){
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    // for(int i=0;i<m;i++){
    //     for(int j=0;j<m;j++){
    //         cout<<dis[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    vvi dp(n+1,vi(m,INF));
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(dp[i][j]>t[j])continue;
            for(int k=0;k<m;k++){
                if(k==j&&i!=0)continue;
                dp[i+1][k]=min(dp[i+1][k],dp[i][j]+a[i]+dis[j][k]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<m;j++){
            // cout<<dp[i][j]<<" ";
            if(dp[i][j]<=t[j])ans=i;
        }
        // cout<<"\n";
    }
    cout<<ans<<endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    // cin>>t;
    while (t--) {
        solve();
    }
    return 0;
}

M. Motorway Stops ​

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

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

    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++) cin >> a[i];

    int ans = 0;
    for (int i = 2; i <= n; i ++) ans = max(ans, a[i] - a[i - 1]);

    int mn = 1e9;
    for (int i = 2; i < n; i ++) {
        mn = min(mn, a[i + 1] - a[i - 1]);
    }

    cout << max(ans, mn);
}

其他没做的题

  • Arboreal Challenge
  • Klaus