CSP2021 J/S复赛游记(Csp2021 J / s semi finals travel notes)

同机房同学的:

  • fffngzzh
  • lzqy_
  • SunsetGlow95

10月3日至10月6日

学校组织S组模拟赛,但全都是原题大赛,所以每次都考了\(300+\)

10月9日

开始在机房晚上集训,刷了一些往年复赛的题目,16日也有打月赛,打了之后比赛情况暴涨50分。

最后三天把黄道绿的模板和部分蓝的模板过了一遍。

10月21日

这天是集训的最后一天,中途教练直接黑屏肃静,讲了一些有关策略的东西:
“你就直接把电脑的桌面改了,文件读写什么的注意事项全部写上”。

“一定要记住,不要死磕一道题。可以出去上个厕所,散散心。”

这两句话是我记得最清楚的两句话,也是我记得最不清楚的两句话。

10月23日

J组(8:30~12:00)

7:50进的考场,在那坐了好久都才开始。

我坐在离大屏幕比较远的地方,我把解压密码写下来之后我隔壁让我给他看密码,不会算我作弊吧。

直接用30min看了一下题。

T1是送的,写了之后还写了暴力对拍。用了不到10min。

之后开T3,不难发现是暴力匹配,我还用类似状压的方式存储每个IP串,时间复杂度\(O(n^2)\),也写了暴力对拍,用了大概1h。

之后开T2,发现修改次数不多,就每次修改都排个序,并用一个数组存答案。

之后发现每次修改只要让修改的数左跳或右跳就行了,优化到\(O(n\log n+Q+5000n)\)

用优化前的代码对拍,共用1h。

T4感觉没啥复杂度严谨的做法,之后用并查集维护删除数(用并查集代替链表)之后暴力删,删完一个就跳到下一个块里,如果下一个块和这一个块的元素一样就一直往后跳,也写了暴力对拍,设初始时有\(m\)个块,删除有\(k\)轮,复杂度就是\(O(n+mk)\),感觉应该有70分,共用30min。

发现T4在随机数据下好像跑得动\(200,000\),之后又试图hack也没超时。

最后不到半小时一直在对拍和检查文件。

10月三十日发现前导零判错了,过不去多半要去世

0.0.0.0:00

估分:\(100+100+60(100)+70(100)=330(400)\)

洛谷民间数据:\(100+100+100+100=400\)

10月30日初评:\(100+100+70+80=350\)

S组(14:30~18:30)

考场要求14:00进去,但是14:20才让我们进机房。

还是一样用了30min看了看题。

感觉T1可能是奇怪的数据结构,T2是码量大的区间DP,T3应该是思维题,T4不可做。

之后悲剧性的开了T2。

前一个小时把题目看成“超级括号序列不能有超过\(k\)个”,之后第一个样例输出4,直接硬调到比赛开始后1h。

*

之后思考T1用了10min,因为虽然想听教练的话,但是我还是想调T2,就没想出个所以然,用10min写了个40分的暴力就接着做T2。

重看了T2题面才发现只是\(S\)不能有超过\(k\)个,之后才开始打正解。

*

20min后打出来了,但是第二个样例输出28。我就开始调。

结果考场Dev Cpp不支持调试(不知道为什么,上午也有这个情况),只能输出调试。

直接调了1h发现这个情况没有判重,又开始写,写了之后发现输出20,不知道是写挂了还是有些重复的情况没有判出来。

ABC

又调试调到还有半小时结束时还没调处来……就去把T3的40写了,可能我很暴躁,一个dfs写了20min。

最后10min我只能绝望地盯着T2的代码看着,除了检查文件什么都干不了。

最后5min我开始回忆被我抛弃的T1,居然想出正解了:用线段树或某种数据结构算出每个飞机停第几个廊桥,之后开个桶算答案。

出考场之后发现T2的也会重复……

ASBSC

估分:\(40+0+40+0=80\)

洛谷民间数据:\(40+0+40+0=80\)

10月30日初评:\(60+0+40+0=100\),T1多给我20分耶,不过还是没有1=吧。

