luogu 2882 Face The Right Way G

题目描述

Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K ≤ N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same *location* as before, but ends up facing the *opposite direction*. A cow that starts out facing forward will be turned backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.

头牛排成一列 。每头牛或者向前或者向后。为了让所有牛都面向前方，农夫每次可以将 头连续的牛转向 ，求使操作次数最小的相应 和最小的操作次数 。 为朝前， 为朝后。

请在一行输出两个数字 和 ，用空格分开。

输入格式

Line 1: A single integer: N

Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.

输出格式

Line 1: Two space-separated integers: K and M

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8

7
B
B
F
B
F
B
B

样例输出 #1

1

3 3

提示

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

分析

这道题的思想跟acwing 95.费解的开关有点像。

xxxxxxxxxx52 1#include2using namespace std;3​4int n, a, b, c;5​6int main()7{8    cin >> n;9    cin >> a >> b >> c;10    if(a > b)11        swap(a, b);12    if(a > c)13        swap(a, c);14    if(b > c)15        swap(b, c);16    if((a + 1 == b && b + 1 == c) || (a == 0 && c == n - 1))17   {18        puts(“JMcat Win”);19        return 0;20   }21/22假如顶点连续，则代表这个黑色三角形在外面。23就像是一个多边形上连续三个点构成的三角形必然在外面24那么先手的野猫就赢了25当然还有一个特殊情况：假如黑色三角形同时包括 0 点和 n 点（首尾相连）26就比如：276280 5 4290 1 2302 4 3314 2 032所以要特判一下这种情况33/34    else if((n - 2) % 2 == 0)35   {36        puts(“JMcat Win”);37        return 0;38   }39/40假如黑色三角形被包在里面41先放着别的三角形不管42假设最后只剩三个个三角形包着黑三角43谁把其中一个三角切了谁就输了44胜负就出来了45所以只要考虑三角形个数的奇偶性就行了46/47    else48        puts(“PZ Win”);49​50    return 0;51}52​cpp

那么只要先枚举一遍修改区间的长度，遍历数组，遇到 0 就改变后面一定长度的区间。如果说要改变的地方超过了数组总长度，这个方案就是不行的。枚举长度+遍历数组+修改，时间复杂度 n = 5000，显然需要优化。枚举长度和遍历数组不好优化，修改的话优化方法较多，比如差分，树状数组啥的。

差分只要修改两个点，就可以将两点间的区间修改，但是求值又是，但是这题也不需要求值，实际上看题解感觉这差分数组跟标记数组差不多。

颠倒两次相当于没变（虽然众所周知，还是有提的必要）

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

#include<iostream>
#include<cstring>
using namespace std;

#define N 5010

bool cha[N];
int n, a[N];
int now, ans1 = 0x3f3f3f3f, ans2, tot;
char ch;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> ch;
        if(ch == 'F')
            a[i] = 1;
    }
    for(int k = 1; k <= n; k ++)//遍历区间长度
    {
        memset(cha, 0, sizeof(cha));
        int flag = 1, tot = 0, now = 0;//now表示这一段区域是否翻转
        for(int i = 1; i <= n; i ++)
        {
            now ^= cha[i];//遇到变化区间的末尾时，再变回来
            if(a[i] ^ now == 0)
            {
                if(i + k - 1 > n)//超出范围
                {
                    flag = 0;
                    break;                    
                }
                tot ++;
                cha[i + k] ^= 1;
                now ^= 1;
            }
        }
        if(flag == 1)
        {
            if(tot < ans1)//记录一下再少变化数量
            {
                ans1 = tot;
                ans2 = k;
            }
        }
    }
    cout << ans2 << " " << ans1 << endl;
    return 0;
}