• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

A. Number Transformation

设\(a=1\),那么\(b=\dfrac{y}{x}\)。

B. Dictionary

暴力预处理一个完整的字典,然后用std:map存储单词和下标的映射。

C. Infinite Replacement

如果\(t\)等于A,则答案是\(1\)。

否则,如果\(t\)包含A,则有一个答案是无穷的。

否则\(s\)中的每个元素都有两种可能,替换或不替换,即答案为\ (2 n \),其中\(n=|s|\)。

D. A-B-C Sort

先做E,F,再返回做d。

对于\(n=3\),所有可能的结果是\(a_1a_2a_3\)和\(a_1a_3a_2\)。

对于\(n=4\),所有可能的结果是\(a_1a_2a_3a_4\),\(a_1a_2a_4a_3\),\(a_2a_1a_3a_4\)和\(a_2a)

以此类推,发现题目给出的运算等价于\(n-i\)为偶数时:\(a_i\)和\(a_{i 1}\)可以互换。

对于满足条件的\(i\),如果\(a_i a_{i 1}\,则两个元素的位置互换,否则保持不变。

然后看数组是否非降序排列。

E. Breaking the Wall

被hack了,待更新。

有三种可能的操作:

只打第一个\(i\)墙。

打第一个\(i\)墙和第一个\(i 1\)墙。

拆除\(i\)墙和\(j\)墙。

对于第一个操作,枚举每面墙。可能第一个\(i\)墙被砸倒了,旁边的墙也顺便被溅射倒了。这种情况将在第二次操作中考虑。可能\(i\)墙没倒,相邻的墙都倒了,代价是\(\max(a_{i-1},a_{i 1})\)。\(O(n)\)枚举\(i\)。

对于第二个运算,假设你打了\(i\) wall \(x\)次和\(i 1\) wall \(y\)次,可以得到一个不等式方程组,求解的代价是\(\ l Ceil \ d frac { a _ { I } a _ \(O(n)\)Enumerate \(I \)。

对于第三个操作,选择\(j\)可以是贪心的。有四个候选:\(i-1\)、\(i 1\)、\(p(i-2)\)、\(s(i 2)\)。\(p(x)\)表示前\(x\)个元素中最小值的下标,\(s(x)\)表示后缀。\(O(n)\)预处理前缀和后缀,然后\(O(n)\)枚举\(i\)。

F. Desktop Rearrangement

请记住,桌面上图标的数量是\(计数\)。

因为行数和列数是固定的,所以可以直接计算重排后有图标的面积。假设这个区域已经有了\(sum\)图标,那么需要的操作数就是\(count-sum\)。

将桌面上的位置重新编号如下。

147

258

369

重新编号后,桌面重排后图标的位置会是一个前缀,然后就是前缀和的单点修改问题,直接用树数组就可以了。

G. Remove Directed Edges

DAG上的DP。

可观察性:最终答案将是.

设\(dp_i\)代表以\(i\)为终点的链的最大长度。对于节点\(u\),考虑与其相邻的点\(v\)是否延伸出以\(u\)为终点的链。

因为它是一条链,除了边\(u\rightarrow v\)之外,\(u\)的其他出边和\(v\)的其他入边都可以删除,所以如果\(outdeg_u 1\)和\(indeg_v 1\),\(那么对于\(v\)可能有多个\(u \),即\ (dp _ v=\ maxdp _ {(u,v) \ in e} dp _ u1 \),因为它是DAG。

进行拓扑排序,然后计算DP。

Link to comment
Share on other sites