Codeforces Round 1019 (Div. 2)

2025-04-21

link: https://codeforces.com/contest/2103

打得很烂的一集，B题这种简单题咋花这么久。C也想好久。

A

for _ in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    st = set()
    for i in a:
        st.add(i)
    print(len(st))

B

就简单分类讨论下，该再细心点的，比如把情况先列出来。

for _ in range(int(input())):
    n = int(input())
    s = input()
    cost = n
    cur = 0
    cnt = 0
    cc = 0
    for i in range(n):
        if s[i]=='0':
            cc+=1
        if int(s[i])!=cur:
            cur^=1
            cost+=1
            if s[i]=='1':
                cnt+=1
    # print(cost)
    if s[0]=='0':
        # print(s,cnt,s[n-1])
        if cnt==1 and s[n-1]!='1':
            cost-=1
        elif cnt>1:
            cost-=2
    else:
        if cnt>=2 and cc:
            cost-=2
        elif cc:
            cost-=1
    print(cost)

C

根据中位数的性质，我们把小于等于 \(k\) 的数字的贡献设为 \(1\) ，大于 \(k\) 的数字的贡献设为 \(-1\) ，那么只有一段贡献值大于等于 \(0\) 的子数组，它的中位数才会小于等于 \(k\) 。所以拿 set 搞一下就行。

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    {
        int cnt = 0, L = 0, R = 0;
        for (int i = 1; i < n; i++)
        {
            if (a[i] <= k)
                cnt++;
            if (cnt * 2 >= i)
            {
                L = i;
                break;
            }
        }
        cnt = 0;
        for (int i = n; i > 1; i--)
        {
            if (a[i] <= k)
                cnt++;
            if (cnt * 2 >= n - i + 1)
            {
                R = i;
                break;
            }
        }
        cnt = 0;
        if (L && R && (L + 1 < R))
        {
            cout << "YEs\n";
            return;
        }
    }
    auto check = [&]()
    {
        vector<int> s(n + 1);
        for (int i = 1; i <= n; i++)
        {
            if (a[i] > k)
                s[i] = s[i - 1] - 1;
            else
                s[i] = s[i - 1] + 1;
        }
        multiset<int> st{s.begin() + 1, s.begin() + n};
        for (int i = 1; i + 1 < n; i++)
        {
            st.erase(st.find(s[i]));
            if (s[i] >= 0)
            {
                auto it = st.lower_bound(s[i]);
                if (it != st.end())
                    return true;
            }
        }
        return false;
    };
    bool ans = false;
    ans |= check();
    reverse(a.begin() + 1, a.end());
    ans |= check();
    cout << (ans ? "YES" : "NO") << '\n';
}