2 条题解

  • 0
    @ 2026-5-18 17:20:37

    我是用通过模拟来判断是否存在可行的方案并记录数量。

    我们首先用两个数组来记录 G\texttt{G}B\texttt{B} 的位置。

    接下来我们再用两个布尔数组 p1p1p2p2 来分别记录来,这一个位置的星星是属于第一张照片还是属于第二张照片,当然,如果这个位置为黑色,那么这个位置的两个布尔数组都是 truetrue

    然后我们再用两个变量 sum1sum1sum2sum2 来分别记录第一张星星的数量和第二张星星的数量(实际上应该只要用一个就行了)。

    我们可以十分肯定地确认,如果照片的某一个位置为 B\texttt{B},那么这个位置肯定就有第一张照片的星星和第二张照片的星星。所以如果一个位置为 B\texttt{B},那么我们可以从此位置向上移动 BB 个单位,再向左移动 AA 个单位,看一下移动后的位置:

    • 第一种情况,如果它已经在这个照片外,那么肯定没有合法方案。因为题目已经说了,第一个照片当中包含了所有的星星,而且第二张照片的星星必须得从第一张照片的星星转移过来。所以就可以判断,如果出现这样的情况,就不存在合法方案。

    • 第二种情况就是这个位置为 W\texttt{W},同理这样也没有合法方案。

    因此如果出现以上两种情况,就直接输出 1-1。否则,我们就将移动后的位置和当今位置的 p1p1 标记成 truetrue,将当今位置的 p2p2 也标记成 truetruesum1sum1sum2sum2 也随之改变。

    接下来我们再考虑 G\texttt{G} 的位置:

    • 第一种情况,如果这个位置我们之前已经标记过了就不用再判断了。

    • 第二种情况,继续判断从此位置向上移动 BB 个单位,再向左移动 AA 个单位后的位置。如果它在照片外面或者这个位置为 W\texttt{W},则当今位置为第一张照片的星星,而且从此位置向下移动 BB 个单位,再向右移动 AA 个单位的位置如果为 G\texttt{G},且这个位置的 p1p1falsefalse,则这个位置为第二张照片的星星。

    • 第三种情况,如果从此位置向上移动 BB 个单位,再向左移动 AA 个单位后的位置在照片内,且该位置的 p1p1truetrue,那这个位置就为第二张照片的星星。

    我们再进行相应的统计。

    最后输出 sum1sum1 就是答案了。

    代码部分:

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=1001;
    int T,n,A,B,sum1,sum2;char a[N][N];
    bool p1[N][N],p2[N][N];
    struct dian{
        int x,y;
    };
    vector<dian>b,g;
    void clean()
    {
        memset(p1,0,sizeof(p1));
        memset(p2,0,sizeof(p2));
        sum1=sum2=0;
    }
    bool solve()
    {
        for(dian i:b)
        {
            int x=i.x,y=i.y;
            if(x-B<1||y-A<1||a[x-B][y-A]=='W') return 0;
            sum1+=!p1[x-B][y-A];
            p1[x-B][y-A]=1;
            sum1+=!p1[x][y];
            p1[x][y]=1;
            p2[x][y]=1;
            sum2++;
        }
        for(dian i:g)
        {
            int x=i.x,y=i.y;
            if(p1[x][y]||p2[x][y]) continue;
            if(x-B<1||y-A<1||!p1[x-B][y-A])
            {
                p1[x][y]=1;
                sum1++;
                if(x+B<=n&&y+A<=n&&a[x+B][y+A]=='G'&&!p1[x+B][y+A])
                {
                    p2[x+B][y+A]=1;
                    sum2++;
                }
            }
            else if(x-B>=1&&y-A>=1&&p1[x-B][y-A]) p2[x][y]=1,sum2++;
        }
        return 1;
    }
    signed main()
    {
        scanf("%lld",&T);
        while(T--)
        {
            clean();
            scanf("%lld%lld%lld",&n,&A,&B);
            b.clear(),g.clear();
            for(int i=1;i<=n;i++)
            {
                scanf("%s",a[i]+1);
                for(int j=1;j<=n;j++)
                {
                    if(a[i][j]=='B') b.push_back((dian){i,j});
                    if(a[i][j]=='G') g.push_back((dian){i,j});
                }
            }
            if(solve()) printf("%lld\n",sum1);
              else printf("-1\n");
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 17:12:38
      #include <bits/stdc++.h>
      using namespace std;
      
      int solve() {
          int N, A, B;
          cin >> N >> A >> B;
          vector<string> rows(N);
          for (auto &row : rows) cin >> row;
          vector<vector<bool>> has_star(N, vector<bool>(N));
          for (int r = 0; r < N; ++r)
              for (int c = 0; c < N; ++c)
                  if (rows[r][c] == 'B') {
                      if (r - B < 0 || c - A < 0) return -1;
                      has_star[r][c] = has_star[r - B][c - A] = 1;
                  }
          for (int r = 0; r < N; ++r)
              for (int c = 0; c < N; ++c) {
                  if (rows[r][c] == 'W') {
                      if (has_star[r][c]) return -1;
                  } else if (rows[r][c] == 'G') {
                      if (has_star[r][c]) continue;
                      if (r >= B && c >= A && has_star[r - B][c - A]) continue;
                      has_star[r][c] = true;
                  }
              }
          int ans = 0;
          for (const auto &row : has_star) ans += accumulate(begin(row), end(row), 0);
          return ans;
      }
      
      int main() {
          ios::sync_with_stdio(False);
          cin.tie(nullptr);
          int T;
          cin >> T;
          while (T--) cout << solve() << "\n";
      }
      
      • 1

      *【模拟】图形重叠分析[USACO25JAN] Astral Superposition B

      信息

      ID
      6915
      时间
      4000ms
      内存
      256MiB
      难度
      8
      标签
      递交数
      67
      已通过
      10
      上传者