【泛做】简单题选做

大概是由于基础太差了,然后打算去做点题补一下基础和脑子…

这个故事告诉我们,永远不要偷懒,有些力气,早晚是要出的。

如果来看我 blog 的你有什么好题推荐,欢迎评论,其他博客也是可以评论的(疯狂暗示

对了,像我这种明明要准备省选却在刷简单题补基础的人,是不是应该发一个「年度最佳人才」奖?

争取一句话题解…先整理十道题吧…因为奇奇怪怪的事情浪费了不少时间。

UVA10891 Game of Sum

有一个长度为 $n$ 的整数序列,两个游戏者 $A$ 和 $B$ 轮流取数,$A$ 先取。每次玩家只能从左端或者右端取任意数量的数,但不能两边都取。所有数都被取走视为游戏结束,然后统计每个人取走的数之和,作为各自的得分。两个人采取的策略都是让自己得分尽可能高,并且两个人都很机智,求 $A$ 得分 - $B$ 得分后的结果。

自己一开始想的 $dp$ 是要 $f_{i,j,0/1}$ ,并且转移有点复杂,结果发现根本不需要…考虑在博弈树上 dp,每个 $max$ 局面接下来一定是一个 $min$ 局面,所以有

也就是找到与一端边界相邻,且最小的那个对方的决策($min$ 局面)。发现前后缀 $min/max$ 维护一下就可以 $O(n^2)$ 了。

CF493D Vasya and Chess

有一个 $n\times n$ 的国际象棋棋盘。将白后放在 $(1,1)$ ,黑后放在 $(1,n)$ ,其余位置全都是中立的卒。
双方交替移动。白方先手。 每次移动,后(Queen)可以朝八个方向(上下左右对角线)之一移动任意格,直到碰到另外一个棋子,然后吃掉这个棋子。注意,在本题中,每次移动必须吃掉一个棋子。
当你的皇后被吃了或者你没有棋子可以吃了,就输了。 给出棋盘大小,请问哪方会赢。

发现这种对称位置决策的…一般后手都比较神必,拖,就硬拖。

考虑后手模仿先手的动作,那么如果两者之前相隔为奇数,后手可以模仿先手,发现这么做一定可以吃掉先手。如果相隔为偶数,那先手就要学聪明,移动到 $(1,2)$ ,然后成为上一种情况的后手…

UVA1099 Sharing Chocolate

给出一块长为 $x$, 宽为 $y$ 的矩形巧克力,每次操作可以沿一条直线把一块巧克力切割成两块长宽均为整数的巧克力(一次不能同时切割多块巧克力)。

问:是否可以经过若干次操作得到 $n$ 块面积分别为 $a_1, a_2, …, a_n$ 的巧克力。

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

大力状压,$f_{s,x,y}$ 表示 $s$ 这个集合内的巧克力是否可以被 $x,y$ 给切出来。考虑这样转移存在问题。因为必须要枚举子集来转移,所以最后时间复杂度 $O(3^nxy)$,空间复杂度 $O(2^nxy)$ 。有点爆炸。

考虑化简状态。发现固定了巧克力集合 $s$ ,那么对于一个固定的 $x$ ,$y$ 要么不存在要么同样被固定。所以状态就可以简化成 $f_{s,\min\{x,y\}}$ 。转移时依旧要判断两个状态是否都可行。注意转移来的状态 $f_{s’,x’}$ 也需要保证信息是落在较短边上的。复杂度 $O(x3^n)$。

神必 uva 卡我常数。不过也需要记得,对于这种信息 $01$ 且求并的转移,一旦某个状态确定为 $1$ 了就可以 break。这个技巧确实要记住。

LA4725 Airport

机场上有两个跑道,分别为 W 和 E,每个时刻 $i$,W和E都分别有 $a_i,b_i$ 架飞机进入跑道。每个跑道的飞机都按顺序从 0 开始排序,每个时刻都允许一架飞机起飞,现要求你安排起飞的飞机,使得任意时刻的飞机的最大编号最小。

$1\leq n\leq 5000$ 。

这题能比较自然地想到要二分。但是问题在于二分了之后并不知道要怎么去 check。这个地方有个很妙的 idea。就是如果之前有机会要飞,可以不飞,等到什么时候攒到了 $mid$ 号再飞。这样就不需要再考虑这东西的后效性了。但是有一点需要注意,就是攒着一起飞的话,在第 $i$ 个时刻只能选择飞之前的,因为这个决策本质上等价于在 $i-1$ 时刻飞。所以也要分别统计 $W$ 和 $E$ 的可飞量。

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$ 为单位)是多少。

