AC. 梦想

frank_c1

Codeforces练习1

发布于2016年03月10日 | 3条评论 | 1,669阅读 | 算法框架

Codeforces 605 - 630 选做

由于本阶段自我修养还在提升中,部分题目尚未解出或未更新,只有翻译。

605B Lazy Students

图G有n个点m条边,现给出每条边的权值以及它是否在MST中,要求你判断这个MST是否存在。若存在,构造出这个图。若有多解,只需输出一个方案。(2 \le n \le 10 ^ 5,1 \le m \le 10 ^ 5)

开始时想复杂了。这道题说是构造一棵树,其实构造一条链就一定可以满足条件。只需要将所有边按权值排一个序,然后把在MST上的边不断往链上加;不在MST上的边就在已有的链上找两个还没有直接相连的结点连一条边,如果在已有的链上找不到这样的结点,那么问题无解。

605C Freelancer's Dreams

n种任务,每种任务有两种权值a,b。每种任务可以做任意实数时间,权值按比例计算,如工作1.5天可以得到1.5倍的权值a和1.5倍的权值b。现要求用尽量少的天数,使所有任务权值a的总和\ge p,权值b的总和\ge q(1 \le n \le 10 ^ 5,1 \le p,q \le 10 ^ 6)

朴素线性规划(TLE)。设第i种任务工作x_i天,则有

\begin{equation} \min {w = \sum_{i=1}^{n} {x_i}} \\ \left\{ \begin{aligned} \sum_{i=1}^{n} {a_i x_i} & \ge p \\ \sum_{i=1}^{n} {b_i x_i} & \ge q \\ x_i & \ge 0 \\ \end{aligned} \right. \nonumber \end{equation}

转化为对偶型求解,此时变量个数只有2个,且恰好为标准形式。但是无奈数据范围太大,TLE。

考虑一下这道题的特殊性质:变量只有2个。变量只有2个,是可以用图解法的呀!画个图试试。
(未完待续)

607B Zuma

有一个长度为n的字符串,每次可以从串中删除一个回文串,最少需要多少次可以删完。(1 \le n \le 500)

607C Marbles

在网格图上有两条长度为n的路径,这条路径可能会和自身相交,如(0,0)-(0,1)-(1,1)-(1,0)-(0,0)-(-1,0),但是不会有回头路,不存在(0,0)-(1,0)-(0,0)这样的路径。在两条路径的起点都有一个大理石,每次可以对两块大理石进行一次移动,即同时向某个方向移动一格,特别地,大理石移动后必须还在原来的路径上。如果某一块大理石的移动不合法,则这块大理石这次移动将被忽略。如果存在一个操作序列,使得两块大理石可以同时到达终点,则输出YES,否则输出NO。(2 \le n \le 10 ^ 6)

609B The Best Gift

n本书,有m种类型。求从n本书中随机取2本,且这两本书类型不同的方案数。2 \le n \le 2 \times 10 ^ 5,2 \le m \le 10

乘法原理,统计一下每两种类型的方案数即可。

609C Load Balancing

n个服务器,初始时第i个服务器要处理m_i个任务。现在要求任务量最多和任务量最少的服务器相差最小,每次可以把某一服务器上的一个任务移到另一个服务器上,求最小次数。

显然调整之后任务量最多和任务量最少的服务器至多相差1,我们只需要令每个服务器的任务量尽量平均即可。

610C Harmony Analysis

构造4个2 ^ k维空间的2 ^ k维向量(0 \le k \le 9),使得任意两个向量之间互相垂直,向量的坐标值只可以是1或-1。n维空间向量a,b垂直当且仅当

\sum_{i=1}^{n} {a_i b_i} = 0

我们观察到如果两个向量a,b是垂直的,那么将其中一个向量所有坐标值符号取反,它们还是垂直的。另外,如果我们得到两个垂直的向量a,b,那么将a,b分别复制一遍得到的向量(a',b')也是垂直的。利用这两个性质,我们可以由2 ^ {k-1}维的可行解直接推得2 ^ k维的可行解。初始解为' + '或' - '。

610D Vika and Segments

有一个网格图,每个网格对应一个坐标(|坐标值|\le 10 ^ 9)。有n次操作,初始时格子都是白色的,每次操作将一段连续的网格涂黑,每一段连续的网格一定平行于坐标轴。求被涂黑的网格数。(1 \le n \le 10 ^ 5)

611D New Year and Ancient Prophecy

有一段长度为n的没有前导0的数字串,将数字串分割成若干段,满足:1.每一段是一个没有前导0的正整数;2.这些正整数按原顺序是严格单调递增的。求合法分割的方案数。(1 \le n \le 10 ^ 5)

611E New Year and Three Musketeers

有三个火枪手,能力值分别为A,B,C。有n个罪犯,第i个罪犯能力值为t_i。火枪手可以独立解决不比他能力值高的罪犯,也可以多个人一起解决能力值不比他们能力值总和高的罪犯,解决一个罪犯的时间是1小时。保证每一个罪犯都可以被解决,现要求解决所有罪犯的最少时间。(1 \le n \le 200000)

613B Skills

n个非负整数,第i个整数为a_i。有m次操作机会,每次可以选择某个整数加1;存在一个上限A,任何时刻整数的值不能超过A。设在操作完成后,这些整数最终值达到A的个数为x,这些整数的最小值为y,给定参数c_f,c_m,求一种方案,使得c_f x + c_m y最大。(1 \le n \le 10 ^ 5,1 \le A \le 10 ^ 9,0 \le m \le 10 ^ {15},0 \le c_f,c_m \le 1000)

613C Necklace

n种字母,第i种字母有a_i个。要求你用上所有字母,构造一个字符串,满足令尽可能多的is[i+1...n]+s[1...i]是一个回文串。若有多解,输出任意一个。(n \le 26,\sum_{i=1}^{n} {a_i} \le 10 ^ 5)

615C Running Track

有两个长度均不大于2100的字符串s,t,在s中可以截取若干段子串[x_i,y_i],若x_i \le y_i,表示是按原顺序截取;若x_i>y_i,表示是按原顺序反向截取。要求截取的若干段子串按某顺序排列可以组成字符串t。若无法满足上述条件,输出-1;若可以满足,还需要使截取的子串段数尽量小。

615D Multipliers

正整数nn=p_1 p_2 p_3...p_m形式给定,其中p_in的质因子。求n的所有因数之积\mod 10 ^ 9 + 7的值。(1 \le m \le 2 \times 10 ^ 5,2 \le p_i \le 2 \times 10 ^ 5)

615E Hexagons

在由无穷多个正六边形组成的区域中建立形如下图的坐标系:

图中标出的坐标为各六边形中心所在的位置。现在沿下图的路径从(0,0)开始移动,每次可以移动到一个相邻的六边形中心。求移动n次后所在的坐标。0 \le n \le 10 ^ {18}