upd 11月8日:发现考场上没看到T3的\(2n\)个数中\(1,2,\cdots,n\)每个分别出现两次,看到之后就会做了……

总结

J组的T3或许将是我这次的败笔,被卡掉\(30\)分,虽然我对拍了,但是我没有拍出这个问题,这说明不能只对拍,还应该自己出数据。

S组是最大的悲剧,T2是一个大坑,而我却要往里跳。

最后交上去的代码应该去年的我也会写,也许去年的我还能拿更高的分数。

但实际上如果我处理会不会过呢,所以实力其实还是不够的。而且想到解法不能急于写代码,要先在草稿纸上看看有没有别的情况,在保证解法正确性、了解代码细节的情况下开始写代码。

ASBSC

当然,策略也是有问题的,先把T1AC,T3拿40分之后写T2,这样可能心态会好些。

而且T3居然还看漏条件了……这说明要仔细看题,不能看漏题目条件。

教练的那两句话,我真的有记住吗……

初中的OI比赛也就差不多结束了,接下来还要中考呢,能读我们学校高中部就最好了。

这次也不过算是一次试水吧,虽然这一年中所有学习的东西几乎都没在比赛中用到。

希望中考后我还能再回到机房,再次看到那些熟悉的面孔。

整理一下

  • 不能只对拍,还应该自己出数据
  • 想到解法不能急于写代码,要先在草稿纸上看看有没有别的情况,在保证解法正确性、了解代码细节的情况下开始写代码
  • 要尽可能保持良好的心态,卡在一题上可以出去散心
  • 不能一直执着于一道题,学会取舍
  • 要仔细看题,不能看漏题目条件
————————

Students in the same computer room:

  • fffngzzh
  • lzqy_
  • SunsetGlow95

October 3 to October 6

The school organized group s simulation competitions, but they were all original competitions, so they took \ (300 + \) every time

October 9th

We began to train in the computer room at night and brushed some semi-finals in previous years. There was also a monthly competition on the 16th. After playing, the competition soared by 50 points.

In the last three days, I went through the zodiac green template and some blue templates.

October 21st

This day was the last day of the training. During the training, the coach went straight to the black screen and talked about some strategies:
“You just change the desktop of the computer and write all the precautions for reading and writing files.”.

“Remember, don’t stick to a problem. You can go out to the bathroom and relax.”

These two sentences are the two sentences I remember most clearly and the two sentences I remember least clearly.

October 23rd

Group J (8:30 ~ 12:00)

7: 50 into the examination room, sat there for a long time before it began.

I sat far away from the big screen. After I wrote down the decompression password, my next door asked me to show him the password. It won’t be my cheating.

Read the question directly in 30min.

T1 was sent. After writing it, it also wrote violence against shooting. It took less than 10 minutes.

After opening T3, it is not difficult to find that it is a violent match. I also store each IP string in a similar way. The time complexity is \ (O (n ^ 2) \), and I also wrote a violent beat, which took about 1H.

After opening T2, it is found that the number of modifications is not much, so each modification is arranged in order, and an array is used to save the answers.

After that, it was found that for each modification, just let the number of modifications jump left or right, and optimize it to \ (O (n \ log n + Q + 5000n) \)

Beat with the code before optimization for 1H.

T4 feels that there is no rigorous method of complexity. After that, use the parallel query set to maintain the deletion number (use the parallel query set instead of the linked list), and then delete it violently. After deleting one, it jumps to the next block. If the next block is the same as the elements of this block, it jumps back all the time. It also writes the violent beat. It is set that there are \ (m \) blocks at the beginning, there are \ (K \) rounds to delete, and the complexity is \ (O (n + MK) \), I think it should be 70 points, sharing 30 minutes.

It was found that T4 seemed to be able to run \ (200000 \) under random data, and then tried hack without timeout.

Last less than half an hour has been shooting and checking documents.

On October 30, it was found that the leading zero was wrongly judged, and most of them would die if they couldn’t pass

0.0.0.0:00

