2019-team666-0013

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
八月集训第5场
[[Image(Submissions.png,1000px)]]
== 流水账 ==
yyc出门签到猛如虎，一看Wa Test 5. 一阵乱改之后'''C2y12'''. tjc开出F，'''F1y31'''，hyw听yyc讲了一下B的题意就上去写了，'''B1y47'''。hyw写B之前跟yyc讲了一下H，yyc和tjc讨论出H，期间因为奇怪的原因wa了一发，'''H2y72'''。然后写了一阵子A发现读了假题，大约1个半小时的时候hyw推完D，等了半个小时机位直到A假了才上去写，尝试交了一发居然过了，'''D1y125'''。很快A修正了做法，'''A2y141'''。yyc给出了G的做法，一开始觉得复杂度不对，后来tjc觉得复杂度是对的，就去写了，'''G2y168'''。最后两个小时tjc写E，yyc写J，没有进展，最后一小时E过了，'''E2y265'''，J“本机AC提交WA”，奥妙重重。
== 总结 == 
=== yyc ===
感觉被评测姬搞了...疯狂WA1...以及急于抢1血导致一发罚时...
=== tjc  ===
这个A题获得了一个假题意，然后还想出来了做法，写完后发现过不了样例，自己读一遍才得知真题意
G的复杂度分析是经典套路（？）
E这个大模拟写得我难受死了，也不知道有没有好的实现方法
=== hyw  ===
今天出了A假了一次爆了一些罚时以外其他没啥大锅。后期卡I想不出也挺正常的，J题其实是个二维偏序但是我一眼觉着不可做...还是没有深入想。L题之前有个题[https://codeforces.com/problemset/problem/1175/F Codeforces 1175F]跟这个挺像的，虽然有一些不一样但是模型有可以借鉴的地方，比赛的时候没想起来，后来还是队友想出来了以后我才想起来，挺不应该的。
=== 题解 ===
A：单调栈
B：简单计算几何
C：签到
D：可以证明第一问答案一定是0.5。我的做法是设f[i](i≠1)为现在轮到第i个人坐，且他自己的位置被人做了的概率，注意i=1的时候第一个人是随机的所以特殊考虑，也可以推出f[i]=0.5. 第二问枚举没票的人在第几个位置即可。
E：模拟
F：按w排序然后floyd
G：树形dp，for到min(size,k)，表面nk^2^实际nk
H：
I：[https://paste.ubuntu.com/p/rMtRcVKQJ6/ 代码]  性质题，冒泡k趟之后新序列的第i项是原序列前min(i+k,n)项中未在新序列前i-1项中出现过的最小值。考虑permutation 1..n以及暴力枚举一个区间[l,r]将其循环左移或右移得到的序列，考虑每个数字可能在的位置个数，用乘法原理计算。细节：左移的时候必须r+k<=n才合法，且a[l]位置固定，其余数任填。右移的时候也必须r+k<=n才合法，且除了a[l+1],...,a[r]位置都固定，其余数任填。不移的时候1,2,...n每个数都任填。
J：注意到三角嵌套的充要条件是点与PQ的两个底角都递减，转化成二维偏序。字典序最小在dp值相同情况下取编号小的就行了。
K：将点集折半分成L和R，现在边可以分为L中的、R中的、L和R之间的三类。首先计算cal[i](i是R的一个子集，压成二进制）表示i里的数的权值积，若不合法（即R中存在边没有被覆盖）则cal[i]=0。然后计算高维前缀和。最后枚举L的一个子集i，先判断合不合法（即L里的边有没有都被覆盖了），然后对于不在i中的点，统计R中所有和这些点连接的点，这个点集的权值用高维前缀和可以算出，统计一下就好了。
L：（线段树，细节有点多，留坑@队友）
M：

[/wiki/2019-team666 返回]

概述

八月集训第5场

流水账

yyc出门签到猛如虎，一看Wa Test 5. 一阵乱改之后C2y12. tjc开出F，F1y31，hyw听yyc讲了一下B的题意就上去写了，B1y47。hyw写B之前跟yyc讲了一下H，yyc和tjc讨论出H，期间因为奇怪的原因wa了一发，H2y72。然后写了一阵子A发现读了假题，大约1个半小时的时候hyw推完D，等了半个小时机位直到A假了才上去写，尝试交了一发居然过了，D1y125。很快A修正了做法，A2y141。yyc给出了G的做法，一开始觉得复杂度不对，后来tjc觉得复杂度是对的，就去写了，G2y168。最后两个小时tjc写E，yyc写J，没有进展，最后一小时E过了，E2y265，J“本机AC提交WA”，奥妙重重。

总结

yyc

感觉被评测姬搞了...疯狂WA1...以及急于抢1血导致一发罚时...

tjc

这个A题获得了一个假题意，然后还想出来了做法，写完后发现过不了样例，自己读一遍才得知真题意

G的复杂度分析是经典套路（？）

E这个大模拟写得我难受死了，也不知道有没有好的实现方法

hyw

今天出了A假了一次爆了一些罚时以外其他没啥大锅。后期卡I想不出也挺正常的，J题其实是个二维偏序但是我一眼觉着不可做...还是没有深入想。L题之前有个题Codeforces 1175F跟这个挺像的，虽然有一些不一样但是模型有可以借鉴的地方，比赛的时候没想起来，后来还是队友想出来了以后我才想起来，挺不应该的。

题解

A：单调栈

B：简单计算几何

C：签到

D：可以证明第一问答案一定是0.5。我的做法是设f[i](i≠1)为现在轮到第i个人坐，且他自己的位置被人做了的概率，注意i=1的时候第一个人是随机的所以特殊考虑，也可以推出f[i]=0.5. 第二问枚举没票的人在第几个位置即可。

E：模拟

F：按w排序然后floyd

G：树形dp，for到min(size,k)，表面nk2实际nk

H：

I：代码 性质题，冒泡k趟之后新序列的第i项是原序列前min(i+k,n)项中未在新序列前i-1项中出现过的最小值。考虑permutation 1..n以及暴力枚举一个区间[l,r]将其循环左移或右移得到的序列，考虑每个数字可能在的位置个数，用乘法原理计算。细节：左移的时候必须r+k<=n才合法，且a[l]位置固定，其余数任填。右移的时候也必须r+k<=n才合法，且除了a[l+1],...,a[r]位置都固定，其余数任填。不移的时候1,2,...n每个数都任填。

J：注意到三角嵌套的充要条件是点与PQ的两个底角都递减，转化成二维偏序。字典序最小在dp值相同情况下取编号小的就行了。

K：将点集折半分成L和R，现在边可以分为L中的、R中的、L和R之间的三类。首先计算cal[i](i是R的一个子集，压成二进制）表示i里的数的权值积，若不合法（即R中存在边没有被覆盖）则cal[i]=0。然后计算高维前缀和。最后枚举L的一个子集i，先判断合不合法（即L里的边有没有都被覆盖了），然后对于不在i中的点，统计R中所有和这些点连接的点，这个点集的权值用高维前缀和可以算出，统计一下就好了。

L：（线段树，细节有点多，留坑@队友）

M：

附加文件