Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals) 做题记录

A. Andryusha and Socks

随便搞搞。。

B. The Meeting Place Cannot Be Changed

题意:给出n个人,以及他们的在一条直线上的坐标和每个人最大的行驶速度。问可以让他们相遇在同一点的最短时间。

二分答案,然后随着时间增大,每个人可以走的区间也是不断的变大,这个是满足单调性的,那么就可以保证更多的人相遇在一点。check的时候维护出来所有人可以到达的区间的左端点以及右端点,如果发现左端点大于右端点,那么就是所有人无法相遇在一点。

C. Andryusha and Colored Balloons

题意:给出一个n个点的树,让你用最少的颜色染完这棵树,要求相邻的任意三个点不能同色。

最少的颜色的话,根据抽屉原理我们需要的颜色数目最少是有最大度的点的度数加1,才可以保证相邻任意三点不同色。然后dfs就可以了,dfs时候有一些细节还是要注意的。。。

D. Innokenty and a Football League

题意:

给n个球队(n<=1000)选择队名缩写。已知每个球队的名字是 <team name> <hometown name> 的形式。取队名缩写的规则是固定的,只有两种:

  1. 选择 team name 的前三个字母作为队名缩写
  2. 选择 team name 的前两个字母与 hometown name 的首字母组成队名缩写。

如果 x 的第一类队名缩写为 x.fst ,第二类队名缩写为 x.sec。若x选择了 x.sec 作为最终的队名缩写,那么如果其他队伍满足y.fst=x.fst的话,不能以 y.fst 作为最终的队名缩写。如果是 y.sec ==x.fst 的话,则仍然可以。

每个队的队名缩写都可以从两种中任选一种,问是否能够使得每个队最终的队名缩写均不同。

先统计所有球队的fst的个数,如果某个球队的fst的出现次数大于1,那么一定只能选择sec命名。然后对于不断地枚举所有球队,看他们的fst是否出现在某些确定是选择的sec命名的球队的fst中。。。然后因为最少一轮可以确定一个球队的命名方式,所以大概是复杂度O(n^2)。。

E. Underground Lab

题意:给出n个点的m条边的一个无向图,让你用k条链覆盖所有的点(每个点在一个链中也可以多次走过)。但是链的长度必须要大于等于1且小于等于ceil(2*n/k)。

ClearY老司机告诉我,一棵树的欧拉序正好是2*n-1个节点的一个序列。那么我们直接在一个图上dfs的话,可以得到一棵生成树,那我们可以在dfs的时候也搞出来这棵生成树的欧拉序。但这个欧拉序上只有2*n-1个节点,我们可以把这些分成k段就好了,一定小于ceil(2*n/k)。我们可以取ceil((2*n-1)/k)为一个区间的长度。。。那么因为是向上取整,所以很可能出现不够k段的情况,那么我们直接随便输出好了。。。

F. Axel and Marston in Bitland

题意:给出n个点m条边的有向图,每条边有一个权值0或者1.现在让你找一条最长的路径,这个路径满足:(1)s[1]=0;(2)s[i]=s[i-1]+(~s[i-1])这样的。也就是01101001…这样的序列。如果这个路径超过了10^18的话,输出-1。

其实可以发现就是按照把整个序列分成若干个2的次幂,而且如果增加的序列长度为2^t的话,那么增加的序列第一位肯定是和原序列的第一位反过来的。我们可以倍增的来做。设表示从i到j走2^k步,且第一步为0或者1的路径是否存在。但是这样的复杂度是,太大了。。。

因为每一个的值都是0或者1,我们可以用一个bitset来维护从i走2^k步的话且起始点为0或者1的话,能到达的点。能到达就都是1。

那么转移方程就类似与floyd了:

然后找答案的时候就按照2的次幂从大到小的顺序维护答案就好了。这样的话复杂度就变成了,w为bitset压位的长度。这样就可以接受了。。。涨姿势了。。。

自己太弱了。。。。

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注