Hướng dẫn giải của Bedao Regular Contest 01 - GRADE


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Vì các điểm x ~\leq 10^6~ nên ta chỉ cần sử dụng hai mảng là ~G~ và ~F~ với:

~G~ là tần suất của điểm ~K~ trong các dãy bàn liên tiếp

~F~ là giá trị lớn nhất của dãy con có điểm chung là ~K~ tại bàn thứ ~i~.

Vậy làm sao để biết được điểm K có xuất hiện trong 1 loạt các dãy bàn liên tiếp nhau không ?

Tại điểm thứ ~K~ của bàn thứ ~i~ ta sẽ tìm kiếm nhị phân ở bàn thứ ~i-1~ trước đó để xem xem điểm ~K~ có xuất hiện trong bàn thứ ~i-1~ hay không. Nếu không có thì ta sẽ gán ~G_K = 0~ vì lúc này ta không thể ghép ~2~ bàn ~i~ với ~i-1~ lại để được dãy bàn liên tiếp có điểm chung là ~K~ được. Sau mỗi lần duyệt như thế, tại điểm ~K~ đang xét tại bàn thứ ~i~, ta sẽ tăng ~G_K~ lên ~1~ và gán ~F_K = max(F_K , G_K)~.

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

int n, q, x, a;
set<int> se[1005];

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> q;

    for1(i,1,n) {
        cin >> x;
        while (x--) {
            cin >> a;
            se[i].insert(a);
        }
    }

    while (q--) {
        int p, cur = 0, res = 0;
        cin >> p;
        for1(i,1,n) {
            if (se[i].find(p) != se[i].end()) cur++;
            else cur = 0;
            res = max(res, cur);
        }
        cout << res << "\n";
    }

}

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -2
    baolong310876  đã bình luận lúc 7, Tháng 1, 2023, 8:51 chỉnh sửa

    my friend write,not me


  • 3
    vidut_206_CNH  đã bình luận lúc 5, Tháng 10, 2021, 11:50

    Dòng cuối phải là ~F_K = max(F_K,G_K)~ chứ ạ ? 😃


    • 2
      ntkwan  đã bình luận lúc 6, Tháng 10, 2021, 4:26

      Cảm ơn bạn đã góp ý, bên mình đã ghi nhận và sửa lại editorial rồi ạ