Star 的档案库

Appearance

2026夏个人训练赛第三十场 ​

A. 数组 ​

  • 算术
cpp
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        long long t;
        cin >> t;
        while (t % 2 == 0) t /= 2;
        res += t;
    }
    cout << res << '\n';
    return 0;
}

B. 装箱 ​

  • 二分查找
  • 贪心

二分答案暴力检查。

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

using namespace std;

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

    auto check = [&](int mid) -> bool {
        int t = 1, cur = 0;
        for (int i = mid; i <= n; ++i) {
            if (a[i] > k) return false;
            else if (cur + a[i] > k) t++, cur = a[i];
            else cur += a[i];

            if (t > m) return false;
        }
        return true;
    };

    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << n - l + 1 << '\n';
    return 0;
}

C. 中位数 ​

  • 数据结构
  • 优先队列

对顶堆。

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

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        priority_queue<int> lq;
        priority_queue<int, vector<int>, greater<int>> rq;
        lq.emplace(-0x3f3f3f3f), rq.emplace(0x3f3f3f3f);
        for (int j = i; j <= n; ++j) {
            if (a[j] > lq.top()) rq.emplace(a[j]);
            else lq.emplace(a[j]);

            while (lq.size() + 1 > rq.size()) rq.emplace(lq.top()), lq.pop();
            while (rq.size() > lq.size() + 1) lq.emplace(rq.top()), rq.pop();

            if (j - i + 1 & 1) res += rq.top();
        }
    }
    cout << res << '\n';
    return 0;
}

E. 生日 ​

  • 线段树
  • 懒标记线段树
  • 位掩码

开线段树维护蛋糕数量的 bitmask，合并的时候全部或起来，查询的时候查 1 的数量，可以用 __popcount。

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

using namespace std;

struct SegmentTree {
    vector<unsigned> tr, tag;

    SegmentTree(int n) {
        tr = vector<unsigned>(n * 4, 1u << 1);
        tag = vector<unsigned>(n * 4, 0);
    }

    void pushdown(int u) {
        if (tag[u]) {
            tag[u << 1] = tag[u << 1 | 1] = tr[u << 1] = tr[u << 1 | 1] = tag[u];
            tag[u] = 0;
        }
    }

    void modify(int u, int l, int r, int ql, int qr, unsigned v) {
        if (ql <= l && r <= qr) {
            tr[u] = v;
            tag[u] = v;
        }
        else {
            pushdown(u);
            int mid = l + r >> 1;
            if (ql <= mid) modify(u << 1, l, mid, ql, qr, v);
            if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, v);
            tr[u] = tr[u << 1] | tr[u << 1 | 1];
        }
    }

    unsigned query(int u, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return tr[u];
        }
        else {
            pushdown(u);
            int mid = l + r >> 1;
            unsigned res = 0;
            if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
            if (qr > mid) res |= query(u << 1 | 1, mid + 1, r, ql, qr);
            return res;
        }
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    SegmentTree tr(n);
    while (m--) {
        char op;
        cin >> op;
        if (op == 'C') {
            int l, r, v;
            cin >> l >> r >> v;
            tr.modify(1, 1, n, l, r, 1u << v);
        }
        else {
            int l, r;
            cin >> l >> r;
            cout << __popcount(tr.query(1, 1, n, l, r)) << '\n';
        }
    }
    return 0;
}

F. 数字 ​

  • 贪心
  • 构造
  • 分类讨论

不难发现只有偶数位的是可行的，先特判掉奇数输出 44444...77777...，然后只看偶数。

  • 先贪心的尽可能填 4，发现填不了了在返回上一个同时有 7 和 4 填了 4 的位置填成 7，然后继续贪心填
  • 如果上面的策略无论如何都填不了，就加两位填 44444...77777...
