CF963

A

直接统计计算即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
void solve()
{
    int n;  cin>>n;
    string s;   cin>>s;
    int a,b,c,d;
    a=b=c=d=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='A')a++;
        else if(s[i]=='B')b++;
        else if(s[i]=='C')c++;
        else if(s[i]=='D')d++;
    }
    int ans=0;
    ans=min(a,n)+min(b,n)+min(c,n)+min(d,n);
    cout<<ans<<"\n";
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

B

不难发现，最后所有的数肯定都是奇数（如果是偶数，那么一定会留下一个数是奇数）。所以最基础的情况就是将所有的偶数变为奇数。

但是需要考虑，如果当前最大的奇数比当前要处理的偶数小，那么得进行额外的一次处理，可以在这个模拟的过程中动态更新最大的奇数。一开始写的很赘余，这是比赛后修改过的。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
void solve()
{
    int n;  cin>>n;
    std::vector<ll> v(n,0);
    bool ok=true;
    int odd=0,even=0;
    ll odd_maxn=0;
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
        if(v[i]&1)  odd++,odd_maxn=max(odd_maxn,v[i]);
        else    even++;
    }
    if(odd && even) ok=false;
    if(ok)
    {
        cout<<0<<"\n";
        return;
    }
    else
    {
        ll ans=even;
        sort(v.begin(),v.end());
        for(int i=0;i<n;i++)
        {
            if(v[i]&1)  continue;
            if(odd_maxn<v[i])
            {
                ans++;
                break;
            }
            odd_maxn=max(odd_maxn,odd_maxn+v[i]);
        }
        cout<<ans<<"\n"; 
    }
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

C

要求最早的所有灯都亮的时刻。不难想到要从最后一个开始亮的灯往后找。

可以发现循环的周期\(T=2k\)，所以我们可以将所有的灯进行整数个周期的时间移动，保证在最后亮的灯的时间附近（尽可能地靠近，可能需要特殊的处理），这样可以尽可能让所有灯在一个时间点附近亮。

我们再将所有的时间排个序，只要最大的和最小的时间差不超过\(k\)即可。输出最大的时刻。否则输出\(-1\)（因为是所有灯都集中亮最近的时刻了）。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
void solve()
{
    ll n,k;    cin>>n>>k;
    std::vector<ll> v(n,0);
    ll maxn=0;
    for(int i=0;i<n;i++)    cin>>v[i],  maxn=max(maxn,v[i]);
    ll t=2*k;
    for(int i=0;i<n;i++)
    {
        v[i]+=(maxn-v[i])/t*t;
        if(maxn-v[i]>=k)    v[i]+=t;	//特殊处理：如果时间差>k 再移动一个T
    }
    sort(v.begin(),v.end());
    bool ok=false;
    if(v[n-1]-v[0]+1<=k)  ok=true;
    if(ok)
    {
        cout<<v[n-1]<<"\n"; 
    }
    else    cout<<-1<<"\n";
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

D

分析数据范围，只能使用\(O(n)\)或者\(O(nlogn)\)的方法。考虑如何在一个数组中找到他的中位数\(x\)，我们采取二分的方法。二分查找这个中位数。可以发现，到时候大于或者等于中位数的个数应该是\(\frac{k+1}{2}\)。我们可以进行预处理：大于\(x\)的数，记录其贡献为\(1\)，其余为\(-1\)，我们只需要选择其中的最多\(k\)个数作为一个子数组，其中大于\(x\)的个数大于\(\frac{k+1}{2}\)即可。这个可以用\(dp\)进行处理。（对应的贡献和就是大于0）

我们使用\(dp_i\)表示：到第\(i+1\)个数时，可以获得的贡献，具体的状态转移看代码。

比较折磨的一点就是原来的二分又出错了，使用jiangly大佬的写法。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    ll n,k;    cin>>n>>k;
    std::vector<ll> v(n,0);
    for(auto &t: v) cin>>t;


    auto check=[&](ll x)->bool
    {
        std::vector<ll> f(n,0);
        std::vector<ll> dp(n,0);
        for(int i=0;i<n;i++)
        {
            if(v[i]>=x)    f[i]=1;
            else    f[i]=-1;
        }

        dp[0]=f[0];
        for(int i=1;i<n;i++)
        {
            if(i%k==0)  dp[i]=f[i];
            else dp[i]=dp[i-1]+f[i];
            if(i>=k)    dp[i]=max(dp[i],dp[i-k]);
        }
        return dp[n-1]>0;
    };

    ll l=0,r=1e9;
    while(l<r)
    {
        ll mid=(l+r+1)>>1;
        if(check(mid))  l=mid;
        else    r=mid-1;
    }
    cout<<l<<"\n";
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}