Hướng dẫn giải của duong3982oj Contest 01 - Phần dư và xâu đối xứng
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.
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ả:
Nhận xét: Nếu ta coi tập số lượng các chữ cái của một người chỉ là ~0~ hoặc ~1~ (tương ứng chẵn hay lẻ), thì xâu đối xứng chỉ được phép có tối đa một ký tự có giá trị đó là ~1~.
Vì vậy, ta sẽ sử dụng một bitset gồm ~2^{26}~ để lưu các chữ cái của một người. Trong thực tế, có thể sử dụng kiểu int để thay thế.
Nhận xét:
- Với ~x_i \le \sqrt n~, thì ta có thể lưu một mảng ~lazy_{i, j}~ với ý nghĩa ta sẽ thêm từng đó ký tự vào những người có số thứ tự chia ~i~ dư ~j~.
- Ngược lại, ta có thể cập nhật trâu, vì số thao tác ta phải
forkhông quá ~\sqrt n~.
Vì vậy, độ phức tạp của thuật toán là ~O~ ~(n \times \sqrt n)~.
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 5, sqr = 450;
int mask[sqr][sqr], ans[MAX];
int main ()
{
ios_base :: sync_with_stdio (false);
cin.tie (NULL);
cout.tie (NULL);
int n, q;
cin >> n >> q;
for (int i = 1; i <= q; i ++)
{
int x, y;
char c;
cin >> x >> y >> c;
if (x < sqr) mask[x][y] ^= (1 << (c - 'a'));
else for (int j = y; j <= n; j += x) ans[j] ^= (1 << (c - 'a'));
}
for (int i = 1; i < sqr; i ++)
for (int j = 0; j < i; j ++)
if (mask[i][j])
for (int k = j; k <= n; k += i)
ans[k] ^= mask[i][j];
int a = 0;
for (int i = 1; i <= n; i ++) if (__builtin_popcount (ans[i]) <= 1) a ++;
cout << a;
}
Bình luận