30.5 แบบฝึกหัด

เขียนแต่ละข้อเป็นไฟล์ใหม่ใน Code::Blocks รันแล้วเทียบกับผลลัพธ์ที่ต้องได้ให้ตรงทุกตัวอักษร รวมถึงช่องว่างและการขึ้นบรรทัด ติดจริงๆ ค่อยเปิดคำใบ้ และเปิดเฉลยหลังทำเสร็จแล้วเท่านั้น

ข้อ 1 ลำดับขั้นทำเค้ก

ระดับง่าย เวลาไม่เกิน 1 วินาที

ร้านขนมเขียนสูตรเค้กไว้ N ขั้นตอน หมายเลข 1 ถึง N บางขั้นต้องรอขั้นอื่นเสร็จก่อน เช่น ต้องร่อนแป้งก่อนผสม ต้องอบก่อนแต่งหน้า เงื่อนไขมีทั้งหมด M ข้อ ข้อหนึ่งเขียนเป็นคู่ a b แปลว่าต้องทำขั้น a ให้เสร็จก่อนเริ่มขั้น b

พ่อครัวทำทีละขั้น ทุกครั้งที่จะเริ่มขั้นใหม่ เขาเลือกขั้นที่ หมายเลขน้อยที่สุด ในบรรดาขั้นที่ยังไม่ได้ทำและทุกขั้นที่ต้องรอเสร็จหมดแล้ว ให้หาลำดับที่พ่อครัวจะทำ ถ้าสูตรเขียนเงื่อนไขวนกันจนทำครบทุกขั้นไม่ได้ ให้ตอบ -1

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ 0 ≤ M ≤ 200000

อีก M บรรทัด บรรทัดละสองจำนวน a และ b โดยที่ 1 ≤ a, b ≤ N และ a ≠ b เงื่อนไขเดียวกันอาจเขียนซ้ำได้

ข้อมูลออก

บรรทัดเดียว เป็นหมายเลขขั้นตอนตามลำดับที่ทำ คั่นด้วยช่องว่าง หรือ -1 ถ้าทำครบไม่ได้

3 1 2 5 4

-1

ดูคำใบ้

ใช้ Kahn ตามหน้า 30.1 นับว่าแต่ละขั้นยังรออีกกี่ขั้น แต่เปลี่ยน queue ธรรมดาเป็น priority_queue แบบน้อยสุดก่อนจากหน้า 20.5 จะได้หยิบขั้นเลขน้อยที่สุดที่พร้อมทำเสมอ ถ้าหยิบออกมาได้ไม่ครบ N ขั้น แปลว่ามีวง ตอบ -1 การไล่หาขั้นที่พร้อมตั้งแต่ขั้น 1 ใหม่ทุกครั้งเป็น O(N²) ไม่ทันเมื่อ N เป็นสองแสน

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> next_steps(n + 1);
    vector<int> waiting(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        next_steps[a].push_back(b);
        waiting[b]++;
    }
    priority_queue<int, vector<int>, greater<int>> ready;
    for (int step = 1; step <= n; step++) {
        if (waiting[step] == 0) {
            ready.push(step);
        }
    }
    vector<int> order;
    while (!ready.empty()) {
        int step = ready.top();
        ready.pop();
        order.push_back(step);
        for (int after : next_steps[step]) {
            waiting[after]--;
            if (waiting[after] == 0) {
                ready.push(after);
            }
        }
    }
    if ((int)order.size() < n) {
        cout << -1 << '\n';
        return 0;
    }
    for (int i = 0; i < n; i++) {
        cout << order[i] << (i + 1 == n ? '\n' : ' ');
    }
    return 0;
}

ข้อ 2 ยอดขายรวมหลายสาขา

ระดับง่าย เวลาไม่เกิน 1 วินาที

ร้านชานมไข่มุกมี N สาขาเรียงตามถนนเส้นเดียว หมายเลข 1 ถึง N ระบบหลังร้านเก็บยอดขายวันนี้ของทุกสาขา ระหว่างวันมีเหตุการณ์ Q ครั้งเรียงตามเวลา แต่ละครั้งเป็นแบบใดแบบหนึ่งต่อไปนี้

