关于T3 O(n^3) 能草过去这件事

一开始我写了个暴力：

/*
 * @Author: Aisaka_Taiga
 * @Date: 2023-08-27 19:42:45
 * @LastEditTime: 2023-08-27 20:33:48
 * @LastEditors: Aisaka_Taiga
 * @FilePath: \Desktop\牛客C.cpp
 * 心比天高，命比纸薄。
 */
#include <bits/stdc++.h>

#define int long long
#define N 1000100

using namespace std;

int ans, n;
char s[N];

signed main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n; i ++)
    {
        for(int j = i + 1; j <= n; j ++)
        {
            int c1 = 0, c2 = 0;
            for(int k = i; k <= j; k ++)
            {
                if (s[k] - '0' == (k & 1)) c1 ++;
                if (s[k] - '0' == ((k + 1) & 1)) c2 ++;
            }
            ans += min(c1, c2);
        }
    }
    cout << ans << endl;
    return 0;
}

然后T了，我就开始想正解，赛后我问另一个人怎么做的，他说暴力不就行吗。

然后这是 AC 代码：

/*
 * @Author: Aisaka_Taiga
 * @Date: 2023-08-27 19:42:45
 * @LastEditTime: 2023-08-27 20:33:48
 * @LastEditors: Aisaka_Taiga
 * @FilePath: \Desktop\牛客C.cpp
 * 心比天高，命比纸薄。
 */
#include <bits/stdc++.h>

// #define int long long
#define N 1000100

using namespace std;

int ans, n;
char s[N];

signed main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n; i ++)
    {
        for(int j = i + 1; j <= n; j ++)
        {
            int c1 = 0, c2 = 0;
            for(int k = i; k <= j; k ++)
            {
                if (s[k] - '0' == (k & 1)) c1 ++;
                if (s[k] - '0' == ((k + 1) & 1)) c2 ++;
            }
            ans += min(c1, c2);
        }
    }
    cout << ans << endl;
    return 0;
}

是的把第11行的define注释掉就A了。

我怎么也想不到暴力能草过去啊？？