Một chuỗi 0-9 được cho. Đối với bài toán này, chúng ta cần tính số chuỗi con chia hết cho 8 và không chia hết cho 3. Đây là bài toán 2 bước, và chúng ta cần viết code từng bước một để giải quyết nó, ví dụ:
Đầu vào
str = "80"
Đầu ra
2
Đầu vào
str = "7675636788"
Đầu ra
15
Cách tiếp cận để tìm giải pháp
Chỉ có các số với 3 chữ số cuối chia hết cho 8, và tổng chữ số chia hết cho 3 thì mới chia hết cho 8.
Bây giờ lưu tổng tiền tố của chuỗi để tổng chữ số của tiền tố modulo 3 là 0, 1, hoặc 2. Sau đó chuỗi được lặp lại cho tất cả các vị trí i. Sau đó đếm số chuỗi con tại i, chia hết cho 8 — bây giờ, trừ đi số chuỗi con tại i, chia hết cho 3 từ giá trị này.
Mảng 2D kích thước |S| X 3 được định nghĩa, |S| là kích thước của một chuỗi, ví dụ dp[i][j].
Tại bất kỳ chỉ số i nào dp[i][j]. Bắt đầu từ chỉ số i đến 0, số chuỗi con có đầu ra j. Vì vậy 0<=j<=0, vì modulo 3.
Chúng ta cần lặp lại qua chuỗi để kiểm tra xem số 1 chữ số, 2 chữ số và 3 chữ số có chia hết cho 8 hay không.
Để xác định xem ký tự có phải là 8 tại chỉ số, kiểm tra số tại chỉ số.
Chia số cho 8 thay vì 3 nếu có 2 chữ số.
Giả sử số chia hết cho 8. Phải có hai (1-3) chuỗi con nếu nó chia hết cho 8. Tuy nhiên, nó cũng sẽ có các chuỗi con, chia hết cho 8. Để loại bỏ chúng.
Ví dụ
#include <bits/stdc++.h> using namespace std; #define MAX 1000 int count (char s[], int len) { int cur = 0, dig = 0; int sum[MAX], dp[MAX][3]; memset (sum, 0, sizeof (sum)); memset (dp, 0, sizeof (dp)); dp[0][0] = 1; for (int i = 1; i <= len; i++) { dig = int (s[i - 1]) - 48; cur += dig; cur %= 3; sum[i] = cur; dp[i][0] = dp[i - 1][0]; dp[i][1] = dp[i - 1][1]; dp[i][2] = dp[i - 1][2]; dp[i][sum[i]]++; } int ans = 0, dprev = 0, value = 0, dprev2 = 0; for (int i = 1; i <= len; i++) { dig = int (s[i - 1]) - 48; if (dig == 8) ans++; if (i - 2 >= 0) { dprev = int (s[i - 2]) - 48; value = dprev * 10 + dig; if ((value % 8 == 0) && (value % 3 != 0)) ans++; } // Lấy số 3 chữ số. if (i - 3 >= 0){ dprev2 = int (s[i - 3]) - 48; dprev = int (s[i - 2]) - 48; value = dprev2 * 100 + dprev * 10 + dig; if (value % 8 != 0) continue; ans += (i - 2); ans -= (dp[i - 3][sum[i]]); } } return ans; } int main () { char str[] = "7675636788"; int len = strlen (str); cout << count (str, len) << endl; return 0; }Đầu ra
4
Kết luận
Trong bài toán này, chúng ta đã học cách tìm số chuỗi con chia hết cho 8 và không chia hết cho 3 cùng với code C++. Code này cũng có thể viết bằng Java, Python và các ngôn ngữ khác. Để giải quyết bài toán này, chúng ta đã đảo ngược chuỗi để tìm số chuỗi con chia hết cho 8 nhưng không chia hết cho 3. Đây là một bài toán rất đơn giản sau khi chia nó thành 2 phần.