Bài toán cụ thể

Có bao nhiêu nghiệm ~(x_1, x_2, x_3, x_4, x_5)~ nguyên dương thỏa mãn:

• ~x_1 ≤ x_2 ≤ x_3 ≤ x_4 ≤ x_5~
• ~x_1 + x_2 + x_3 + x_4 + x_5 = 8~

~3~ nghiệm thỏa mãn:

• ~1 + 1 + 1 + 1 + 4 = 8~

• ~1 + 1 + 1 + 2 + 3 = 8~

• ~1 + 1 + 2 + 2 + 2 = 8~

Hướng giải quyết

• Gọi ~dp[i][j]~ là số cách tạo thành tổng ~j~ dùng đến đúng ~i~ số nguyên dương.

Cơ sở quy hoạch động

• ~dp[i][i] = 1~ với mọi ~i~ từ ~1~ đến ~k~ Biểu thị cho việc luôn tìm ra cách phân tích số có tổng ~i~ bằng việc dùng đúng ~i~ số nguyên dương.

Chả hạn:

• ~3 = 1 + 1 + 1~

• ~5 = 1 + 1 + 1 + 1 + 1~

Tìm nguyên tắc duyệt

• Xác định rằng không thể tạo thành tổng ~x~ mà lại dùng nhiều hơn ~x~ số nguyên dương.

Chả hạn: Không thể tạo thành tổng ~7~ mà dùng đúng ~8~ số nguyên dương

• Do đó chỉ xét các trường hợp tạo thành tổng ~i, i+1, i+2,…~ đến ~n~ dùng đúng ~i~ số nguyên dương. Quá trình xét này thể hiện qua vòng for:

for (int i = 1; i <= k; i++){
    for (int j = i; j <= n; j++){
        //dp
    }
}

Tìm hệ thức truy hồi

• Để tạo thành tổng ~j~ dùng đúng ~i~ số nguyên dương, ta có các trường hợp sau:

Trường hợp 1: Số đầu tiên trong dãy số hạng là số ~1~.

• Khi đó số cách thỏa mãn trường hợp ~1~ chính là là cách tạo thành tổng ~j-1~, dùng đúng ~i-1~ số hạng.
• Tức là ta thêm một số hạng duy nhất là số ~1~, trong đó số hạng này nằm ở đầu dãy.

=> Chỉ có một cách duy nhất để dùng thêm đúng ~1~ số như vậy, tức là không thể đặt số ~1~ này vào ví trí nào khác ngoài vị trí đầu tiên

Chả hạn: có đúng ~3~ cách để tạo thành số ~7~ dùng đúng ~2~ số nguyên dương:

• ~1 + 6 = 7~

• ~2 + 5 = 7~

• ~3 + 4 = 7~

Thì cũng chỉ có ~3~ cách để thêm được số ~1~ vào trong bộ đáp án này, tạo thành tổng ~8~ dùng đúng ~3~ số nguyên dương:

• ~1 + 1 + 6 = 8~

• ~1 + 2 + 5 = 8~

• ~1 + 3 + 4 = 8~

Do đó ~F_1 = dp[i-1][j-1]~, trong đó ~F_1~ là số cách thỏa mãn trường hợp ~1~

Trường hợp 2: Số hạng đầu tiên trong dãy không phải là ~1~, bắt đầu là các số ~≥ 2~

• Ở trên ra có ~3~ cách tạo thành tổng bằng ~8~ dùng đúng ~3~ số nguyên dương, trong đó các số đầu tiên bằng ~1~

• Giờ ta sẽ thử xem có bao nhiêu cách tạo thành tổng bằng ~8~ dùng đúng ~3~ số nguyên dương, trong đó số đầu tiên khác ~1~

Ví dụ: Ngoài ~3~ cách

• ~1 + 1 + 6 = 8~

• ~1 + 2 + 5 = 8~

• ~1 + 3 + 4 = 8~

Thì còn có thêm hai cách nữa:

• ~2 + 2 + 4 = 8~

• ~2 + 3 + 3 = 8~

Cấu hình của ~2~ cách này tương đương với cấu hình của ~2~ cách tạo thành tổng bằng ~5~ dùng ~3~ số nguyên dương, chỉ khác là các số hạng đều cộng thêm ~1~ đơn vị:

• ~1 + 1 + 3 = 5~

• ~1 + 2 + 2 = 5~

Số cách thỏa mãn điều kiện này chính là ~dp[i][j-i]~ (do mỗi số hạng đều bị cộng thêm ~1~ đơn vị tối thiểu)

• Đây là nghệ thuật của quy hoạch động, không phải lúc nào cũng có bài vở để nhìn ra được!

Do đó ~F_2 = dp[i][j-i]~, trong đó ~F_2~ là số cách thỏa mãn trường hợp ~2~

Kết luận