柱子只能竖着摆。接雨滴的定义:满则溢。

比较神仙的 dp,对着代码啃了很久…

考虑直接求雨滴量并不好求,因为要去考虑左右两边的柱子高度。考虑对于一个排布 $4,2,5$ ,那么中间 $=2$ 或者 $=1$ 时要分开考虑;但是我们发现无论怎样,中间在接完雨滴之后高度都会变成 $4$ ,所以考虑求所有可能的雨滴+柱子的体积和。由于每个柱子都要摆,所以最后只需要去 check 那些 $\sum h_i\sim max$ 的答案。

考虑定义 $f_{i,v}$ 表示用了 $i$ 个柱子之后能否凑出体积 $v$ 来。考虑一个比较常用的 trick,将所有 $h_i$ 从小到大排序之后,按顺序转移。这样就能保证每次加进来的柱子都是当前最高的(无中生有了一个很有用的性质)。考虑一个状态 $f_{i,v}$ ,他的转移应该为:

其中 $p_j$ 是每个柱子的高度,需要从小到大转移,且转移时需要严格按照先枚举 $p_j$ 再枚举 $1\sim i$ 的顺序。

考虑这个式子的意义。对于任何一个大小为 $i\in[1,n-1]\cap\mathbb{Z_+} $ 的柱子集合 $o$,按秩转移时每次加入一个 $\geq \max_{t\in o}p_t$ 的新柱子 $p’$,放在最左边(或者最右边),同时再加入一个按高度从小到大排序后,恰好排名比 $p’$ 大 $1$ 的柱子 $p’’$ 放在 $p’$ 的同侧(即,如果 $p’$ 放在了整个序列的左边,$p’’$ 应该被放在 $p’$ 的左边)。那么此时考虑,每当加进来一个元素 $p_0$,集合大小从 $i-1$ 变成 $i$ ,$p’$ 就向右交换一个,这样新加进来的这个柱子上方水位高度一定会是 $p’$ 的高度(因为最左边有 $p’’$), 所以体积的变化量是 $\Delta v=(p’-p_0)+p_0$,前一半是水,后一半是新的柱子,所以可以从 $i-1,v-p’$ 转移过来。

需要注意的是,这样转移一定是不包含最高那个柱子的,因为当最高的柱子为 $p’$ 不存在一个更高的 $p’’$ 。

于是最后复杂度 $O(n^2\sum h)$ ,当然可以用 bitset 优化成 $O(\frac{n^2\sum h}{w})$ 。但其实在注意到本题只关注可达性判断之后,就可以发现等高的柱子不用重复转移,就可以优化成 $O((\sum h)\cdot n\cdot \max\{h\})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int s ; 
int n, m ;
int base[N] ;
//bool f[N][M] ;
bitset <M> f[N] ;

int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = qr(), m = max(m, base[i]) ;
sort(base + 1, base + n + 1) ;
for (int i = 1 ; i < n ; ++ i)
s += base[i] ; f[0][0] = 1 ;
for (int i = 1 ; i < n ; ++ i){
for (int j = 1 ; j <= i ; ++ j)
f[j] |= (f[j - 1] << base[i]) ;
//for (int k = base[i] ; k <= n * m ; ++ k)
// f[j][k] |= f[j - 1][k - base[i]] ;
}
for (int i = s ; i <= n * m ; ++ i)
if (f[n - 1][i]) printf("%d ", i - s) ; return 0 ;
}

UVA1073 Glenbow Museum

对于一个各边长度任意且都平行于坐标轴的多边形,我们可以用这样的方式描述它:考虑它的每一个内角,如果这个内角为 $90$ 度,那么用 $R$ 代表它;如果这个内角为 $270$ 度,那么用 $O$ 代表它。从某个点开始,按照逆时针的顺序读取 $R$ 和 $O$,最后得到一个由 $O,R$ 组成的字符串。

给定整数 $n$,问有多少个长度为 $n$ 的 $O,R$ 组成的字符串,使得有一个或以上与之对应的多边形,满足这个多边形内部有一点,可以看到这个多边形的所有内角(即,这个点与多边形所有内角顶点的连线都不与多边形的边相交)。

显然最后一定是 $\frac{n}{2}-2$ 个 $O$ 和 $\frac{n}{2}+2$ 个 $R$。同时显然不会有相邻的 $O$,证明大概是需要拐回来之类的。那么问题就是给你固定数量的 R 和 O ,O 和 O 之间不相邻的方案数。