1 i v สาขาที่ i ส่งยอดขายล่าสุดมา ยอดขายของสาขานี้ กลายเป็น v บาท (ไม่ใช่บวกเพิ่ม v)
2 l r ผู้จัดการเขตถามว่าสาขาที่ l ถึง r รวมกันขายได้กี่บาท

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ Q คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ 1 ≤ Q ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือยอดขายตอนเริ่มของสาขาที่ 1 ถึง N แต่ละตัวอยู่ระหว่าง 0 ถึง 10⁹

อีก Q บรรทัด บรรทัดละหนึ่งเหตุการณ์ในรูปแบบข้างบน โดยที่ 1 ≤ i ≤ N, 0 ≤ v ≤ 10⁹ และ 1 ≤ l ≤ r ≤ N

ข้อมูลออก

ทุกเหตุการณ์แบบ 2 ให้พิมพ์ยอดขายรวมหนึ่งบรรทัด

5 6
120 80 0 45 300
2 1 5
1 3 60
2 2 4
1 1 100
1 3 10
2 1 3

545
185
190

ดูคำใบ้

ต้องทั้งปรับค่าและถามผลรวมช่วงสลับกันเป็นแสนครั้ง Fenwick tree ทำได้ทั้งสองอย่างใน O(log N) ยอดรวมสาขา l ถึง r คือ prefix_sum(r) - prefix_sum(l - 1) เหตุการณ์แบบ 1 ไม่ได้บอกว่าเพิ่มเท่าไร แต่บอกค่าใหม่ ต้องเก็บยอดปัจจุบันของทุกสาขาไว้อีกอาเรย์ แล้วบวกส่วนต่าง v - sales[i] เข้าไปในต้นไม้ ยอดรวมถึง 2 × 10¹⁴ ใช้ long long การบวกทีละสาขาทุกคำถามเป็น O(NQ) ไม่ทัน

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> tree;

void add(int i, long long delta)
{
    for (; i <= n; i += i & -i) {
        tree[i] += delta;
    }
}

long long prefix_sum(int i)
{
    long long total = 0;
    for (; i > 0; i -= i & -i) {
        total += tree[i];
    }
    return total;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    tree.assign(n + 1, 0);
    vector<long long> sales(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> sales[i];
        add(i, sales[i]);
    }
    for (int k = 0; k < q; k++) {
        int type;
        cin >> type;
        if (type == 1) {
            int i;
            long long v;
            cin >> i >> v;
            add(i, v - sales[i]);
            sales[i] = v;
        } else {
            int l, r;
            cin >> l >> r;
            cout << prefix_sum(r) - prefix_sum(l - 1) << '\n';
        }
    }
    return 0;
}

ข้อ 3 ท่าไม้ตาย

ระดับง่าย เวลาไม่เกิน 1 วินาที

เกมต่อสู้เกมหนึ่งบันทึกปุ่มที่ผู้เล่นกดไว้ทั้งแมตช์ เป็นข้อความตัวอักษรภาษาอังกฤษตัวเล็ก ปุ่มละหนึ่งตัวอักษร เรียงตามเวลา ท่าไม้ตายของตัวละครคือการกดปุ่มตามลำดับที่กำหนดติดกันพอดี เช่น ท่า ddp คือกด d d แล้ว p โดยไม่มีปุ่มอื่นคั่น

ผู้จัดการแข่งอยากรู้ว่าในบันทึก มีช่วงที่กดตรงกับท่าไม้ตายกี่ช่วง ช่วงที่ซ้อนกันนับแยกกัน เช่น บันทึก aaaa กับท่า aa มี 3 ช่วง และอยากรู้ว่าช่วงแรกเริ่มที่การกดครั้งที่เท่าไร โดยนับการกดครั้งแรกเป็นครั้งที่ 1

ข้อมูลเข้า

บรรทัดแรกเป็นบันทึกการกดปุ่ม ยาว N ตัวอักษร (1 ≤ N ≤ 1000000)

