# Solution Contest Happy1 :rocket:
## [Link contest](https://hnoj.edu.vn/contest/tin2326_happy1)
---
## Bài 29: LSEQ
### Cách 1:
Ta sử dụng thuật toán tham lam như sau:
- Trước hết xây dựng mảng $b[]$ là các số khác 0 theo thứ tự tăng dần, lưu ý các phần tử mảng $b[]$ là **đôi một phân biệt**.
- Để thuận tiện hơn, ta cộng các giá trị lên $10^6$, từ đó ta hoàn toàn làm việc với các giá trị không âm.
- Với mỗi $a_i$ và $a_{i + 1}$, ta chỉ cần quan tâm đến khoảng cách giữa chúng, tức số số cần thêm vào để tạo thành 1 dãy liên tiếp, vậy nên ta xây dựng mảng $c[]$ là khoảng cách giữa các số liên tiếp trong $b$, hay $c_i = b_{i + 1} - b_i$, sau đó sử dụng tổng cộng dồn cho mảng $c$.
- Gọi số lượng số $0$ là $cnt$. Khi duyệt qua các phần tử của $c$, ta quan tâm với $cnt$ hiện có, ta có thể phủ được đến bao nhiêu phần tử trước đó, tức tìm phần tử $j$ xa nhất sao cho $c_i - c_j \leq cnt$, chuyển vế ta có $c_i - cnt \leq c_j$ (có thể sử dụng Two Pointer hoặc Binary Search). Sau khi tìm được $j$, biết rằng với số lượng số $0$ còn lại, ta không thể vươn đến phần tử trước đó nữa, ta cộng vào biến $current$ một lượng bằng ```cnt - (c[i] - c[j])``` và so sánh với biến kết quả.
> Time: $O(N)$ hoặc $O(N log N)$
::: spoiler Code mẫu
```cpp=
/* #pragma GCC optimize("Ofast,unroll-loops") */
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
#define int long long
const int maxn = 2e6+5;
int n, a[maxn], cnt;
void solve(){
cin >> n;
vector<int> b, c;
for(int i = 1; i <= n; ++i){
cin >> a[i];
a[i] += 1e6;
if(a[i] == 1e6) ++cnt;
else b.push_back(a[i]);
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
if(b.size() == 0){
cout << cnt;
return;
}
c.push_back(b[0] - 1);
for(int i = 1; i < (int)b.size(); ++i){
c.push_back(b[i] - b[i - 1] -1);
}
int ans = 1;
for(int i = 1; i < (int)c.size(); ++i) c[i] += c[i - 1];
for(int i = 0; i < (int)c.size(); ++i){
int x = lower_bound(c.begin(), c.end(), c[i] - cnt) - c.begin();
int nigga = (cnt - c[i] + c[x]);
ans = max(ans, b[i] - b[x] + 1 + nigga);
}
cout << ans;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int test = 1;
/* cin >> test; */
for(int i = 1; i <= test; i++){
/* cout << "Case " << "#" << i << ": "; */
solve();
}
return 0;
}
```
:::
### Cách 2:
Ta sử dụng chặt nhị phân kết quả, ở đây là độ dài lớn nhất đạt được. Sử dụng mảng $a$ là mảng đánh dấu, ban đầu đặt tất cả phần tử của $a$ bằng $1$, tức các số chưa xuất hiện. Sau đó với mỗi $x$ khác $0$, ta cộng $x$ lên $10^6 + 1$ (do mảng chỉ cho phép lưu các phần tử không âm) và lưu vào trong mảng, tức xét $a[x] = 0$. Sau đó sử dụng tổng cộng dồn như trước, ta thu được $a[i]$ là số số cần được thêm vào để thu được dãy liên tiếp từ $0$ đến $i$. Sau đó chặt nhị phân kết quả, với mỗi $mid$ hiện tại, ta xét các khoảng $[i, i + mid - 1]$ và check xem tồn tại hay không 1 khoảng có số số cần thêm vào $\leq cnt$, nếu tồn tại ta tăng $L$, ngược lại ta giảm $R$.
> Time: $O(10^6 * log N)$
::: spoiler Code mẫu
```cpp=
/**
* author: fryingduc
* created:13.09.2023 17:57:37
**/
/* #pragma GCC optimize("Ofast,unroll-loops") */
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
#define int long long
const int maxn = 2e6+6;
int n, cnt, a[maxn], sz;
bool check(int mid){
for(int i = mid; i <= sz; ++i){
if(a[i] - a[i - mid] <= cnt){
return 1;
}
}
return 0;
}
void solve(){
cin >> n;
fill(a, a + maxn, 1);
for(int i = 1; i <= n; ++i){
int x; cin >> x;
if(x == 0) ++cnt;
else{
x += 1e6 + 1;
a[x] = 0;
sz = max(sz, x);
}
}
for(int i = 1; i <= sz; ++i){
a[i] += a[i - 1];
}
int l = cnt, r = n, ans = cnt;
while(l <= r){
int mid = (l + r) / 2;
if(check(mid)){
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << ans;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int test = 1;
/* cin >> test; */
for(int i = 1; i <= test; i++){
/* cout << "Case " << "#" << i << ": "; */
solve();
}
return 0;
}
```
:::
---
## Bài 35: DLIGHT
### Subtask 1: $n \leq 10^6$; $t = 1$
Do chỉ có 1 đoạn $[l_1, r_1]$ được phủ, ta tính các giá trị không nằm trong đoạn trên.
> Time: $O(N)$ hoặc $O(1)$
### Subtask 2: $n \leq 10^3; t \leq 10^5$
Trên tổng số $t$ đoạn, ta for trong khoảng $[l_i, r_i]$ và cộng các giá trị lên $1$. Sau đó for $n$ giá trị, với mỗi $i$, nếu $a_i$ chia hết cho $3$, ta cộng biến kết quả lên $1$.
### Subtask 3: $n \leq 10^6; t \leq 10^5$
Ta cải tiến *Subtask 2* bằng kĩ thuật *đánh dấu hai đầu*, cụ thể ta tạo trước một mảng rỗng có $n$ phần tử, khi tăng đoạn $[l_i, r_i]$, ta tăng $a[l_i]$ lên $1$ và trừ $a[r_i + 1]$ đi $1$, và sau đó sử dụng tổng cộng dồn ```a[i] += a[i - 1]```.
### Subtask 4 $n \leq 10^9; t \leq 10^5$
Do $n \leq 10^9$ nên ta không thể lưu các giá trị vào mảng như *Subtask 3*, ta có nhận xét: từ đó ta có 2 cách tiếp cận:
- Lưu hai đầu mút của đoạn vào 1 cấu trúc dữ liệu ```map<int, int>```
- Sử dụng ```vector<pair<int, int>>``` để add thêm các đầu mút cùng vị trí xuất hiện của các đoạn.
Dù trong cách nào, ta cũng duyệt tuần tự các giá trị trong map, đồng thời lưu lại 1 biến $temp$ là vị trí gần nhất sao cho $a_i$ chia hết cho $3$, và cộng vào biến kết quả các khoảng chia hết cho $3$.
* Lưu ý hai khoảng $[0, l_1]$ và $[r_t, n]$ luôn có giá trị $0$ ban đầu.
> Time: $O(T * log(N))$
::: spoiler Code mẫu
```cpp=
/* #pragma GCC optimize("Ofast,unroll-loops") */
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
/* #define int long long */
const int maxn = 1e5+5;
int n, k, ans = maxn;
map<int, int> mp;
void solve(){
cin >> n >> k;
int mx = 0;
for(int i = 1; i <= k; ++i){
int x, y; cin >> x >> y;
mp[x]++;
mp[y + 1]--;
ans = min(ans, x - 1);
mx = max(mx, y);
}
//debug(mp);
ans += (n - mx);
int prev = 0, div3 = 0;
for(auto &i:mp){
if(div3 != 0) ans += i.first - div3, div3 = 0;
i.second += prev;
prev = i.second;
if(i.second % 3 == 0) div3 = i.first;
}
//debug(mp);
cout << ans;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("dlight.inp", "r", stdin);
//freopen("dlight.out", "w", stdout);
int test = 1;
/* cin >> test; */
for(int i = 1; i <= test; i++){
/* cout << "Case " << "#" << i << ": "; */
solve();
}
return 0;
}
```
:::
---
## Bài 38: Đếm dãy chia hết
Trước hết, ta xây dựng:
- $f[i]$: $\Sigma_{j=1}^{i} a[j]$ (có thể dễ dàng tính bằng công thức: $f[i] = f[i - 1] + a[i]$)
- Mảng đếm $cnt[i]$: số lượng tiền tố có số dư $i$ khi chia $d$.
Ta duyệt tuần tự từng phần tử trong mảng, khi đến vị trí $i$, ta cập nhật kết quả lên $cnt[f[i] \% k]$, và tăng biến $cnt[f[i]\%k]$ lên 1.
* Lưu ý: Đặt $cnt[0] = 1$ và reset lại mảng $cnt[]$ sau mỗi test.
> Time: $O(N)$
::: spoiler Code mẫu
```cpp=
//#pragma GCC optimize("Ofast,unroll-loops")
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
//#define int long long
const int maxn = 5e4+5;
int n, a[maxn], d;
void solve(){
cin >> d >> n;
vector<int> re(d);
for(int i = 1; i <= n; ++i){
cin >> a[i];
a[i] = (a[i - 1] + a[i]) % d;
}
re[0] = 1;
long long ans = 0;
for(int i = 1; i <= n; ++i){
ans += re[a[i]];
re[a[i]]++;
}
cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int test = 1;
cin >> test;
for(int i = 1; i <= test; i++){
// cout << "Case " << "#" << i << ": ";
solve();
}
return 0;
}
```
:::
---
## Bài 39: Nghệ thuật trừu tượng
Ta xét một trường hợp đặc biệt của lưới ô vuông với $n = 1$. Khi đó, bảng vuông suy biến thành mảng có $m$ phần tử. Tiếp tục nhận xét, một cột có thể được nhìn thấy khi và chỉ khi tất cả các cột trước đó đều có chiều cao **nhỏ hơn** cột đó. Mặt khác, do ta được phép nhìn dãy ở nhiều hướng khác nhau, quá trình này lặp lại một lần nữa theo chiều ngược lại.
Gọi $mx$ là giá trị lớn nhất đang xét, ta duyệt $j$ từ $1$ đến $n$, nếu $a[j] > mx$, ta cập nhật kết quả và làm tương tự theo chiều ngược lại.
```cpp=
int mx = 0;
for(int j = 1; j <= m; ++j){
if(a[j] > mx){
check[j] = 1;
mx = a[j];
}
}
mx = 0;
for(int j = m; j; --j){
if(a[j] > mx){
check[j] = 1;
mx = a[j];
}
}
```
Đến đây ta tổng quát hóa bài toán bằng cách xét thêm chiều dọc, lưu cái giá trị có thể được nhìn thấy vào mảng $see[][]$, ta thu được lời giải hoàn chỉnh.
> Time: $O(M * N)$
::: spoiler Code mẫu
``` cpp=
/**
* author: fryingduc
* created:12.09.2023 22:43:46
**/
/* #pragma GCC optimize("Ofast,unroll-loops") */
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
/* #define int long long */
const int maxn = 1005;
int n, m, a[maxn][maxn], see[maxn][maxn];
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
cin >> a[i][j];
}
}
for(int i = 1; i <= n; ++i){
int mx_i = 0;
for(int j = 1; j <= m; ++j){
if(a[i][j] > mx_i){
see[i][j] = 1;
mx_i = a[i][j];
}
}
mx_i = 0;
for(int j = m; j; --j){
if(a[i][j] > mx_i){
see[i][j] = 1;
mx_i = a[i][j];
}
}
}
for(int j = 1; j <= m; ++j){
int mx_j = 0;
for(int i = 1; i <= n; ++i){
if(a[i][j] > mx_j){
see[i][j] = 1;
mx_j = a[i][j];
}
}
mx_j = 0;
for(int i = n; i; --i){
if(a[i][j] > mx_j){
see[i][j] = 1;
mx_j = a[i][j];
}
}
}
int ans = 0;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
ans += see[i][j];
}
}
cout << ans;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int test = 1;
/* cin >> test; */
for(int i = 1; i <= test; i++){
/* cout << "Case " << "#" << i << ": "; */
solve();
}
return 0;
}
```
:::
---
## Bài 40: Máy quét
### Subtask 1: $N \le 2000$
Với mỗi vị trí $i$ ta duyệt tất cả các phần tử trong khoảng $[i - K, i + K]$ để tìm kết quả.
> Time: $O(N^2)$
### Subtask 2: $N \le 10^5$
Với subtask này, ta sẽ sử dụng mảng đếm, với $cnt[x]$ là số phần tử có giá trị bằng $x$. Và để đảm bảo các phần tử trong mảng đếm khi duyệt đến vị trí thứ $i$ đều trong khoảng $[i - K, i + K]$, ta sẽ sử dụng kĩ thuật **cửa sổ trượt** (sliding window).
> Time: $O(N)$
::: spoiler Code mẫu
``` cpp=
#include "bits/stdc++.h"
using namespace std;
#define F first
#define S second
#define sz(x) int((x).size())
using ll = long long;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
assert(l <= r);
return uniform_int_distribution<ll> (l, r)(rng);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
const int N = 1e5 + 3;
int n, k, a[N], cnt[N];
void solve(){
cin >> n >> k;
for(int i = 1; i <= n; ++i)
cin >> a[i];
// Thêm đoạn [1, K]
for(int i = 1; i <= k; ++i)
++cnt[a[i]];
int left = 1, right = k;
for(int i = 1; i <= n; ++i){
// Nếu left nằm ngoài đoạn [i - K, i + K] thì xóa đi
if(left < i - k){
--cnt[a[left]];
++left;
}
// Tăng right lên để phủ toàn bộ đoạn [i - K, i + K]
if(right < i + k and right < n){
++right;
++cnt[a[right]];
}
// In ra các số bằng a[i] trong khoảng [i - K, i + K]
cout << cnt[a[i]] << ' ';
}
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(0);
int test = 1;
// cin >> test;
for(int i = 1; i <= test; ++i){
// cout << "Case #" << i << ": ";
solve();
}
cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
return 0;
}
```
:::
---
## Bài 44: Points
Công thức khoảng cách Manhattan giữa hai điểm $(x_1, y_1)$ và $(x_2, y_2)$: $|x_1 - x_2| + |y_1 - y_2|$
Cho các điểm sau:
Giả sử ta đang duyệt đến điểm $A$. Khi đó, ta thấy rằng chỉ điểm **gần nhất về bên phải và gần nhất về bên trái** của điểm $A$ trên đường thẳng còn lại có thể là đoạn thẳng nhỏ nhất.
Ví dụ ở hình trên, chỉ có $AY$, $AZ$ có thể là đáp án mà không phải $AX$, $AT$ vì $AX > AY$, $AT > AZ$ nên ta không cần xét $AX$, $AT$.
Việc còn lại là tìm điểm gần nhất với $A$, ta có thể sử dụng tìm kiếm nhị phân hoặc hai con trỏ. Ở đây lời giải sẽ giải thích cách làm bằng hai con trỏ.
Đầu tiên ta sắp xếp các điểm tăng dần trên các đường thẳng, sau đó duyệt các điểm $A$ ở một đường bất kì. Đồng thời ta duy trì một con trỏ $cur$, là điểm gần nhất về bên phải của $A$ ở đường thẳng còn lại. **Khi đó vì $cur$ là điểm gần nhất ở bên trái $cur + 1$ chính là điểm gần nhất ở bên phải của $A$.**
> Time: $O(N \log N + M \log M)$
:::spoiler Code mẫu
```cpp=
#include "bits/stdc++.h"
using namespace std;
#define F first
#define S second
#define sz(x) int((x).size())
using ll = long long;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
assert(l <= r);
return uniform_int_distribution<ll> (l, r)(rng);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
const int N = 1e6 + 3;
int n, m, x1, x2, a[N], b[N];
int dist(int x, int y, int u, int v){
return abs(x - u) + abs(y - v);
}
void solve(){
cin >> n >> m;
cin >> x1 >> x2;
for(int i = 1; i <= n; ++i)
cin >> a[i];
for(int i = 1; i <= m; ++i)
cin >> b[i];
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
int cur = 0;
int min_len = INT_MAX, cnt = 0;
for(int i = 1; i <= n; ++i){
// Tìm b[cur] lớn nhất mà vẫn < a[i]
while(cur < m and b[cur + 1] < a[i])
++cur;
if(cur > 0){ // Điểm gần nhất bên trái
// Nếu đáp án hiện tại chưa tối ưu thì cập nhật lại
if(min_len > dist(x1, a[i], x2, b[cur])){
min_len = dist(x1, a[i], x2, b[cur]);
cnt = 1;
}
// Nếu đoạn thẳng bé nhất bằng đáp án hiện tại thì tăng số lượng cặp thỏa mãn
else if(min_len == dist(x1, a[i], x2, b[cur]))
++cnt;
}
if(cur + 1 <= m){ // Điểm gần nhất bên phải
if(min_len > dist(x1, a[i], x2, b[cur + 1])){
min_len = dist(x1, a[i], x2, b[cur + 1]);
cnt = 1;
}
else if(min_len == dist(x1, a[i], x2, b[cur + 1]))
++cnt;
}
}
cout << min_len << ' ' << cnt << '\n';
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(0);
int test = 1;
// cin >> test;
for(int i = 1; i <= test; ++i){
// cout << "Case #" << i << ": ";
solve();
}
cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
return 0;
}
```
:::
# Solution Contest Happy2 :muscle:
## [Link contest](https://hnoj.edu.vn/contest/tin2326_happy2)
## BÀI 2: CABC
### SOLUTION: Ta xét 2 trường hợp như sau
#### TH1: $k$ lẻ
$k \mid a+b,k \mid b+c,k \mid c+a$
$\Rightarrow k \mid 2a, k \mid 2b, k\mid 2c$
$\Rightarrow k \mid a, k \mid b, k\mid c$
Dễ thấy với mỗi số $a,b,c$ ta có $\lfloor$ $n \over k$ $\rfloor$ cách chọn nên đáp án là
$(\lfloor$ $n \over k$ $\rfloor )^3$ (hoặc có thể đếm bằng cách for đến $n$)
#### TH2: $k$ chẵn
$k \mid 2a, k\mid 2b, k\mid 2c$
$\Rightarrow a,b,c \equiv 0$ (mod $k$) hoặc
$a,b,c \equiv$ $k \over 2$ (mod $k$) $\Leftrightarrow$ $a,b,c \equiv 0$ (mod $k\over 2$)
Đáp án sẽ là $(\lfloor$ $n \over k$ $\rfloor )^3 + (\lfloor$ $2n \over k$ $\rfloor - \lfloor$ $n \over k$ $\rfloor )^3$ (Do cần loại bỏ những số chia hết cho $k \over 2$ có số chia hết cho $k$)
:::spoiler Code mẫu
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
//int t; cin>>t; while(t--)
int n,k,cnt=0,count=0;
cin>>n>>k;
cnt=n/k;
if(k%2==0){
count=(n/(k/2));
count-=cnt;
}
if(k%2==0) cout<<cnt*cnt*cnt+count*count*count;
else cout<<cnt*cnt*cnt;
}
```
:::
## BÀI 3: CNTSQR
### Subtask 1: $h,v \le 2$
Có tối đa $4$ điểm trên mặt phẳng nên ta chỉ cần xét $4$ điểm đó có phải là 4 đỉnh trên của một hình vuông không.
### Subtask 2: $h,v \le 600$
**Nhận xét** : Ta thấy $4$ đường thẳng cắt nhau tạo ra hình vuông khi khoảng cách giữa $2$ đường thẳng song song Ox bằng khoảng cách giữa $2$ đường thẳng song song Oy.
Từ đó, với mỗi cặp $x[i]-x[j]=d$ $(i>j)$, ta sẽ đếm xem có bao nhiêu cặp $y[l]-y[k]$ tương ứng.
Bằng cách sử dụng CTDL $map$, ta sẽ lưu số lần xuất hiện của mỗi $d$, từ đó duyệt các cặp $y[l]-y[k]$.
> Time: $O(N^2 * 30)$ (sử dụng $map$ tốn $log(x_i) \approx 30$)
### Subtask 3: $h,v \le 1500$
Ở subtask này, thay vì ta lưu số lần xuất hiện của các giái trị $d$, ta cho chúng vào một mảng $luu$ sau đó sort lại .
Với mỗi giá trị $y[l]-y[k]$, ta sử dụng chặt nhị phân để tìm kiếm số lần xuất hiện của nó trên mảng $luu$
> Time: $O(N^2 * log(N^2))$
:::spoiler Code mẫu
```cpp=
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define cebug(x) cerr << "[" << #x << "] = " << x << endl
const int N=1505;
const int mod=1e9+7;
int h,v,y[N],x[N],luu[N*N],ans,cnt=1;
void sol(){
cin>>h>>v;
for(int i=1; i<=h; i++) cin>>y[i];
for(int i=1; i<=v; i++) cin>>x[i];
for(int i=1; i<h; i++){
for(int j=i+1; j<=h; j++){
luu[cnt]=y[j]-y[i];
cnt++;
}
}
sort(luu+1,luu+cnt);
for(int i=1; i<v; i++){
for(int j=i+1; j<=v; j++){
int res=x[j]-x[i];
int k=upper_bound(luu+1,luu+cnt,res)-luu;
int z=lower_bound(luu+1,luu+cnt,res)-luu;
k--;
if(luu[z]!=res) continue;
ans+=k-z+1;
}
}
cout<<ans;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
int t=1;
//cin>>t;
while(t--){
sol();
}
cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
return 0;
}
/** /\_/\
* (= ._.)
* / >💖 \>💕 topbar
**/
// toi yeu mrtee
```
:::
Sign in with Wallet
Connect another wallet