2016-C11-team1

从 Trac 迁移的文章

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

原文章内容如下：

||User||Problem||Result||Memory||Time||Language||Length||Submit Time||
||Siunaus||G||WA||  ||  ||C++ 5.3.0||1019||2016-08-11 14:15:41||
||Siunaus||G||WA||  ||  ||C++11 5.3.0||923||2016-08-11 14:09:54||
||Siunaus||J||WA||  ||  ||C++11 5.3.0||2385||2016-08-11 14:08:22||
||Siunaus||G||WA||  ||  ||C++ 5.3.0||910||2016-08-11 14:07:35||
||Siunaus||J||WA||  ||  ||C++11 5.3.0||2381||2016-08-11 14:07:02||
||Siunaus||G||WA||  ||  ||C++ 5.3.0||910||2016-08-11 14:03:35||
||Siunaus||C||CE||  ||  ||C++11 5.3.0||527||2016-08-11 14:01:22||
||Siunaus||J||WA||  ||  ||C++11 5.3.0||1301||2016-08-11 13:26:36||
||Siunaus||J||WA||  ||  ||C++11 5.3.0||1277||2016-08-11 13:21:11||
||Siunaus||J||WA||  ||  ||C++11 5.3.0||1270||2016-08-11 13:17:21||
||Siunaus||J||WA||  ||  ||C++11 5.3.0||1262||2016-08-11 13:14:15||
||Siunaus||H||AC||0||405||C++ 5.3.0||2274||2016-08-11 12:37:32||
||Siunaus||I||AC||0||69||C++11 5.3.0||3593||2016-08-11 12:06:57||
||Siunaus||F||AC||0||4755||C++11 5.3.0||1654||2016-08-11 11:51:56||
||Siunaus||C||AC||0||1602||C++ 5.3.0||2825||2016-08-11 11:47:27||
||Siunaus||I||WA||  ||  ||C++11 5.3.0||2904||2016-08-11 11:44:58||
||Siunaus||I||WA||  ||  ||C++11 5.3.0||2880||2016-08-11 11:36:57||
||Siunaus||C||WA||  ||  ||C++ 5.3.0||2815||2016-08-11 11:19:59||
||Siunaus||D||AC||0||29||C++11 5.3.0||437||2016-08-11 10:21:02||
||Siunaus||A||AC||0 KB||599 ms||C++11 5.3.0||555||2016-08-11 10:01:07||
||Siunaus||E||AC||0||4712||C++11 5.3.0||1294||2016-08-11 09:55:36||
||Siunaus||D||WA||  ||  ||C++11 5.3.0||1203||2016-08-11 09:47:43||
||Siunaus||D||WA||  ||  ||C++11 5.3.0||1044||2016-08-11 09:41:54||
||Siunaus||B||AC||0||3||C++11 5.3.0||629||2016-08-11 09:16:10||

start at 09:10

