Li Kou Week 248 (Ii)

This is the 4th day of my participation in the August More Text Challenge

1921. Maximum number of monsters destroyed

Thought analysis

Throw the existence of speed, this problem can not be easier, each time the smallest number of monsters can be destroyed. So consider the speed, in fact, is changed from the nearest distance to the shortest time, recalculate the sort, and finally destroy the monster with the smallest number.

If you think about the boundary conditions, this feels like a five minute problem,

code

int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
    vector<double> vec;
    for(int i = 0 ; i < dist.size(a); i++ ){ vec.push_back((double)dist[i]/(double)speed[i]);
    }
    sort(vec.begin(), vec.end());
    int t = 1;
    while(t < vec.size()) {if (t >= vec[t]){
            return t;
        }
        t++;
    }
    return vec.size(a); }Copy the code

1923. Longest public subroad

Thought analysis

Encounter the problem will not be poor to find a way to prune.

I don’t need to go into details.

Since there must be a common subpath len-1 when the longest common subpath length is len, we can find len by binary search. So, given length len, how do you tell if there is a common subpath?

Given that path[0] has a set of subpaths set0, then we find set0… The union of setn is ok, but in practice we know that the union operation is a false false, so we can use the premise of set0, if a path does not exist, it is not a public path, if after iterating through a set, set0 is not accessed, then set0 minus that element.

Now, the question is how do you tell if there is a common subpath if you have length len. To determine whether an element exists or not, because it takes too long to determine whether an element exists or not if it is an array, we can try to store the key by converting an array to a string.

However, it’s a bit of a hassle to keep working with strings, and when we look at the answer, we find that the answer uses a scrolling hash, which is actually a number as the hash key.

How to convert an array of numbers to a number, this is a very common conversion to n base, (and n base n also as a parameter to you!! The answer to a very classic riddle is on the answer surface, unexpectedly did not notice! And the nice thing about this is that you can compute the I +1 subarray from the I +1 subarray,

Here the official solution gives a recursive formula that looks like an infinite series, although it is correct, but in fact it is not a good way to kill a chicken

It’s actually pretty easy,