### 514A : A. Chewbaсca and Number
#### tags : greedy, implementation, 1200 elo
#### link : https://codeforces.com/problemset/problem/514/A
#### 

### [1420B - Rock and Lever | Elo 1200](https://codeforces.com/problemset/problem/1420/B)
:::spoiler
#### AC
#### Code

#include <iostream>
#include <unordered_map>
using namespace std;
long long t, n, x;
unordered_map <long long, long long> a;
long long MostSignificantBit(long long x)
{
    long long index = 0;
    while (x > 1)
    {
        x >>= 1;
        index++;
    }
    return index;
}
int main()
{
    cin >> t;
    for (long long j = 0; j < t; j++)
    {
        a.clear();
        cin >> n;
        for (long long i = 0; i < n; i++)
        {
            cin >> x;
            a[MostSignificantBit(x)]++;
        }
        long long c = 0;
        for (auto [i, j] : a)
        {
            c += j * (j - 1) / 2;
        }
        cout << c << "\n";
    }
}

#### Giải thích
Ta để ý khi dùng `&`, các số có cùng bit cao nhất sẽ cho ra số lớn hơn khi `^`. Đọc [Bitwise Operators](https://hackmd.io/@NMQuan57/BitwiseOperators) để hiểu hơn về cách hoạt động.
#### Độ phức tạp
**Input** $O(t) * O(n)$
**Xử lí bit** $O(\log_2(a_i))$
**Push `unordered_map`** $O(n)$
**Tính kết quả**(chạy hết qua các phần tử trong `unordered_map`) $O(n)$ trường hợp tệ nhất nếu không có số nào có cùng bit cao nhất
**Worst case** $O(t) * O(n * \log_2(a_i)) + O(n) + O(n) = O(t) * O(n * \log_2(a_i)) + O(2n)$
:::

### [1328C - Ternary XOR | Elo 1200](https://codeforces.com/problemset/problem/1328/C)
:::spoiler
#### AC
#### Code

#include <iostream>
using namespace std;
int t, n;
char x;
string a, b;
int main() 
{
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        a = ""; b = a;
        cin >> n;
        bool greater = false;
        for (int j = 0; j < n; j++)
        {
            cin >> x;
            if (x == '0'){a += "0"; b += "0";}
            else if (x == '1')
            {
                if (!greater){a += "1"; b += "0"; greater = true;}
                else {a += "0"; b += "1";}
            }
            else
            {
                if (!greater){a += "1"; b += "1";}
                else {a += "0"; b += "2";}
            }
        }
        cout << a << "\n" << b << "\n";
    }
    return 0;
}

#### Giải thích
Ta để ý thấy khi cộng a và b theo từng chữ số thì sẽ bằng n.
#### Độ phức tạp
**Input** $O(t)$
**Xử lí bài toán** $O(n)$
**Worst case** $O(t) * O(n) = O(t * n)$
:::
### [2A - Winner | Elo 1500](https://codeforces.com/problemset/problem/2/A)
:::spoiler
#### AC
#### Code

#include <iostream>
#include <unordered_map>
#include <vector>
#include <utility>
using namespace std;
string name;
int n, score;
unordered_map <string, int> a;
vector <pair<string, int>> progress;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> name >> score;
        a[name] += score;
        progress.push_back({name, a[name]});
    }
    int maxscore = -1005;
    for (auto [i, j] : a) {if (j > maxscore) maxscore = j;}
    for (auto [i, j] : progress) {if (j >= maxscore && a[i] == maxscore) {cout << i; return 0;}}
    return 0;
}

#### Giải thích
Chọn ra người chơi có số điểm cao nhất, trường hợp có nhiều người có cùng số điểm cao nhất thì chọn ra người có đạt số điểm đó trước.
#### Độ phức tạp
**Input** $O(n)$
**Duyệt qua `unordered_map` a** $O(n)$ (trong trường hợp có tới `n` người chơi khác nhau)
**Duyệt qua `vector` progress** $O(n)$
**Worst case** $O(n) + O(n) + O(n) = O(3n)$
:::

