CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 2022暑期训练 ======
  - 牛客“蔚来杯”第2场 -7.23
  - 牛客“蔚来杯”第3场 -7.25
  - cf加训第1场 -7.28
  - 牛客“蔚来杯”第4场 -7.30
  - 牛客“蔚来杯”第5场 -8.1
  - cf加训第2场 -8.4
  - 牛客“蔚来杯”第6场 -8.6
  - 牛客“蔚来杯”第7场 -8.8
  - 牛客“蔚来杯”第8场 -8.13
  - 牛客“蔚来杯”第9场 -8.15
  - 牛客“蔚来杯”加训 -8.17
  - 牛客“蔚来杯”第10场 -8.20
  - cf加训第3场 -8.25
====== 牛客“蔚来杯”第2场 ======
7.23
总题数：12 现场过题数：3 总过题数：7

比赛过程

一开始就卡了签到题G，说实话不太应该，也是整个队伍的思路都有一些被带偏了...
没有看出根号n的结论，一直在想n或者logn量级的答案范围，卡到最后还是没过。
腰子哥开了E（腰）

在此期间xcj想出了K的正解，一发AC（K AC 84min）

陆续过了一些其他的简单题之后，J题又想直接套模板结果被多次卡精度（WA*3 -3)，

无奈之下用python重写竟然过了 (J AC 197min）

最后队伍里希望能够把G题过了再陆续开新题，但G题一直没有想到特别好的构造方法，属于是心态炸裂了

A

B

C

D（补题）
取log之后只需要利用spfa判断是否有正环，利用二分得到结果即可。
E
这题是一个比较常见的容斥题，考虑的是至少填多少个red然后再来去重，朴素算法复杂度是n^2的，有一个二项式反演的方法，将原式写成可以用ntt计算的形式，复杂度即nlogn

F

G
签到题

H（补题）
很直观的贪心感受就是每次都到最高点，然后到最高点的过程中尽可能地把最高的点再塞进去，实现时利用mutiset存点，利用迭代器遍历更新删除，再把当前存在电梯里的点利用优先队列维护依次踢出，得到答案。
I

J
最小二乘模板题
K
一个DP的三维转化，属于是简单题
L（补题）
二维的dp转化，当前到i这个位置最晚可以从哪个世界出发？因为卡空间的原因，需要利用原地滚动，要注意利用一组temp数组防止转移的时候被当前状态影响。

总结：
G题没过太伤了，很多能开的题没有开 -lbsbf





====== 牛客“蔚来杯”第3场 ======
7.25
总题数：10 现场过题数：2 总过题数：5

replay and dirt

一开始因为看C题过的人很多，其实很快就想到排序的策略了。因为本身排序的复杂度被出题人吓住了，一开始尝试了一发T了，结果一直在写Trie树，实际上出了一点点小问题连续WA，浪费了很长时间。

后续开A题，其实是个很简单的LCA合并的题，但因xcj在想办法拆解LCA，因为数组没清干净wa一发（-1）

之后迅速AC，但写的实在是太过于笨拙不忍直视，又浪费了大量时间。（xcj）

J题一看就是简单题，又是因为当时脑子不太清醒，算错了应该开的数组大小，段错误了半天（-4）

后来又没有判断无法到达的情况，WA一发（-5）

又浪费了大量的时间。因本身时间大量的被消耗（xcj）

腰子哥H题写SAM时模板略微有些抄错没过，赛后很快就过了遗憾败北

A

合并后缀LCA与前缀LCA即可得到答案。

B

C

D(补）solved by lbsbf

不难发现随即走由子节点向父节点走期望步数为2*size-1。
考虑删除的对于答案的影响：
对于选择的单向边，下面的子树每一步期望均没有变化而上面父亲相当于少了一个子树。

答案要统计给定主链的期望步数之和，对于不在主链上的点，若其到主链的路径上存在另一条单向边，则其影响会被离主链更近的单向边效果覆盖。
对于在主链上的边，若到1（终点）路径上存在另一条单向边，效果也会被覆盖。
统计答案时，考虑每条边对于主链上每一点的贡献，为-2*子树大小*该条边到主链上一点无其他单向边的概率（C(k-1,n-2-d),d为两点间距离)
统计答案即可，时间复杂度O（n）

E

F

G

H

I

J

把每条（点，边）映射成点之后连边，利用01bfs或者dij迅速计算出结果即可


总结：
又被卡签到题啦...为什么其他队C暴力一发就过了但是我们没有（委屈）想正解浪费了好多时间还没做出来 -lbsbf



====== cf加训第一场 ======
7.28
总题数：10 现场过题数：3 总过题数：3

replay and dirt

一开始xcj和腰子哥讨论A题，发现结论后腰子哥通过！（腰）

lbsbf睡过了1.5h，
回来的时候已经把A题过了，看E题，想了想大概是反悔贪心，写了一下发现细节有点问题，

过了一会想好了继续写，写出来以后交了一发，（WA -1)，
检查了一下发现忘记初始化vis数组时有可能会会出现问题，改了以后又交了一发 （AC 258min）

