You still need to immerse yourself in it. C, D, and E are all good questions. The DP for E question should be figured out. What’s going on?
A Bounding Box
$N$ points, coordinates $x_i,y_i$, use the smallest rectangle (sides must be parallel to the coordinate axis) to surround these points, and ask for the smallest rectangular area.
Given $X(X<10^9)$, you can add $1$ to $X$, subtract $1$, divide it by $3$ (if $3$ can be divided), and ask the minimum number of operations to become $1$.
From the analysis, it is greedy. If you can eliminate it, then do it. If you can’t, then make up. . .
The meaning of the question is that there is a line segment $(0,X)$ on the $X$ coordinate axis. Now there are $N$ points $(x_i,y_i)(x_i>0,y_i>0)$. It is required to divide these line segments into several parts so that the point on each line segment with the shortest distance from the N points is the same point. Ask about the length of the interval segment controlled by each point.
The question is a bit convoluted. . . I watched it for a long time. . .
If it is two points, then the perpendicular bisector of the two points intersects with the $X$ axis. The left side is the smaller line segment interval from the previous point, and the right side is the interval of the later point.
$N$ points are sorted according to the $X$ axis. Maintain a stack in the same way. Each element in the stack is the farthest distance currently controllable. When the previous position is encountered, the top of the stack is popped.
int n; double x; int nx[maxn], ny[maxn]; map< pair<int, int>, int>hax; map<int, int>px; vector< pair<int, int> >sta; double ans[maxn];
doubleInsec(pair<int, int> a, pair<int, int>b) { double k = 1.0*(a.second - b.second) / (a.first - b.first); double x = (a.first + b.first) / 2.0; double y = (a.second + b.second) / 2.0;
return x + y*k; }
voidsolve() { sa(n); scanf("%lf", &x); repp(i, 1, n) { int a, b; sa(a), sa(b); if (px.find(a) == px.end() || px[a]>b) { px[a] = b; } hax[mp(a, b)] = i; } for (auto it : px) { while (1) { if (sta.size()<2) { break; } auto a = *(sta.end() - 1); auto b = *(sta.end() - 2); double A = Insec(b, a); double B = Insec(a, it); if (A>B) { sta.pop_back(); } else { break; } } sta.push_back(it); } double left = 0; for (int i = 0; i + 1<sta.size(); i++) { int id = hax[sta[i]]; double now = Insec(sta[i], sta[i + 1]); now = min(now, x); if (now > left) { ans[id] = now - left; } left = max(left, now); } int id = hax[sta[sta.size() - 1]]; double now = Insec(sta[sta.size() - 2], sta[sta.size() - 1]); if (x > now) { ans[id] = x - now; }
for (int i = 1; i <= n; i++) { printf("%.7lf\n", ans[i]); } }
E Free Palindromes
Question meaning: For a palindrome string with a length of $N$, it is required that none of the preceding $N-1$ prefixes are palindrome strings. Such a palindrome string meets the requirements. Now each position has $K$ characters to choose from. How many types of strings meet the requirements?
For a palindrome string of length X, there are $K^{(\frac{x+1}{2})}$ types, minus those that do not match. That is, there is a situation where the previous string is a palindrome.
Now it is concluded that if the prefix has a palindrome string, then the shortest length must be less than or equal to $N/2$. Assume that the shortest length $H$ is greater than $N/2$, then set $L=H-N/2$. In this way, because the whole is a string, the $2*L$ in the middle is also a string, symmetrically equal. In the same way, the previous prefix $2*L$ is also symmetrically equal. The shortest length will be found to be $2*L$.
Consider dp at this time. dp[x] represents a string of length x that meets the requirements. At this time there are: $$ dp[x]=k^{\frac{x+1}{2}}-\sum_{j=2}^{\frac{i}{2}}dp[j]*k^{\frac{i+1}{2}-j} $$ The latter part can be prefixed and recorded.