### [580C - Kefa and Park | Elo 1500](https://codeforces.com/problemset/problem/580/C)
:::spoiler
#### AC

#### Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n,m;
vector<int> a[100009];
bool cat[100009];
int ans=0;
bool visit[100009];
void solve(int x,int demMeo)
{
    visit[x]=true;
    bool check=true;
    for(auto i:a[x])
    {
        if(!visit[i])
        {
            check=false;
        }
    }
    if(check)
    {
        ans++;
        return;
    }
    for(auto i:a[x])
    {
        if(!visit[i])
        {
            if(demMeo<m&&cat[i])
            {
                solve(i,demMeo+1);
            }
            else if(!cat[i]) solve(i,0);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);

    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        cin >> cat[i];
    }
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    if(cat[1]) solve(1,1);
    else solve(1,0);
    cout << ans;
    return 0;
}

#### Giải thích
Vừa dfs vừa đếm số lượng mèo gặp trên path, nếu lố số mèo quy định thì ko chọn đi lối này. Để kiểm tra xem liệu đã gặp phần đáy của tree chưa thì ta kiểm tra xem liệu nó còn visit được phần tử nào nữa không, nếu không thì nó là đáy của cây (tức là gặp đc nhà hàng) thì ta ans++;
#### Độ phức tạp
**Input** $O(n)$

**Worst case** $O(n) + O(n-1)$ do duyệt dfs là cây
:::

### [1418C - Mortal Kombat Tower | Elo 1500](https://codeforces.com/problemset/problem/1418/C)
:::spoiler
#### AC

#### Code

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int MAX=2*1e5+5;
vector<int> a(MAX);
int n;
int dp[MAX][2];
 
int solve(int i,int person)
{
    if(i>=n)
    {
        return 0;
    }
    if(dp[i][person]!=-1) return dp[i][person];
    int tmp1=INT_MAX,tmp2=INT_MAX;
    if(person==1)
    {
        if(a[i]==1)
        {
            tmp1 = 1+solve(i+1,0);
            tmp2 = 1+solve(i+2,0);
            if(i+1<n&&a[i+1]==1) tmp2+=1;
        }
        else
        {
            tmp1 = solve(i+1,0);
            tmp2 = solve(i+2,0);
            if(i+1<n&&a[i+1]==1) tmp2+=1;
        }
        return dp[i][person] = min(tmp1,tmp2);
    }
    if(person==0)
    {
        tmp1 = solve(i+1,1);
        tmp2 = solve(i+2,1);
        return dp[i][person] = min(tmp1,tmp2);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        memset(dp,-1,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            cin >> a[i];
        }
        cout  << solve(0,1)<< "\n";
    }
    return 0;
}

#### Giải thích
Bài này thuộc dạng DP, ở đây ta dùng memoization.
Ta có 2 lựa chọn:
+ Nếu đến lượt 'mình' thì ta sẽ có hai choice là chọn đánh 1 con quái, hoặc chọn đánh 2 con quái. Ta sẽ lấy min của hai lựa chọn này.
+ Nếu đến lượt 'bạn mình' thì ta cũng sẽ có 2 choice, tuy nhiên ta phải tốn thêm điểm nếu gặp a[i]=1, tùy lối đi mình chọn tốn bấy nhiêu điểm. Ta sẽ lấy min của hai option này.

#### Độ phức tạp
**Input** $O(n*t)$

**Worst case** $O(2*n*t)$ vì có n x 2 trạng thái của dp và t test cases.
:::

### [189A - Cut Ribbon | Elo 1300](https://codeforces.com/problemset/problem/189/A)
:::spoiler
#### AC

