CF970

A

思路

先将b的进行自我抵消，然后计算a能否消除b，再看a能否自我抵消。

代码

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void solve()
{
    int a,b;    cin>>a>>b;
    b%=2;
    a-=b*2;
    if(a<0) cout<<"NO\n";
    else if(a==0 || a>0 && a%2==0)   cout<<"Yes\n";
    else    cout<<"No\n";
}    
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

B

思路

直接按照题意进行模拟即可。

代码

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void solve()
{
    int n;  cin>>n;
    string s;   cin>>s;
    bool ok=false;
    int siz=0;
    for (int i = 1; i*i <= n; ++i)
    {
        if(i*i==n)  ok=true,siz=i;
    }
    if(ok==false)
    {
        cout<<"No\n";
    }
    else
    {
        s='#'+s;
        if(siz==1 || siz==2)
        {
            for (int i = 1; i <= n; ++i)
            {
                if(s[i]=='0')
                {
                    cout<<"No\n";
                    return;
                }
            }
            cout<<"YES\n";
            return;
        }
        bool ok=false;
        for (int i = 1; i <= n ; ++i)
        {
            if(s[i]=='0')
            {
                ok=true;
                if(i<siz+1 || i>n-siz)
                {
                    cout<<"NO\n";
                    return;
                }
                else
                {
                    if((i%siz)>0 && (i%siz)<siz)
                    {
                        continue;
                    }
                    else 
                    {
                        cout<<"NO\n";
                        return;
                    }
                }
            }
        }
        if(ok)  cout<<"yes\n";
        else    cout<<"NO\n";
    }
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

C

思路

不难想到从l进行构造，依次增加1，2，3等等。

代码

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void solve()
{
    int l,r;    cin>>l>>r;
    if(l==r)
    {
        cout<<"1\n";
        return;
    }
    int d=r-l;
    int cur=0;
    for (int i = 0; i*(i+1) <= 2*d; ++i)
    {
        cur=i;    
    }
    cout<<cur+1<<"\n";
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

D

思路

可以使用并查集进行维护，维护可以跳到的所有点。当一个点的颜色为黑色时，那么他的祖先也是可以到达该点的。我们直接计算即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct DSU {
    vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (f[x] != x) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};
void solve()
{
    int n;  cin>>n;
    DSU dsu(n);
    for (int i = 0; i < n; ++i)
    {
        int x;  cin>>x;
        dsu.merge(i,x-1);
    }
    string s;   cin>>s;
    std::vector<int> ans(n,0);
    for (int i = 0; i < n; ++i)
    {
        if(s[i]=='0')
        {
            int fa=dsu.find(i);
            ans[fa]++;
        }
    }
    for (int i = 0; i < n; ++i)
    {
        int fa=dsu.find(i);
        cout<<ans[fa]<<" \n"[i==n-1];
    }
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

E

原来打了一个暴力，但是TLE了。

思路

偶数的情况比较好处理。奇数的情况比较麻烦，直接暴力会TLE。

可以遍历不选第i个字符的情况，这里可以使用前缀和进行优化。

我们可以先计算前i个字符中，26个字符出现的情况。

然后在不选第i个字符时，直接计算偏移一位的前缀和即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n;  cin>>n;
    string s;   cin>>s;
    if(n==1)
    {
        cout<<1<<"\n";
        return;
    }
    else if(n==2)
    {
        cout<<0<<"\n";
        return;
    }
    int ans=1e9;
    if(n&1)
    {
        s='#'+s;
        std::vector<std::vector<int>> odd(n+1,std::vector<int>(26));
        std::vector<std::vector<int>> even(n+1,std::vector<int>(26));
        for (int i = 1; i <= n; ++i)
        {
            odd[i]=odd[i-1];
            even[i]=even[i-1];
            if(i%2==0) even[i][s[i]-'a']++;
            else    odd[i][s[i]-'a']++;
        }
        int omax=0,emax=0;
        int ocnt=0,ecnt=0;
        for (int i = 1; i <= n; ++i)
        {
            omax=0,emax=0;
            for (int j = 0; j < 26; ++j)
            {
                ocnt=odd[i-1][j]+even[n][j]-even[i][j];
                ecnt=even[i-1][j]+odd[n][j]-odd[i][j];
                omax=max(ocnt,omax);
                emax=max(ecnt,emax);
            }
            ans=min(ans,n-omax-emax);
        }
        cout<<ans<<"\n";
    }
    else
    {
        std::map<int, int> even;
        std::map<int, int> odd;
        for (int i = 0; i < n; ++i) 
        {
            if(i&1)
            {
                even[s[i]]++;
            }     
            else
            {
                odd[s[i]]++;
            }
        }
        int omax=0,emax=0;
        for (auto [x,y]: even)
        {
            emax=max(emax,y);   
        }
        for (auto [x,y]: odd)
        {
            omax=max(omax,y);
        }
        ans=n-omax-emax;
        cout<<ans<<"\n";   
    }
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

F

WA了十发。。。

思路

就是直接求期望，直接找个模板计算逆元即可。使用前缀和优化一下。

该死的取模运算。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
ll qpow(ll a, ll n, ll p)// 快速幂
{
    ll ans = 1;
    while (n)
    {
        if (n & 1)
            ans = ans % p * a % p;
        a = a % p * a % p;
        n >>= 1;
    }
    ans%=mod;
    return ans;
}
ll inv(ll a, ll p)
{
    return qpow(a, p - 2, p);
}
void solve()
{
    int n;  cin>>n;
    std::vector<ll> a(n,0);
    std::vector<ll> sum(n,0);
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
    }
    sum[0]=a[0];
    for (int i = 1; i < n; ++i)
    {
        sum[i]=sum[i-1]+a[i];
    }
    ll ans=0;
    for (int i = 0; i < n; ++i)
    {
        ans=(ans%mod+((a[i]%mod)*((sum[n-1]-sum[i])%mod)%mod)%mod)%mod;
    }
    ll cnt=(((((n-1)%mod)*(n%mod))%mod)%mod)*(inv(2,mod)%mod)%mod;
    cout<<((ans%mod)*(inv(cnt,mod)%mod))%mod<<"\n";
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

G

思路

这其实是一个结论题：

给你一个数列，你可以对其中的元素进行互相加减，（\(a_i=a_i+a_j\)或者\(a_i=a_i-a_j(a_i>a_j)\)）。那么他们每一项都可以变换成\(gcd(a_1,a_2,······a_n)\)的若干倍。

那么这样就容易解决了，我们可以发现构造成\(0,x,2x,3x\)等等这样是最好的。那么接下来就依次填充空白的部分即可。这里讨论比较麻烦：

• 如果n=1，那么直接判断是否比k大。
• 如果gcd=1，那么答案就是n-k+1。
• 否则进行讨论：
  1. 如果k需要填充的空白块大于n-1，那么就是n-k+1。
  2. 如果恰好是n-1，那么答案就是(n-1)*g-1，注意是倒数第二个元素，所以要减去1。
  3. 否则直接计算最大可以填充的空白块，然后进行类似的计算。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    ll n;  cin>>n;
    ll k;   cin>>k;
    std::vector<ll> v(n,0);
    ll g=0;
    for (int i = 0; i < n; ++i)
    {
        cin>>v[i];
        g=gcd(g,v[i]);
    }
    if(n==1)
    {
        cout<<k-(k<=v[0])<<"\n";
        return;
    }
    if(g==1)
    {
        cout<<n-1+k<<"\n";
    }
    else
    {
        ll t=0;
        if(k/(g-1)>=(n-1))
        {
            t=k%(g-1);
            if(k/(g-1)==(n-1) && t==0)
            {
                cout<<(n-1)*g-1<<"\n";
            }
            else
            {
                cout<<n-1+k<<"\n";
            }
        }
        else
        {
            t=k%(g-1);
            if(t==0)    cout<<k/(g-1)*g-1<<"\n";
            else    cout<<k/(g-1)*g+t<<"\n";
        }
    }
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

H

思路

中位数的话，不难想到二分。

如何找到\(a_i\)为\(x\)的时候，中位数\(mid\)是什么？所有数都是\(mod\ x < mid\)。

事实上，我们可以尝试为所有的\(k\)找到范围\([k⋅x,k⋅x+m]\)中的元素的数量，因为如果我们对\(x\)取模，所有这些元素将小于\(m\)。我们计算这些的所有个数：\(pref[i+mid]-pref[i]\)。判断是否大于\(\frac{n}{2}\)，并由此调整\(l\)和\(r\)。

代码

Code 1

#include<bits/stdc++.h>
using namespace std;
using ll=long long;  
const string narek="narek";
void solve()
{
    int n,q;    cin>>n>>q;
    std::vector<int> pref(n+2,0);
    for (int i = 0; i < n; ++i)
    {
        int x;  cin>>x;
        pref[x+1]++;
    }
    for (int i = 0; i <= n; ++i)
    {
        pref[i+1]+=pref[i];
    }
    std::vector<int> ans(n+1,0);
    auto check=[&](int x,int mid)
    {
        int cnt=0;
        for (int i = 0; i <= n+1; i+=x)
        {
            cnt+=pref[min(i+mid,n+1)]-pref[i];
        }
        if(cnt<=n/2)
        {
            return true;
        }
        else    return false;
    };
    for (int i = 1; i <= n; ++i)
    {
        int l=0,r=i-1;  //二分中位数的值
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(check(i,mid))
            {
                l=mid;
            }
            else
            {
                r=mid-1;
            }
        }
        ans[i]=l;
    }
    for (int i = 0; i < q; ++i)
    {
        int x;  cin>>x;
        cout<<ans[x]<<" \n"[i==q-1];
    }
}
int main()
{
    int t;  cin>>t;
    for (int i = 1; i <= t ; ++i)
    {
        //cout<<"case "<<i<<": "<<"\n";
        solve();
    }
    return 0;
}

Code 2

官方题解

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        int n,m;
        cin>>n>>m;
        vector<int>a(n);
        vector<int>c(n+1,0ll);
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            c[a[i]]++;
        }
        for(int i=1;i<=n;i++)
        {
            c[i]+=c[i-1];
        }
        int res[n+1]={0};
        for(int x=1;x<=n;x++)
        {
            int l=0,r=x;
            while(l<r)
            {
                int mid=(l+r)/2;
                int cnt=c[mid];
                for(int k=1;k*x<=n;k++)
                {
                    cnt+=c[min(k*x+mid,n)]-c[k*x-1];
                }
                if(cnt-1>=n/2)
                {
                    r=mid;
                }
                else
                {
                    l=mid+1;
                }
            }
            res[x]=l;
        }
        while(m--)
        {
            int x;
            cin>>x;
            cout<<res[x]<<" ";
        }
        cout<<endl;
    }
}