## T1

赛前最后一节课才复习完字符串啊，复习的好啊，反正就是一个看自己想咋写就咋写的判断题呗，我觉得有一万种写法：

```cpp
bool side(char x)
{
    if(x == 'A' || x == 'B' || x == 'C')
        return 1;
    else return 0;
}
int wz(char x)
{
    if(x == 'A') return 1;
    if(x == 'B') return 2;
    if(x == 'C') return 3;
    if(x == 'D') return 4;
    if(x == 'F') return 5;
}
string c1, s1, c2, s2;
int ans1, ans2, ans3, ans4;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> c1 >> s1 >> c2 >> s2;
    ans1 = (c1 == c2);
    string row1 = s1.substr(0, 2);
    string row2 = s2.substr(0, 2);
    ans2 = (ans1 & (row1 == row2));
    char seat1 = s1.back();
    char seat2 = s2.back();
    int same1 = side(seat1);
    int same2 = side(seat2);
    ans3 = (ans2 & (same1 == same2));
    ans4 = (ans3 & (abs(wz(seat1) - wz(seat2)) == 1));
    cout << ans1 << ans2 << ans3 << ans4 << "\n";
    return 0;
}
```
## T2 

先给一个不用脑子的 $48$ 分的暴力吧：

```cpp
int a[200010], len, n;
char c[200010], s[200010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i] >> c[i];
        len += a[i];
    }
    if(len >= 200000)
    {
        cout << "0\n";
        return 0;
    }
    len = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= a[i]; j++)
            s[++len] = c[i];
    }
    int l = 1, r = len, ans = 0;
    while(l < r)
    {
        if(s[l] != s[r])
            ans++;
        l++; r--;
    }
    cout << ans << "\n";
    return 0;
}
```

$48$ 分都会了，满分还会远吗？把每个块看作一个整体，然后统计数量不就好了。而且样例也告诉你了需要 $long long$，毫无坑点。

```cpp
long long a[200010], n;
char c[200010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i] >> c[i];
    }
    long long l = 1, r = n, ans = 0;
    while(l < r)
    {
        ll sum = min(a[l], a[r]);
        if(c[l] != c[r])
        {
            ans += sum;
        }
        a[l] -= sum;
        a[r] -= sum;
        if(a[l] == 0) l++;
        if(a[r] == 0) r--;
    }
    cout << ans << "\n";
    return 0;
}

```

## T3 

感觉是讲过的原题吧，把数字转换成二进制数，优先考虑高位的数位能否为 $1$，然后尝试让这以为是 $1$，算一下目前情况下，有多少个数字满足，做完了。

关于判断满足，代码形如这样：

`(a[i] & tmp) == tmp` 这样就可以判断目前为是 $1$ 的都满足了。

所以做法就是枚举每一位，然后把所有数字遍历一遍，时间复杂度为 $O(30 * n)$。

```cpp
int n, m, a[200010], ans;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 29; i >= 0; i--)
    {
        int tmp = ans | (1 << i), num = 0;
        for(int j = 1; j <= n; j++)
        {
            if((a[j] & tmp) == tmp)
            {
                num++;
            }
        }
        if(num >= m)
            ans = tmp;
    }
    cout << ans << "\n";
    return 0;
}
```

## T4

直接用栈和 $map$ 模拟这一过程，拿到 $36$ ~ $48$ 分：

```cpp
int n, m, a[300010], ans[300010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        stack<int>st;
        map<int, int>mp;
        for(int j = i; j <= n; j++)
        {
            int k = a[j];
            if(mp.find(k) != mp.end())
            {
                if(st.empty() == 0)
                {
                    while(st.top() != k)
                    {
                        mp.erase(st.top());
                        st.pop();
                    }
                    st.pop();
                }
            }
            st.push(k);
            mp[k] = st.size();
        }
        while(st.empty() == 0)
        {
            ans[st.top()]++;
            st.pop();
        }
    }
    for(int i = 1; i <= m; i++)
        cout << ans[i] << " ";
    cout << "\n";
    return 0;
}
```

改成 哈希版本的 $map$ 分数应该会更高，拿满 $48$ 分。

```cpp
int n, m, a[300010], ans[300010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        stack<int>st;
        unordered_map<int, int>mp;
        for(int j = i; j <= n; j++)
        {
            int k = a[j];
            if(mp.find(k) != mp.end())
            {
                if(st.empty() == 0)
                {
                    while(st.top() != k)
                    {
                        mp.erase(st.top());
                        st.pop();
                    }
                    st.pop();
                }
            }
            st.push(k);
            mp[k] = st.size();
        }
        while(st.empty() == 0)
        {
            ans[st.top()]++;
            st.pop();
        }
    }
    for(int i = 1; i <= m; i++)
        cout << ans[i] << " ";
    cout << "\n";
    return 0;
}
```

我们要分析一些显然的结论：

1.最后一张牌谁也不能把他收走。

2.本局的第一张牌 $a[i]$，永远在最前面。

当你打完你的最后一张 $a[i]$，是不是等于从这个位置的下一个位置，开始了新的一局牌局？

然后考虑按照这个思路，可以写出来一个 $76$ 分的 $dfs$ ：
```cpp
int a[maxn], lst[maxn], nxt[maxn], cnt[maxn];
int ans[maxn], vis[maxn], n, m;
void dfs(int u, int add)
{
    if(u == 0 || vis[u] == 1)
        return;
    vis[u] = 1;
    ans[u] += add;
    dfs(nxt[u], add);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        lst[a[i]] = i;
        cnt[a[i]]++;
    }
    for(int x = 1; x <= m; x++)
    {
        if(lst[x] == n) nxt[x] = 0;
        else nxt[x] = a[lst[x] + 1];
    }
    for(int x = 1; x <= m; x++)
    {
        fill(vis, vis + m + 1, 0);
        dfs(x, cnt[x]);
    }
    for(int i = 1; i <= m; i++)
        cout << ans[i] << " ";
    return 0;
}
```

上述代码的主要思路是：

对于每个点数 $x$，有 $cnt[x]$ 局从它开始。

沿着链 $x -> nxt[x] -> nxt[nxt[x]]...$ 一直走，把 $cnt[x]$ 加到链上每个点数的答案中。

慢在哪里？这个代码是 $O(m^2)$ 的复杂度。

把 $dfs$ 换成直接传递答案呗，这样不就满分了：

```cpp
int a[maxn], lst[maxn], nxt[maxn], cnt[maxn];
int ans[maxn], vis[maxn], n, m, tim;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        lst[a[i]] = i;
        cnt[a[i]]++;
    }
    for(int x = 1; x <= m; x++)
    {
        if(lst[x] == n) nxt[x] = 0;
        else nxt[x] = a[lst[x] + 1];
        ans[x] = cnt[x];
    }
    for(int i = 1; i <= n; i++)
    {
        int x = a[i];
        // i 是 x 的最后出现位置，说明现在轮到处理 x
        if(lst[x] == i)
        {
            if(nxt[x] != 0)
            {
                ans[nxt[x]] += ans[x];
            }
        }
    }
    for(int i = 1; i <= m; i++)
        cout << ans[i] << " ";
    return 0;
}
```