SDU暑期集训排位(5)
2024-09-01 06:26:01
SDU暑期集训排位(5)
A. You’re in the Army Now
题意
- 类似选志愿。每个人有 mark,有优先级从高到低的志愿。
做法
- 定睛一看,鲨鼻题。然后 WA。
- 为什么会 WA 呢?名字排序。
- 前缀后缀空格的去除。
- 题面中讲:人的名字由小写大写字母与空格组成,那么有可能名字里有连续多个空格。
- a 和 B 优先级谁小呢?
When letters are equal consider capital letters less, in other case
don’t consider their case
Orc name can consist only from lowercase and uppercase Latin letters and
spaces, but does not have leading and trailing spaces (you should omit them if they’re in the input).
- 题面中该表达的信息表达得很清楚,如果读题读成憨憨了,没什么好抱怨的。
D. Castle
upsolved
题意 给 \(n\) 个凸多边形,形成一个闭集套,给 \(m\) 个点,每个点被选择后,这个点所在的平面区域涂成黑色,求黑色面积。
做法 对凸多边形按照面积从小到大排序,对于一个点,二分最内层的包含这个点的多边形。判断点是否在凸包内可以 \(O(log n)\) 时间实现。
unlimited Wrong Answer on Test 5 Work
- PS 小心凸包会不会三点共线。
upd: sdcgvhgj使用了憨憨排序,红书的板子需要传入严格凸包
G. Princess
题意 当头发长度为 \(k\) 时剪成光头,头发增长速度会变成 \(k\) m/每周,一个光头初始增长速度为 \(1\) m/每周。以最快的速度头发长度增长到 \(L\)。
做法 剪头发的决策是个泛函,具体证明得请教《泛函分析》
- 口胡结论,我们每 \(x\) 周减一次头发。
- 那么第 \(k\) 次剪头发时,即第 \(kx\) 周头发长度为 \(x^k\) (\(k\)为整数)
- 从小到大枚举一下 \(k\)。对答案取极小。
- 神妙的事情:这个问题,可以成为自然对数的背景之一。
I. Spell
题意 给n个字符串,输出字典序第k大的,同时是n个字符串的子串的字符串
做法
- 求一个字符串的第k大子串是SAM的经典问题,只需要dp出从每个点开始的路径数,然后边在SAM上跑边输出答案就好
- 求同时是n个字符串的子串的串也是SAM的经典问题,只需要对n个串建广义SAM然后统计每个点的子树中是否包含所有n个串中的位置
- 所以这题是个不算麻烦的题,只需要把第二个问题中合法的点拿出来给第一个问题
- WA->重读题->没毛病->对拍->拍不出错->乱改->xjb交->WA->..(2h)..->发现读错题。。。我是憨憨
J. Orcish Transportation
题意
- 定义 \(f(i)=[i \geq n]?i-n:i+n\)。
- 输入边 \(u,v,w\)。\(u\) 向 \(v\) 连容量为 \(w\) 的边,\(f(v)\) 向 \(f(u)\) 连容量为 \(w\) 的边。
- 求 \(1\) 到 \(n+1\) 最大流。
做法
- 直接建图求最大流,边 \(u,v\) 的流为 \(flow(u,v)\),\(flow_{ans}(u,v) = \frac{flow(u,v)+flow(f(u),f(v))}{2}\)
证明
- 考虑流可行的充要条件。
- 对边:流量小于容量上限。
- 对非源、汇的点:流量守恒。
- 从源点流出的流量,等于流入汇点的流量。
- 对 1 的证明:\(flow(u,v) \leq lim(u,v), flow(f(u),f(v)) \leq lim(u,v)\),因此 \(flow_{ans}(u,v) = \frac{flow(u,v)+flow(f(u),f(v))}{2} < lim(u,v)\)
- 对 2 的证明:
- 考虑 \(u\) 点建立的流量守恒等式,称为
最新文章
- 关于xib的一些细节/ 真机调试/ GitLab
- IIS报错 试图加载格式不正确 的程序集解决办法
- mysql replace 替换函数
- Ubuntu14.04环境下Samba报错排错过程
- 一个java的DES加解密类转换成C#
- js添加遮罩层
- ios delegate 和 block
- 10令人惊叹的模型的影响HTML5应用程序及源代码
- ssh 自动登录
- 关于文件读写IDL
- 两百条微信小程序跳坑指南(不定时更新)
- RabbitMQ 消息流程、AMOP 概念
- xht37的码风
- ZooKeeper 典型的应用场景——及编程实现
- unity3d 材质概述 ---- shader
- mybatis-generator命令行生成代码
- Visual Studio Code 工具使用教程
- 【bzoj1901】Zju2112 Dynamic Rankings 离散化+主席树+树状数组
- 在C/C++函数中使用可变参数
- 【C++】多重继承
热门文章
- 考虑 \(u\) 点建立的流量守恒等式,称为