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

一时失言乱红尘 2023-08-17 15:46 80阅读 0赞

中文体面而且超简洁就不解释了。

神仙题.jpg

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

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

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

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

orz神仙结论。

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

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

[出题人的证明][Link 1]

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

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

知道结论后瞎写就行

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     4 using namespace std;
     5 
     6 typedef long long ll;
     7 const int maxn = 100000 + 10;
     8 int a[maxn],n;
     9 int record[maxn][3];        
    10 int sum[3];
    11 int cnt[3];            //记录当前队列中3种宝石的数目
    12 
    13 int solve()
    14 {
    15     for (int i = 0; i < 3; i++)  sum[i] = record[n][i] / 2;
    16     for (int i = 1; i <= n; i++)
    17         if (record[i][0] == sum[0] && record[i][1] == sum[1] && record[i][2] == sum[2])  return 1;
    18     int l = 1;
    19     for (int r = 1; r <= n; r++)
    20     {
    21         cnt[a[r]]++;
    22         for (int i = 0; i < 3; i++)
    23         {
    24             while (l <= r && cnt[i] > sum[i]) { cnt[a[l]]--;  l++; }
    25         }
    26         if (cnt[0] == sum[0] && cnt[1] == sum[1] && cnt[2] == sum[2])  return 2;
    27     }
    28     return 3;
    29 }
    30 
    31 int main()
    32 {
    33     scanf("%d", &n);
    34     for (int i = 1; i <= n; i++)
    35     {
    36         scanf("%d", &a[i]);
    37         record[i][0] = record[i - 1][0];
    38         record[i][1] = record[i - 1][1];
    39         record[i][2] = record[i - 1][2];
    40         record[i][a[i]]++;
    41     }
    42     int ret = solve();
    43     printf("%d\n", ret);
    44     return 0;
    45 }

1 #include<cstdio>
     2 using namespace std;
     3 
     4 int main()
     5 {
     6     int n, m;
     7     scanf("%d%d", &n, &m);
     8     printf("%d\n", m);
     9     return 0;
    10 }

参考链接

1.  [https://www.cnblogs.com/henry-1202/p/10300686.html][https_www.cnblogs.com_henry-1202_p_10300686.html]
2.  [https://www.cnblogs.com/lfri/p/10327066.html][https_www.cnblogs.com_lfri_p_10327066.html]

转载于:https://www.cnblogs.com/lfri/p/10327146.html

[3Blue1Brown]: https://www.bilibili.com/video/av9885078?t=579
[Link 1]: http://www.cnblogs.com/juruolty/p/6806029.html
[https_www.cnblogs.com_henry-1202_p_10300686.html]: https://www.cnblogs.com/henry-1202/p/10300686.html
[https_www.cnblogs.com_lfri_p_10327066.html]: https://www.cnblogs.com/lfri/p/10327066.html