【思维】Flippy Sequence

题目链接:ZOJ4060

题意:

两个二进制串a与b,进行两次段取反操作,使得a变为b,问有多少种方法?

思路:

用if统计不同的段数,分类讨论:

段数 sumOfpart 分析 答案
>=3 只能进行两次操作,所以无解 0
==2 如样例有三种选择3*2=6 6
==1 把区间分成不交叉的两部分 *2 (n-1)*2
==0 两次操作必须选择相同位置 (n+1)*n/2

代码(注意cin会超时,在函数体外声明字符数组,否则会溢出):

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
const int maxn = 1000000+50;
char a[maxn], b[maxn];
int main()
{
  int t = 0;
  scanf("%d", &t);
  while (t--)
  {
    int n;
    scanf("%d", &n);
    scanf("%s", a);
    scanf("%s", b);
    int sumOfpart=0;
    bool isNew = 0;
    for (int i = 0; i < n; i++)
    {
      if (a[i]== b[i])
      {
        if (isNew)
        {
          sumOfpart++;
          isNew = false;
        }
        
      }
      else
      {
        isNew = true;
      }
    }
    if (isNew)
    {
      sumOfpart++;
    }
    if (sumOfpart>=3)
    {
      printf("0\n");
    } 
    else if (sumOfpart==2)
    {
      printf("6\n");
    }
    else if (sumOfpart == 1)
    {
      printf("%d\n",(n-1)*2);
    }
    else 
    {
      printf("%d\n", n*(n + 1) / 2);
    }
  }
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

12 + 12 =