2020-team1-078

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team1 返回]


== 概述 ==

[[Image(111.png,800px)]]

（数据范围和时限和题目都改过，榜好像没啥参考价值）

做的时候剩2.5h剩2个题，都没过（


== 总结 ==

几何题似乎有一些可以讲的东西？

lwn_16：JTJL几何题是真NM牛逼，我和张静圳写出的程序拍上了，结果都是错的。最后那个重心必须在两根线之间的情况其实挺难想到的

== 题解 ==

(lwn_16备注：验题的题目顺序和现在的题目顺序不一样了，我不知道该以怎么样的方式安排题解，决定就按现在的顺序吧)

A: 签到

B: 找循环节，分奇偶讨论

C: NB几何，分点挂、线挂、面挂讨论，注意线挂情况重心必须在两根线之间。

D: 小贪心

E: 新加的题，验题的时候没有

F: 网络流

G: 最外面套个二分，设f[i]/g[i]为以i为开头满足每段和>=mid最少/最多能分多少段，有个结论是[ f[i], g[i] ]区间内的段数都能被分出来。f[i]和g[i]可以nlog^2求。然后考虑输出字典序最大解：对当前i，相当于找到最大的j>i满足f[j]<=A，g[j]>=B。由于A，B是递减的，我们可以在到B的时候将j插入到线段树里，f[j]不满足A的限制的时候将j从线段树中删除，可以logn的维护这个东西。

H: 日语题，分类讨论

I: 牛逼贪心，见浙江省赛pool。先二分，用1个3砍>=3的奇数，用2个3砍>=6的偶数，剩下的3砍>=4，2，1；2先砍>=2的所有数，再砍1；1砍剩下

J: 考虑到蚂蚁撞墙有循环节，可以O(n)的算出第一堵墙破是什么时候，然后就可以直接算全掉下去的时间。题解的想法是让两堵墙都减去n的若干倍直到其中一堵<n，然后去做两个队列的模拟，最后时间加上循环节2*（1e9+1）的若干倍。

K: 按题意构造即可

L: 简单BFS，卡输出，cout << "\n"比cout << endl快，因为后者有flush

M:新加的题，验题的时候没有

[/wiki/2020-team1 返回]

概述

（数据范围和时限和题目都改过，榜好像没啥参考价值）

做的时候剩2.5h剩2个题，都没过（

总结

几何题似乎有一些可以讲的东西？

lwn_16：JTJL几何题是真NM牛逼，我和张静圳写出的程序拍上了，结果都是错的。最后那个重心必须在两根线之间的情况其实挺难想到的

题解

(lwn_16备注：验题的题目顺序和现在的题目顺序不一样了，我不知道该以怎么样的方式安排题解，决定就按现在的顺序吧)

A: 签到

B: 找循环节，分奇偶讨论

C: NB几何，分点挂、线挂、面挂讨论，注意线挂情况重心必须在两根线之间。

D: 小贪心

E: 新加的题，验题的时候没有

F: 网络流

G: 最外面套个二分，设f[i]/g[i]为以i为开头满足每段和>=mid最少/最多能分多少段，有个结论是[ f[i], g[i] ]区间内的段数都能被分出来。f[i]和g[i]可以nlog^2求。然后考虑输出字典序最大解：对当前i，相当于找到最大的j>i满足f[j]<=A，g[j]>=B。由于A，B是递减的，我们可以在到B的时候将j插入到线段树里，f[j]不满足A的限制的时候将j从线段树中删除，可以logn的维护这个东西。

H: 日语题，分类讨论

I: 牛逼贪心，见浙江省赛pool。先二分，用1个3砍>=3的奇数，用2个3砍>=6的偶数，剩下的3砍>=4，2，1；2先砍>=2的所有数，再砍1；1砍剩下

J: 考虑到蚂蚁撞墙有循环节，可以O(n)的算出第一堵墙破是什么时候，然后就可以直接算全掉下去的时间。题解的想法是让两堵墙都减去n的若干倍直到其中一堵

K: 按题意构造即可

L: 简单BFS，卡输出，cout << "\n"比cout << endl快，因为后者有flush

M:新加的题，验题的时候没有

附加文件