#### Code

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
vector<int> dp(5000,-1);
int solve(int n,int a,int b,int c)
{
    if(n==0) return 0;
    if(n<0) return -INT_MAX;
    if(dp[n]!=-1) return dp[n];
    return dp[n] = 1+max(solve(n-a,a,b,c),max(solve(n-b,a,b,c),solve(n-c,a,b,c)));
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    int n,a,b,c;
    cin >> n >> a >> b >> c;
    cout << solve(n,a,b,c);
    return 0;
}

#### Giải thích
Bài này thuộc dạng DP, ở đây ta dùng memoization.

Với mỗi độ dài n, ta sẽ có 3 option: cắt A, cắt B, cắt C. Ta sẽ lấy 1 + max(solve(n-a),solve(n-b),solve(n-c)).

Tuy nhiên nếu khi cắt mà N còn lại giá trị âm, thì tức là ko thể có cách cắt như vậy, nên ta trả về giá trị cho cách cắt này thật thấp để ko chọn nó nữa.

#### Độ phức tạp
**Input** $O(n)$

**Worst case** $O(n)$
:::

### [1106D - Lunar New Year and a Wander | Elo 1500](https://codeforces.com/problemset/problem/1106/D)
:::spoiler
#### AC

#### Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n,m;
vector<int> ans;
vector<int> a[100009];
bool mark[100009];
void solve(int s)
{
    priority_queue<int,vector<int>,greater<int>> q;
    q.push(s);
    mark[s]=true;

    while(!q.empty())
    {
        int u = q.top();q.pop();
        ans.push_back(u);
        if(ans.size()==n) break;
        for(int i=0;i<a[u].size();i++)
        {
            int v = a[u][i];
            if(!mark[v])
            {
                mark[v]=true;
                q.push(v);
            }
        }
    }
    for(int i=0;i<ans.size();i++) cout << ans[i] << " ";
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cin >> n >> m;
    while(m--)
    {
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    solve(1);
    return 0;
}

#### Giải thích
Bài này ta sẽ sử dụng BFS + priority_queue, ở mỗi node, ta sẽ add node 'hàng xóm' chưa visited vào priority_queue của mình để vào lần thăm tiếp theo ta sẽ lấy được node có value thấp nhất.
Basically, tham lam là ta sẽ luôn chọn node thấp nhất ở mỗi lần thăm.
#### Độ phức tạp
**Input** $O(m)$

**Worst case** $O(n log n + m)$ n log n là do ta sẽ vistit N nodes, mỗi lần như vậy ta sử dụng priority_queue để push,pop. Còn m là do input.
:::

### [1037D - Valid BFS? | Elo 1700](https://codeforces.com/problemset/problem/1037/D)
:::spoiler
#### AC

#### Code

#include <iostream>
#include <vector>
#include <queue>
 
 
using namespace std;
typedef long long ll;
vector<int> a[200009];
bool mark[200009];
vector<int> tmp(200009);
int n;
 
bool solve(int s)
{
    queue<int> q;int pos=1;
    if(tmp[0]!=1) return false;
    q.push(s);
    mark[s]=true;
    while(!q.empty())
    {
        int u = q.front();int cnt=0;
        q.pop();
        vector<bool> b(n+1,false);
        for(auto i:a[u])
        {
            if(!mark[i]) b[i]=true;
            else cnt++;
        }
        for(int i=pos;i<pos+a[u].size()-cnt;i++)
        {
            b[tmp[i]]=false;
        }
        for(auto i:a[u])
        {
            if(b[i]) return false;
        }
        for(int i=pos;i<pos+a[u].size()-cnt;i++)
        {
            q.push(tmp[i]);
            mark[tmp[i]]=true;
        }
        pos+=(a[u].size()-cnt);
    }
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cin >> n;
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(int i=0;i<n;i++)
    {
        cin >> tmp[i];
    }
    if(solve(1)) cout << "Yes";
    else cout << "No";
 
    return 0;
}

#### Giải thích
Bruh giải thích cái này hơi bị khó.

Giải thích đề bài trước: đề bài cho dãy, hỏi liệu dãy ấy có 'mô phỏng' được một BFS không. Để giải bài này, ta sẽ chạy 'mô phỏng' bfs. Ta sẽ set value của mảng b thành false, sau đó chạy qua các neighbor chưa thăm của u và set value của chúng trong mảng b thành true; Sau đó ta sẽ duyệt một đoạn của dãy cần check mà đón lẽ ra sẽ 'mô phỏng' lại khi ta thăm các neighbor của u, set value trong b khi thăm đoạn ấy lại thành false, sau đó quay lại duyệt hàng xóm của u, nếu tất cả b[neighborOfu] có value false, tức là đoạn trong dãy ấy thực sự sẽ 'mô phỏng' được bfs của chúng ta, ngược lại thì coi như vứt. Sau đó ta add queue theo đoạn của dãy cần check. Sau đó lặp lại.

#### Độ phức tạp
**Input** $O(2*n -1)$ nhập n-1 cạnh của đồ thị là cây, nhập vào dãy cần check

**Worst case** $O(4*n)$ thăm tree nên đảm bảo độ phức tạp này, nhưng mà phải nhân cỡ 4 lần vì phần kiểm tra.
:::

### [474D - Flowers | Elo 1700](https://codeforces.com/problemset/problem/474/D)

#include <iostream>
using namespace std;
#define int long long
const int maxn=1e5+5,mod=1e9+7;
int a[maxn],sum[maxn];
signed main(){
    int t,k;
    cin>>t>>k;
    for(int i=0;i<k;++i) a[i]=1;
    for(int i=k;i<maxn;++i){
        a[i]=(a[i-1]+a[i-k])%mod;
    }
    sum[0]=a[0];
    for(int i=1;i<maxn;++i){
        sum[i]=(sum[i-1]+a[i])%mod;
    }
    while(t--){
        int a,b;
        cin>>a>>b;
        cout<<(sum[b]-sum[a-1]+mod)%mod<< '\n';
    }
    return 0;
}

#### Độ phức tạp
$O(n)$
### [507B - Amr and Pins | Elo 1400](https://codeforces.com/problemset/problem/507/B)

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    long long r,x,y,xx,yy;
    cin>>r>>x>>y>>xx>>yy;
    double d=sqrt((x-xx)*(x-xx)*1.0+(y-yy)*(y-yy)*1.0);
    if(d/(r*2)==(long long)d/(r*2)) cout<<(long long)d/(r*2);
    else cout<<(long long)d/(r*2)+1;
    return 0;
}

