# UVA1099 Sharing Chocolate

$n\leq 15,1\leq x,y\leq 100$ 。

# LA4725 Airport

$1\leq n\leq 5000$ 。

# LA4094 Wonder Team

There are $n$ football teams participating in the competitions, each team plays twice (home and away) against each other team. Each team receives three points for a win and one point for a draw. No point is awarded for a loss.

When the games are finished, teams are ranked by numbers from $1$ to $n$ according to the total points. The rank of each team $t$ having $p$ points is one plus the number of teams having more than $p$ points. It is possible that more than one team have the same ranks. In addition to the Champion (the first ranked team or teams), the Wonder Team is also awarded, if there exists one. The team that has absolutely the highest number of wins (absolutely means no other teams has the same number of wins), absolutely the highest number of goals scored, and absolutely the lowest number of goals conceded, is called the WonderTeam. (WonderTeam should have all these properties.)

Your task is to find out the worst possible rank for the Wonder Team.

$1\leq n\leq 50$ 。

English problem, English solution!

First of all, I’d like to claim that the 2nd Constraint and 3rd Constraint is no-use, becauce we always can let WT won another team with $10^9:1$.

Let’s assume $a_1,b_1$ means the WonderTeam’s wins and draws, $a_2,b_2$ means an arbitrary team’s wins and draws, whose rank is higher than WT. After a series of easy inference, if one team has higher rank than WT, the equation below should be satisfied:

Then my train of thought ended up with this:(

Thinking more carefully, if we want to maxmize WT’s rank, we have to get other teams’ score as high as we can. So we can use a greedy way to construct it : Just let WT’s wins actually one more than others. At the same time let WT lose its other games. Also we let other teams won WT one time, and draw with each other.

Then we can find that $\forall a_2$ ，there is $a_1-a_2=1$, which means $(1)$ turned to be:

And about $b_2$ , there will exists two teams who losed in the game with WT , which means the-two has exactly $1$ win and $2n-4$ draws, while the rest teams has exactly $1$ win and $2n-3$ draws.

So we can cliam that when $n>4$ , WT’s lowest rank can be $n$ ; when $n=4$, it can be $2$ ; otherwise it can only be $1$ 。

# CCO 2017 Rainfall Capture

Lucy 有 $n$ 个高度为 $h_1,h_2,…,h_n$ 的柱子。她想知道，在所有可能的摆放方案中，所有可能的雨滴量（以 $r$ 为单位）是多少。

# UVA1073 Glenbow Museum

1、尾部不是 O 的方案数，显然就是前面 $\frac{n}{2}+2$ 个空填 $\frac{n}{2}-2$ 个O的方案数。

2、尾部是 O 的方案数，此时第一个位置不能放 O。类似的组合一下就完了。

# CF340E Iahub & Permutations

$n\leq 5000$ 。

orz 一个十分巧妙的转化，大概就是对于这种带有放置限制的排列问题，比如某个下标不能放置某个数，那么可以将这个排列对应到一个 $n$ 阶摆 $rook$ （即 $n\times n$ 的棋盘上放 $n$ 个互不攻击的车）问题上。这样一方面可以把「位置 x 不能放 y」约束展开，抽象成一个二维约束点 $(x,y)$ 上不能放车的约束；另一方面可以知道这个对应一定是完备的。

# CF212D Cutting Fence

$1\leq n,m\leq 10^6$.

1、 $1\leq L\leq x-l$ ，这种区间每个元素都可以是 $x$ ，所以贡献为 $L\cdot a_x$ 。

2、$x-l+1\leq L\leq r-x$ ，这种区间最多只能取到 $x-l$ 次 $x$ ，所以贡献为 $(x-l)\cdot a_x$ 。

3、$r-x+1\leq L\leq r-l-1$ ，这种区间最多只能取到 $r-l-L$ 次，故贡献为 $(r-l-L)\cdot a_x$ 。

# USACO12 Bovine Alliance G

$1\leq m\leq n\leq 10^5$ 。

1、不难发现一个简单环的定向方式总共是 $2$ 。

2、考虑去计算一棵树的定向方式。发现随便找一个根，显然哪个点当根对于整棵树的方案数没有影响。考虑如果将所有边都向儿子定向，那么这样一定合法，这是第一种方案。同时，单独把某一条边取反，假设这条边连接的儿子是 $x$ ，那么同时需要把 $x\to fa_x,fa_x\to fa_{fa_x}, fa_{fa_x}\to fa_{fa_{fa_x}}$ 全部取反，那么最终会取反到根，根的入度会变成 $1$ ，这也就说明不能有 $>1$ 条边同时取反。所以可以知道一棵树的定向方式为 $1+(n-1)=n$ 。