🔍 Trường hợp 1 và Trường hợp 2 cho ra hai loại nghiệm không bị đếm trùng nhau và cùng thỏa mãn việc dùng đúng ~i~ số nguyên dương tạo thành tổng ~j~

Do đó kết hợp trực tiếp nghiệm của hai trường hợp sẽ cho ra kết quả:

~dp[i][j] = F_1 + F_2 = dp[i-1][j-1] + dp[i][j-i]~

Code

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

const int maxn = 1e3 + 10;
int x[maxn];
int n,k;

void Print(){
    for (int i = 1; i <= k; i++) cout << x[i] << " ";
    cout << "\n";
}

void Try(int pos, int sum){
    if (pos > k){
        Print();
        return;
    }

    if (pos == k){
        if (n - sum < x[pos-1]) return;
        x[pos] = n-sum;
        Print();
        return;
    }

    for (int i = x[pos-1]; i <= n-sum; i++){
       x[pos] = i;
       Try(pos+1, sum+i);
   }
}

int dp[maxn][maxn];
signed main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);

   cin >> n >> k;

   dp[0][0] = 1;
   for (int i = 1; i <= k; i++){
       for (int j = i; j <= n; j++){
           dp[i][j] = dp[i-1][j-1] + dp[i][j - i];
       }
   }

   cout << dp[k][n];

   cout << "\n";

   x[0] = 1;
   Try(1, 0);
}

Bài Toán

DQUERY

Tài liệu

VNOI - Persistent Segment Tree

Thuật toán

QUORA

Xét một mảng ~a~ gồm ~7~ phần tử như sau:

~1, 2, 3, 2, 1, 3, 4~

Và một mảng ~prev~, với ~prev[i] = j~ biểu thị cho vị trí ~j~ gần nhất về phía bên trái đối với ~i~ mà ~a[i] = a[j]~ (Nếu ~a[i]~ xuất hiện lần đầu tiên, ~prev[i] = 0~)

Mảng ~prev~ của ~a~ sẽ có giá trị như sau:

~0, 0, 0, 2, 1, 3, 0~

Định nghĩa mảng ~F~ của bài toán

Xây dựng ~N~ phiên bản của một mảng ~F~. Ở phiên bản thứ ~k~, sẽ gồm ~k~ phần tử đầu tiên đã được xây dựng và có ý nghĩa như sau:

• ~F[i] = 0~, thể hiện rằng mảng a TỒN TẠI một vị trí ~j~ ~(i < j <= k)~ mà ~a[j] = a[i]~
• ~F[i] = 1~, thể hiện đây là vị trí ~j~ ~(j = i <= k)~ xa nhất và ~<= k~ về phía bên phải mảng ~a~ mà ~a[i]~ xuất hiện
• ~F[i] = {rỗng}~, thể hiện vị trí ~i~ chưa được xây dựng ở phiên bản hiện tại ~(i > k)~

mảng ~F~ xây dựng ở các phiên bản có thể hình dung như sau:

          | a[]     1     2     3     2     1     3     4
          | prev[]  0     0     0     2     1     3     0
----------|----------------------------------------------
Phiên bản |                            
    1.    |         1                  
    2.    |         1,    1            
    3.    |         1,    1,    1     
    4.    |         1,    0,    1,    1                       
    5.    |         0,    0,    1,    1,    1              
    6.    |         0,    0,    0,    1,    1,    1
    7.    |         0,    0,    0,    1,    1,    1,    1

Để xây dựng được mảng ~F~ ở một phiên bản ~k~:

• ~+1~ vị trí ~k~ ở mảng ~F~ lên
• ~-1~ vị trí ~prev[k]~ ở mảng ~F~ xuống (Nếu ~prev[k] = 0~ thì không cần trừ)

Tính đúng đắn

Dưới góc nhìn trực quan

Thuật toán có đảm bảo mảng ~F~ hoạt động theo đúng định nghĩa ?

Ta thấy rằng mỗi lần cập nhật một vị trí ~k~ trong mảng ~F~ lên ~+1~ đơn vị, ta lại ~-1~ đi vị trí ~prev[k]~ đi một đơn vị (là vị trí GẦN NHẤT và phía BÊN TRÁI đối với ~a[k]~ mà ~a[prev[k]] = a[k]~)

-> Mảng ~F~ hoạt động theo đúng định nghĩa

Ý tưởng của cách làm này, đó là ta sẽ dồn sự xuất hiện của một số ~a[i]~ về phía bên phải nhất của mảng ~F~, đảm bảo ~a[i]~ chỉ được tính duy nhất ~1~ lần

Số phần tử khác nhau trong đoạn ~[L, R]~ là tổng mảng ~F~ ở phiên bản ~R~, đoạn ~[L, R]~

Ta thấy được ý nghĩa của mảng ~F~ ở phiên bản ~R~ trong khoảng ~[L, R]~ như sau:

