Warning: session_start(): open(/tmp/sess_06f10811fed9ce29f14a4701115e75e3, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== Update on Wiki ======
* 创建了本周训练周报
* 创建了暑期牛客第九次集训界面
* 创建了暑期牛客第十次集训界面
----
====== 团队训练 ======
[[front_page_SummerTrain11|2020牛客暑期多校训练营(第九场)]]
\\ [[front_page_SummerTrain12|2020牛客暑期多校训练营(第十场)]]
----
====== 每周推荐 ======
fyh:
\\ 题目大意:给一个无向图,你要不在图中找到一个长度大于等于$\lceil \frac{n}{2} \rceil$ 的简单路径,要不就找若干个二元组(其中这些二元组的元素不能重复,至少要多于等于$\lceil \frac{n}{2} \rceil$ ),使得任意两个二元组组成的子图,至多有两条边。
\\ tag:dfs树,构造
\\ 做法:随便找一点开始求他的dfs树,如果dfs树中有深度大于等于$\lceil \frac{n}{2} \rceil$ 的点,就直接输出即可,否则就找所有深度相同的点,两两配对,一定能保证配出$\lceil \frac{n}{4} \rceil$ 对。怎么证明呢?
先证这任意两个二元组组成的子图吧,根据dfs树的性质,**所有非树边一定是祖先连往子孙,不可能存在子树之间的连边** ,深度相同的点显然是属于两个子树,所以保证两个二元组$(a,b),(c,d)$ 其中$deep[a]=deep[b],deep[c]=deep[d]$ 令$deep[a] max + 1$,显然对答案没有影响
但是假若$x \le max + 1$,显然最大区间变为$[1,max + x]$,答案变为$max + x + 1$
那么我们就能得出这题的解法了
将区间内的数排序,一开始$ans = 0$,然后逐一将数加入集合之中, 一但出现$x > max + 1$的情况,由于是有序的,后面的数也无法更新答案,此时答案就是最优的
但是暴力排序枚举显然不行,我们可以用主席树优化
每求出一个新的区间$[1,max]$后,$[1,max + 1]$内的数都可以参与贡献,那么此时新的区间为$[1,\sum a_i]$,其中$a_i \le max + 1$
当$max$不变时算法结束
显然$max$是成倍增长的,所以复杂度为$O(nlog^2(\sum a_i))$
\\ comment:贪心思路+数据结构优化
----
====== 个人训练 ======
====== 傅云濠 ======
比赛:[[https://www.cnblogs.com/FYH-SSGSS/p/13480766.html|Codeforces Round #663 (Div. 2)]]
\\ 补第九场J 第十场J
整理了树上哈希的板子
----
====== 王兴罡 ======
补了cf664的部分题
----
====== 黄旭民 ======
比赛:无
\\ 整理单纯形板子