Edu167

A

B

暴力构造，使用双指针扫描\(a,b\)串，记录最多的相同的个数\(maxn\)，利用容斥原理减去即可，这里\(a\)串为辅，容易处理。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
void solve()
{
    string a,b; cin>>a>>b;
    int j=0;
    int cnt=0;
    int tmp=0;
    int maxn=0;
    for(int i=0;i<b.size();i++)
    {
        int tmp=i;
        while(j<a.size())
        {
            if(a[j]==b[tmp])
            {
                ++j;
                ++cnt;
                ++tmp;
            }
            else    ++j;
        }
        j=0;
        maxn=max(maxn,cnt);
        cnt=0;
    }
    cout<<a.size()+b.size()-maxn<<"\n";
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}
 

C

原来写了个很复杂的分类讨论，但是一直过不去。学习一下jiangly神的方法。

显然的，如果\(a_i>b_i\)，补\(score1\)，反之补\(score2\)，如果相等呢，我们需要考虑后面数字的影响，这样考虑非常麻烦。

不妨先搁置下来，存到\(tmp\)中，后续再进行分配。如果\(a_i=b_i\):

• 为1，那么暂时加入到\(tmp\)中
• 为-1，那么\(score1、score2\)都减一，\(tmp\)加一（后面两者之中选择一个再补即可）。

那么最后\(score1、score2\)都是最低的基础分数了，我们只需要再将\(tmp\)进行分配即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
void solve()
{
    int n;  cin>>n;
    std::vector<int> a(n,0);
    std::vector<int> b(n,0);
    for(auto &t: a) cin>>t;
    for(auto &t: b) cin>>t;
    int score1=0,score2=0;
    int tmp=0;      //用来补，对应同时为1或者-1的情况 
    for(int i=0;i<n;i++)
    {
        if(a[i]>b[i])   score1+=a[i];
        else if(a[i]<b[i])  score2+=b[i];
        else
        {
            if(a[i]==1) tmp++;
            else if(a[i]==-1)
            {
                score1-=1;
                score2-=1;
                tmp++;
            }
        }
    }
    cout<<min({score1+tmp,score2+tmp,(score1+score2+tmp)>>1})<<"\n";
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}