[http://acm.hust.edu.cn/vjudge/contest/127594 比赛链接] (password: 20160811)

== 流水账 ==

== 总结 ==

== 题解 ==

=== A. Automatic Cheater Detection [JTJL] ===

di很小

=== B. Counting Weekend Days [JTJL] ===

周五，而不是周日

=== C. Toll Management IV [sfiction] ===

给定一个无向图(n<=1e3,m<=1e4)和它的一个生成树，满足生成树上路径为图上路径中最大值最小的路径。求每条边权值的变动（单独变动）范围使得该生成树性质保持。

树上边无下界，非树边无上界。非树边可以视作树上路径，其下界即为路径上最大值。非树边对路径上所有边形成约束，树上边上界为约束中最小值。前者可以在倍增LCA中顺带完成，后者可以从LCA拆开后由端点向LCA传递，每个节点维护所有约束组成的优先队列，通过检查队首的退出时间戳来保证合法性。使用可并堆可以做到O(nlogm)，也可以用启发式合并+非可并堆做到O(nlognlogm)。总体复杂度为O(mlogn+nlogm)。

后半部分也可以用缩点的做法。将约束条件从大到小排序，每一对求LCA并从端点向上合并。ci<=1000，约束条件不需要排序，LCA离线O(1)，因此复杂度为O(m)。

=== D. Owllen [sfiction] ===

给定一个串S，求与S同长的与S的LCS最小的串。

似乎只需要输出字符集中出现次数最少的字符即可，待证明。

=== E. Sum of MSLCM [sfiction] ===

给定n(<=2e7)，求1-n所有数约数之和。

\sum_{i=1}^{n}{[n/i]*i}。O(n^0.5)。

=== F. Unique Party [sfiction] ===

给定一个矩阵(n,m<=250)，有Q(<=10)个询问，每个询问包含一个正整数h，求中位数(第n/2+1个)>=h的最大子矩阵大小。

首先将矩阵处理为1和-1，一维上区间枚举，这样就转化成了最长非负和子序列。从前缀和s[i]角度考虑即为求每个位置i后大于等于其的最远位置。注意到可以忽略i<j且s[i]<=s[j]的j项。而对于剩余的项，其对应位置满足单调性。因此可以在O(n)时间内求解。

=== G. Honey King [sfiction] ===

给六边形网格上一个点集，求能覆盖所有点的最小格点正六边形的半径。

二分边长。以一个点为中心的正六边形与六个半平面的交等价，六个半平面又分别属于三个方向(x,y,x+y)，因此只需在三个方向上做区间交即可。注意即使三个方向各自满足条件也可能无解，需要判定[xl+yl, xh+yh]和[xyl,xyh]是否有交。

=== H. Design New Capital [sfiction] ===

给定平面上n(<=1e5)个点，且均不位于坐标轴上，设optimal point为到给定点集曼哈顿距离之和最小的点（可能不唯一）。对所有的k，求有多少k元子集的optimal point可以为(0,0)。

k为奇数时答案为0。设四个象限所选点数为abcd，则条件等价于 a+b=c+d && a+d=b+c，则有 a=c && b=d。设四个象限总点数为 ABCD，则ans[k]= \sum_{i=0}!^(k){C(A,i)*C(C,i) * C(B,k-i)*C(D,k-i)}。做一遍NTT即可。O(nlogn)。

=== I. Numbered Cards [JTJL] ===

数位DP预处理，状压DP求答案。

发现前缀0可以合在一起处理而不用枚举长度……

=== J. The Hypnotic Spirals [JTJL] ===

给定一条等速螺线和n(<=10)条射线，形成对极坐标平面的一个划分，给定m(<=1e3)个点，求这些点所在区域的面积之和，注意一个区域可能有多个点。

对区域由内向外标号，计算每个点所属区间并去重，积分求和。

一些坑：

n为0的时候，m=0时答案为0，否则为-1

前两圈的极坐标轴所在区间需要特殊处理


== 补题 ==

~~G~~ ~~J~~

=== JTJL ===

 * Unaccepted: J

=== sfiction === 

 * Unaccepted: G
UserProblemResultMemoryTimeLanguageLengthSubmit Time
SiunausGWA C++ 5.3.010192016-08-11 14:15:41
SiunausGWA C++11 5.3.09232016-08-11 14:09:54
SiunausJWA C++11 5.3.023852016-08-11 14:08:22
SiunausGWA C++ 5.3.09102016-08-11 14:07:35
SiunausJWA C++11 5.3.023812016-08-11 14:07:02
SiunausGWA C++ 5.3.09102016-08-11 14:03:35
SiunausCCE C++11 5.3.05272016-08-11 14:01:22
SiunausJWA C++11 5.3.013012016-08-11 13:26:36
SiunausJWA C++11 5.3.012772016-08-11 13:21:11
SiunausJWA C++11 5.3.012702016-08-11 13:17:21
SiunausJWA C++11 5.3.012622016-08-11 13:14:15
SiunausHAC0405C++ 5.3.022742016-08-11 12:37:32
SiunausIAC069C++11 5.3.035932016-08-11 12:06:57
SiunausFAC04755C++11 5.3.016542016-08-11 11:51:56
SiunausCAC01602C++ 5.3.028252016-08-11 11:47:27
SiunausIWA C++11 5.3.029042016-08-11 11:44:58
SiunausIWA C++11 5.3.028802016-08-11 11:36:57
SiunausCWA C++ 5.3.028152016-08-11 11:19:59
SiunausDAC029C++11 5.3.04372016-08-11 10:21:02
SiunausAAC0 KB599 msC++11 5.3.05552016-08-11 10:01:07
SiunausEAC04712C++11 5.3.012942016-08-11 09:55:36
SiunausDWA C++11 5.3.012032016-08-11 09:47:43
SiunausDWA C++11 5.3.010442016-08-11 09:41:54
SiunausBAC03C++11 5.3.06292016-08-11 09:16:10

start at 09:10

比赛链接 (password: 20160811)

流水账

总结

题解

A. Automatic Cheater Detection [JTJL]

di很小

B. Counting Weekend Days [JTJL]

周五，而不是周日

C. Toll Management IV [sfiction]

给定一个无向图(n<=1e3,m<=1e4)和它的一个生成树，满足生成树上路径为图上路径中最大值最小的路径。求每条边权值的变动（单独变动）范围使得该生成树性质保持。

树上边无下界，非树边无上界。非树边可以视作树上路径，其下界即为路径上最大值。非树边对路径上所有边形成约束，树上边上界为约束中最小值。前者可以在倍增LCA中顺带完成，后者可以从LCA拆开后由端点向LCA传递，每个节点维护所有约束组成的优先队列，通过检查队首的退出时间戳来保证合法性。使用可并堆可以做到O(nlogm)，也可以用启发式合并+非可并堆做到O(nlognlogm)。总体复杂度为O(mlogn+nlogm)。

后半部分也可以用缩点的做法。将约束条件从大到小排序，每一对求LCA并从端点向上合并。ci<=1000，约束条件不需要排序，LCA离线O(1)，因此复杂度为O(m)。

D. Owllen [sfiction]

给定一个串S，求与S同长的与S的LCS最小的串。

似乎只需要输出字符集中出现次数最少的字符即可，待证明。

E. Sum of MSLCM [sfiction]

给定n(<=2e7)，求1-n所有数约数之和。

\sum_{i=1}{n}{[n/i]*i}。O(n0.5)。

F. Unique Party [sfiction]

给定一个矩阵(n,m<=250)，有Q(<=10)个询问，每个询问包含一个正整数h，求中位数(第n/2+1个)>=h的最大子矩阵大小。

首先将矩阵处理为1和-1，一维上区间枚举，这样就转化成了最长非负和子序列。从前缀和s[i]角度考虑即为求每个位置i后大于等于其的最远位置。注意到可以忽略i

G. Honey King [sfiction]

给六边形网格上一个点集，求能覆盖所有点的最小格点正六边形的半径。

二分边长。以一个点为中心的正六边形与六个半平面的交等价，六个半平面又分别属于三个方向(x,y,x+y)，因此只需在三个方向上做区间交即可。注意即使三个方向各自满足条件也可能无解，需要判定[xl+yl, xh+yh]和[xyl,xyh]是否有交。

H. Design New Capital [sfiction]

给定平面上n(<=1e5)个点，且均不位于坐标轴上，设optimal point为到给定点集曼哈顿距离之和最小的点（可能不唯一）。对所有的k，求有多少k元子集的optimal point可以为(0,0)。

k为奇数时答案为0。设四个象限所选点数为abcd，则条件等价于 a+b=c+d && a+d=b+c，则有 a=c && b=d。设四个象限总点数为 ABCD，则ans[k]= \sum_{i=0}!^(k){C(A,i)*C(C,i) * C(B,k-i)*C(D,k-i)}。做一遍NTT即可。O(nlogn)。

I. Numbered Cards [JTJL]

数位DP预处理，状压DP求答案。

发现前缀0可以合在一起处理而不用枚举长度……

J. The Hypnotic Spirals [JTJL]

给定一条等速螺线和n(<=10)条射线，形成对极坐标平面的一个划分，给定m(<=1e3)个点，求这些点所在区域的面积之和，注意一个区域可能有多个点。

对区域由内向外标号，计算每个点所属区间并去重，积分求和。

一些坑：

n为0的时候，m=0时答案为0，否则为-1

前两圈的极坐标轴所在区间需要特殊处理

补题

G J

JTJL

  • Unaccepted: J

sfiction

  • Unaccepted: G
附加文件