X Samara Regional Intercollegiate Programming Contest
2024-10-08 03:57:02
A. Streets of Working Lanterns - 2
- 对于每个括号序列，存在一个\(mv\)，表示要接上这个序列至少需要\(-mv\)个左括号，同时处理出接上这个序列后，左括号数量的增量\(add\)。
- 假设当前左括号数量为\(sum\)，对于\(sum+mv_i>=0\)的片段都是可添加的，一个比较容易想到的贪心，取\(add_i\)最大的那个序列，使得左括号数量尽可能多。这个贪心的正确性是建立在\(add_i>=0\)的情况，否则是错误。
- 考虑\(sum = 7, (mv_1,add_1)=(-4, -1), (mv_2, add_2)=(-7, -2)\)。
- 只考虑两个序列时，应该取\(sum+add_i+mv_j\)大的那个，就转换成经典的贪心排序问题。
B. Pursuing the Happiness
- happiness在原串上不会重叠，所以只需要考虑原串包含happiness的个数。
- 如果要求的串\(t\)会出现重叠，上述做法不完善。
- 若原串包含串\(t\)，则对应的串\(t\)上至少有一个位置要交换出去，那么可以枚举串\(t\)的交换位置，同时\(O(n)\)枚举另一个交换位置。交换完，两个位置涉及长度\(|t|\)的子串都要更新，这一步可以用哈希解决。
F. Circuits
- 好的元件不会把坏的测成好的，而坏的会把好的测成坏的。
- 一旦测出坏元件，则我们把这两个都当成坏的，由于题目保证少于一半的是坏的，所以最后必然会剩下一个好的。
I. Matrix God
- 两个矩阵都左乘一个\(1 * n\)的随机向量，判断结果是否一致。
J. Catch the Monster
- 注意怪兽可以躲在时间隧道内。
- 若把一个点去掉后，形成的子树中存在超过两个非链的子树，则无法抓住怪兽，否则总是有办法遍历整棵树。
L. High Probability Cast
- 李超线段树。
M. Last Man Standing
- 倒着做。
最新文章
- Instant Radiosity实现
- iOS 6.0之后支持一个页面横屏的方法
- 第十章 PageRank——Google的民主表决式网页排名技术
- mapreduce 模板
- POJ 1654 Area(水题)
- ArcGIS 设置地图显示范围大小（全屏显示）
- 详解<a>标签
- ajax使用jquery的实现方式
- Backbone.js学习之View
- UVA1673 str2int（SAM）
- hdoj 2178 猜数字
- 吉特仓储管系统(开源)--使用Grunt压缩JS文件
- Hadoop搭建全程
- Objective-C语法概述
- ibufds原语
- GoogLeNet 之 Inception v1 v2 v3 v4
- emmet前端模板
- hdu-1176免费馅饼
- python 字符串的split()函数详解
- Ubuntu下Eclipse的安装方法