AC. 梦想

frank_c1

2016多校联合训练2

发布于2016年07月21日 | 暂无评论 | 906阅读 | 比赛经历

没有学长的增幅…… 于是爆炸了。

1004,1005两题我们都想出了标算,为什么出题人卡常数…… 只过了四题简直药丸。

[ 施工中... , 不当之处敬请在评论中指出 ]

1001. Acperience

给定数组A,构造Bx,满足B_i \in \{-1, 1\}, x \in R_{+},并最小化

k = \sum_{i=1} ^ {n} {(A_i - x B_i}) ^ 2

输出最小的k,以最简分数形式输出。

1 \le n \le 10 ^ 5, -10 ^ 4 \le A_i \le 10 ^ 4

先确定B。如果A_i是正数,应有B_i = 1,因为B_i = -1一定没有B_i = 1优。A_i是负数同理。

于是现在每一项是(A_i - x) ^ 2(A_i + x) ^ 2的形式。化简一下可以得到

k = nx ^ 2 + bx + \sum_{i=1} ^ {n} {A_i ^ 2}

其中b可以通过A_i的正负算出来,注意到b一定是非正的。于是就是二次函数求最值问题。

时间复杂度O(Tn)

1002. Born Slippy

给定n个点的带权有根树,点i的权值为w_i

定义某点sf值如下。选择一个点序列v_1, v_2, ..., v_m,要求v_1 = sv_iv_{i-1}的祖先。最大化

f(s) = w_{v_1} + \sum_{i=2} ^ {m} {w_{v_i} \; opt \; w_{v_{i-1}}}

其中opt可能是AND, OR, XOR中的一种。

求所有点sf(s)

1 \le T \le 300, 2 \le n \le 2 ^ {16}, 0 \le w_i \le 2 ^ {16}, \sum{n} \le 10 ^ 6

g(s) = \sum_{i=2} ^ {m} {w_{v_i} \; opt \; w_{v_{i-1}}},则

f(s) = w_s + g(s)

g(s)显然可以递推,有

g(s) = \max \{g(t) + w_s \; opt \; w_t \}

其中ts的祖先。暴力DP是O(n ^ 2)的,考虑优化。

[this part is incomplete.]

1003. Call It What You Want

给定nm边的简单无向连通图。求最长简单路径长度。

简单路径定义为,不经过重复点的路径。

1 \le T \le 350, 3 \le n \le 10 ^ 4, n \le m \le n+4

1004. Differencia

维护数组ab,支持两种操作:

1. + l r x 将a_l, a_{l+1}, ..., a_r的值设为x

2. ? l r 询问对多少i \in [l,r]a_i \ge b_i

要求强制在线。

1 \le n \le 10 ^ 5, 1 \le m \le 3 \cdot 10 ^ 6, 1 \le a_i, b_i, x \le 10 ^ 9

1005. Eureka

平面上有n个点,第i个点在(x_i, y_i)。求有多少点集,满足集合中的所有点都在一条直线上。答案对10 ^ 9 + 7取模。

1 \le n \le 1000, -10 ^ 9 \le x_i, y_i \le 10 ^ 9

1006. Fantasia

给定nm边的带权无向图G。定义G_i是从G删去点i得到的图。

定义一个图G的权值如下。

1. 如果图连通,权值为所有点权的积。

2. 如果图不连通,权值为所有连通块权值的和。

G_1, G_2,..., G_n的权值。答案对10 ^ 9 + 7取模。

2 \le n \le 10 ^ 5, 1 \le m \le 2 \cdot 10 ^ 5, \sum{n}, \sum{m} \le 1.5 \cdot 10 ^ 6

这种题考场上怎么没人做啊…… 亏大了。

对每个连通块分别处理。我们DFS一个连通块时,像求割点一样维护点x在DFS树上最远能到达的祖先low(x)

我们发现,删去一个点x时,点x可能会把原来的连通块分成几块,在DFS树上就是x的祖先和x的各个子树。我们设x所在的连通块的点权积为a,则如果x的某个子树v能到达x的祖先,x删去就对它们没有影响,否则x删去会使子树v形成一个新的连通块,故我们把子树v的点权积从a中除掉再加上即可。于是对全图DFS一遍即可。

时间复杂度O(\sum{(n+m)})

1007. Glorious Brilliance

给定nm边的无向图,每个点初始有黑或白中的一种颜色。每次可以交换一对相邻结点的颜色。

求至少多少次能使所有相邻结点的颜色互不相同并给出一种方案。如果无解,输出-1。