A
由于操作是翻倍和相加，所以可以考虑二进制，通过对位进行操作最终解决这一道题，没有罚时。
B

C

D solve by lbsbf

反悔贪心，每次选择要么选择最小的L和次小的L再将已选择的一个L转化为R，要么选择最小的L和最小的R，要么选择最小的R和次小的R再
将已选择的一个R转化成L，用两个优先队列分别维护L转化为R和R转化为L的最小代价，统计答案即可，时间复杂度O（nlogn）

细节：最小的L和R可能是同一个

E

F
根号分治的算法，大于根号和小于根号的分开考虑，朴素算法n根号n，没有什么技巧，一遍AC。
G

H

I

J

总结：
睡过了，对不起qaq...码代码速度也太慢了，要加强练习，知识面也太窄了，要多学习 -lbsbf
====== 牛客“蔚来杯”第4场 ======
7.30
总题数：14 现场过题数：3 总过题数：4

replay and dirt

xcj发现签到K，就开始写了，交了好几发WA，实在找不到问题

lbsbf发现签到N，开始写，一发AC （12：54）

debug K
发现K题Conner case n==1 ans应该为0，一发AC（13：53）

xcj发现D题很签，开始写，发现题目看错了，讨论主席树三位偏序，发现强制在线，又发现题目条件，确定三位前缀和，开始写，交了一发(WA)

从此开始了漫长的D题debug，三个人都不知道代码有什么问题，看了半天还重构了一下，还是没有过 一发（WA）

lbsbf和xmy讨论出A题做法，开始写，一发AC（15：34）

xcj发现H可做，写暴力，开始写 一发WA，其实暴力是对的，但是暴力也有暴力的策略，没有能够通过(WA-1)

lbsbf重构D 一发WA

xcj尝试H,lbsbf尝试D并与出题人确认数据生成问题，坐牢做到结束。

结束后发现数据生成问题，D 过了


A solved by lbsbf

不难发现，给定m后排列只需要要求w1+p1*w2 > w2+p2*w1即可（序列中两个数调换关系对序列前后均无影响）
先将n个数排序，排序后只会按顺序选择，由于m<=20,不难想到动态规划,dp[i][j],第一维为位置，第二维为选择个数。
从后往前转移即可 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]*pi+wi); O（nlogn+mn）

B

C

D

E

F

G

H

I

J

K

L

M

N solved by lbsbf

操作过程中每一位0，1个数不变，最终情况下任意两个数操作后不变，从数位上类似A⊆B的关系，因此变成了一道构造题
统计每一位1的个数，生成n个从大到小的数，生成时有1放1，没1放0，简单推式子后统计答案，最后gcd，O（n）

细节：注意0

总结

被D题搞得真的很痛苦，题面描述很像是把定义直接放到文件最前面而不是读入seed后再定义，比赛结果又很伤士气，调整心态重新来过吧。
比赛策略可能也有些问题，前期做水题过程中应该减少多个人对一道题的思考，多开题，后期做不出来题后要多讨论。打代码速度也要控制，
代码量小的情况下尽量做到想到正解后10min内过题。我本身熟练度也不太够，知识体系也不是很全，还要多练习 -lbsbf



====== 牛客“蔚来杯”第5场 ======

8.1 总题数11 过题数4 总过题数5

replay and dirt