บรรทัดที่สองเป็นท่าไม้ตาย ยาว M ตัวอักษร (1 ≤ M ≤ 1000000)

ทั้งสองบรรทัดมีแต่ตัวอักษร a ถึง z

ข้อมูลออก

บรรทัดแรกเป็นจำนวนช่วงที่ตรงกับท่าไม้ตาย บรรทัดที่สองเป็นครั้งที่ของการกดที่ช่วงแรกเริ่ม ถ้าไม่มีช่วงไหนตรงเลย บรรทัดที่สองให้พิมพ์ -1

kddpkddpddpp
ddp

3
2

aaaa
aa

3
1

ดูคำใบ้

ต่อท่ากับบันทึกเป็น combo + "#" + presses แล้วหา prefix function ตำแหน่ง i ที่ได้ค่าเท่ากับ M คือช่วงที่ตรงท่าพอดี และช่วงนั้นจบที่ตัว i ของข้อความที่ต่อแล้ว ลองไล่ตัวอย่างเล็กๆ ด้วยมือเพื่อหาว่าต้องลบเท่าไรถึงได้ครั้งที่เริ่มกด จำนวนช่วงมีได้เกือบล้าน การเทียบทีละตำแหน่งแบบหน้า 13.5 ใช้ได้กับชุดเล็ก แต่บันทึกที่เป็น a ทั้งหมดทำให้ต้องเทียบถึง N × M ครั้ง

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string presses, combo;
    cin >> presses >> combo;
    int m = combo.size();
    string joined = combo + "#" + presses;
    int total = joined.size();
    vector<int> border(total, 0);
    long long count = 0;
    int first = -1;
    for (int i = 1; i < total; i++) {
        int j = border[i - 1];
        while (j > 0 && joined[i] != joined[j]) {
            j = border[j - 1];
        }
        if (joined[i] == joined[j]) {
            j++;
        }
        border[i] = j;
        if (j == m) {
            count++;
            if (first == -1) {
                first = i - 2 * m + 1;
            }
        }
    }
    cout << count << '\n' << first << '\n';
    return 0;
}

ข้อ 4 สถานีที่หนาวที่สุด

ระดับง่าย เวลาไม่เกิน 1 วินาที

กรมอุตุนิยมวิทยาตั้งสถานีวัดอุณหภูมิไว้ N สถานีเรียงตามแนวเทือกเขา หมายเลข 1 ถึง N แต่ละสถานีรายงานอุณหภูมิล่าสุดเป็นจำนวนเต็มองศาเซลเซียส ซึ่งติดลบได้ ระหว่างคืนมีเหตุการณ์ Q ครั้งเรียงตามเวลา แต่ละครั้งเป็นแบบใดแบบหนึ่งต่อไปนี้

1 i t สถานีที่ i รายงานอุณหภูมิใหม่ เป็น t องศา
2 l r นักข่าวถามว่า ตอนนี้ในสถานีที่ l ถึง r สถานีไหนหนาวที่สุด และกี่องศา ถ้ามีหลายสถานีที่หนาวที่สุดเท่ากัน ให้ตอบสถานีที่หมายเลขน้อยที่สุด

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ Q คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ 1 ≤ Q ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คืออุณหภูมิตอนเริ่มของสถานีที่ 1 ถึง N

อีก Q บรรทัด บรรทัดละหนึ่งเหตุการณ์ในรูปแบบข้างบน โดยที่ 1 ≤ i ≤ N และ 1 ≤ l ≤ r ≤ N อุณหภูมิทุกค่าอยู่ระหว่าง -1000000000 ถึง 1000000000 (โจทย์ตั้งให้กว้างเพื่อฝึกเลือกค่าเริ่มต้นของค่าต่ำสุด)

ข้อมูลออก

ทุกเหตุการณ์แบบ 2 ให้พิมพ์หนึ่งบรรทัด มีอุณหภูมิต่ำสุดกับหมายเลขสถานีนั้น คั่นด้วยช่องว่าง

6 6
12 5 9 -3 7 4
2 1 3
2 2 6
1 4 10
2 2 6
1 2 8
2 1 2

ดูคำใบ้

