2022 / 4 / 11 exam summary

7:20~7:40

Soon found T1 Laws
But the classification discussion is extremely complicated , Don't want to be reckless as soon as you come up
So jump first

7:40~8:30

T2 Try to halve , Root division
In the end, nothing happened , Yes 30 The pressure of the minute

8:30~9:00

T3 It looks interesting , Write it first 60pts Hash
But it seems that the error rate is quite high , But if you use double hash, it will be very slow
Finally gave up
Wanted to think , Found that when m Greater than $sqrtn$ when , There are few fundamentally different answer strings
But it won't work , Go back and write T1 了

9:00~10:40

Write T1
Originally planned to write dsu on tree But later it was found that only a doubling was needed
The rest is classified discussion
Finished writing the sample , I also constructed several groups of small samples by hand , No problem

10:40~11:00

Keep thinking T3, The discovery problem can be transformed into the counting problem on the prefix tree and suffix tree
It seems that I have done many such counting problems of two trees
Divide and conquer on the first tree / Point divide and conquer , Build virtual tree statistics on the second tree
So I found that doing so can count the total number of answers , But you can't count every
Mind blowing up

11:00~11:10

Wanted to think T2 Can it be tolerated , Not very good

11:10~11:40

Find out T3 It seems that the root division of water can be divided into many parts
Start writing immediately , But I finally found it false

Exam summary

T1
First , Violence should be written first , Instead of finding a positive solution and being reckless
secondly , Although this question won't beat to each other , But I can still write checker Check it
Third , Some mentally retarded mistakes cannot be made again
T3
hash Hang up
I knew it would overflow naturally
The thinking of positive solution is similar to that of examination , Just use dsu+ Tree array statistics , Then you can maintain the value of each position