Estimated score: \ (100 + 100 + 60 (100) + 70 (100) = 330 (400) \)

Luogu folk data: \ (100 + 100 + 100 + 100 = 400 \)

Preliminary evaluation on October 30: \ (100 + 100 + 70 + 80 = 350 \)

Group s (14:30 ~ 18:30)

The examination room asked us to enter at 14:00, but we were not allowed to enter the computer room until 14:20.

It took 30 minutes to read the questions.

It seems that T1 may be a strange data structure, T2 is an interval dp with a large number of codes, T3 should be a thinking problem, and T4 should not be done.

Then it opened tragically.

In the first hour, the title was regarded as “no more than \ (K \) super bracket sequences”, and then the first example output 4, which was directly hard adjusted to 1h after the start of the game.

*

After that, it took 10 minutes to think about T1, because although I wanted to listen to the coach, I still wanted to adjust T2, so I didn’t think of a reason. However, I wrote a 40 point violence in 10 minutes and then did T2.

After reviewing the T2 question, I found that there should be no more than \ (K \) of \ (s \), and then began to correct the solution.

*

After 20 minutes, it is typed, but the second sample output is 28. I started adjusting.

As a result, dev CPP in the examination room does not support debugging (I don’t know why, this is also the case in the morning), and can only output debugging.

After 1 hour of direct adjustment, it was found that there was no duplication judgment and started writing again. After writing, it was found that the output was 20. I don’t know whether the writing hung up or some repeated cases were not judged.

ABC

It was adjusted to half an hour before the end of the debugging… I went to write the 40 of T3. Maybe I was very angry and wrote a DFS for 20 minutes.

In the last 10 minutes, I could only stare at the T2 code in despair. I couldn’t do anything except checking the file.

In the last five minutes, I began to recall the T1 abandoned by me, and actually came up with a positive solution: calculate the number of corridor bridges where each aircraft stops with a segment tree or some data structure, and then open a bucket to calculate the answer.

After leaving the examination room, I found that T2 will also repeat

ASBSC

Estimated score: \ (40 + 0 + 40 + 0 = 80 \)

Luogu folk data: \ (40 + 0 + 40 + 0 = 80 \)

Initial comment on October 30: \ (60 + 0 + 40 + 0 = 100 \), T1 gave me 20 more points, but I still didn’t have 1 =.

UPD November 8: it was found that \ (1,2, \ cdots, n \) of the \ (2n \) number of T3 not seen in the examination room appeared twice respectively. After seeing it, you will do it

summary

T3 of group J may be my failure this time, and I was stuck with \ (30 \) points. Although I took the right shot, I didn’t take this problem, which shows that I should not only take the right shot, but also give my own data.

Group s is the biggest tragedy. T2 is a big pit, but I have to jump in.

Finally, I will write the code handed in last year. Maybe I can get higher scores last year.

But in fact, if I deal with it, will it be too much, so my strength is not enough. And when you think of the solution, you can’t rush to write code. You should first see if there are other situations on the draft paper, and start writing code under the condition of ensuring the correctness of the solution and understanding the details of the code.

ASBSC

Of course, the strategy is also problematic. First get 40 points for t1ac and T3 and then write T2. In this way, the mentality may be better.

And T3 actually missed the conditions… This shows that we should look at the questions carefully and can’t miss the conditions.

Did I really remember the two words of the coach

The OI competition in junior high school is almost over, and there will be a high school entrance examination next. It’s best to study in the high school Department of our school.

This is just a test of the water, although almost all the things learned this year were not used in the competition.

I hope I can go back to the computer room after the high school entrance examination and see those familiar faces again.

Tidy up

  • You can’t just shoot, you should also produce your own data
  • When you think of the solution, you can’t rush to write code. You should first check whether there are other situations on the draft paper, and start writing code under the condition of ensuring the correctness of the solution and understanding the details of the code
  • To maintain a good attitude as much as possible, you can go out to relax if you get stuck in a problem
  • You can’t always stick to a problem and learn to choose
  • We should look at the questions carefully and not miss the conditions of the questions