poj 3276 Face The Right Way 开关问题

缘起

日常浪费生命 poj 3276 Face The Right Way

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
N头牛排成一排，每头牛向前或者向后. 为了让所有牛都面向前方. FJ 买了一台自动转向的机器. 
这个机器在购买时就必须要设定一个数值K. 机器每操作一次恰好使得K头连续的牛转向. 请求出为了让所有的牛都
面向前方最少需要操作的次数M和对应的K.

【输入】
N（1 ≤ N ≤ 5,000）， 然后N行，每行是'F'或者'B' 表示牛是面朝前面还是后面

【输出】
K和M
1 ≤ K ≤ N

【样例输入】
7
B
B
F
B
F
B
B

【样例输出】
3 3

【限制】
2s

【hint】
For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and 
finally (5,6,7)

此类问题是一类反转问题（或者叫开关问题）

以前没接触过此类问题，所以耻辱的看了题解. 发现还是蛮简单的. 但是模拟的会被T掉.

一般反转问题是要注意到下面的事实

  1. 一头牛反转2次相当于没转
  2. 一个顶点的正反和两次翻转执行的顺序无关

所以本题其实就可以模拟来写了. 首先因为答案不具备单调性, 所以只能枚举k. 对于固定的k，从1到N考虑各个端点, 如果1已经是’F’的话, 不需要翻转, 否则是一定要翻转的，而且只需要翻转一次（性质1），然后1这个端点就变成’F’了，从而问题规模得到了简化. 下一步考虑的是2这个端点的翻转，和1是一样的——如果已经是’F’的话，就不需要翻转，如果是’B’就需要翻转. 直至考察到第N-k+1这个点. 如果不需要翻转的话，则就要继续考察后面的所有k-1头牛（即N-k+2,…,N），看看他们是不是已经’F’了. 如果不是的话, 说明此k办不到.

但是注意，每次考察牛i,看看它是不是要进行[i,i+k-1]的翻转，是取决于此时i的朝向的. 但是i的朝向明显受制于前面

[i-k+1,i],[i-k+2,i+1],…,[i-1, i+k-2] 这k-1个区间的翻转情况. 如果采用模拟的话, 则算法的复杂度是O(枚举k*遍历1,…N-k+1进行区间翻转*模拟长度为k的区间的翻转)=O(n^3). 对于n=5000这个量级，是一定会被T掉的. 所以我们一定要优化. 怎么优化呢? 其实考察i要不要参与 [i,i+k-1]这个区间的翻转的时候，它已经参与了i-k+1、i-k+2、…、i-1 开头的区间的翻转（如果真的翻转了的话）. 所以如果维护一下前面的牛是否翻转的话，就很轻易的知道现在考察的牛i是否需要翻转了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

int n,f[5005],ff[5005]; // f[i]=0表示[i,i+k-1]区间没有翻转, f[i]=1表示翻转了, ff是f的部分和
char s[5005];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 1; i<=n; i++)
	{
		getchar();
		s[i] = getchar();
	}
	int m = ~0u>>1, kk = -1;
	for (int k = 1,ret,i; k<=n;k++) // 枚举k
	{
		ret = 0;
		for (i = 1; i<=n-k+1; i++) // 逐步考虑i这头牛是否要翻转
		{
			int t = ff[i-1]-(i>=k?ff[i-k]:0); // i-k+1,...,i-1的翻转与否才能影响到i
			if (t&1) // 这里其实可以用异或写的简短风骚~ 但是不易读和体现思想, 所以放弃了
			{
				if (s[i]=='B') // 如果伊始就是'B'的话, 就不需要翻转了
				{
					f[i] = 0;
				}
				else // 如果伊始是'F',前面又翻了奇数次的话, 则此时还需要翻转
				{
					f[i] = 1;
					ret++;
				}
			}
			else
			{
				if (s[i]=='B')
				{
					f[i] = 1;
					ret++;
				}
				else
				{
					f[i] = 0;
				}
			}
			ff[i] = ff[i-1]+f[i]; // 更新部分和
		} // 最后得到ff[n-k+1]
		bool flag = true;
		for (;i<=n;i++)
		{
			if ((ff[n-k+1]-ff[i-k])&1)
			{
				if (s[i]=='F')
				{
					flag = false;
					break;
				}
			}
			else
			{
				if (s[i]=='B')
				{
					flag = false;
					break;
				}
			}
		}
		if (flag && m>ret)
		{
			m = ret;
			kk = k;
		}
	}
	printf("%d %d\n", kk, m);
	return 0;
}

ac情况

Status Accepted
Time 438ms
Memory 140kB
Length 1258
Lang C++
Submitted 2019-09-01 21:28:46
RemoteRunId 20824188

1A什么的，伦家最喜欢了~