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;
}