Star 的档案库

Appearance

2025春个人训练赛第七场 ​

除了 K 和 L 都是大水题，所以大部分就只留个记录了。

A. Host City ​

cpp
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30;
string s[N];
int a[N][N];
int h[N], t[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> s[i] >> h[i] >> t[i];
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                cin >> a[i][j];
            }
        }
        int mn = 0x3f3f3f3f, mnp = 0;
        for (int i = 1; i <= n; ++i) {
            int cur = 0;
            for (int j = 1; j <= n; ++j) {
                if (j != i) cur += t[j] * (h[i] + a[j][i]);
            }
            if (cur < mn || cur == mn && s[i] < s[mnp]) mn = cur, mnp = i;
            // cout << cur << endl;
        }
        cout << s[mnp] << endl;
    }
    return 0;
}

B. Flagpoles ​

cpp
#include <iostream>
#include <iomanip>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        double a, b, d;
        cin >> a >> b >> d;
        cout << fixed << setprecision(3) << a * b / (a + b) << endl;
    }
    return 0;
}

C. Ordering Paper ​

cpp
#include <iostream>

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        LL res = 0;
        cin >> n;
        while (n--) {
            int s, p;
            cin >> s >> p;
            res += s * ((p + 3) / 4);
        }
        cout << res << endl;
    }
    return 0;
}

D. Pass or Fail ​

竟然还有像这种的语法题。

cpp
#include <iostream>

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int t;
        cin >> t;
        cout << (t >= 6 ? "PASS" : "FAIL") << endl;
    }
    return 0;
}

E. Rating Teachers ​

cpp
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const int N = 110;

struct Teacher {
    string name;
    LL r1, r2;
    LL avg1, avg2;
};

bool cmp(const Teacher &a, const Teacher &b) {
    if (a.r1 * b.r2 == a.r2 * b.r1) return a.avg1 * b.avg2 > a.avg2 * b.avg1;
    else return a.r1 * b.r2 > a.r2 * b.r1;
}

vector<Teacher> small, mid, big;
int b[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        small.clear(), mid.clear(), big.clear();
        string city;
        int n;
        cin >> city >> n;
        for (int i = 1; i <= n; ++i) {
            string name;
            cin >> name;
            LL sum = 0, ok = 0, cnt = 0;
            for (int j = 1; j <= 10; ++j) {
                cin >> b[j];
                cnt += b[j];
                sum += b[j] * j;
                if (j >= 6) ok += b[j];
            }
            if (cnt <= 10) small.push_back({name, ok, cnt, sum, cnt});
            else if (cnt <= 30) mid.push_back({name, ok, cnt, sum, cnt});
            else big.push_back({name, ok, cnt, sum, cnt});
        }
        sort(small.begin(), small.end(), cmp);
        sort(mid.begin(), mid.end(), cmp);
        sort(big.begin(), big.end(), cmp);
        cout << city << " COUNTY" << endl;

        cout << "SMALL CLASS RANKING" << endl;
        for (auto i : small) cout << i.name << endl;
        cout << endl;
        
        cout << "MEDIUM CLASS RANKING" << endl;
        for (auto i : mid) cout << i.name << endl;
        cout << endl;

        cout << "LARGE CLASS RANKING" << endl;
        for (auto i : big) cout << i.name << endl;
        cout << endl;

    }
    return 0;
}

F. Correct Answer Recovery ​

直接暴力所有情况。

cpp
#include <iostream>
#include <cstring>
#include <bitset>

using namespace std;

const int N = 50;
bitset<15> a[N];
int t[N], b[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        char c;
        cin >> n >> m;
        for (int i = 1; i <= m; ++i) {
            int s = 0;
            a[i].reset();
            for (int j = 0; j < n; ++j) {
                cin >> c;
                a[i][j] = (c == 'T');
            }
        }
        for (int i = 0; i <= n; ++i) cin >> t[i];
        int res = 0;
        for (int i = 0; i < (1 << n); ++i) {
            bitset<15> msk(i);
            memset(b, 0, sizeof(b));
            for (int j = 1; j <= m; ++j) {
                b[(msk ^ a[j]).count()]++;
            }
            bool f = true;
            for (int j = 0; j <= n; ++j) {
                if (b[j] != t[j]) {
                    f = false;
                    break;
                }
            }
            res += f;
        }
        cout << res << endl;
    }
    return 0;
}

G. Sorting Exams ​

合并果子。

cpp
#include <iostream>
#include <queue>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        priority_queue<int, vector<int>, greater<int>> q;
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            int t;
            cin >> t;
            q.emplace(t);
        }
        int res = 0;
        while (q.size() != 1) {
            int x = q.top(); q.pop();
            int y = q.top(); q.pop();
            res += x + y;
            q.emplace(x + y);
        }
        cout << res << endl;
    }
    return 0;
}

