东北赛回顾

1001

中期的时候喵了一下这题,成功把模型转换成最小生成树,然后就不会做了。

1002

网络流裸题。ly写完+WA*2,AC。

1003

题目大意:定义了一个模(x+1)的类似hash的函数F(x),再定义了一个函数g(n, m),表示一个数n经过mF嵌套后得到的值。求g(n, 1)g(n, m)的和。

solution:发现有人过了此题,我就去看了。开始感觉没什么思路,搞不懂这个F(x)是在干啥,也找不到什么规律。思考了一会之后感觉这个%(x+1)必有蹊跷,这样x只增不减,说不定很快就收敛了。然后迅速写了一个暴力发现果然是这样,交了一下WA。原来我的F(x)x=0的时候会输出1。。。修改了一下就过了。成功贡献一发罚时。

1004

题目大意:糖豆人模拟题。一个皇冠在0-H的高度上以1/s的速度上下移动,当且仅当皇冠高度小于等于h时,糖豆人才能够得着。给出每个人到达皇冠的时间和延迟,求最后谁最先摸到皇冠。

solution:本场我过的第二道题(说实话第一次看到此题的时候直接就跳了,以为会花很多时间)。做法很简单,计算到达皇冠的时候皇冠的位置,如果能够得着就直接结束,不行就再模拟计算一下皇冠下一次到达h的时间。最后加上延时sort一下。

1005

题目大意:构造一个包含NN01向量的向量组,每个向量中1的个数为K,且向量组在XOR运算下线性无关。

solution:写完1003就来看这题了,本以为可以通过贪心+线性基求第k大+二分过此题,然后发现事情没有这么简单,挣扎了10分钟后放弃了去看ly题。最后在czq写了一个较为奇妙但又WA又T的暴力然后不经意间看到了输出的答案发现了构造方法后PE了一下才A掉了这题(这合理吗.jpg)。

1007

题目大意:有K个人在打牌。有A,B,G,P四种牌,牌上有一个数字x。现在要给这K个人轮流发一共N张牌,每发一张牌会覆盖那个人上一次得到的牌。记cnt_i为发了这张牌后,桌面上数字和为5的牌的种类数。求cnt_1cnt_N的和。

solution:本场我过的第一题。说实话这题意我看了足足有5min。交的第一发初始化把i打成了另一个变量然后WA了一下。成功贡献一发罚时。做法也很简单,直接模拟。

1008

题目大意:给一个小写字符串,每次可以将一个连续的子串压缩,压缩方式是将连续的字母以单字母紧接一个16进制数来表示个数。现可以从原串中最多删去一个字母(删去后,两端的字符串不连续),求一个压缩结果最短的方案。若有多个方案使压缩结果最短,输出字典序最小的。

solution:看完1009就来看此题,和ly讨论了一下大致做法后就开写。一共WA了四次,原因是没发现可以选择子区间压缩:总结,一道阅读理解题+模拟题。做法就是将连续的字母提取出来,然后分为几种情况考虑。1.只有一个字母。2.连续两个字母。3.连续大于2个。对于第一种情况,不压缩比压缩优,于是删了后会使长度减少1;若删了后字典序变小(与后一个字母比较),则优先考虑位置靠前的否则尽量靠后。对于第二种情况,压缩比不压缩优(a2比aa字典序小),删了后会形成单字母,长度减少1,而字典序一定会增大,则尽量往后考虑。对于第三种情况,又分为两种情况:退位和不退位。退位(1000->FFF)长度-1,字典序增大,尽量往后考虑。不退位(1100->10FF, 1A00->19FF,etc.)长度不变,字典序减小,那么在长度-1不存在的情况下,选择首位删除。

1009

题目大意:给一个n*ndis矩阵,保证所对应的图联通且的边长是定值,求一个边数最小的子图,满足Dis矩阵和原dis矩阵相同。输出边数。

solution:在看1005的时候听ly高呼说这是多校原题()。我想那应该稳了。过了一会ly说复杂度不太对,然后我去看了一下题,看见了边长相等这个条件,此题瞬间变成了签到题(这个条件需要稍微细心一点才能发现,出题人还是需要在题面中强调一下)。ly发现事情真相后破口大骂,随即A掉此题。

1011

本场过的最后一题。当时不知道是否可以连续憋气,加上写了一个倍增维护答案,就一直WA。然后发现K大于1000的时候我的数组会溢出(竟然没有显示RE)。最后输入K的时候对1000取了一个min就A了。感觉挺离谱的。标程是用的单调队列,比倍增少个log,还很好写。当时怎么没想到用单调队列啊。。

1012

czq肝到比赛结束依然没有肝出来。

1013

签到题,czq写完一发A。

总结

这次夺冠也是我万万没有想到的。一些不足之处在于边界情况忘判导致的罚时以及题意阅读上的疏漏。

发表评论

邮箱地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>