3 条题解

  • 4
    @ 2025-10-27 14:56:50
    using namespace std;
    
    int w[3000]={0};//每行W有几个
    int b[3000]={0};
    int r[3000]={0};
    char a[60][60]={0};
    
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
                if(a[i][j]=='W'){
                    w[i]++;
                }else if(a[i][j]=='B'){
                    b[i]++;
                }else{
                    r[i]++;
                }
            }
        }
        int min=3000;
        for(int i=1;i<=n-2;i++){
            for(int j=1;j<=n-1-i;j++){//枚举W、B、R区间并计算
                int sum=0;
                for(int k1=1;k1<=i;k1++){
                    sum+=m-w[k1];
                }
                for(int k2=i+1;k2<=n-j;k2++){
                    sum+=m-b[k2];
                }
                for(int k3=n-j+1;k3<=n;k3++){
                    sum+=m-r[k3];
                }
                if(min>sum) min=sum;
            }
        }
        cout<<min<<endl;
        return 0;
    }
    
    
    • 2
      @ 2025-10-27 13:18:23
      #include<iostream>
      #include<algorithm>
      using namespace std;
      int main()
      {
          int n,m;
          cin>>n>>m;
          char a[n+1][m+1];
      //打印数组
          int w[n+1]={0};
          int r[n+1]={0};
          int b[n+1]={0};
          for(int i=1;i<=n;i++)
          { 
      //记录每行3种颜料数
              int cntr=0,cntb=0,cntw=0;
              for(int j=1;j<=m;j++)
              {
                  cin>>a[i][j];
                  if(a[i][j]=='W')
                  cntw++;
                  else if(a[i][j]=='B')
                  cntb++;
                  else
                  cntr++;
              }
      //前缀和算出前i行3种涂改所需涂料
              w[i]=w[i-1]+(m-cntw);
              r[i]=r[i-1]+(m-cntr);
              b[i]=b[i-1]+(m-cntb);
          }
          int mn=100000;
          int sum=0;
      //暴力枚举找出最优
          for(int i=1;i<n-1;i++)
          {
              for(int j=i+1;j<n;j++)
              {
                  sum=w[i]+b[j]-b[i]+r[n]-r[j];
                  mn=min(mn,sum);
              }
          }
          cout<<mn;
          return 0;
      }``
      
      • 1
        @ 2025-10-28 10:58:37

        • @ 2025-10-28 10:59:32

          解题思路: 要使旗帜成为合法图案(上白、中蓝、下红,每部分至少一行),需最小化涂色格子数。我们可以通过预处理每行涂成白、蓝、红的成本,再枚举白色和蓝色的分界行,计算三部分的总成本,取最小值。(数据范围很小,暴力就行。)

          1.预处理成本数组: w[i]:前i行全部涂成白色的总涂色数。 b[i]:前i行全部涂成蓝色的总涂色数。 r[i]:前i行全部涂成红色的总涂色数。

          2.枚举分界行: 枚举白色结束行i(1 ≤ i < n-1)和蓝色结束行j(i+1 ≤ j < n),则: 白色部分成本:w[i]

          蓝色部分成本:b[j] - b[i](i+1到j行涂成蓝色的成本)

          红色部分成本:r[n] - r[j](j+1到n行涂成红色的成本)

          总费用为三部分之和,取所有枚举情况的最小值。

      • 1

      茶杯头的三色挑战:恶魔的旗帜

      信息

      ID
      1161
      时间
      1000ms
      内存
      256MiB
      难度
      5
      标签
      递交数
      56
      已通过
      20
      上传者