ค่าต่ำสุดถอนกลับไม่ได้ จึงใช้ prefix sum หรือ Fenwick tree แบบผลรวมไม่ได้ segment tree ปรับค่าจุดเดียวกับถามช่วงได้ใน O(log N) ทั้งคู่ ส่วนที่ต้องคิดเพิ่มคือต้องตอบหมายเลขสถานีด้วย ให้แต่ละโหนดเก็บคู่ (อุณหภูมิ, หมายเลขสถานี) แล้วรวมด้วย min ของ pair ซึ่งเทียบอุณหภูมิก่อน ถ้าเท่ากันก็เทียบหมายเลข จึงได้สถานีหมายเลขน้อยสุดเองโดยไม่ต้องเขียนเงื่อนไขเพิ่ม โหนดที่อยู่นอกช่วงที่ถามต้องคืนคู่ที่ไม่มีผลกับ min เช่น {INT_MAX, INT_MAX} อุณหภูมิติดลบได้และใหญ่ได้ถึง 10⁹ อย่าใช้ 0 หรือ 1000000 การไล่หาค่าต่ำสุดทุกคำถามเป็น O(NQ) ไม่ทัน

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int n;
vector<pair<int, int>> tree;

void update(int node, int left, int right, int pos, int value)
{
    if (left == right) {
        tree[node] = {value, pos};
        return;
    }
    int mid = (left + right) / 2;
    if (pos <= mid) {
        update(2 * node, left, mid, pos, value);
    } else {
        update(2 * node + 1, mid + 1, right, pos, value);
    }
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}

pair<int, int> query(int node, int left, int right, int from, int to)
{
    if (to < left || right < from) {
        return {INT_MAX, INT_MAX};
    }
    if (from <= left && right <= to) {
        return tree[node];
    }
    int mid = (left + right) / 2;
    return min(query(2 * node, left, mid, from, to), query(2 * node + 1, mid + 1, right, from, to));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    tree.assign(4 * n, {INT_MAX, INT_MAX});
    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        update(1, 1, n, i, t);
    }
    for (int k = 0; k < q; k++) {
        int type, a, b;
        cin >> type >> a >> b;
        if (type == 1) {
            update(1, 1, n, a, b);
        } else {
            pair<int, int> coldest = query(1, 1, n, a, b);
            cout << coldest.first << ' ' << coldest.second << '\n';
        }
    }
    return 0;
}

ข้อ 5 แผนสร้างหุ่นยนต์

ระดับกลาง เวลาไม่เกิน 1 วินาที

ชมรมหุ่นยนต์ของโรงเรียนแตกงานสร้างหุ่นยนต์แข่งออกเป็น N งาน หมายเลข 1 ถึง N งานที่ i ใช้เวลา d_i วัน บางงานต้องรอให้งานอื่นเสร็จก่อนจึงเริ่มได้ เช่น ต้องออกแบบโครงก่อนตัดโลหะ เงื่อนไขมี M ข้อ ข้อหนึ่งเป็นคู่ a b แปลว่างาน b เริ่มได้หลังจากงาน a เสร็จแล้วเท่านั้น

ชมรมมีสมาชิกมากพอ งานที่เงื่อนไขครบแล้วเริ่มพร้อมกันได้ทันทีกี่งานก็ได้ ถ้าเริ่มวันแรกพร้อมกัน ทั้งโครงการจะเสร็จเร็วที่สุดเมื่อผ่านไปกี่วัน รับประกันว่าเงื่อนไขไม่วนกัน

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ 0 ≤ M ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ d₁ ถึง d_N โดยที่ 1 ≤ d_i ≤ 10⁹

อีก M บรรทัด บรรทัดละสองจำนวน a และ b โดยที่ 1 ≤ a, b ≤ N และ a ≠ b

ข้อมูลออก

จำนวนวันที่น้อยที่สุดที่ทำครบทุกงาน

6 5
3 2 4 1 5 2
1 2
1 3
2 4
3 4
5 6

ดูคำใบ้

