比赛地址

Splitting Pile

枚举即可。

代码

Fennec VS. Snuke

双方显然是先把对方到自己这边来的路堵上。

于是我们只要找到分界点,看看哪边的点多即可。

需要注意的是,如果两边的点一样多,那么是后手胜。

代码

Awkward Response

首先可以把 $N$ 的位数确定出来:依次问 $1,10,100,\cdots$ 直到回答是 N,则前一个数和 $N$ 的位数相同。

那么可以考虑二分。假设当前二分出的数是 $mid$,我们只需要询问一下 $10mid$,因为 $10mid$ 一定大于 $N$,那么返回 N 说明 $mid$ 小了,否则说明 $mid$ 大了。

然而这样子会得到 WA,因为这样并不能处理 $N=1,10,100,\cdots$ 的情况。

所以我们先把这个特判掉。先询问 $10^9$,如果是 Y 那么 $N=1,10,100\cdots$,我们只要依次询问 $10^9-1,10^8-1,\cdots$ 就可以求出 $N$ 的位数了。

代码

Mole and Abandoned Mine

我们把题意转化为留下的边权值和最大。

数据范围很小,考虑状压 DP。设 $dp_{i,S}$ 表示考虑 $S$ 中的点,$1\to i$ 只有一条路径时留下的边的最大权值和。转移有两种:

  • $dp_{i,S}+w_{i,j}\to dp_{j,S\cup\left\{j\right\}}\;(j\notin S)$:意思是加入边 $(i,j)$,从 $1\to j$ 只有 $1\to i\to j$ 这条路径。
  • $dp_{i,S}+sum_{T\cup\left\{i\right\}}\to dp_{i,S\cup T}$,$sum_S$ 表示 $\sum_{i,j\in S,(i,j)\in E} w_{i,j}$:意思是把 $T$ 中的点和 $i$ 连成一个完全图,从 $1\to i$ 仍然只有 $1$ 条路径。

最后拿所有边的边权减去 $dp_{n,U}$ 即为答案。

代码

然而你甚至可以随机化艹过去

最后修改:2020 年 09 月 21 日 05 : 18 PM