cpp
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string s;
    while (cin >> s) {
        if (s.length() & 1) {
            for (int i = 0; i < (s.length() + 1 >> 1); ++i) cout << "4";
            for (int i = 0; i < (s.length() + 1 >> 1); ++i) cout << "7";
            cout << '\n';
        }
        else {
            string t;
            bool f = false, g = true;
            int c4 = s.length() >> 1, c7 = c4;
            int ls = -1, bk4, bk7;
            for (int i = 0; i < s.length(); ++i) {
                if (f) {
                    if (c4) t += '4', c4--;
                    else t += '7', c7--;
                }
                else if (c4 && s[i] <= '4') {
                    t += '4';
                    c4--;
                    if (c7) ls = i, bk4 = c4, bk7 = c7;
                    if (s[i] < '4') f = true;
                }
                else if (c7 && s[i] <= '7') {
                    t += '7';
                    c7--;
                    if (s[i] < '7') f = true;
                }
                else if (ls != -1) {
                    f = true;
                    t.erase(t.begin() + ls, t.end());
                    t += '7';
                    c4 = bk4, c7 = bk7;
                    c4++, c7--;
                    i = ls;
                }
                else {
                    g = false;
                    break;
                }
            }
            if (g) cout << t << '\n';
            else {
                for (int i = 0; i < (s.length() + 2 >> 1); ++i) cout << "4";
                for (int i = 0; i < (s.length() + 2 >> 1); ++i) cout << "7";
                cout << '\n';
            }
        }
    }
    return 0;
}

H. digits 2 ​

  • 构造
  • 字符串
  • 预处理

其实输出 str(n) * n 就好了，结果我打了个表😇