2 \le n \le 500, 1 \le m \le n(n-1)/2

1008. Helter Skelter

给定一个01串。有m个询问,每次询问是否存在一个子串,其中恰好有a0b1

字符串以如下形式给出。设该串有n段,每段字符相同,第i段的长度是x_i。如(2,3,3)表示00111000

1 \le n \le 1000, 1 \le m \le 5 \cdot 10 ^ 5, 1 \le a_i + b_i \le |s|, 1 \le x_i \le 10 ^ 6

1009. It's All In The Mind

给定长度为n的数列A的一部分。

已知A单调不增,且A_i \in [0,100]A不是全零数列。最大化

k = \frac{A_1 + A_2} {\sum_{i=1} ^ {n} {A_i}}

输出最大的k。给定部分保证合法。

1 \le n \le 100

x = \sum_{i=3} ^ {n} {A_i}, v = A_1 + A_2。则我们需要最大化

\frac{v} {v+x}

我们将v当作常数,可知x应最小化。将x当作常数,最大化\frac{v} {v+x}等价于最小化1 + \frac{x} {v},即v应最大化。于是贪心扫一下就好了。

时间复杂度O(Tn)

1010. Join The Future

已知长度为n的数列A满足A_i \in [x_i, y_i],且满足m条限制。

i条限制形如,下标k \in [l_i, r_i]的元素的和模2的余数是s_i

求有多少个可能的A,答案对10 ^ 9 + 7取模。并输出字典序最小的方案,如果无解,输出-1

1 \le n \le 40, 0 \le m \le n(n+1)/2, 0 \le x_i \le y_i \le 10 ^ 9

考场上在czt的援助下把这题切了感觉资瓷。

首先x_i,y_i的限制并没有什么用,因为考虑的是奇偶性,我们只需记录一下第i个位置可以取多少种奇数,可以取多少种偶数即可。于是就转化成每个位置上填0,1的问题。

朴素枚举是2 ^ {40}的,考虑优化。

p_iA的前缀异或和。则对于[l, r]余数为s的限制,就可以知道p_{l-1} \; xor \; p_r = s。我们对于每个区间在l-1r连一条边。连边时若产生矛盾则无解。

于是现在图中有若干连通块。我们发现连通块中,只要有一个位置的值被确定了,其他所有位置的值也能推出。连通块之间互不干扰。我们可以枚举每个连通块的取值,然而这样并不能降低复杂度,因为最坏情况还是2 ^ {40}的。

我们发现这其中有一些大小为1的连通块与其他位置无关,可以不枚举。于是我么只需要枚举大小大于等于2的连通块的取值,没有确定的位置我们O(n)DP一遍即可。DP过程中同时维护一下字典序最小的解。情况稍有点多,需要认真考虑。

时间复杂度O(Tn 2 ^ {n/2})

1011. Keep On Movin

给定n种字符,第i种字符有a_i个。要求用这些字符造一些回文串,且字符要全部用完。

最大化其中最短的回文串长度。输出该长度。

1 \le n \le 10 ^ 5, 1 \le a_i \le 10 ^ 4

如果所有的字符都有偶数个,我们可以将其拼成一个大回文串,长度就是字符总数。

如果存在某个字符有奇数个,则最优方案下,不可能出现长度为偶数的回文串。因为我们可以将其拼到一个长度为奇数的回文串上。而两个长度为奇数的回文串是拼不起来的。

于是我们可以得到,回文串的总数就是奇数字符的个数。我们只需要把剩下的字符尽量平均分给每个串即可。

时间复杂度O(Tn)

1012. La Vie en rose

有字符串s和模板串p,长度分别是n,m

我们可以对p作一些变换,可以交换其中任意相邻的字符,且一个字符至多被交换一次。

p及其变换得到的所有串可以匹配s中的哪些位置。

1 \le n \le 10 ^ 5, 1 \le m \le \min(n, 5000)

1013. Memento Mori

给定n \times m的矩阵和某[1,4]的排列p。有k个位置上的数字是1,其他均为0

统计满足如下条件的子矩阵个数。

1. 子矩阵中恰好有41

2. 设1的位置为(r_1,c_1), (r_2,c_2), (r_3,c_3), (r_4,c_4),不妨设r_1 < r_2 < r_3 < r_4,须满足(p_i - p_j)(c_i - c_j) > 0

3. 该子矩阵不能包含任意一个满足上述两个条件的子矩阵。

1 \le n,m,k \le 2000