Hackerrank HourRank 13

Title link and Code link

Before the National Day, my rating on Codeforces was 1876. When I saw that there were four games during the National Day, I thought that I could get up to 1900. But it turned out that I was so happy. I knelt down three times in a row during the National Day (the remaining number 8 still felt like kneeling), and dropped directly to 1800. Once again, I felt like a noob.

In the afternoon, I had a lot of personal thoughts that I wanted to include in my blog, but I just spent two hours writing in my diary. . . Suddenly I realized that I had finished saying everything.

I really want to become purple this year. Come on—keep working away.

I really like HourRank on Hackerrank because the time is short and the questions are not that difficult. The gap with others is not that big (it only lasts for an hour anyway, and Daniel can’t finish what he has written, so I don’t have to feel uncomfortable staring at it for too long). Things like Week of Code were really miserable. In the later stage, someone still solved the problem. Watching the countdown of the game disappear little by little, and the Rank dropped little by little. It was too painful to feel that I was still powerless. But I still have to play Week of Code, it’s so fun

I missed a lot of questions on LeetCode, so I’ll pick them up tomorrow. . .

Sum vs XOR

The question is given a number $n(n\leq10^{15})$, find $x$ that meets the following requirements:

1.$x(0\leq x \leq n)$

2.$x + n =x \oplus n$

Find how many $x$s satisfy the above requirements.

It is found that if n is expressed in binary, if the bit is 1, then x can only be 0 in this bit, otherwise it will be carried. If the bit is 0, then x can be 1 or 0 in that bit. So calculate how many 0’s there are in n and then raise it to the power of 2.

Coprime Conundrum

The meaning of the question is to find out how many coprime pairs there are, the product of which is less than or equal to $k(0\leq k \leq 10^9)$.

It is the same question as HDU1695. They are based on the inclusion-exclusion principle. Find the number that is less than or equal to up and is not co-prime with x.

However, I enumerated from 1 to n, and the final result was divided by 2. Am I a sand tea? . .

Enumerate directly to $\sqrt k$, then search deeply and subtract the ones smaller than yourself, and the rest will not be considered duplicates.

Longest Palindromic Subsequence

The meaning of the question is to give a string with a length of $n(1\leq n \leq 3000)$. Now you are asked to add a character to it at any position to increase the maximum palindrome sequence (not a string) of this string by at least k.

It can be seen that if one character is added, the maximum palindrome sequence can be up to 2. If k is greater than 2, it will be GG directly.

Then it is time to enumerate the added position. The added character may be as a middle character, so the largest palindrome sequence is the longest common subsequence *2+1 on both sides (one side is reversed); if it is as a character on both sides, then the length of the longest palindrome subsequence is calculated in the middle, and the length of the longest common subsequence is calculated on both sides, and dp records the status of the two. Finally, determine whether it is greater than or equal to k.