周赛全部题解

A.游游画U

对于画图形问题我们一定要找到图形的具体的变化所在，比如这题我们能够发现是由不变化的上半部分和变化的下半部分组合而来的，我们考虑下半部分的特点,最开始外围是一个点一直到n个点的处理方式，所以按照这个要求来构造就好了

char dt[M][M];
char s[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=3*n;i++)
    {
      for(int j=1;j<=n;j++) cout<<'*';
      for(int j=1;j<=2*n;j++) cout<<'.';
      for(int j=1;j<=n;j++) cout<<'*';   
      cout<<endl;
    }//上半部分
    
    for(int i=1;i<=n;i++)
    {
        string s;
        for(int j=1;j<=i;j++) s+='.';
        for(int j=1;j<=n;j++) s+='*';
        for(int j=1;j<=n-i;j++) s+='.';
        cout<<s;
        reverse(s.begin(),s.end());
        cout<<s;
        cout<<endl;
    }// 下半部分
    return ;
}

b.游游的数组染色

对于这种题我们发现他是对于一个个相同的数的不同颜色进行处理,那么我们就可以固定一个数的然后用两种颜色来乘积计算就好了，我们不妨使用mp来处理,我们把两个颜色变为0,1这样便于我们来处理这个问题

map<PII,int> mp;
int a[N],b[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) 
    {
        char s; cin>>s;
        if(s=='B') mp[{1,a[i]}]++;
        else mp[{0,a[i]}]++;// 同一个数的不同属性确定了一个数
    }
    int res=0;
    for(auto &[P,cnt]:mp){
        auto [s,x]=P;
       res+=mp[{1-s,x}]*mp[{s,x}];// 这个时候取出来这个数的两个属性
    }
    res/=2;// 由于不考虑顺序
    cout<<res<<endl;
    return ;
}

C.游游的交换字符

不妨考虑这么一个问题不论怎么排列最后要么是1在第一位要么是0在第一位一,所以我们就这两种情况来取一个最优解，对于一开始固定1是第一个位置那么下一个1一定是第三个位置，当下一个一不是在目标位置的时候我们需要的是最靠前的目标位置-当前位置也就是需要和相邻的0交换这么多次,当然1的数量比0多那么1一定是从奇数位置开始的

void solve()
{
    string s; cin>>s;
    n=s.size();
    s=' '+s;
    int res1=0,res2=0,res;
    int cnt1=1,cnt2=2,cnt=0;
    // 表示1放在第一位和第二位的答案
    for(int i=1;i<=n;i++){
        if(s[i]=='1')
        {
            res1+=abs(cnt1-i);
            res2+=abs(cnt2-i);
            cnt1+=2,cnt2+=2;
            cnt++;
        }
    }
    if(cnt*2==n) res=min(res1,res2);
    else if(cnt*2>n) res=res1;
    else res=res2;
    cout<<res<<endl;
    return ;
}

D.游游的9的倍数

这是子序列问题也就是我当前这个点可以由我们前面的所有点转移而来，但是我们发现前面的点的状态只有9种，所以我们考虑状态机dp,定义当前位置为i的方案数由多少,那么我们当前的状态只能由前面的满足9种状态转移而来，所以就是一个dp即可,这种方法一般是在状态很少的情况下对于状态数做n^2的处理

int dp[15],d[15];
void solve()
{
    string s; cin>>s;
    n=s.size(); s=' '+s;
    
    dp[0]=1;
    for(int i=1;i<=n;i++){
        int x=s[i]-'0';
        x%=9;
        memcpy(d,dp,sizeof dp);// 上一次的不会被这一次的影响
        for(int j=0;j<=8;j++){
            int y=(j+x)%9;// 与其他的方案组合
            dp[y]=(dp[y]+d[j])%mod;
        }
    }
    cout<<dp[0]-1<<endl;
    return ;
}