BZOJ4893: 项链分赃 && BZOJ4895: 项链分赃（增强版）

Solution

神仙题.jpg

切一刀简单啊，维护一个前缀和。

切两刀简单啊，拿个队列维护中间那一段。

切三刀，这tm什么毒瘤题。

于是打开题解：“保证不会答案不会超过宝石种类”。

orz神仙结论。

于是去研究了一下证明，但是看不懂拓扑学...

可以看一下3Blue1Brown的这个视频

出题人的证明

出题人大概是看了这个视频后出了这题？

这两题是一样的。第二题直接输出m就行了。

知道结论后瞎写就行

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 100010
int cnt[3], sum[N][3];
int n, a[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        sum[i][0] = sum[i - 1][0];
        sum[i][1] = sum[i - 1][1];
        sum[i][2] = sum[i - 1][2];
        sum[i][a[i]]++;
    }
    for(int i = 1; i <= n; ++i) {
        if(sum[i][0] * 2 == sum[n][0] 
        && sum[i][1] * 2 == sum[n][1] 
        && sum[i][2] * 2 == sum[n][2])
            {puts("1"); return 0;}
    }
    int l = 1;
    for(int i = 1; i <= n; ++i) {
        cnt[a[i]]++;
        for(int j = 0; j < 3; ++j) {
            while(l <= i && cnt[j] * 2 > sum[n][j]) cnt[a[l]]--, ++l;
        }
        if(cnt[0] * 2 == sum[n][0] 
         && cnt[1] * 2 == sum[n][1] 
         && cnt[2] * 2 == sum[n][2])
         {puts("2"); return 0;}
    }
    puts("3");
}

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 100010

int n, m;
int main() {
    scanf("%d%d", &n, &m);
    printf("%d\n", m);
}

BZOJ4893: 项链分赃 && BZOJ4895: 项链分赃（增强版）

原文：https://www.cnblogs.com/henry-1202/p/10300686.html