ChangKe's Blog

写在HAOI2016之后

Orz红太阳hs，Orz蓝月亮mzx，Orz被Menci钦点进队的gcx和Fancy，Orz lzz，Orz KZ。

I hope to convey my best wishes,through the blog,to the HA teamers.

（没报CTSC和APIO真是今年下得最烂的一步棋。。。当时确实被周围人硬点退役(@班主任 @家长)，然后就不资瓷了。。。）

BestCoder Round #80游记

What!PE!仔细检查一下，应该换行了啊，字母也都是大写啊，还有什么问题呢？

D题比较有趣，因为出圈顺序已知，所以我们可以运用“重标号法”，得出一些同余方程，关键是怎么解。。。百度了一下非互质的CRT，抄了一遍交上去。什么？WA了？我再改改。。。什么？又WA了？不对吧。。。开始人脑对拍，并没有问题啊。。。然后刷新页面，发现题目中多了一行黑体字，意思是输入的内容和我理解的不一样，但样例太弱所以我没看出来。。。

Hack也很有意思。从下往上点，一堆堆没特判0的，连叉四个，然后就找不出来Hack点了。。。首页某大神Hack21次。。。

（以上均为口胡）

Day 1

Menci在中午把题发给我，我吓傻了，一道也不会。后来她还告诉我有人AK，感觉心灵受到了震撼。

Day 2

Menci说她可以去Round2了。我又去看各位神犇的游记，见一个膜一个。

后续

Menci把题放到了COGS上，然后混了个管理员权限。然后我才开始正式刷SDOI2016Round1的6道题。

软件安装(t4)

算法二

（感觉口胡了好多啊，建议对着代码理解）

UOJ Round #13：暴力练习大赛

A暴力$O(n^2 \log n)$二分+贪心，B暴力$O(n^3)$DP，C暴力$O((r-l)\log r)$分解质因数。

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).

题2.M序列(mseq)

样例说明

$2,2,8,10$
$1,3,7,11$
$0,4,6,12$
$-1,5,5,13$

数据范围

$50\%$的数据$n \leq 1000,m_i \leq 20000$
$100\%$的数据$2 \leq n \leq 100000,m_i \leq 10^9$

题3.竞技比赛(bnb)

数据范围

$20\%$的数据中，$1 \leq n \leq 10$
$40\%$的数据中，$1 \leq n \leq 100$
$60\%$的数据中，$1 \leq n \leq 1000$
$1000\%$的数据中，$1 \leq n \leq 100000$，且所有选手的实力值在$0$$10000000$之间。

Hello World

Hi, This a demo post of Logdown.

Logdown use Markdown as main syntax, you can find more example by reading this document on Wikipedia

Logdown also support drag & drop image uploading. The picture syntax is like this:

inline code

MathJax Example

Inline Mathjax

The answser is $a^2 + b^2 = c^2$.

Table Example

Tables Are Cool
col 1 Hello $1600 col 2 Hello$12
col 3 Hello \$1