比赛总结——CF #462 & LG 通往地底的旅行
差点就退役的选手又回来更新博客啦
CF #642
第一次打CF，ce了无数次 ，不过还好ce不掉分（逃）
T1
A. A Compatible Pair
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Nian is a monster which lives deep in the oceans. Once a year, it shows up on the land, devouring livestock and even people. In order to keep the monster away, people fill their villages with red colour, light, and cracking noise, all of which frighten the monster out of coming.
Little Tommy has n lanterns and Big Banban has m lanterns. Tommy’s lanterns have brightness a1,?a2,?…,?an, and Banban’s have brightness b1,?b2,?…,?bm respectively.
Tommy intends to hide one of his lanterns, then Banban picks one of Tommy’s non-hidden lanterns and one of his own lanterns to form a pair. The pair’s brightness will be the product of the brightness of two lanterns.
Tommy wants to make the product as small as possible, while Banban tries to make it as large as possible.
You are asked to find the brightness of the chosen pair if both of them choose optimally.
Input
The first line contains two space-separated integers n and m (2?≤?n,?m?≤?50).
The second line contains n space-separated integers a1,?a2,?…,?an.
The third line contains m space-separated integers b1,?b2,?…,?bm.
All the integers range from ?-?109 to 109.
Output
Print a single integer — the brightness of the chosen pair.
Examples
input
2 2
20 18
2 14
output
252
input
5 3
-1 0 1 2 3
-1 0 1
output
2
Note
In the first example, Tommy will hide 20 and Banban will choose 18 from Tommy and 14 from himself.
In the second example, Tommy will hide 3 and Banban will choose 2 from Tommy and 1 from himself.
我当时的做法是把 最大×次大 最大×最大 最小×最小 最小×次小排序找次小
我想这样如果最大值是正×正 & 正×负都可以解决了
But
如果最大值是正×负呢？然后就gg了
其实这个范围 O（n^2*m）完全可做！
T2
构造题不写了
T3
给你一个0，1序列 你可以翻转一次 求最长不下降子序列 n<=2000
我是这么干的：枚举l 找最优r 更新答案一次
时间复杂度证明：每个1是l 0不可能是l 然后0只被遍历一次 1只被枚举一次so：O(n^2)
T5
由于T4英文题面没看懂，直接pass了
T5是问3个圆切平面为几份
我写了10个特判左右，但还是漏了一个内切的情况（雾）
LG
LG题显然比div2难诶
传送门：https://www.luogu.org/contestnew/show/5877
T1
这个题我一开始发现 符合sliding windows的特征（即如果i到j才能成为一个环，则i+1至少到j成为一个环），然后我就往这边想，我发现对于每个p1 找到 p2利用一点差分就能统计答案！而sw的复杂度是O(n)，那么就需要我们logn判环！那怎么办呢？并查集？不对 并查集不能拆边啊（伏笔），然后我就不会做了，最后写了个n^2（每次重新构造并查集）60’。
那正解是啥呢？
并查集不能拆边，但是有东西可以啊！
What？
LCT！
嗯。。好难写 我宁可要60'
T2
以前ZHX告诉我可以线段树区间+等差数列，好嘛！我一看mlogn！完美！然后10min敲出了线段树！交！爆栈！！！！n是1e7，我的天，感觉整个人都不好了！然后我想手写栈，但只有30min了，然后我就去又xjb怼T1，这时！我发现T1的sw的性质使她可以O(n)扫完差分，那么？排序？？！mlogm！对啊，然后就靠T1写出来T2（逃）
conclusion
- 能写暴力过就不要xjb推式子因为可能不对
- LCT要学。。
- 要相信题不是都是NOI+。。。排序是个好东西