งาน b เริ่มได้เมื่องานก่อนหน้าทุกงานเสร็จแล้ว วันเริ่มของ b จึงเป็นค่ามากสุดของวันเสร็จของงานก่อนหน้า เป็น DP บน DAG แบบเส้นทางยาวสุดในหน้า 30.1 ต้องคำนวณตามลำดับ topological ใช้ Kahn ได้ลำดับไปพร้อมกัน คำตอบคือวันเสร็จที่มากที่สุดของทุกงาน ไม่ใช่ของงานสุดท้ายในลำดับ ผลรวมถึง 2 × 10¹⁴ ใช้ long long การวนปรับค่าทุกเงื่อนไขซ้ำจนไม่มีอะไรเปลี่ยน ใช้ได้ผลแต่อาจต้องวนถึง N รอบ

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<long long> days(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> days[i];
    }
    vector<vector<int>> next_tasks(n + 1);
    vector<int> waiting(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        next_tasks[a].push_back(b);
        waiting[b]++;
    }
    vector<long long> start(n + 1, 0);
    queue<int> ready;
    for (int task = 1; task <= n; task++) {
        if (waiting[task] == 0) {
            ready.push(task);
        }
    }
    long long answer = 0;
    while (!ready.empty()) {
        int task = ready.front();
        ready.pop();
        long long finish = start[task] + days[task];
        answer = max(answer, finish);
        for (int after : next_tasks[task]) {
            start[after] = max(start[after], finish);
            waiting[after]--;
            if (waiting[after] == 0) {
                ready.push(after);
            }
        }
    }
    cout << answer << '\n';
    return 0;
}

ข้อ 6 จองห้องพักออนไลน์

ระดับยาก เวลาไม่เกิน 1 วินาที

โฮสเทลริมทะเลเปิดให้จองห้องพักล่วงหน้า N คืน หมายเลขคืนที่ 1 ถึง N ทุกคืนต้องจ่ายค่าทำความสะอาดตามจำนวนแขกที่พักคืนนั้น ระบบจองออนไลน์รับเหตุการณ์ Q ครั้งเรียงตามเวลา แต่ละครั้งเป็นแบบใดแบบหนึ่งต่อไปนี้

1 l r g มีการจองใหม่ แขก g คนพักตั้งแต่คืนที่ l ถึงคืนที่ r รวมทั้งสองคืนนั้น
2 l r ฝ่ายบัญชีถามว่า ตามการจองที่เข้ามาถึงตอนนี้ คืนที่ l ถึงคืนที่ r รวมกันมีแขกพักกี่คนคืน คือนำจำนวนแขกของแต่ละคืนในช่วงนั้นมาบวกกัน

คำถามแทรกอยู่ระหว่างการจอง และต้องตอบทันทีตามการจองที่มีอยู่ ณ ตอนที่ถาม

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ Q คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ 1 ≤ Q ≤ 200000

อีก Q บรรทัด บรรทัดละหนึ่งเหตุการณ์ในรูปแบบข้างบน โดยที่ 1 ≤ l ≤ r ≤ N และ 1 ≤ g ≤ 10000

ข้อมูลออก

ทุกเหตุการณ์แบบ 2 ให้พิมพ์จำนวนแขกรวมของช่วงนั้นหนึ่งบรรทัด

ดูคำใบ้

เริ่มจาก difference array เก็บการเปลี่ยนแปลง c ไว้ใน Fenwick tree การจองหนึ่งครั้งบวก g ที่คืน l และลบ g ที่คืน r + 1 จำนวนแขกคืนที่ i คือ c₁ + ... + c_i ส่วนที่ต้องคิดเพิ่มคือคำถามถามผลรวมของจำนวนแขกหลายคืน ผลรวมคืนที่ 1 ถึง x คือผลรวมของ c_j × (x - j + 1) ทุก j ไม่เกิน x กระจายได้เป็น (x + 1) × (ผลรวมของ c_j) - (ผลรวมของ j × c_j) จึงใช้ Fenwick tree สองต้น ต้นแรกเก็บ c_j ต้นที่สองเก็บ j × c_j แล้วตอบช่วง l ถึง r ด้วยผลรวมถึง r ลบผลรวมถึง l - 1 ระวังการจองที่จบคืนสุดท้าย ช่อง r + 1 อยู่นอกต้นไม้ ผลรวมถึงราว 4 × 10¹⁴ ใช้ long long ทุกที่ รวมถึงตอนคูณ j × c_j

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> change_tree, weighted_tree;

