A correction book full of sad tears

I am （ Konnyaku ） several times wind (WA) wind (dao) rain (zi) rain (bi), The following huge pits are listed ：

    1. Cycle sequence error （ Section DP）.

    2. The array definition is smaller , subject （ maze , Line segment tree , Link string , Loop around the array , Chairman tree ） Given n,m It is not the actual storage size . Be careful when calculating , And after that, we should check .

    3. When setting the boundary, you must pay attention to , Draw a sketch and make a simple data simulation , A little more is endless regret .

    4.< still <=, Divisible or decimal , Many details of judgment , Be sure to dig through the topic , Each condition is listed , Ensure no repetition and no leakage .

    5.freopen.

    6.long long It's a huge pit , Sometimes the data is obscene , It doesn't seem to explode on the surface int, But the intermediate operation process may also explode , Be sure to pay attention to . When inputting and outputting windows System is "%I64d",（ uppercase i） But the evaluation environment Linux System is "%lld",（ Lowercase l）, Generally, if you want to hand it in for testing "%lld", Don't get it wrong （cf Is to use the %I64d）. Some questions are even worse , involves 10 To the power of , Data offset longlong The upper bound of , Finally, take a 10 Just blow up longlong 了 , Use unsigned long long.

    7. Do not forget to modify after a lot of optimization ...

    8. Multiple groups of data are cleared ...

    9.mod If there is a negative number in the middle （ For example, tolerance and exclusion ）, final ans must do (ans+mod)%mod  !!!    There are others mod yes 1234567891 And so on int Add up to blow up ,attention!!! And be careful not to put INF Add up , take min！

    10. Global variables are used as local variables in recursion Ten (WA) branch (dao) fast (zi) Happy (bi)...（dfs, Take the right and check the collection ）

    11. Judge binary numbers x Of the y Whether the bit is one , use x>>y&1, And don't use x&1<<y, Because the result of the latter may be 2 To the powers of , stay if Judge ==1 It's easy to make a mistake when you

    12.struct node{ node(int a,int b):a(a),b(b){} } Inside node(int a,int b) It is better not to write node(int a=0,int b=0), That would make the memory ten times larger ..

    13.dfs If the number of recursion layers is small and the code is short, it is also recommended to add inline...

    14. When you find that your code is almost the same as others, but you are WA perhaps RE, Or you can stick other people's code over, but you can't , Most of the time, the array is out of bounds and changed to the next array 0 Location or something .. When an array is out of bounds, there will often be strange errors that can not be adjusted even if it is autistic （ And it's often a negative number ）..

    15. That kind of need unsigned int The range of nausea data is 1<<31 Pay attention to , This is wrong , need 1u<<31 perhaps 1ll<<31, and 1u<<32 yes 0（2019 Provincial election D1T1 Therefore, zero explosion ..）

    add： build Trie Tree space , If there is k side , There is k+1 A little bit , The space should be open maxn*(k+1)（<2^k Namely k side ）

    16. When you need the information of the original array subscript after sorting an array , Note that the array is sorted back by number （ Or open another array to store the original information ）

    17.dfs use vis When the array judges the loop or the cost flow , Pay attention to the last vis=0 Has it been executed , Not halfway return. When the base ring tree judges the ring, if it is an undirected graph, the second access should compare the depth , If it is a directed graph, you should determine whether it is on the stack .

    18. To find the inverse, use x^(mod-2) The power must be noted mod Is it a prime number ..（ Some questions are input mod, The habitual inverse element is written as mod-2 Power . Then autistic , Should be φ(mod)-1 Power ）

    19.two pointer As well as the modification operation when the double pointer moves, you should pay attention to whether it is correct , Most of the time the operation is reversible , The modification of moving the right endpoint is undone when moving the left endpoint

    20. Don't forget to write a segment tree pushdown and pushup（ Pay attention to maintenance when you don't write a function ）

    21. Pay attention to the edge weight when calculating the diameter on the tree , Don't put the dis Easy to write dep..

    22. hold id[i]=i Array by A When sorting the weights of an array, remember that id[i] Instead of directly substituting i...

    23. The graph with special treatment such as base ring tree should pay attention to whether the graph is connected , There may be more than one special point set

    24. about NOIP Level string nausea Simulation question , Best use getchar(), Special characters and space line breaks should be tested , There may be no line break at the end of the file EOF.

    25. When backpacking, you must pay attention to subtracting the array to avoid crossing the bounds ！！！

    26. When the problem has both the maximum value and the module operation , Note that the maximum value should be taken from the original value , You can't use the value after the module ！！！

    27. Write KD The evaluation function must be checked when the tree is , Be careful longlong, also nth_element Don't forget to add cmp！（ Not written cmp It's hard not to make compilation errors , And the small data can not be tried out ...）

    28. When optimizing the slope, if the problem maker opens the range to 1e16 above , When comparing the slope and the output, you have to use long double 了 , in addition , When optimizing the slope, pay attention to the following steps: x Sort ,x When equal, you must also press y Sorting can ensure the correct stack ！（ If it is x Orderly and y Disorder can be used P-S[tp] And S[tp]-S[tp-1] Compare the slope ( If you use cross product, you can only add special judgment ）.

    29.O(nlogn)~O(1) seek LCA Pay attention to ST The size of the table is 2*n！ When doubling, also note that the cycle boundary is 2*n！

    30. When writing about the rule of division, pay attention to the father on the tree. Don't save him as the father on the tree ！ The son on the dot tree needs to return ！

    31. When writing a double hash, if you use both ULL Note that the intermediate process of module taking cannot be negative (ULL No negative number )！

    32. Computational geometry involves point product, cross product and so on fabs, Maybe positive and negative will determine the direction ！

    33. Write 2^log( The number ) Note that the array size is not on n But open 2^log( The number )！！ Especially when the original array is regarded as an array of record numbers ！

    34.cdq When divide and conquer, note that when the first dimension is the same, it should be sorted according to the second dimension ！

    35. hold id[i] Do not forget to write when sorting according to the weight of another array sort(id+1,id+1+n,cmp); cmp!!!!!

    36. When the data structure （ Line segment tree /LCT） There is maintenance in “ Leftmost in subtree / The rightmost key ” When there is an interval reversal mark , Or change the information into whether there are key points in the subtree , Then at the time of inquiry, two minutes ; Either the leftmost and rightmost must be saved at the same time , Exchange information when flipping , You can't just flip the tag without flipping the left and right information ！！

    37. When merging two pieces of information (vector.resize, Minkowski ), Especially when the initial value is the first term on both sides , Pay attention to judge whether a piece is empty ！

    38. Mathematical problem derivation , Involving the number of combinations, etc , Note that the range of summation is possible according to the number of combinations n>=m Smaller , Thus simplifying the operation of combinatorial numbers .

    39. When writing a puzzle, you must pay attention to the execution of a certain section return 0 / exit(0), Don't go into other situations , It is easy to ignore this point after debugging and modifying , Pay attention to inspection ！！

---

A little summary ：

    1. Concerned about data range , Many times the range will give you the type of positive solution , Let you find the right direction , And space and time should also be paid attention to

    2. Let yourself keep a relaxed mood to do questions , No hurry, no slow .

    3. Get the question , Think about its type , Should I use the learned algorithm , Or mathematical methods , Or enumerate , Positive solutions often do not go beyond what you have learned , It's just that I haven't really learned it well , To master ideas and methods is AC The key to , As for the ability to implement code , It's up to you to write questions .

    4.0 Cannot divide , When calculating division, make sure that the denominator variable is not 0, Find ways to avoid this problem , Sometimes the problem is fatal , It can be used to judge whether the problem has a solution .

    5. Try to make your program easy to understand , Think about some details clearly , Do you need special treatment , Sometimes the algorithm of the program can actually avoid some data that looks very special , Let each if All have value , If your program requires too much special handling , Then it must not be a good program , Be sure to figure out what the program should do at each stage , Where to deal with , How to deal with the simplest , Most right , Think well before you start .

    6. High precision operation is easy to time out when there are many bits , Pressure level treatment can be considered （ For details, please see High precision square ）  

    7. If you want to cheat points, you must do a little better , Try to optimize , Some obvious optimizations will have obvious effects , Especially the arrangement and sorting . The essence of the algorithm is to solve problems in a certain order .

    8.bitset Plus, if you quit halfway, you may even pass 1000 Of n^4... Faith is important .

    9. If you can't think of it, you can rebuild your thinking model , Change direction , Or another solution .

    10. The inequality problem can be transformed into the maximum value problem , For example, any x>1 Can be translated as x The minimum value of >1, There is x>1 Can be translated as x The maximum of >1. This little trick More commonly used , It's also ingenious .

    11.DP If the status has aftereffect , You can try to write it to the status , Or enumerate certain quantities , Or transfer layer by layer in a certain order .

    12. When doing the number thesis, if there is gcd(a,b)=1 Conditions , signify a In the mold b In this sense, there is an inverse element , It may greatly simplify the practice .

    13. When doing interactive questions, if the number of times of asking is enough after some theoretical analysis, it will actually run a lot more , How to adjust the parameters has not changed , It's probably a mistake somewhere , Or there are obvious optimizations without adding （ In particular, the situation that other people wrote almost the same but passed easily ）.

---

What should be paid attention to in the exam ：

    1. A top priority ： An array , modulus （ Be careful not to write x+=(...)%mod）,long long（1ll Don't multiply by the wrong place when there are too many parentheses ）, The border , file name , The size .

    2. Construct small data test , Pay attention to special situations , Rigorous derivation .

    3. Generate the largest amount of data , Test timeout ,RE etc. .

    4. Violent shooting . After shooting, you must pay attention to whether your understanding deviates from the meaning of the topic , Whether the range of some variables is what you understand （ If violence and positive solutions come out of the pot at the same time, it will be really uncomfortable ..）

    5. Before the end of the exam 10 Minutes, be sure to check whether debugging information is output , Whether the file name and file location are correct .

    6. There is now a C++11, When using, you must pay attention to whether this compilation option is available , In general, there is no , It's best not to use... In official competitions .

（ In a continuous series ......）