第一种 $dp$ 就是 $f_{k_1,k_2,l,r}$ 表示用了 $k_1$ 个 O 和 $k_2$ 个 R,最左端的字母是 $l$,最右端是 $r$ 的方案数。转移的时候考虑新加入一个 $R$ 还是 $O$ 即可。

第二种 $dp$ 则是一个改进,因为显然我们不关心 $O$ 的数量,因为最后是一定的;只关心如何排列。所以令 $f_{k_1,k_2,c}$ 表示有 $k_1$ 个 R ,$k_2$ 对相邻的 RR,第一个字母是 $c$ 的方案数。转移的时候考虑向后加一个 R​ 还是 OR 即可 。

然而显然这种 dp 是有组合意义的。所以我们分类讨论:

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

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

于是就可以组合数做。处理的时候因为答案过大,所以可以考虑取对数(学到许多)

CF340E Iahub & Permutations

有一个长度为 $n$ 的排列 $a$,其中有一些位置被替换成了 -1。你需要尝试恢复这个排列,将 -1 替换回数字。
求多少种可行方案使得得到的是一个排列且不存在 $a_i=i$ 的位置。

$n\leq 5000$ 。

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

那么就转化成了,有些行和列已经放了车,整个棋盘对角线不能放车,有多少种本质不同的放车方案数。首先可以发现,如果某行某列有车,这一行一列就可以删掉;同时如果对于某个 $-1$ ,他所在的这个位置对应的行/列恰好被删了(同时存在位于下标 $k$ 的 $-1$ 和一个 $pos$ 使得 $a_{pos}=k$ ),那么对于这个 $-1$ 而言就没有限制了。

这样考虑 $dp$ 。$f_{i,j}$ 表示 $i\times i$ 的方格里考虑 $j$ 个限制的方案数。那么 $f_{i,0}=i!$。同时注意到 $f_{i,j-1}$ 到 $f_{i,j}$ 恰好多了一个限制,这个限制对应的应该是 $f_{i-1,j-1}$ 的方案数。所以有转移

复杂度 $n^2$ 。

CF212D Cutting Fence

给出 $a[1…n]$ 。
定义 $f$ :

之后有 $m$ 个询问,每个询问给出一个数 $k$,问所有 $f(j,k) (1\leq j\leq n-k+1)$ 的平均值。
$1\leq n,m\leq 10^6$.

首先不难知道要求出每个 $a_i$ 对包含其区间的贡献,然后对于长度为 $1\sim n$ 的区间分别计算其和,最终除以 $n-k+1$ 即为答案。

考虑两遍单调栈求出每个元素 $x$ 左/右边第一个比他小的元素下标 $l,r$,可知 $x$ 的贡献区间即为 $[l+1,r-1]$。枚举 $x$ ,那么区间 $l+1,r-1$ 的所有跨过 $x$ 的子区间都会存在贡献。此处假设 $x-l<r-x$,考虑分类讨论子区间长度 $L$ :

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$ 。

然后观察这些修改,发现 $L\cdot a_x$ 这东西,对于一个区间是在加一个等差数列的形式,$(x-l)\cdot a_x$ 和 $(r-l)\cdot a_x$ 都是区间加一个常数的形式。于是可以维护二阶差分。复杂度线性。

USACO12 Bovine Alliance G

给出 $n$ 个点 $m$ 条边的图,现把点和边分组,每条边只能和相邻两点之一分在一组,点可以单独一组,问分组方案数.

以上是错误的题意,以下是正确的题意:

题意是给每条边找一个配对的点,要求边 $(u,v)$ 配对的点是 $u$ 或 $v$ ,且每个点最多只能被一条边配对,求不同方案数。

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

对着错误的题意思考了半天也不会…觉得首先对于点分组可以直接跑一个第二类斯特林数,但是这样边就没法分配了,因为可能存在边的两个端点在同一个点集内,所以可能需要套一个容斥什么的。推容斥系数可能会很高妙反正我不会

然后正确的题面的话,考虑问题可以转化成给每条边定向,使得最后整张图每个点的度数都 $\leq 1$ 的方案数。然后…然后就是考察对于图论模型的洞见性有多强了:

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$ 。

发现对于无向图,本质上就是树插环的形态。所以拿一个带权并查集维护即可。有一个坑点,就是如果两个点不在同一个即集合里,边数也要++。