#### Độ phức tạp
$O(1)$

### [4C - Registration system | Elo 1300](https://codeforces.com/problemset/problem/4/C)

#include <iostream>
#include <map>
using namespace std;
int main() {
    int n;
    cin >> n;
    map<string, int> name;
    while (n--) {
        string s;
        cin >> s;
        if (name.find(s) == name.end()) {
            cout << "OK" << '\n';
            name[s] = 0;
        } else {
            int cnt = name[s] + 1;
            string name2 = s + to_string(cnt);
            cout << name2 << '\n';
            name[s]++;
            name[name2] = 0;
        }
    }
    return 0;
}

#### Độ phức tạp
$O(n \log_2{n})$

### [459 - Pashmak and Flowers | Elo 1300](https://codeforces.com/problemset/problem/459/B)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    map<int,int> mp;
    int a[n];
    for(int i=0;i<n;++i){
        cin>>a[i];
        mp[a[i]]++;
    }
    sort(a,a+n);
    if(a[n-1]-a[0]==0) cout<<a[n-1]-a[0]<<" "<<1LL*mp[a[0]]*(mp[a[0]]-1)/2;
    else cout<<a[n-1]-a[0]<< " "<<1LL*mp[a[0]]*mp[a[n-1]];
    return 0;
}

#### Độ phức tạp
$O(n \log_2{n})$