腰子哥没来，开局xcj把b切了（B AC 12min)

尝试写K，以为很简单，结果读错题了（K WA -1）

实在不理解为什么会错，随便改了改又交了一发（K WA -2)

强行曲解题意找到原来的问题，又交了一发（K WA -3)

发现了奇数偶数不同情况（K AC 54min）

G题想了一会，马拉车，结果数组开小了（G SE -1）

开大了以后过了（G AC 100min）

H题一开始样例锅了，后来改过来以后过了一会才发现，交了一发(H AC 137min）

F题题意简单，赛场上因为纠结角度区间合并的问题，一直WA（一直到比赛结束）

比赛截止后学习了别人的区间并集的技巧，顺利通过。

======cf加训第2场======

总题数：12 过题数：6 总过题数：7

replay and dirt

腰子哥狂c场！今日高哥有事未能参加。

xmy和xcj 一共过了6道题 

xcj开场找到签到A，因为不小心把字符弄错了导致寄了两发（非常不应该）（12：39）


B.很简单的模拟，从a枚举到b，由于(n/a+…+n/b)是nlogn级别的，可以通过, 但是由于一开始写的cin，cout输入输出太慢，所以t了两发。

C.
 
D.这道题有一个性质，即如果相邻两段都能被整除的话，两段合起来也能被整除，所以答案是2^x, x表示最多可以分的段数。 

E. 

F.走格子问题很容易和组合数联系起来，这题有一个难点就是后面的常数项有点不好处理，非常数项的话就是很简单的组合数，然后经过一系列推导，发现常数项我们可以递推求得，于是可以在O(n)时间复杂度内解决该问题 

G.

H.

I.

J.可以将该问题转化为一个最小割的问题，由于这道题的条件比较特殊，度数小于等于三，所以很显然最小割要小于等于三，1和3我们都可以较为简单的求出来，剩下的情况即最小割为2的情形。 

K. 好像是一道策略题，具体是啥我忘了，当时手画几个觉得挺对的，然后就过了 

L.


xcj在比赛快要结束的时候发现I题其实很简单，但赛场上有一些急躁导致没能好好写出来，

一直没有注意点到线段的距离和点到直线的距离有不同的情况

赛后套用解析几何的模板很快就补出来了
======牛客“蔚来杯”第6场======

题目数：13 过题数：5 总过题数：7

腰子哥开局把j开了，交了一发，挂了（腰）（J WA -1)

改了改过了（J AC 34min）

lbsbf写G，写的有点慢，但是一发AC（G AC 49min）

写的过程中想到了B 的正解，一发AC（B AC 55min）

感觉M可做，写M，写刮了（腰） 

最后过了（M AC 100min）

开始乱搞A ，其实很快就写出来了，然后第一发忘记答案1到n的范围（A WA -1)

第二发忘记输出第一行（A WA -2)

第三方忘记删除文件操作（A WA -3)

第四发过了（A AC 125min）实在抱歉

开始了漫长的坐牢之旅期间尝试了两发I，均WA

======牛客“蔚来杯”第7场======

总题数：12 过题数：4 总过题数：6

xcj上来吧c开了，写了一发，挂了（xcj，）（C WA -1)

改了改，过了（C AC 30min）

lbsbf写F，第一发忘记考虑特殊情况n=1（其实也是后两个物品的情况）（F WA -1)

第二发忘记考虑最后两个物品的合并（F WA -2)

第三发忘记考虑第一轮合并过后首尾两个物品可能进行合并的情况（F WA -3)

第四发终于过了（F AC 84min）

开始读题G 弄懂题意后直接一发AC（G AC 138min）

腰子哥同时做出来J，过了G以后迅速写出，一发AC（J AC 157min）

同时宣布当天坐牢的开始




======牛客“蔚来杯”第8场======

8.13 总题数：12 过题数：1 总过题数：1

replay and dirt

腰子哥有事，今天非常的寄！

高哥对于F题很快有了思路，一发WA后找到了正解！（12：40）

但是却被卡常了，xcj帮助高哥优化了常数之后通过（14：00）

最后因为一直坐大牢，提前退出了

总结：
算法水平太次了，面对比较困难的题显得太笨。

