3.19 CF

List

Simons and Making It Beautiful

Observe that index n is always ugly, so the answer is at least 1. This remains to show that this lower bound is achievable. Set so that for each i, As result, the only ugly index is n.

Simons and cakes for Success

We all kown the fomular , so this problem can be solved.

Eating Game

greedy,easy

Deletion sort

Attention is all you need. This one is easy too.

Specialty String

All the problems like this, we can slove this with stack, and for some other cases, we can use queue to solve it.

Here we can solve this use stack, and note that there exited inserted function in c++.

And we introduce the operations of stack in c++ here. use .empty() to judge the stack is empty. Use pop() and push(). And importantly, use .top() to access the top element.

Portal

This one we can find the two side element which divided by the portal is fixed. What we should consider here is which position we insert into the fixed string that can make the whole string has the lexicographically smallest permutation.

Actually we can use internal function like rotate() and insert() to finish this problem.

cpp

rotate(b.begin(), min_element(b.begin(), b.end()), b.end());
int m = b[0];

auto it = a.begin();
while (it < a.end() && *it < m)
it++;

a.insert(it, b.begin(), b.end());

But here i want to introduce anorther algorithm that used to solving: a sequence that can move looply, find a position used for cutting, and let the lexicographically smallest string read from this position.

We mantain two pointers, i and j, and k is two guys all get. We compare v[i+k] and v[j+k]. And if a==b, we let k++. And if a!=b, we let i+=k or j+=k, this is the key point that we can finish this in . Beacuase though v[i+k] lose to v[j+k], the position between i and i+k can beat j.

And for easy operations, we double the array so we dont to do the mod operations

cpp

//   auto get = [&](vector<int> &v) {
//     int len = v.size();
//     if (len == 0)
//       return v;
//
//     vector<int> dou = v;
//     dou.insert(dou.end(), v.begin(), v.end());
//
//     int i = 0, j = 1, k = 0;
//     while (i < len && j < len && k < len) {
//       int a = dou[i + k];
//       int b = dou[j + k];
//       if (a == b)
//         k++;
//       else {
//         if (a > b)
//           i += k + 1;
//         else
//           j += k + 1;
//         if (i == j)
//           j++;
//         k = 0;
//       }
//     }
//
//     int pos = min(i, j);
//     vector<int> res;
//
//     for (int i = 0; i < len; i++) {
//       res.push_back(dou[pos + i]);
//     }
//
//     return res;
//   };

3.19 CF ​

List ​

Simons and Making It Beautiful ​

Simons and cakes for Success ​

Eating Game ​

Deletion sort ​

Specialty String ​

Portal ​