• Mỗi số ~1~ xuất hiện trong mảng ~F~, sẽ đại diện cho ~1~ lần duy nhất phần tử ở vị trí đó được tính đúng ~1~ lần.
• Mỗi số ~0~ trong mảng, thể hiện rằng tồn tại một phần tử khác trong khoảng ~[L, R]~ cũng đã xuất hiện trong mảng rồi, nên không cần tính nữa

-> Điều phải chứng minh

Dưới góc nhìn quy nạp

Mình không chắc nên chứng minh như thế nào :Đ

Code - Persistent Segment Tree

#include <bits/stdc++.h>
#define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
#define ep emplace_back
using namespace std;

const int maxn = 2e5 + 10;
const int LOG = log2(maxn)+2;
struct Node{
   int l = 0, r = 0;
   int sum = 0;
};
Node T[maxn*LOG];

int n,q;
int cnt = 0;
int ROOT[maxn];
int a[maxn];

void build(int& nod, int l, int r){
   nod = ++cnt;
   if (l == r){
       T[nod].sum = 0;
       return;
   }
   int mid = (l+r) >> 1;
   build(T[nod].l, l, mid);
   build(T[nod].r, mid+1, r);
}

void push_up(int nod){
   T[nod].sum = T[T[nod].l].sum + T[T[nod].r].sum;
}

void update(int& nod, int prev_nod, int l, int r, int pos, int val){
   nod = ++cnt;
   T[nod] = T[prev_nod];
   if (l == r){
       T[nod].sum += val;
       return;
   }

   int mid = (l+r) >> 1;
   if (pos <= mid) update(T[nod].l, T[prev_nod].l, l, mid, pos, val);
   else update(T[nod].r, T[prev_nod].r, mid+1, r, pos, val);
   push_up(nod);
}

int query(int nod, int l, int r, int u, int v){
   if (l > v || r < u) return 0;
   if (l >= u && r <= v) return T[nod].sum;
   int mid = (l+r) >> 1;
   int L = query(T[nod].l, l, mid, u, v);
   int R = query(T[nod].r, mid+1, r, u, v);
   return L+R;
}

int pre[1000001];
signed main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);

   cin >> n;
   up(i,1,n) cin >> a[i];
   build(ROOT[0], 1, n);

   up(i,1,n){
       if (pre[a[i]]){
           update(ROOT[i], ROOT[i-1], 1, n, pre[a[i]], -1);
           update(ROOT[i], ROOT[i], 1, n, i, 1);
       }
       else update(ROOT[i], ROOT[i-1], 1, n, i, 1);
       pre[a[i]] = i;
   }

   cin >> q;
   while (q--){
       int l, r;
       cin >> l >> r;
       cout << query(ROOT[r], 1, n, l, r) << "\n";
   }
}

A. Tìm xâu

Cho 2 xâu A, B độ dài không vượt quá ~10^6~. Đưa ra những vị trí xuất hiện xâu A trong xâu B.

Input

Dòng đầu chứa xâu A

Dòng hai chứa xâu B

Output

Dòng đầu chứa số k là số vị trí xuất hiện xâu A trong xâu B.

Dòng 2 chứa k số nguyên tăng dần xác định k vị trí xuất hiện A trong B

Example

Input

viet
vietnamnamvietviet

Output

3
1 11 15

Hướng dẫn

Hoàn toàn có thể làm trâu bài toán này với độ phức tạp ~O(n*m)~ cùng hàm ~find()~ trong thư viện

Tuy nhiên với thuật toán Hash String thì chỉ cần khởi tạo mã Hash trong ~O(m+n)~ và kiểm tra trong thời gian tuyến tính

Code

#include <bits/stdc++.h>
#define Task ""
#define up(i,a,b) for (int i = (a); i <= (b); i++)
#define base 311
using namespace std;

const int maxn = 10000001;
const int MOD = 1e9 + 7;
const long long MM = 1ll*MOD*MOD;

long long H[maxn];
long long B[maxn];
string a,b;
int n,m;

long long gethash(int u, int v){
    return (B[v] - B[u-1]*H[n] + MM) % MOD;
}

signed main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> b >> a;
    n = a.size();
    m = b.size();
    a = '@' + a;
    b = '@' + b;

    long long hashA = 0;
    for (int i = 1; i <= n; i++){
        hashA = (hashA*base + a[i]) % MOD;
    } // Hash code of string a

    H[0] = 1;
    for (int i = 1; i <= m; i++){
        B[i] = (B[i-1]*base + b[i]) % MOD;
        // Hash code of substrings from 1 to i in b
        H[i] = (H[i-1]*base) % MOD;
        // Decryptor
    }

    for (int v = n; v <= m; v++){
        int u = v - n + 1;
        if (gethash(u, v) == hashA){
            cout << u << " ";
        }
    }
    return 0;
}