### [298C - Parity Game | Elo 1700](https://codeforces.com/problemset/problem/298/C)
:::spoiler
#### AC
#### Code

#include <iostream>
using namespace std;
string a, b;
int CountSetBit(string x)
{
    int count = 0;
    for (int i = 0; i < x.size(); i++)
    {
        if (x[i] == '1') count++;
    }
    return count;
}
int main()
{
    cin >> a >> b;
    int a1 = CountSetBit(a), b1 = CountSetBit(b);
    if (a1 >= b1) cout << "YES";
    else if (a1 % 2 != 0 && b1 - a1 == 1) cout << "YES";
    else if (a1 == 1 and b1 == 2) cout << "YES";
    else cout << "NO";
    return 0;
}

#### Giải thích
Ta để ý thấy số lượng các số "1" trong `a` và `b` có mối liên hệ, vì vậy chỉ cần kiểm tra số lượng số "1" trong `a` và `b` rồi đem đi so sánh.
#### Độ phức tạp
Coi $|x|$ là độ dài của chuỗi `x`
**Input** $O(1)$
**Đếm bit** $O(|a| + |b|)$
**Xử lí** $O(1)$
**Worst case** $O(|a| + |b| + 2)$
:::

### [550A - Two substrings | Elo 1500](https://codeforces.com/contest/550/problem/A)
:::spoiler
#### AC
### Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    string a;
    cin >> a;
    for(int i=0;i<a.size()-1;i++)
    {
        if(a[i]=='A'&&a[i+1]=='B')
        {
            for(int j=i+2;j<a.size()-1;j++)
            {
                if(a[j]=='B'&&a[j+1]=='A')
                {
                    cout << "YES";
                    return 0;
                }
            }
            goto mark;
        }
    }
    mark:
    for(int i=0;i<a.size()-1;i++)
    {
        if(a[i]=='B'&&a[i+1]=='A')
        {
            for(int j=i+2;j<a.size()-1;j++)
            {
                if(a[j]=='A'&&a[j+1]=='B')
                {
                    cout << "YES";
                    return 0;
                }
            }
            goto mark2;
        }
    }
    mark2:
    cout << "NO";
    return 0;
}

### Giải thích
Bài này chỉ là implement thôi. Tìm "AB" rồi duyệt tiếp tìm "BA", và ngược lại để xét hết 2 trường.
### Độ phức tạp
**Input** $O(n)$
**Output** $O(n)$
:::

### [466C - Number of ways | Elo 1700](https://codeforces.com/contest/466/problem/C)
:::spoiler
#### AC

### Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll upperz(vector<int>&b,int x)
{
    int l=0,r=b.size();
    while(l<r)
    {
        int mid = (l+r)/2;
        if(b[mid]<=x) l=mid+1;
        else r=mid;
    }
    return l;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    int n;ll ans=0;
    cin >> n;
    vector<ll> a(n+1);
    vector<ll> pre(n+1);
    vector<int> b;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        pre[i]+=pre[i-1]+a[i];
    }
    if(pre[n]%3!=0)
    {
        cout << 0;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(pre[i] == (pre[n]/3)*2 && i!=n) b.push_back(i);
    }
    for(int i=1;i<n;i++)
    {
        if(pre[i]!=pre[n]/3) continue;
        ll tmp = upperz(b,i);
        ans += (b.size()-tmp);
    }
    cout << ans;
    return 0;
}

}

### Giải thích

Ta tính prefix sum của mảng A, tạo mảng b lưu index của các pre[i] sao cho pre[i] chính là tổng hai đoạn đầu, rồi ta duyệt i, sao cho nếu pre[i]==n/3, tức tìm được khúc đầu, thì ta đi chặt nhị phân mảng b chứa index để tìm số lượng khúc 2 phù hợp.
### Độ phức tạp
**Input** $O(n)$
**Output** $O(n \log_2{n})$
:::