Star 的档案库

Appearance

2026夏组队训练赛第七场 ​

C. Flippy Sequence ​

  • 分类讨论
cpp
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        string s, t;
        cin >> s >> t;
        vector<int> a;
        int cur = 0, r = -1;
        for (int i = 0; i < n; ++i) {
            if (s[i] != t[i]) cur++;
            else if (cur) {
                a.emplace_back(cur);
                cur = 0;
                r = i;
            }
        }
        if (cur) a.emplace_back(cur), r = n;
        if (a.size() == 0) {
            cout << (long long)n * (n + 1) / 2 << '\n';
        }
        else if (a.size() == 1) {
            cout << (a[0] - 1) * 2 + (n - a[0]) * 2 << '\n';
        }
        else if (a.size() == 2) {
            cout << "6\n";
        }
        else cout << "0\n";
    }
    return 0;
}

D. Magic Multiplication ​

  • 暴力
  • 解析
cpp
#include <bits/stdc++.h>
using namespace std;

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

    string s;
    cin >> s;
    int len = size(s);

    vector<pair<string, string>> ans;

    auto check = [&](int x) -> void {
        string a, b;
        int pos_a = 0, i = 0;

        for (; i < len; i ++) {
            int num = s[i] - '0';
            if (num % x) {
                num *= 10;
                if (i + 1 >= len) return;
                i ++;
                num += s[i] - '0';
            }
            if (num % x) return;
            int t = num / x;
            if (t >= 10) return;
            b += to_string(t);
            if (b.size() == m) break;
        }

        if (size(b) < m) return;

        a += to_string(x);
        i ++;
        for (; i < len; i ++) {
            int num = s[i] - '0';
            int t = b[0] - '0';

            if (num % t) {
                if (i + 1 >= len) return;
                i ++;
                num *= 10;
                num += s[i] - '0';
            }

            if (num % t) return;
            int y = num / t;
            if (y >= 10) return;
            a += to_string(y);
            if (size(a) > n) return;

            for (int j = 1; j < m; j ++) {
                int q = b[j] - '0';
                int z;
                if (y * q >= 10) {
                    if (i + 2 >= len) return;
                    z = (s[i + 1] - '0') * 10 + (s[i + 2] - '0');
                    i += 2;
                } else {
                    if (i + 1 >= len) return;
                    z = s[i + 1] - '0';
                    i ++;
                }
                if (z != y * q) return;
            }
        }
        if (size(a) < n) return;
        ans.push_back({a, b});
    };

    for (int i = 1; i < 10; i ++) check(i);

    sort(ans.begin(), ans.end());
    if (ans.size() == 0) cout << "Impossible\n";
    else {
        cout << ans[0].first << ' ' << ans[0].second << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t --) solve();
}

E. Plants vs. Zombies ​

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

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

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

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

    auto calc = [&](ll t) -> bool {
        __int128 tmp = 0;
        ll nxt = 0;
        for (int i = 1; i <= n; i ++) {
            ll cur = t;
            cur -= nxt;

            if (i == n) {
                if (cur <= 0) break;
            }

            cur -= a[i];
            tmp ++;
            if (cur > 0) {
                ll need = (cur + a[i] - 1) / a[i];
                tmp += need * 2;
                nxt = a[i + 1] * need;
            } else nxt = 0;
        }
        //debug(tmp) DL
        if (tmp > m) return 0;
        return 1;
    };  

    ll l = 0, r = 1e18;
    while (l < r) {
        ll mid = (l + r + 1) / 2;
        if (calc(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << '\n';
}

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

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

F. Tournament ​

  • 构造
  • 模拟
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

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

    int mx = 0, base = 1, x = n;
    while (x % 2 == 0) {
        mx += base;
        base <<= 1;
        x >>= 1;
    }

    if (k > mx) {
        cout << "Impossible\n";
        return;
    }

    vector<vector<int>> ans(k + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i ++) ans[0][i] = i;

    int block = 1, sign = 1, cnt = 0, sub = 0;
    for (int i = 1; i <= k; i ++) {
        for (int j = 1; j <= n; j ++) {
            ans[i][j] = ans[i - block][j] + sign * block;
            sub ++;
            if (sub == block) {
                sub = 0;
                sign *= -1;
            }
        }
        cnt ++;
        if (cnt == block) {
            cnt = 0;
            block <<= 1;
        }
    }

    for (int i = 1; i <= k; i ++) {
        for (int j = 1; j <= n; j ++) {
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }
}

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

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

I. Soldier Game ​

  • 树形 DP
  • 线段树
  • 扫描线
cpp
#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 100010;
const int inf = LLONG_MAX >> 1;
 
struct Mat {
    int a[2][2]{{-inf, inf}, {inf, -inf}};
 
    Mat mul(const Mat &b) const {
        Mat res{{{inf, inf}, {inf, inf}}};
        for (int k = 0; k < 2; ++k) {
            for (int i = 0; i < 2; ++i) {
                for (int j = 0; j < 2; ++j) {
                    res.a[i][j] = min(res.a[i][j], max(a[i][k], b.a[k][j]));
                }
            }
        }
        return res;
    }
};
 
Mat tr[N * 4];
int a[N];
 
void build(int u, int l, int r) {
    if (l == r) tr[u] = {{
        {inf, a[l] + a[l - 1]},
        {-inf, a[l]}
    }};
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        tr[u] = tr[u << 1].mul(tr[u << 1 | 1]);
    }
}
 
void modify(int u, int l, int r, int p, int f) {
    if (l == r) {
        tr[u].a[f][1] = inf;
    }
    else {
        int mid = l + r >> 1;
        if (p <= mid) modify(u << 1, l, mid, p, f);
        else modify(u << 1 | 1, mid + 1, r, p, f);
        tr[u] = tr[u << 1].mul(tr[u << 1 | 1]);
    }
}
 
int query() {
    return tr[1].a[1][1];
}
 
vector<pair<int, int>> t[N * 2];
 
signed 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 >> a[i];
        a[0] = a[n + 1] = inf;
        build(1, 1, n);
        int lim = inf;
        vector<int> values;
        for (int i = 1; i <= n; ++i) values.emplace_back(a[i]);
        for (int i = 1; i < n; ++i) values.emplace_back(a[i] + a[i + 1]);
        sort(values.begin(), values.end());
        values.erase(unique(values.begin(), values.end()), values.end());
        int m = values.size();
        int res = query() - values[0];
        auto get = [&](int x) {
            return lower_bound(values.begin(), values.end(), x) - values.begin() + 1;
        };
        for (int i = 1; i <= m; ++i) t[i].clear();
        for (int i = 1; i <= n; ++i) {
            t[get(a[i])].emplace_back(1, i);
        }
        for (int i = 1; i < n; ++i) {
            t[get(a[i] + a[i + 1])].emplace_back(0, i + 1);
        }
        for (int i = 1; i < m; ++i) {
            for (auto &[j, k] : t[i]) {
                modify(1, 1, n, k, j);
            }
            res = min(res, query() - values[i]);
            // cout << values[i] << ' ' << query() - values[i] << '\n';
        }
        // cout << '\n';
        cout << res << '\n';
    }
    return 0;
}

