2018 青岛区域赛 C - Flippy Sequence

╰+攻爆jí腚メ 2022-04-16 03:27 126阅读 0赞

#                                             Flippy Sequence #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvbmdzYW5qaW4_size_16_color_FFFFFF_t_70][]

### Sample Input ###

3
    1
    1
    0
    2
    00
    11
    5
    01010
    00111

### Sample Output ###

0
    2
    6

### Hint ###

For the second sample test case, there are two valid operation pairs: (1, 1, 2, 2) and (2, 2, 1, 1).

For the third sample test case, there are six valid operation pairs: (2, 3, 5, 5), (5, 5, 2, 3), (2, 5, 4, 4), (4, 4, 2, 5), (2, 4, 4, 5) and (4, 5, 2, 4).

###  题意描述： ###

给出两个长度为n的01串，通过一种变化，每次可将一个连续区间里的0变为1，1变为0。求若经过两次这种变化，使得两个01串完全相同共有多少中方法。

### 解题思路： ###

将两个01串通过按位异或，得到一个新的01串，0代表此位置两个01串相同，1代表此位置两个01串不同。通过按位异或得到的01串其中0可经过两次变化还为0，即此位置还是相同的，1可经过一次变化，此位置变为相同。通过找规律可知，因求的是经过两次变化01串相同的方法，若1被分为三段或三段以上则经过两次无法实现使得两个01串相同。若1被分为两段，可知共有6种方法；当1只有一段且含有0段时，共有（n-1）\*2种方法；当全为0时共有（n+1）\*n/2方法；当全为1时共有(n-1)\*2种方法。

### 程序代码： ###

#include<stdio.h>
    #define N 1000020
    char a[N],b[N];
    int c[N];
    int main()
    {
    	long long t,n,i,sum,temp;
    	scanf("%lld",&t);
    	while(t--)
    	{
    		sum=0;
    		scanf("%lld",&n);
    		scanf("%s %s",a,b);
    		for(i=0;i<n;i++)
    		{
    			c[i]=(a[i]-'0')^(b[i]-'0');
    			sum+=c[i];
    		}
    		if(sum==n)
    		{
    			printf("%lld\n",(n-1)*2);
    			continue;
    		}
    		if(sum==0)
    		{
    			printf("%lld\n",n*(n+1)/2);
    			continue;
    		}
    		temp=0;
    		if(c[0]==1)
    			temp++;
    		for(i=1;i<n;i++)
    		{
    			if(c[i]==1&&c[i-1]!=1)
    				temp++;
    			if(temp>2)
    				break;
    		}
    		if(temp>2)
    		{
    			printf("0\n");
    			continue;
    		}
    		if(temp==1)
    		{
    			printf("%lld\n",(n-1)*2);     
    		}
    		else if(temp==2)
    		{
    			printf("6\n");
    		}
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvbmdzYW5qaW4_size_16_color_FFFFFF_t_70]: /images/20220416/d909df8f6a504d338d55bc81815c922b.png