CF1549B题解

FiraCode · 2021-11-29 17:38:34 · 题解

题意：

• 上面是黑棋。
• 下边是白棋。
• 如果对面是空的即可直接走过来 。
• 如果对边相邻的棋子有并且没被吃掉，就可以吃掉它。
• 求最多我方能到达最上方的人数。

  贪心：

• 如果自己有棋子，对边没有棋子，ans++。
• 如果自己有棋子，对面旁边有棋子，并之前没有被标记过，ans++并标记。

  代码：

  #include <bits/stdc++.h>//万能头文件 
  using namespace std;
  #define ll int//…… 
  inline ll read() {//快读模板 
  register ll num = 0 , neg = 1;
  register char ch = getchar();
  while (ch < '0' && ch > '9'){
      if (ch == '-')neg = -1;
      ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
      num = (num << 1) + (num << 3) + (ch ^ 48);
      ch = getchar();
  }
  return num * neg;
  }
  inline void print(int num) {//快输模板 
  if (num < 0)putchar('-') , num = -num;
  if (num > 9)print(num / 10);
  putchar(num % 10 + '0');
  }
  const int maxn = 2e5 + 10; 
  int falg[maxn]; 
  int main() {
  int t = read();
  while (t--) {
      int n = 0;
      cin >> n;//输入n，n*n的棋盘 
      string s , w;
      cin >> s >> w;
      int ans = 0;//储存答案 
      memset (falg , 0 , sizeof(falg));//每一次用都要，不然会很惨，初始化 
      for (int i = 0; i < n; ++ i) {
          if (w[i] == '1') {//如果我方这里有人 
              if (s[i] == '0')ans++;//如果对方这里没人，就跳到这里，ans++
              else {//否则就看看对方旁边有没有人并没有被吃掉，那么ans++ ，并标记这个人被吃掉了。 
                  if (i - 1 >= 0 && falg[i - 1] == 0 && s[i - 1] == '1') {//如果左上有敌人并没有被吃掉并且 i-1 合法。 
                      ans++;//ans++ 
                      falg[i - 1] = 1;//达标记 
                  } else if (i + 1 < n && falg[i + 1] == 0 && s[i + 1] == '1') {//如果右上有敌人并没有被吃掉并且 i+1 合法。 
                      ans ++;//ans++ 
                      falg[i + 1] = 1;//达标记 
                  }
              }
          } 
      } 
      print(ans) , putchar('\n');//输出结果 
  } 
  return 0;
  }

  如有错误请大佬指出