This is the 8 days I participated in the August More text challenge, see the details: August more text Challenge

1930. A sequence of different subtexts of length 3

Thought analysis

Through observation, we find that for a palindrome sequence of length 3, in fact, the only requirement for us is to select the starting point and ending point from the left and right sides with the same elements on both sides, and the type of characters contained in the middle of the two is the number of different sub-sequences of the length 3 with the first element of I.

There is really nothing to say and the code is omitted.

1931. Color the grid with three different colors

Thought analysis

In general the enumeration method is definitely wrong, after the data size changes can still break down multiple sub problem of big probability is the dynamic programming, such as the problem is, in the case of determine the column, in fact, the m – 1 row, n the number of columns is m rows n columns the number of subsets, or all m rows n columns satisfy answer conditions of graphics, His first m-1 rows are all and only m-1 row, n column answers.

However, STATE compression DP I do learn is not very clear, here to explain the thinking of the official answer

Since the m line is small, only between 1 and 5, the answer is in the range of M.

  1. So let’s figure out the number of possible m rows and 1 column
  2. And then figure out the number of next legitimate vectors that this vector can match
// Preprocess all (mask1, mask2) binary groups such that mask1 and mask2 are adjacent rows and the colors of the two cells on the same column are different
        unordered_map<int, vector<int>> adjacent;
        for (const auto& [mask1, color1]: valid) {
            for (const auto& [mask2, color2]: valid) {
                bool check = true;
                for (int i = 0; i < m; ++i) {
                    if (color1[i] == color2[i]) {
                        check = false;
                        break; }}if (check) {
                    adjacent[mask1].push_back(mask2); }}}Copy the code

The code calculates the number of f[I +1] that can be iteratively calculated through the f[I] of MASk1 by judging whether there is the same element in the same position in mask2 and then calculating the number of valid MASK2.

  1. Finally, layer by layer using F [n].

In this case, the code associated with shape pressure is simply a representation of color, using 3 to the NTH power to represent (since there are only three colors) the many possibilities of color.