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);

}