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 100010int n, m; int main() {scanf("%d%d", &n, &m);printf("%d\n", m); }

轉載于:https://www.cnblogs.com/henry-1202/p/10300686.html

總結

以上是生活随笔為你收集整理的BZOJ4893: 项链分赃 BZOJ4895: 项链分赃（增强版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。