(Incomplete) Codeforces 394 (Div 2 only)

A. Dasha and Stairs

保证a,b不同时为0,而且a 和 b 的绝对值不超过1即可。(心态崩了的我强行写出一个暴力,枚举了所有的情况。)

code:

B. Dasha and friends

对于两个跑道,分别计算出每个片段的长度。固定第一个跑道的起点,枚举第二个跑道的起点,看两个跑道能否匹配。本题n很小,所以O(n^2)的暴力即可。既然是匹配,而且两个序列长度相同,也可以使用最小表示法,或者kmp,或hash等其它高效的匹配算法。

code:

C. Dasha and Password

方法:暴力/dp

注意,对于第i (0 <=i < n) 个string,我们只关心将其pointer指向第j (j = 0, 1, 2)种字符的最少步数,讥为d[i][j]。

然后对于三种字符,我们各需要至少一个string使其pointer指向该类型的字符,所以是An3 种。暴力枚举即可。

code:

傻傻的我还用了背包,pack[i][set] 为使用前i个string,达到set里的字符都存在的最小cost。最终答案为pack[n][(1<<3)-1]。太傻了。

code:

D. Dasha and Very Difficult Problem

方法:贪心 暴力

从最大的ci开始赋值,每次都取最大的bi,而且要保证ci < ci-1, 要求 ci = min(r-ai, ci-1 - 1)。 如果此时bi = ai+ci < l, 则返回不存在。

code:

E. Dasha and Puzzle

方法:dfs

观察可得,因为n比较小而long long 范围很大,如果树上每个节点的degree都不超过4,那么就可以画出来这棵树。至于没子节点nxt与其根节点cur之间的距离,我们设cnt[i] 为以i节点为根的子树的节点数,让cur 和 nxt 之间的距离等于cnt[nxt] 即可,这样从cur出发的四个方向互不影响,因为每个子树所能达到的区域都被对角线分隔开。然后dfs给点赋值即可。dfs的时候,注意不能向根节点的方向画树。

code:

F. Dasha and Photos

原文地址:https://www.cnblogs.com/skyette/p/6359695.html