void add(vector<long long> &tree, int i, long long delta)
{
    for (; i <= n; i += i & -i) {
        tree[i] += delta;
    }
}

long long prefix_sum(const vector<long long> &tree, int i)
{
    long long total = 0;
    for (; i > 0; i -= i & -i) {
        total += tree[i];
    }
    return total;
}

void add_change(int night, long long delta)
{
    if (night > n) {
        return;
    }
    add(change_tree, night, delta);
    add(weighted_tree, night, delta * night);
}

long long guest_nights_up_to(int x)
{
    return (x + 1) * prefix_sum(change_tree, x) - prefix_sum(weighted_tree, x);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    change_tree.assign(n + 1, 0);
    weighted_tree.assign(n + 1, 0);
    for (int k = 0; k < q; k++) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            long long guests;
            cin >> guests;
            add_change(l, guests);
            add_change(r + 1, -guests);
        } else {
            cout << guest_nights_up_to(r) - guest_nights_up_to(l - 1) << '\n';
        }
    }
    return 0;
}

ข้อ 7 แม่แบบลายผ้า

ระดับกลาง เวลาไม่เกิน 1 วินาที

ช่างทอผ้าทอลายตามแม่แบบหนึ่งชุด แม่แบบคือลำดับสีของเส้นด้าย ทอจบแม่แบบแล้วก็เริ่มแม่แบบเดิมต่อทันที วนไปเรื่อยๆ แล้วตัดผ้าออกมาหนึ่งผืน ผืนที่ตัดอาจจบกลางแม่แบบก็ได้ เราเห็นแค่ผ้าผืนนั้น เขียนเป็นข้อความ s ที่ตัวอักษรหนึ่งตัวแทนสีของเส้นด้ายหนึ่งเส้น

ให้หาความยาวของแม่แบบที่สั้นที่สุดที่ทอแล้วตัดได้ผ้าแบบนี้พอดี ตัวอย่างเช่น ผ้า abcabcab ทอจากแม่แบบ abc ได้ ตอบ 3 ส่วนผ้า abcd ไม่มีส่วนไหนซ้ำ แม่แบบต้องเป็นทั้งผืน ตอบ 4

พูดอีกแบบคือ หา p ที่น้อยที่สุดที่ 1 ≤ p ≤ N และทุกตำแหน่ง i ที่ p ≤ i < N มี s[i] เท่ากับ s[i - p] เมื่อนับตำแหน่งตั้งแต่ 0

ข้อมูลเข้า

บรรทัดเดียว เป็นข้อความ s ยาว N ตัวอักษร (1 ≤ N ≤ 1000000) มีแต่ตัวอักษร a ถึง z

ข้อมูลออก

ความยาวของแม่แบบที่สั้นที่สุด

abcabcab

abcd

ดูคำใบ้

ถ้าแม่แบบยาว p ผ้า N - p ตัวแรกต้องเหมือนกับผ้า N - p ตัวสุดท้ายพอดี เพราะเลื่อนไป p ตัวแล้วต้องได้สีเดิม ส่วนต้นที่เป็นส่วนท้ายด้วยและยาวที่สุดคือค่าสุดท้ายของ prefix function ในหน้า 30.4 คำตอบจึงเป็น N ลบค่านั้น คำตอบไม่จำเป็นต้องหาร N ลงตัว เพราะผ้าจบกลางแม่แบบได้ การลองทุกความยาวแล้วเทียบทั้งผืนใช้ได้กับผ้าสั้น แต่ผ้าที่เป็น a ทั้งผืนแล้วจบด้วย b ทำให้ต้องเทียบราว N²/2 ครั้ง

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string cloth;
    cin >> cloth;
    int n = cloth.size();
    vector<int> border(n, 0);
    for (int i = 1; i < n; i++) {
        int j = border[i - 1];
        while (j > 0 && cloth[i] != cloth[j]) {
            j = border[j - 1];
        }
        if (cloth[i] == cloth[j]) {
            j++;
        }
        border[i] = j;
    }
    cout << n - border[n - 1] << '\n';
    return 0;
}