======牛客“蔚来杯”第9场======
8.15 总题数：11 过题数：4 总过题数：5

replay and dirt

开始时xcj看到签到题A，不多思考一发线段树，迅速AC（12：12）

随后xcj又找到B为概率dp，推出公式过了样例之后T了（没有提前处理逆元，导致复杂度为n方log）

一开始没在意这个问题，以为是longlong的问题，改为int交了一发还是T，后来发觉是逆元的问题，提前处理之后有ME了（因为开了longlong）

改回int之后AC（13：15，多交了3发）

腰子哥尝试F题，本来以为过了结果赛后一直都没过，出现了一些问题没有解决

之后先后开了I、E、G，

G题由于笨拙的马拉车写法和稀烂的hash技巧导致写的时间较长同时因为精度问题交了一发（WA -1)，
int 改longlong 后交一发 仍然WA （WA -2)
在计算过程中注意爆longlong 加入int128后AC (G AC 264min）

I题因为一开始考虑用线段树优化没有能够得到正确的复杂度，在最后腰子哥用单调栈优化绝杀（16：56）

E题赛后补过，因为是构造题，了解思路之后很好写出。

总结：
对于题目的感觉还是太稚嫩，要是能在想出解法之后迅速的能够AC，很多麻烦都会被避免。
======牛客“蔚来杯”加训======
8.17 总题数13 过题数3 总过题数3

replay and dirt

开场高哥找到签到M，迅速AC（12：14）

随后腰子哥两次DFS，完成了与LCA相关的H题（12：48）

之后xcj开始看E题，找到结论之后迅速就准备通过，但题意一直读错了

题意读错之后不断修正，但没法找到正确的题意，导致一直WA（13-15点）

此时高哥开始尝试G，维护线段树但WA了，之后一起解读E题题意

终于在15：20理解，AC了E

之后xcj尝试乱搞J，但没法AC，随后发觉无题可开，寄！

总结：

这次比赛大家大多有一些事，中途退场，没有好好的去努力思考。还是需要不断地努力，不断地克服困难，才能最终获得成功。


======牛客“蔚来杯”第10场======
8.20 总题数11 过题数3 总过题数3

replay and dirt

腰子哥没来，开局坐牢

高哥看出H题只与两个人的血量有关，一发暴力复杂度太高，记忆化搜索写挂了导致2^m逆天复杂度，没过（TLE -1 12：42）


后来手搓公式顺利通过（H AC 93min）

xcj看出F题结论，一发ME（因为忘记打vis标记了）

后看出问题得以AC（13：49）

本来以为又要坐牢，E题尝试贪心+二分图匹配，在正确性与复杂度的双重怀疑中一发AC（14：32）

之后确实坐大牢，I题被标题欺骗，运用了FFT，时间复杂度不合适，因为太过于纠结N*M的超高复杂度，却忘了鸽巢原理（最多只有2e7次就可以找到答案），一直没能通过该题。

时间到最后进入经典惩罚测评机环节，以为FFT被卡常，疯狂提交I题，无一发通过。

总结：

太容易被题目过题人数、题目所提示的题意影响心态和对于题目的看法，没有抓住题目本质的能力。

可能归咎到底还是经验不足，算法熟练度、灵活运用的能力并没有在大量的题目里得到锻炼，同时算法的了解广度也有些低。

======cf加训第3场======

总题数：10 过题数：4 总过题数：4

replay and dirt

腰子哥狂C

和腰子哥简单讨论I题题意后，发现只用考虑每一轮新增的1的个数即可，由xmy写完，但是忘记取模，wa了一发。

B.考虑1的个数就行，如果1的个数大于一半，无法匹配完全，否则可以。 由xmy写完，没有fst。
H.挺奇妙的一道题，二分图上dp，很常见的一个套路，即考虑分段式dp，用左边的点把右边的点连起来，即dp[i][j],表示到第i个点，有j条链的方案数，要注意左边的点和右边的点对状态的影响不一样，然后链内部是有顺序的，所以不用考虑要连哪一端。样例很大，所以一遍过了。

lbsbf想了很久F，后来发现是一个简单的反悔贪心，一发AC（256min）
CVBB ACM Team

用户工具

站点工具

页面工具
