2020-team1-C021

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]

== 概述 ==

solved: 8/12  dirt: 52%

rank: 29

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

== 总结 ==

Grammy：

这场感觉自己的状态比较萎靡，有点想题想不对，写题写不对的感觉

开场开了A，糊了一个假做法，声称自己会了，然后看榜J过了很多就去开J，J又糊了一个分治假做法，写完发现不对，osc给了正解的思路，写完之后好像是数组爆了一发，TLE爆了一发（写的时候感觉log^2能过但事实上不太行）

然后osc丢过来一个C，上去写了过了后开始准备A。

A写的时候完全没有考虑空间，写完直接MLE on test1，马上改了离线，交上去wa了，百思不得其解，osc听了做法感觉没问题，查了半个多小时找不到错，就把lwn叫过来给他讲做法。讲到一半发现自己假了，开始试图从原来的思路去fix，推了半天不等式推了一个错的以为自己fix好了，上去写着写着发现不对劲又下来了，推了一会不等式推对了发现自己原来的思路没救，于是fix了一个递归的做法，每次递归下去规模至少折半所以是可行的，又上去改，改了又wa了
，查了一会突然意识到因为离线了，之前层的信息没有保留，询问的时候递归是没救的。想了想又改成了先递归完分成log个询问再离线，才终于过了A。赛后发现做法复杂化了。

D是Hopcraft板子题，还好补了第二天甚至又用到了（）

Oscar: 

开场写了个K和G，准备把C丢给Grammy，接到Grammy 假做法的J后发现有个简单想法，让Grammy继续写。过了以后花了1分钟丢了个C的做法过去然后去找Sakuya讨论E。

Sakuya把E过了以后Grammy就一直在A。Oscar大概想明白了F和L，把F丢给Grammy后上去写L，调了好久。最后上去抄圆方树板子，让Grammy推式子，还是没来得及。

lwn_16:

sblwn开场就看不懂K的题意，然后今天也只出了一道E，实力太菜还需要被教写代码

其实赛场后发现这个A我也能嘴（？

我其实很想知道在我开场出完一道题后，后面我的定位是什么

== 题解 ==

A: 如果空间够的话做法是算出每个点往下2的幂的三角形以及每个点作为左上角的正方形。现在空间不够就把询问离线掉

B: 给定终点计算答案时枚举2个方向，或者1个垂直坐标轴的方向只走一步+2个斜着的方向更新答案

枚举起点两两交点周围的4个点作为终点更新答案，常数过大可以shuffle枚举顺序然后加卡时

C: 竖着的刀从下往上枚举点后二分位置，横着的刀同理，算出每个点对应的蛋糕块，用map维护答案

D: hopcraft板子题（？

E: 分块打表算阶乘的前缀和，顺着曲线转一圈并用转的角度判断正负

F: dp维护有没有B、有没有C、AB之间的位置数、BC之间的位置数、CD之间的位置数，然后dp，注意更新顺序

G: 枚举相邻蜂巢，矩乘

H: 

I: [Baltic2016][BZOJ5184] Spiral

J: 固定左端点后会导致区间or变化的右端点数只有log个，排序后枚举更新答案

K: for一遍

L: 枚举开头位置的差diff，双指针求当前区间需要多少步变为相同串，对字符串有交和没有交统计答案，没有交的情况位置数量差就是答案，有交的情况按模diff的同余类维护出总数-众数的和就是答案，需要维护每种同余类下字符出现次数和出现次数的出现次数，以及当前每种同余类下的众数出现次数和当前答案。

[/wiki/2020-team1 返回]

概述

solved: 8/12 dirt: 52%

rank: 29

总结

Grammy：

这场感觉自己的状态比较萎靡，有点想题想不对，写题写不对的感觉

开场开了A，糊了一个假做法，声称自己会了，然后看榜J过了很多就去开J，J又糊了一个分治假做法，写完发现不对，osc给了正解的思路，写完之后好像是数组爆了一发，TLE爆了一发（写的时候感觉log^2能过但事实上不太行）

然后osc丢过来一个C，上去写了过了后开始准备A。

A写的时候完全没有考虑空间，写完直接MLE on test1，马上改了离线，交上去wa了，百思不得其解，osc听了做法感觉没问题，查了半个多小时找不到错，就把lwn叫过来给他讲做法。讲到一半发现自己假了，开始试图从原来的思路去fix，推了半天不等式推了一个错的以为自己fix好了，上去写着写着发现不对劲又下来了，推了一会不等式推对了发现自己原来的思路没救，于是fix了一个递归的做法，每次递归下去规模至少折半所以是可行的，又上去改，改了又wa了

，查了一会突然意识到因为离线了，之前层的信息没有保留，询问的时候递归是没救的。想了想又改成了先递归完分成log个询问再离线，才终于过了A。赛后发现做法复杂化了。

D是Hopcraft板子题，还好补了第二天甚至又用到了（）

Oscar:

开场写了个K和G，准备把C丢给Grammy，接到Grammy 假做法的J后发现有个简单想法，让Grammy继续写。过了以后花了1分钟丢了个C的做法过去然后去找Sakuya讨论E。

Sakuya把E过了以后Grammy就一直在A。Oscar大概想明白了F和L，把F丢给Grammy后上去写L，调了好久。最后上去抄圆方树板子，让Grammy推式子，还是没来得及。

lwn_16:

sblwn开场就看不懂K的题意，然后今天也只出了一道E，实力太菜还需要被教写代码

其实赛场后发现这个A我也能嘴（？

我其实很想知道在我开场出完一道题后，后面我的定位是什么

题解

A: 如果空间够的话做法是算出每个点往下2的幂的三角形以及每个点作为左上角的正方形。现在空间不够就把询问离线掉

B: 给定终点计算答案时枚举2个方向，或者1个垂直坐标轴的方向只走一步+2个斜着的方向更新答案

枚举起点两两交点周围的4个点作为终点更新答案，常数过大可以shuffle枚举顺序然后加卡时

C: 竖着的刀从下往上枚举点后二分位置，横着的刀同理，算出每个点对应的蛋糕块，用map维护答案

D: hopcraft板子题（？

E: 分块打表算阶乘的前缀和，顺着曲线转一圈并用转的角度判断正负

F: dp维护有没有B、有没有C、AB之间的位置数、BC之间的位置数、CD之间的位置数，然后dp，注意更新顺序

G: 枚举相邻蜂巢，矩乘

H:

I: [Baltic2016][BZOJ5184] Spiral

J: 固定左端点后会导致区间or变化的右端点数只有log个，排序后枚举更新答案

K: for一遍

L: 枚举开头位置的差diff，双指针求当前区间需要多少步变为相同串，对字符串有交和没有交统计答案，没有交的情况位置数量差就是答案，有交的情况按模diff的同余类维护出总数-众数的和就是答案，需要维护每种同余类下字符出现次数和出现次数的出现次数，以及当前每种同余类下的众数出现次数和当前答案。

附加文件