AC. 梦想

frank_c1

2016多校联合训练4

发布于2016年07月28日 | 暂无评论 | 1,323阅读 | 比赛经历

这场我们考场上A了七题,感觉比起前几场有所长进呢……

希望能一直进步。

1001. Another Meaning

给定字符串s。求在s中选取若干不相交的子串t的方案数。

1 \le T \le 30, 1 \le |t| \le |s| \le 10 ^ 5

1002. After a Sleepless Night

有一棵带权有根树,第i个点的权值是a_ia构成一个[1,n]的排列。

b_i为子树i中的点权最大值。现给定这棵树和b,求出一种可能的a。注意,根没有给定。

如果有多解,输出任意一种。如果无解,输出"Impossible"。

1 \le T \le 20, 1 \le n \le 10 ^ 5, \sum {n} \le 2 \cdot 10 ^ 5

1003. Bonds

给定n个点m条边的无向连通图。求图中极小割集的数量。

定义一个图的割集为一个边集,且删去该集合中的边后图不再连通。

定义一个图的极小割集为不包含任何子割集的割集。

1 \le T \le 20, 2 \le n \le 20, n - 1 \le m \le n(n-1)/2,不包含重边和自环,大数据不超过5组。

1004. Filling

你可以用2 \times 2矩形覆盖n \times n的网格。只需要满足矩形之间互不重叠,不一定要完全覆盖。

求合法覆盖方案数,答案对10 ^ 9 + 7取模。

两种覆盖方案认为是一样的,当且仅当旋转一定角度后,两个网格图案相同。

1 \le T \le 20, 1 \le n \le 20

1005. Lucky7

给定n元数组pa

[L,R]中有多少整数k满足k \mod p_i \neq a_i,且k7的倍数。

1 \le T \le 20, 0 \le n \le 15, 0 \lt a_i \lt p_i \le 10 ^ 5, 0 \lt L \lt R \lt 10 ^ {18}, \prod_{i=1} ^ {n} {p_i} \le 10 ^ {18}

1006. Substring

给定字符串s和字符c,仅包含小写英文字母。

统计s中有多少个包含字符c的本质不同子串。

1 \le T \le 30, 1 \le |s| \le 10 ^ 5, \sum {|s|} \le 7 \cdot 10 ^ 5

1007. Treasure

给定n个点的树和m条有向带权路径(u,v,w)

要求选择一条有向路径(s,t),最大化方向与(s,t)方向相同且两端点都在(s,t)上的路径权值和。

1 \le T \le 30, 1 \le n, m \le 10 ^ 5, 1 \le u_i, v_i \le n, |w_i| \le 1000, \sum {n}, \sum {m} \le 6 \cdot 10 ^ 5

1008. Turn Game

有一个n \times m的棋盘,初始所有格子均为白色。

每次能选择一个1 \times cc \times 1的矩形改变其中所有格子的颜色,c自行决定。

求在k步内能到达多少种不同的棋盘。

1 \le T \le 600, 1 \le n \le 4, 1 \le m \le 10, 0 \le k \le nm

1009. String problem

给定一个长度为n的数字串,要求选择了一个子序列(不要求连续)。

定义子序列的权值V如下。设p_1, p_2, ..., p_m是选择的子序列位置,则

V = \sum_{i=1} ^ {m} \sum_{j=1} ^ {m} {w[p_i][p_j]}

定义子序列的花费C如下。设选择的子序列中字符i出现k_i次。则当k_i = 0时,该字符花费为0,当k_i \neq 0时,该字符的花费为C_i = a_i(k_i - 1) + b_i。子序列总花费是所有种类字符的花费总和。

最大化V - C

1 \le T \le 20, 0 \le n \le 100, 0 \le a_i \le b_i \le 1000, 0 \le w[i][j] \le 1000

1010. The All-purpose Zero

给定长度为n的数列a。你可以将0改成任意整数。

求改动后最长上升子序列的最大值。

1 \le T \le 10, 0 \le n \le 10 ^ 5, 0 \le a_i \le 10 ^ 6

1011. Where Amazing Happens

已知NBA球队近70年的总冠军球队名称。

给定一个球队名称s,输出球队获得了多少次总冠军。

1 \le T \le 30, 1 \le |s| \le 30s可能包含字母、数字、标点、空格。

1012. Bubble Sort

给定冒泡排序的代码如下。

给定n元排列P。设整数i在排序过程中最左到达的位置是L_i,最右到达的位置是R_i

对于整数i \in [1,n],求出R_i - L_i

1 \le T \le 20, 1 \le n \le 10 ^ 5,大数据不超过1组。