CF972

A

思路

假设所有元音字符的数量\(a_0+a_1+a_2+a_3+a_4=n\)，那么总的回文串数量就是\(A=2^{a_0}+2^{a_1}+2^{a_2}+2^{a_4}+2^{a_4}-5\)（减5是考虑一个字符的情况）。

问题就是要\(A\)最小：可以发现：应该尽可能均分：因为如果堆在一个\(a_i\)上，指数增长的速度是非常快的。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;  
void solve()
{
    int n;  cin>>n;
    string s="aeiou";
    int x=n/5,y=n%5;
    for (int i = 0; i < 5; ++i)
    {
        for (int j = 0; j < x; ++j)
        {
            cout<<s[i];
        }
        if(i<y)
        {
            cout<<s[i];
        }
    }
    cout<<"\n";
}
int main()
{
    int t;  cin>>t;
    for (int i = 1; i <= t ; ++i)
    {
        //cout<<"case "<<i<<": "<<"\n";
        solve();
    }
    return 0;
}

B1

直接看B2

B2

思路

很容易就想到二分。

但是需要考虑一些特殊情况：

• 首先就是这个数是找不到的，我们只能找到临近的数。理想的情况是在左右两边夹中间。取均值即可。
• 另外的情况就是在左边或者右边，这个需要先特判一下，否则会WA。（比方说有一个最大的，比老师所在的位置还大，那么我们一直二分，肯定是找不到临近的）。最后的结果就是最近的老师的位置和最左端/最右端之差。

代码

Code 1

大佬用的STL，比较优雅。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;  
void solve()
{
    ll n;   cin>>n;
    int m,q;    cin>>m>>q;
    std::vector<ll> b(m,0);
    for (int i = 0; i < m; ++i)
    {
        cin>>b[i];
    }
    sort(begin(b),end(b));
    for (int i = 0; i < q; ++i)
    {
        int a;  cin>>a;
        if(a>b[m-1])
        {
            cout<<n-b[m-1]<<"\n";
            continue;
        }
        else if(a<b[0])
        {
            cout<<b[0]-1<<"\n";
            continue;
        }
        else
        {
            int pos=lower_bound(begin(b),end(b),a)-begin(b); 	//直接找第一个大于的位置  
            int l=b[pos-1],r=b[pos];
            cout<<(r-l)/2<<"\n";
        }
    }
}
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;
using ll=long long;  
void solve()
{
    ll n;   cin>>n;
    int m,q;    cin>>m>>q;
    std::vector<ll> b(m,0);
    for (int i = 0; i < m; ++i)
    {
        cin>>b[i];
    }
    sort(begin(b),end(b));
    for (int i = 0; i < q; ++i)
    {
        int a;  cin>>a;
        if(a>b[m-1])
        {
            cout<<n-b[m-1]<<"\n";
            continue;
        }
        else if(a<b[0])
        {
            cout<<b[0]-1<<"\n";
            continue;
        }
        else
        {
            int l=0,r=m-1;
            while(l+1<r)
            {
                int mid=(l+r)>>1;
                if(b[mid]<=a)
                {
                    l=mid; 
                }
                else
                {
                    r=mid-1;
                }
            }
            int pos=l;
            if(b[pos]<a)
            {
                if(pos+1<m)
                {
                    //cerr<<"case 1: ";
                    cout<<(b[pos+1]-b[pos])/2<<"\n";
                }
                else
                {
                    //cerr<<"case 2: ";
                    cout<<n-b[pos]<<"\n";
                }   
            }
            else
            {
                if(pos>0)
                {  
                    //cerr<<"case 3: ";
                    cout<<(b[pos]-b[pos-1])/2<<"\n";
                }
                else
                {
                    //cerr<<"case 4: ";
                    cout<<b[pos]-1<<"\n";
                }
            }
        }

    }
}
int main()
{
    int t;  cin>>t;
    for (int i = 1; i <= t ; ++i)
    {
        //cout<<"case "<<i<<": "<<"\n";
        solve();
    }
    return 0;
}

C

补题。

不难想到是dp。但是不会。

思路

一开始想的是第几个字符串不选，第几个选。思考一下可以发现：这与前面是哪一个字符是相关的。也就是说状态是与Narek中的哪一个字符相关。

那我们不难想到这样设计dp状态：\(dp_i\)表示我们当前正在寻找第i个字符的最大答案。（就是\(score_n-score_c\)，i的范围是0~4，对应Narek）。

那么对应当前的字符串：我们对五个字母进行处理，计算分别从这五个字母开始，可以获得的最大价值。

假设当前字符是\(j_{th}\)，如果\(dp_j\)不为\(-inf\)，那么可以进行状态转移，我们检索这个字符串：查看\(j+1_{th}\)字符，一直下去，直到\(dp_k\)，

如果从\(dp_j\)到达\(dp_k\)大于之前的值\(dp_k\) ，我们将\(dp_k\)更新为\(dp_j+counted_{score}\) 。

需要注意的是，在这个过程中，如果使用一个数组，会修改原来状态的值，所以我们需要使用两个数组：ndp和dp，状态转移时是使用ndp，转移后再将dp=ndp赋值回去。

此外，最后的答案不是简单的\(max(dp_i)\)，因为我们还需要减去最后不能拼接成完整单词的片段，（注意是减去\(2*i\)）。所以答案是\(max(dp_i-2*i)\)。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;  
const string narek="narek";
void solve()
{
    int n,m;    cin>>n>>m;
    std::vector<string> s(n);
    for (int i = 0; i < n; ++i)
    {
        cin>>s[i];
    }
    std::vector<int> dp(5,-1e9),ndp;
    dp[0]=0;
    for (int i = 0; i < n; ++i)
    {
        ndp=dp;
        int cal=0;
        for (auto ch: s[i])
        {
            if(ch=='a' || ch=='r' || ch=='n' || ch=='e' || ch== 'k')    cal++;
        }
        for (int j = 0; j < 5; ++j)
        {
            if(dp[j]==-1e9)  continue;
            int value=0,next=j;
            for (int k = 0; k < m; ++k)
            {
                if(s[i][k]==narek[next])
                {
                    next=(next+1)%5;
                    value++;	//score_n的值
                }
            }
            //cal是全部的arnek字符的个数,cal-value就是score_c的值
            ndp[next]=max(ndp[next],dp[j]+value-(cal-value));
        }
        dp=ndp;
    }
    int ans=0;
    for (int i = 0; i < 5; ++i)
    {
        ans=max(ans,dp[i]-2*i);
    }
    cout<<ans<<"\n";
}
int main()
{
    int t;  cin>>t;
    for (int i = 1; i <= t ; ++i)
    {
        //cout<<"case "<<i<<": "<<"\n";
        solve();
    }
    return 0;
}