BZOJ4893: 项链分赃 && BZOJ4895: 项链分赃(增强版)
amp 增强版 项链
2023-09-27 14:27:46 时间
中文体面而且超简洁就不解释了。
神仙题.jpg
切一刀简单啊,维护一个前缀和。
切两刀简单啊,拿个队列维护中间那一段。
切三刀,这tm什么毒瘤题。
于是打开题解:“保证不会答案不会超过宝石种类”。
orz神仙结论。
于是去研究了一下证明,但是看不懂拓扑学...
可以看一下3Blue1Brown的这个视频
出题人大概是看了这个视频后出了这题?
这两题是一样的。第二题直接输出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 }
参考链接
相关文章
- Css & JavaScript & jquery 实现选项卡的制作
- how to deal with "no such file error or diretory" error for a new programmer in QT creator
- Java8:从匿名内部类到Lambda表达式&方法引用
- Spark DataSource V1 & V2 API 一文理解
- MySQL视图&触发器
- (数据科学学习手札26)随机森林分类器原理详解&Python与R实现
- NSAutoreleasePool & thread
- 浅谈npx&&npx和npm之间的关系
- 面向过程编程&面向对象编程
- Qt 模拟鼠标点击(QApplication::sendEvent(ui->pushbutton, &event0);)
- 《微机接口原理》A+学习笔记系列--概论&端口寻址
- std::stringstream转换为std::vector<char>
- 【创作赢红包】< 二叉树OJ题(一) >单值二叉树&&二叉树的最大深度&&翻转二叉树&&相同的树&&对称二叉树
- mysql Access denied for user 'root'@'localhost' (using password: YES)