J. Books ​

  • 贪心
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 = 5e5 + 5;
void init() {
    
}
void solve() {
    int n,m;
    cin>>n>>m;
    vi a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    if(n==m){
        cout<<"Richman"<<endl;
        return;
    }
    int cnt=0;
    vi b;
    for(int i=0;i<n;i++){
        if(a[i]==0)cnt++;
        else b.pb(a[i]);
    }
    m-=cnt;
    if(m<0){
        cout<<"Impossible"<<endl;
        return;
    }
    n=sz(b);
    vi mn(n,INF);
    mn[n-1]=b[n-1];
    for(int i=n-2;i>=0;i--)mn[i]=min(mn[i+1],b[i]);
    int ans=0;
    for(int i=0;i<m;i++){
        ans+=b[i];
    }
    ans+=mn[m]-1;
    cout<<ans<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

L. Sub-cycle Graph ​

  • 组合数学
  • 模逆元
  • 快速幂
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 = 1e9 + 7;
const int INF = 1e18;
const int N = 1e5 + 5;
 
int power(int n, int p) {
    int res = 1, base = n;
    while (p) {
        if (p & 1)
            res = res * base % mod;
        base = base * base % mod;
        p >>= 1;
    }
    return res;
}
 
int fac[N], inv[N], p2[N];
 
void init() {
    int n = 100000;
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[n] = power(fac[n], mod - 2);
    for (int i = n - 1; i; --i) {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
    p2[0] = 1;
    int inv2 = (mod + 1) / 2;
    for (int i = 1; i < N; i++) p2[i] = p2[i - 1] * inv2 % mod;
}
 
int C(int n, int m) {
    if (m < 0 || n < 0)
        return 0;
    if (m > n)
        return 0;
    return fac[n] * inv[n - m] % mod * inv[m] % mod;
}
void solve() {
    int n, m;
    cin >> n >> m;
    if (m == 0) {
        cout << 1 << endl;
        return;
    }
    if (m > n) {
        cout << 0 << endl;
        return;
    }
    if (m == n) {
        cout << fac[n - 1] * p2[1] % mod << endl;
        return;
    }
    int ans = 0;
    for (int i = 1; i + m <= n; i++) {
        ans += C(n, i + m) * p2[i] % mod * C(m - 1, i - 1) % mod * fac[m + i] % mod * inv[i] % mod;
        ans %= mod;
    }
    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. Function and Function ​

  • 数学
  • 模拟
cpp
#include <bits/stdc++.h>
using namespace std;

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

int f[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
int calc(int n, int k) {
    //debug(n) 
    if (k == 0) return n;
    else {
        string s = to_string(n);
        int tmp = 0;
        for (auto c : s) tmp += f[c - '0'];
        return calc(tmp, k - 1);
    }
}

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

    int need = max(0, k - 50);

    k -= need;
    int ans = calc(n, k);
    if (need % 2) ans ^= 1;
    cout << ans << '\n';
}

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

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

其他没做的题

  • Sequence and Sequence
  • Kawa Exam
  • Repair the Artwork
  • Mirror
  • Airdrop