1 条题解

  • 1
    @ 2025-5-25 15:44:31

    贪心大致分为两种: 对于情况1: #... ...# 都是放三个,但是

    #..# ...# (中间省略了)

    比 #... #..#(中间省略了)

    更优。

    对于情况二:

    #...# #.... 肯定是将第一排填满最优。

    #include <bits/stdc++.h>
    using namespace std;
    int main()
    {
      string s[2];
      cin>>s[0];
      cin>>s[1];
      int len = s[0].size();
      int ans = 0;
      int l = -1, r = -1;
      for(int i = 0;i<len;i++)
        if(s[0][i] == '#' || s[1][i] == '#')
        {
          l = i;
          break;
        }
      for(int i = l + 1;i<len;i++)
        if(s[0][i] == '#' || s[1][i] == '#')
        {
          r = i;
          break;
        }
    
      if(r == -1 || l == -1)
      {
        cout<<0;
        return 0;
      }
    
      for(int i = r + 1;i<=len;i++)
        if(i == len || s[0][i] == '#' || s[1][i] == '#')
        {
          if((s[0][r] == '#' && s[1][r] == '#') || (s[0][l] == '#' && s[1][l] == '#'))
            ans += r - l - 1;
          else if(s[0][r] == '#')
          {
            if(s[1][l] == '#')
            {
              ans += r - l;
              s[1][r] = '#';
            }
            else if(s[0][l] == '#')
              ans += r - l - 1;
          }
          else if(s[1][r] == '#')
          {
            if(s[0][l] == '#'){
              ans += r - l;
              s[0][r] = '#';
            }
            else if(s[1][l] == '#')
              ans += r - l - 1;
          }
          l = r;
          r = i;
        }
      
      cout<<ans;
      return 0;
    }
    

    信息

    ID
    343
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    463
    已通过
    53
    上传者