# ChangKe's Blog

## 3.卡牌游戏

In the simple case where high card always wins one optimal strategy that Bessie can take is to always answer FJ's plays with her lowest card that is still higher than FJ's card (or her lowest card in the case she can't beat FJ). This works because if we can take something we should; otherwise the best that the card we didn't end up using can gain us is 1 trick so there can be no net gain.
This strategy informs the more complicated scenario where we switch from high card wins to low card wins at some point. In this case we should always allocate our highest cards to the section where high card wins and are lowest cards to the latter section. Then this reduces to the simpler case.
To solve this problem where we need to determine the best switch point we can make use a segment tree data structure that will enable us to solve the online version of the simple case. We will be able to insert a card for each player and determine the max score Bessie could achieve. Using this data structure we can determine how many points Bessie will get from the high card wins and low card wins part of each game and output the switch point that yields the highest overall score.
Building this data structure can be done by tracking for each segment in the tree the number of available cards in this segment that Bessie could play over lower cards, the number of coverable cards that FJ has played in this segment that haven't been covered, and the number of points we can score in this segment. Combining two segments is then done by summing the points and awarding points based on the min of coverables on the left and coverers on the right. The other fields are updated similarly (see comb() in my code below). The rest is a standard segment tree implementation.

## 5.哞哞城堡

This problem suggests a DP approach, and the bounds suggest that $O(n^3)$ is a comfortable target to aim for. There are several ways to approach this problem, but all of these focus on fixing some property of the rectangle, iterating over all possible values of that property, and finding the best rectangle for each iteration. One of the simpler ways is to fix an edge of the rectangle, and calculate the maximum possible rectangle with that edge.
For simplicity, we will fix the left edge of the rectangle. There are $O(n^2 \cdot n) = O(n^3)$ possible left edges, so we will reach our desired runtime if we can compute the best possible rectangle with this edge in $O(1)$ time. Luckily, we can use a sliding window to do so: if we process the left edges in order from left to right, we can note that the right edge of the rectangle must also move to the right over time. This is because a candidate rectangle will never become invalid as we move its left edge more to the right. We can use a simple data structure to query subrectangles of our given array in $O(1)$ time (see the code below if you're not quite sure how).