python
table = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "11111111110", "3138428376721", "35831808", "1792160394037", "44998795805848373114515226624", "170859375", "68719476736", "4913", "5832", "232582849345724962061808152564655542758970670101721869455380995292050708596028544827179076934311238442854429336643819", "81920000000000000", "630880792396715529789561", "234256", "148035889", "36520347436056576", "390625", "17576", "19683", "614656", "52666193272726422601456708224751866691705278695881", "4502839058909973630000000000000000000000000000000000000", "27512614111", "38685626227668133590597632", "234506656247776905017748821460251500238366110067843569034036522087377377", "52523350144", "52521875", "1679616", "1877944508893233281587362192715149196869044938545410448866468981413670579521", "1245460660457141741027199056744286587178373074792962048381730134771558730309614591679073991263090852946941654947469234594999265123637054963484678755657785883626957686714396221374464", "482880748567480579719", "671088640000000000000", "221822398694336087038494354935485779722471164141393582990227272499977995888144455072605973880845186381659055658005220561", "3937657486715347520027492352", "271818611107", "9198307260930553905406593486096283472413604774285163241841976875686185351859783457013486011285504", "8303765625", "205962976", "504259791173073764962624993256787072590202228938280313545791203663903421551808598806276295587242622229997910640961", "202332657110324584212719915287707648", "88124787089723195184393736687912818113311201", "4235164736271501695341612503398209810256958007812500000000000000000000000000000000000000000000000000000000000000000000000", "36859027642628666340203552228411828601", "152784834199652075368661148843397208866816", "1174711139837", "24794911296", "390672210499139759508933851733987138283760342802448695404195140573454781253737801417359286268079196897002820507386831472610251404652284850744456286256121283186727768288550123630219292009656017652916202444192294580541063873968855915388616757373197269272934444051262603775347750622193034700306566841732287299893133791783839114941656589508056640625", "248259322782482263282193785272646366651148161300460020540464495552366358449991116691716928669814358016", "5287428596672976715163780828050216834886802869826665262027771999249", "2207984167552", "464798130469793589516643498190087912509935907396786423681", "6236738252042932566690891978831298560000000000000000000000000000000000000000000000", "362990325539372200679554918670984996723331903112927801", "394187650154532338423324471516400882803226167512009299729459217901910348087953996311222204130899338827655673064891954049525898225443789903863568687127150193113030206539335652051695974392093860557306125495912469917175540730028815449849856", "248155780267521", "68719476736", "22693550454432941386493640092237813714990263156639645053105139266155929139519477148323297928459034655864843034472880695720489128014819852392579998244005745622331460253917612135410308837890625", "3080338106901226309985045499661656392913125376", "1348388182829587790576678777080628432665556757822476173632753081626945886953185830470923910683", "6722988818432", "1965753632901132991452851230906979378964909", "1264622433847811452634797305324544679795286587352887784765274932287046481842855442591741163910133792804900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "45848500718449031", "521578814501447328359509917696", "45268634033651390055938773929758873992164981297731912450685679766349037290327584903722145853267790546953337653909842713695682225704240218823601173550958617", "1237132024797846216530465001778167458914724835301826327694755253581951396221716404956698835088390037876623435327158519990260916169998649767907181415696562392791440789496767538269236828461733298133236617728885784576", "2381094535600196404612205469675245694816112518310546875", "1534740497155751995863607836604084898735922962704391288651776", "60836646375089738827772895325058963868619710608275993919909664595969806866127678816330005053990641328942444787650477361759718397342524668625684026885445410310461256595849", "579212706592939054456238001058547123517325472344282497024", "206336132715709669990485567530001552309415935666586885734738159549121", "225179981368524800000000000000000", "150094635296999121", "13744803133596058624", "399282135658682469334331901689876886678820965774126540592961885129481494196023689", "758263253073010241157973569975696406218966848080183296", "19687440434072265625", "14076019706120526112710656", "23281975115079758034812815774679634671599619370786183", "6836348814727706172435256284182582457596722356451245137939566998046325604352", "444161152626944308084544631272547248672303386383111387033940070559009066085645918078720726540739267427438234811034145222036960278626103754897977761304116330958944487761", "13508517176729920890000000000000000000", "2670419511272061205254504361", "26849471499163592760924811564282772953345175974499209716300342515232650306823066497746798994432531539929922057202910767106750677584034398208", "108992637981686311568835180660866140697857591774212303033098326839397388263834064026123482532590360623202171014332688046969855294606987834055250166206373987386296614920355835822292909049", "53861511409489970176", "769449752767133292742943790958350921451790972423891374406296339660826788531267084181308746337890625", "230019359300543000719451366059583317129007590117361290008767206885687296", "73742412689492826049", "8007313507497959524352", "8179069375972308708891986605443361898001", "1" * 100 + "0" * 2]


T = int(input())
for _ in range(T):
    n = int(input())
    print(table[n - 1])

I. generator 1 ​

  • 数学
  • 快速幂
  • 模逆元

快速幂的小巧思，当时没想到，用一个 base, base2, base4, base8 表示一个十进制位，然后用 2 次和 8 次合并出一个 10 次更新 base。

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

using namespace std;

typedef long long LL;

LL x0, x1, a1, b1, mod;

struct Mat {
    LL a[2][2] = {{0, 0}, {0, 0}};

    Mat mul(const Mat &b) {
        Mat res;
        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] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
                }
            }
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string n;
    cin >> x0 >> x1 >> a1 >> b1 >> n >> mod;
    Mat res = {{{1, 0}, {0, 1}}}, base = {{{0, b1}, {1, a1}}};
    reverse(n.begin(), n.end());
    for (char c : n) {
        Mat b[4] = {base};
        for (int i = 1; i < 4; ++i) b[i] = b[i - 1].mul(b[i - 1]);
        int cur = c - 48;
        for (int i = 0; i < 4; ++i) {
            if (cur >> i & 1) res = res.mul(b[i]);
        }
        base = b[1].mul(b[3]);
    }
    cout << (res.a[0][0] * x0 % mod + res.a[1][0] * x1 % mod) % mod << '\n';
    return 0;
}

其他没做的题

  • 图计数
  • 飞行棋
  • generator 2
  • generator 3
  • independent set 1