本文共 5611 字，大约阅读时间需要 18 分钟。

成绩

题目

T1：杯子

题目

小明买了$N$个容积可以是无穷大的杯子，刚开始的时候每个杯子里有$1$升水，接着小明发现杯子实在太多了，于是他决定保留不超过$K$个杯子。每次他选择两个当前含水量相等的杯子，把一个杯子的水全部倒进另一个里，然后把空瓶丢弃。（不能丢弃有水的杯子）

显然在有些情况下小明无法达到他的目标，比如$N=3$，$K=1$。此时小明会重新买一些新的杯子（新杯子容积无限，开始时有$1$升水），以达到目标。

现在小明想知道，最少需要买多少个新杯子才能达到目标呢？

输入

一行两个正整数，$N$，$K$。

输出

一个非负整数，表示最少需要买多少新杯子。

样例输入1

3 1

样例输出1

1

样例输入2

13 2

样例输出2

3

样例输入3

1000000 5

样例输出3

15808

数据范围

对于$50％$的数据，$N\le 10000000$；
对于$100％$的数据，$1\le N\le 1000000000$，$K\le 1000$。

T2：玩具

题目

商店正在出售小$C$最喜欢的系列玩具，在接下来的$n$周中，每周会出售其中的一款，同一款玩具不会重复出现。

由于是小$C$最喜欢的系列，他希望尽可能多地购买这些玩具，但是同一款玩具小$C$只会购买一个。同时，小$C$的预算只有$m$元，因此他无法将每一款都纳入囊中。此外，小$C$不能连续两周都购买玩具，否则他会陷入愧疚。现在小$C$想知道，他最多可以买多少款不同的玩具呢？

输入

输入文件共$2$行；
第一行两个正整数$n$和$m$，中间用一个空格隔开；
第二行共$n$个正整数，第$i$个正整数表示第$i$周出售的玩具的价格。

输出

输出文件只有一行，包含一个整数，表示小$C$最多能买多少款不同的玩具。

样例输入

3 8 4 4 5 

样例输出

1

数据范围

对于$30％$的数据，$n\le 10$；
对于$60％$的数据，$n\le 100$，$m\le 1000$；
对于$100％$的数据，$n\le 1000$，$m\le 1000000$，单个玩具的价格$\le 1000$。

T3：恐怖的奴隶主

题目

小$L$热衷于$undercards$。
在$undercards$中，有四个格子。每个格子要么是空的，要么住着一只$BigBob$。

每个$BigBob$有一个不超过$k$的血量；血量减到$0$视为死亡。那个格子随即空出。

当一只$BigBob$受到伤害后，假如它没有死亡且剩余血量为$t$，它会从左数第一个空格处召唤一只血量为$a[t]$的$BigBob$；若没有空格，则不会召唤。

法术$R$定义为：从左往右，对每个$BigBob$造成一点伤害；假如有$BigBob$死亡，重复上述效果。

聪明的小$L$发现，在某些情况下，当他发动法术$R$时，游戏会陷入循环。
他想求出这样的初始情形有多少种。

输入

输入一个正整数$k$；
随后一行$k-1$个正整数，表示$a[1]～a[k-1]$；

输出

输出一个整数，表示答案。

样例输入

22

样例输出

31

样例解释

$Bigbob$最多有$2$血，满血$bigbob$受伤会召出新的。
循环的初始状态有：
$(2,1,0,0),(1,2,0,0),(2,0,1,0),(2,1,1,0),(0,2,1,0),(1,2,1,0),(2,2,1,0),(1,0,2,0),(0,1,2,0),$
$(1,1,2,0),(2,1,2,0),(2,1,0,1),(0,2,0,1),(1,2,0,1),(0,2,1,1),(1,2,1,1),(0,0,2,1),$
$(1,0,2,1),(0,1,2,1),(1,1,2,1),(2,1,2,1),(0,2,2,1),(1,2,2,1),(2,1,0,2),(1,2,0,2),$
$(2,0,1,2),(2,1,1,2),(0,2,1,2),(1,2,1,2),(2,2,1,2),(2,1,2,2)$
共$31$种。

数据范围

对于$30％$的数据，$k\le 5$；
对于$70％$的数据，$k\le 10$, $a[i]=k$；
对于$100％$的数据，$k\le 15$, $1\le a[i]\le k$。

T4：组合树(tree)

题目

$Bob$想要和$Carrol$玩游戏。但$Carrol$觉得玩游戏太无聊，就和$Tuesday$去写歌了。于是现在$Bob$来找你玩游戏。

这个游戏是这样的：给定一棵$n$个节点的树， $1$号点为根节点，设$v$的父亲是$f(v)$ 。其中每个节点有一个颜色，要么是黑色，要么是白色。不妨记第$i$个节点的初始颜色是$ci$。$ci=0$或$1$，表示黑色或白色。

在游戏开始时，$Bob$为每个节点选择一个目标颜色$di$，要求你经过若干次操作，将每个节点变成其目标颜色。你的操作是这样的：
●选定一个点$u$，将$u$,$f(u)$,$f(f(u))$,$\dots$,$fk-1(u)$这$k$个节点的颜色翻转（将白色节点变为黑色节点，将黑色节点变为白色节点）。其中$k$是游戏开始前确定的一个正整数。

只有$u$,$f(u)$,$f(f(u))$,$\dots$,$fk-1(u)$这$k$个节点均存在，你才能执行这样的操作。当然，你可以执行任意多次操作。

现在$Bob$要和你玩$T$次这样的游戏，每次你都想要知道你是否有可能完成要求，即通过若干次操作，将所有节点变成其目标颜色。

输入

第一行仅一个数$T\le 10$，表示这样的游戏的次数；
●接下来共有$T$组数据。对于每一组数据：
○第一行是两个正整数$n$,$k$，$n$表示树的大小，$k$的含义请参见题目描述。数据满足$n,k\le 2\times 105$
○接下来$n-1$行每行两个数$u$,$v$，表示树上有一条边$(u,v)$ 。注意：输入并不保证边的方向。
○接下来一行$n$个数$c1$ , $c2$，$\dots$，$cn$，表示初始颜色。
○接下来一行$n$个数$d1$ , $d2$，$\dots$，$dn$，表示目标颜色。

输出

输出包含$T$行，第$i$行对应第$i$次游戏的答案；
对于第$i$次游戏，如果你有可能完成任务，输出$Yes$，否则输出$No$ 。

样例输入

2 3 2 1 2 2 3 0 0 0 1 0 1 3 2 1 2 2 3 0 0 0 1 1 1 

样例输出

YesNo

样例解释

●对于第一次游戏，第一次选择$2$号点操作，$1$,$2$号点被翻转；第二次选择$3$号点操作，$2$,$3$号点被翻转。即达成目标状态。
●对于第二次游戏，可以证明，无法将初始状态经过操作变为目标状态。

数据范围

对于前 $10％$ 的数据，$n\le 5$；
对于前 $30％$ 的数据，$n\le 20$；
对于前 $50％$ 的数据，$n\le 2000$；
对于前 $70％$ 的数据，$n\le 50000$；
对于全部测试点：$T\le 10$, $k\le n\le 2\times 10^5$，保证数据给出的是一棵树。

做出来的题目博客