ข้อ 8 ชั้นวางพัสดุ

ระดับยาก เวลาไม่เกิน 1 วินาที

โกดังของร้านหนังสือออนไลน์มีชั้นวาง N ชั้นเรียงจากหน้าโกดังไปหลังโกดัง หมายเลข 1 ถึง N ชั้นที่ i มีที่ว่างเหลือ c_i เซนติเมตร กล่องพัสดุเข้ามา Q กล่องตามลำดับ กล่องที่ j หนา x_j เซนติเมตร พนักงานเดินเข้าไปจากหน้าโกดัง แล้ววางกล่องบนชั้นแรกที่เจอซึ่งยังมีที่ว่างอย่างน้อย x_j เซนติเมตร วางแล้วที่ว่างของชั้นนั้นลดลง x_j ถ้าไม่มีชั้นไหนมีที่พอ กล่องนั้นถูกส่งไปโกดังอื่น และไม่มีชั้นไหนเปลี่ยน

ให้บอกว่าแต่ละกล่องถูกวางบนชั้นไหน

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ Q คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ 1 ≤ Q ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ c₁ ถึง c_N โดยที่ 0 ≤ c_i ≤ 10⁹

บรรทัดที่สามมีจำนวนเต็ม Q ตัว คือ x₁ ถึง x_Q โดยที่ 1 ≤ x_j ≤ 10⁹

ข้อมูลออก

Q บรรทัด บรรทัดที่ j เป็นหมายเลขชั้นที่วางกล่องที่ j หรือ 0 ถ้ากล่องนั้นถูกส่งไปโกดังอื่น

4 7
5 12 3 8
4 6 7 2 9 3 1

ดูคำใบ้

เก็บที่ว่างของทุกชั้นใน segment tree แบบค่ามากสุดตามหน้า 30.3 ถ้ารากมีค่าน้อยกว่าขนาดกล่อง ไม่มีชั้นไหนรับได้ ตอบ 0 ถ้ารับได้ ให้เดินลงจากรากทีละชั้น ถ้าลูกซ้ายมีค่ามากสุดอย่างน้อยเท่ากล่อง ชั้นแรกที่รับได้อยู่ฝั่งซ้ายแน่ ไปทางซ้าย ไม่อย่างนั้นไปทางขวา จนถึงใบ คิดแบบเดียวกับรอยต่อของ binary search ในหน้า 19.1 แต่ค้นบนต้นไม้ วางกล่องแล้วปรับค่าใบนั้นและพ่อทุกชั้น ทั้งหมดเป็น O(log N) ต่อกล่อง การเดินหาจากชั้นแรกทุกครั้งไม่ทันเมื่อชั้นหน้าโกดังเต็มหมด

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> tree;

void update(int node, int left, int right, int pos, int value)
{
    if (left == right) {
        tree[node] = value;
        return;
    }
    int mid = (left + right) / 2;
    if (pos <= mid) {
        update(2 * node, left, mid, pos, value);
    } else {
        update(2 * node + 1, mid + 1, right, pos, value);
    }
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

int first_fit(int need)
{
    if (tree[1] < need) {
        return 0;
    }
    int node = 1, left = 1, right = n;
    while (left < right) {
        int mid = (left + right) / 2;
        if (tree[2 * node] >= need) {
            node = 2 * node;
            right = mid;
        } else {
            node = 2 * node + 1;
            left = mid + 1;
        }
    }
    return left;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    tree.assign(4 * n, 0);
    vector<int> space(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> space[i];
        update(1, 1, n, i, space[i]);
    }
    for (int j = 0; j < q; j++) {
        int box;
        cin >> box;
        int shelf = first_fit(box);
        if (shelf > 0) {
            space[shelf] -= box;
            update(1, 1, n, shelf, space[shelf]);
        }
        cout << shelf << '\n';
    }
    return 0;
}