# Thầy Đông
## 24/11/2022

### [Đề bài](https://drive.google.com/file/d/17cN8LZMfOBptF1hzwO9XTxVG6xKlJg-k/view?usp=share_link)

### Palfriendship - pfs

#### Editorial
* Với mỗi bạn $1$, ta sẽ xét các bạn $j$, bắt đầu từ bạn có số thứ tự lớn nhất, là bạn của $i$ và kiểm tra xem đoạn $[i, j]$ có phải là đoạn đối xứng bạn bè không. Mỗi khi xét xong một cặp bạn sẽ xóa cặp đó ra khỏi danh sách.

#### Code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;
int n, m;
vector<int> pos[maxn];

void solve()
{
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        if (u > v) swap(u, v);
        pos[u].push_back(v);
    }

    for (int i = 1; i <= n; i++) sort(pos[i].begin(), pos[i].end(), greater<int>());

    int res = 1;
    for (int i = 1; i <= n; i++) {
        while (pos[i].size() && pos[i].back() <= i + 2) {
            int cur = (pos[i].back() == i + 2);
            for (int l = i, r = pos[i].back(); 1 <= l && r <= n; l--, r++) {
                while (pos[l].size() && pos[l].back() < r) pos[l].pop_back();
                if (pos[l].size() && pos[l].back() == r) {
                    cur += 2;
                    pos[l].pop_back();
                }
                else break;
            }
            res = max(res, cur);
        }
    }

    cout << res;
}

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

    solve();
}

___

### Trò chơi ghép từ - wg

### Editorial
* Bài này là một bài khá cơ bản ứng dụng dp, ta sẽ dp là đã viết được đến kí tự thứ $i$ của xâu $s$ và kết thúc là kí tự $c$ thì độ dài xâu bé nhất có thể là bao nhiêu.
* Ta có thể sử dụng priority_queue để mỗi trạng thái chỉ phải tính $1$ lần.

### Code

#include <bits/stdc++.h>

using namespace std;

template<typename T>
inline bool maxi(T &x, const T &val)
{
    if (x < val) return x = val, true;
    return false;
}

template<typename T>
inline bool mini(T &x, const T &val)
{
    if (x > val) return x = val, true;
    return false;
}

const int maxn = 1010, maxs = 255, maxc = 26, oo = 1e9;
int n;
string s;
string t[maxn];
int dp[maxs][maxc];
vector<int> pos[maxc];

int go(int pos, string &t)
{
    for (char c : t) {
        if (c == s[pos]) pos++;
    }
    return pos;
}

priority_queue<pair<int,pair<int,int> >, 
        vector<pair<int,pair<int,int> > >,
       greater<pair<int,pair<int,int> > > > pq;

void solve()
{
    cin >> s;
    int siz = s.size();
    s.push_back('#');
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
        pos[t[i][0] - 'a'].push_back(i);

    }

    memset(dp, 60, sizeof dp);
    for (int i = 0; i < maxc; i++) {
        pq.push({0, {0, i}});
        dp[0][i] = 0;
    }
    while (!pq.empty()) {
        auto x = pq.top();
        pq.pop();
        int w = x.first;
        int i = x.second.first;
        int j = x.second.second;

        if (dp[i][j] != w) continue;

        for (int id : pos[j]) {
            int nex = go(i - (i != 0 && t[id][0] == s[i - 1]), t[id]);
            if (mini(dp[nex][t[id].back() - 'a'], w + (int)t[id].size() - 1)) {
                pq.push({w + (int)t[id].size() - 1, {nex, t[id].back() - 'a'}});
            }
        }
    }
    
    int res = oo;
    for (int i = 0; i < maxc; i++) mini(res, dp[siz][i]);

    if (res == oo) cout << "-1\n";
    else cout << res + 1 << '\n';
}

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

    solve();
}

___

## Trò chơi trên bảng chữ - wgogame

### Editorial
* Sub $1$: Duyệt trâu
* Sub $2$: