CF964

A

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const double PI=acos(-1);
void solve()
{
    int n;  cin>>n;
    cout<<n%10+n/10<<"\n";
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

B

当初一直WA，忘记考虑两个回合中，一胜一平的情况了。

只需要交换一下\(a\)和\(b\)，就能枚举出所有的情况了。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
const double PI=acos(-1);
ll a[MAXN],sum[MAXN];
void solve()
{
    int a,b,c,d;    cin>>a>>b>>c>>d;
    int cnt=0;
    if(a>c && b>=d || a>=c && b>d)  cnt+=2;
    swap(a,b);
    if(a>c && b>=d || a>=c && b>d)  cnt+=2;
    cout<<cnt<<"\n";  
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

C

只需要找每一个区间的起点和前一个区间的终点中间的这段时间即可，注意考虑起点和终点。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const double PI=acos(-1);
void solve()
{
    int n;
    ll s,m;
    cin>>n>>s>>m;
    vector<ll> l(n,0);
    vector<ll> r(n,0);
    for(int i=0;i<n;i++)   cin>>l[i]>>r[i];
    ll cnt=l[0];
    for(int i=1;i<n;i++)
    {
        cnt=max(cnt,l[i]-r[i-1]);
    }
    cnt=max(cnt,m-r[n-1]);
    if(cnt>=s)  cout<<"YES\n";
    else    cout<<"NO\n";
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

D

直接暴力构造，使用一个指针扫描\(t\)串，并对此进行构造\(s\)即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
const double PI=acos(-1);
ll a[MAXN],sum[MAXN];
void solve()
{
    string s,t; cin>>s>>t;
    int j=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='?')
        {
            if(j<t.size())  s[i]=t[j],j++;
            else    s[i]='a';
        }
        else if(j<t.size() && s[i]==t[j])
        {
            j++;
        }
    }
    if(j==t.size())
    {
        cout<<"Yes\n"<<s<<"\n";
    }
    else
    {
        cout<<"NO\n";
    }
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

E

思路一开始忘记了，现在想起来了。

我们不难发现先找最小的一个变为0，然后后面一直找0作为\(x\)进行运算即可。

这个题一看就知道适合离线处理，我们可以使用一个数组\(a[i]\)：表示将\(i\)操作为0需要的次数，最小方案数就是\(2a[l]+a[l+1]+······+a[r]\)，然后用前缀和进行优化即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
const double PI=acos(-1);
ll a[MAXN],sum[MAXN];
void solve()
{
    int l,r;    cin>>l>>r;
    cout<<sum[r]-sum[l-1]+a[l]<<"\n";
}
int main()
{
    for(int i=1;i<=MAXN;i++)
    {
        int tmp=i;
        while(tmp)
        {
            a[i]++;
            tmp/=3;
        }
        sum[i]=sum[i-1]+a[i];
    }
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

F

不妨设我们抽取\(x\)个1，\(k-x\)个0，如果对答案有贡献：那么需要\(\frac{k+1}{2}\leq x\)。

不难想到答案的贡献就是\(C_{cnt_1}^{i} \times C_{cnt_0}^{k-i}\)，我们只需要枚举\(i\)并累计计算即可。

求组合数得用一些数学知识（费马小定理）：快速幂+乘法逆元，需要预处理出阶乘，主题特判\(cnt_1<i\)和\(cnt_0<k-i\)的情况。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
const ll mod=1e9+7;
const double PI=acos(-1);
ll a[MAXN],cnt[2];
ll fact[MAXN];
ll qpow(ll a, ll n)
{
    ll ans = 1;
    while (n)
    {
        if (n & 1)
            ans = ans * a % mod ;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}
ll inv(ll a)
{
    return qpow(a, mod - 2);
}
ll C(ll m, ll n)
{
    return m < n ? 0 : fact[m] * inv(fact[n]) %  mod * inv(fact[m - n]) % mod;
}
void solve()
{
    ll k,n;    cin>>n>>k;
    cnt[0]=cnt[1]=0;
    for(ll i=1;i<=n;i++)   
    {
        cin>>a[i];
        if(a[i])    cnt[1]++;
        else    cnt[0]++;
    }
    ll ans=0;
    for(ll i=(k+1)/2;i<=k;i++)
    {
        if(cnt[1]<i)    continue;
        if(cnt[0]<k-i)  continue;
        ans+=C(cnt[1],i)*C(cnt[0],k-i)%mod;
    }
    cout<<ans%mod<<"\n";
}
int main()
{
    fact[0]=1;
    for(int i=1;i<MAXN;i++)
    {
        fact[i]=(fact[i-1]*i)%mod;
    }
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}