H. What to Teach? ​

0/1 背包。

cpp
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, M = 5010;
int f[M], a[N], b[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i] >> b[i];
        }
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; ++i) {
            for (int j = m; j >= a[i]; --j) {
                f[j] = max(f[j], f[j - a[i]] + b[i]);
            }
        }
        cout << f[m] << endl;
    }
    return 0;
}

I. 仓鼠小队 ​

显然排个序然后顺着取就是最优的。

cpp
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010;
LL a[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);

    LL res = 0;
    for (int i = 1; i <= n; i += 3) {
        res += a[i + 2] - a[i];
    }
    cout << res << endl;
    return 0;
}

J. 羊腿出售 ​

NOTE

这道题刚开始测试数据只有一组样例，然后发现之后反应给老师重判完之后除了当时 std 全部挂了，感觉用了不止一年了，所以之前打训练赛的人真就都在混吗🤯

我想到一个比较暴力的做法。考虑从左到右依次向后添加字符，一个新的字符会给前面的所有字符的组合贡献 1。只需要把所有询问按照右端点排序（可以通过双指针扫描原串和询问保证右端点不越界，现在就只用考虑左端点了），然后动态的维护出来 26 * 26 对组合的贡献，添加一个新的字符的时候对和他相关的 26 组做区间加，查询答案的时候找到那一个贡献数组做区间查询。由于时间和空间都非常的极限，我选择了用 vector 开出 26 * 26 个大小极限的树状数组维护区间加和区间查询，因为线段树常数太大 TLE 了（悲），空间复杂度只有 O(n⋅26)（例如 b 对 a 的贡献只用记 a 的位置即可，b 对所有的贡献加起来是一个 n），时间复杂度是极限的 O(nlog⁡n⋅26) 正好卡过去了。

cpp
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const int N = 200010;

struct FenwickTree {
    int n;
    vector<LL> a, b;

    void init(int n) {
        this->n = n;
        a = vector<LL>(n + 1, 0);
        b = vector<LL>(n + 1, 0);
    }

    private:

    void add(int x, LL v) {
        for (int i = x; i <= n; i += i & -i) {
            a[i] += v;
            b[i] += v * x;
        }
    }

    LL query(int x) {
        LL res = 0;
        for (int i = x; i; i -= i & -i) {
            res += (x + 1) * a[i] - b[i];
        }
        return res;
    }

    public:

    void modify(int l, int r, int v) {
        add(l, v);
        add(r + 1, -v);
    }

    LL queryL(int l) {
        return query(n) - query(l - 1);
    }

} tr[26][26];

struct Query {
    int id, l, r;
    char a, b;
};

LL res[N];
vector<int> pos[26];
vector<Query> qs;

int main() {
    // freopen("input", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, q;
    string s;
    cin >> n >> q >> s;
    for (int i = 1; i <= n; ++i) {
        pos[s[i - 1] - 'a'].emplace_back(i);
    }
    qs.resize(q);
    for (int i = 0; i < q; ++i) {
        auto &[id, l, r, a, b] = qs[i];
        id = i;
        cin >> l >> r >> a >> b;
    }
    sort(qs.begin(), qs.end(), [](Query a, Query b) {
        return a.r < b.r;
    });
    for (int i = 0; i < 26; ++i) {
        for (int j = 0; j < 26; ++j) {
            tr[i][j].init(pos[i].size());
        }
    }
    for (int i = 0, j = 1; i < q; ++i) {
        while (j <= n && qs[i].r >= j) {
            int cur = s[j - 1] - 'a';
            for (int k = 0; k < 26; ++k) {
                // if (k == 0 && cur == 0) cout << lower_bound(pos[k].begin(), pos[k].end(), j) - pos[k].begin() << endl;
                tr[k][cur].modify(1, lower_bound(pos[k].begin(), pos[k].end(), j) - pos[k].begin(), 1);
            }
            j++;
        }
        res[qs[i].id] = tr[qs[i].a - 'a'][qs[i].b - 'a'].queryL(lower_bound(pos[qs[i].a - 'a'].begin(), pos[qs[i].a - 'a'].end(), qs[i].l) - pos[qs[i].a - 'a'].begin() + 1);
    }
    for (int i = 0; i < q; ++i) cout << res[i] << endl;
    return 0;
}

K. 数字拼接 ​

直接暴搜。

cpp
#include <iostream>
#include <set>

using namespace std;

const int N = 20;
string a[N];
set<string> s;
int n, m;
bool v[N];

void dfs(int x, string t) {
    if (x == m + 1) {
        s.insert(t);
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (!v[i]) {
            v[i] = true;
            dfs(x + 1, t + a[i]);
            v[i] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    dfs(1, "");
    cout << s.size() << endl;
    return 0;
}