Codeforces Round 545

C

题目HERE

题目大意

n 个点 (1<=n<=100000)

m 条边 (1<=m<=100000)

有向图

从端点1出发，总共走d (1<=d<=50)天，每天能走一条边，能访问多少个不同的开放的点

开放时间表 n*d,0表示N号点 在D天关闭，1表示开放

解法

翻译自官方题解

新建一个图

图上的点为 ([1->n],[0->d-1]) O(nd)

如果原来题目图上有(u,v)

建立边 (u,t) -> (v,(t+1)%d) , O(m d d)

然后算 新图 的强连通分量，对每一个强连通分量缩点，计算 不同的开放的点的个数 = cost

在新的DAG上求最长路

假设一个点u 在新图中拆成 (u,j1)和(u,j2),也就是u 能通过某些边走到j1，注意到，新图里的边只和原图是否连通有关，所以 (u,j2) 能走到(u,(j2+(j2-j1))%d) 沿着j1->j2的路径，沿着这条路径走d-1次，那么走到(u,(j2+(d-1)(j2-j1))%d) = (u,j1+d*(j2-j1)%d) = (u,j1) 所以如果(u,j1)和(u,j2)弱连通，则它们强连通

在新的DAG(缩点后的)上 不会存在2个 u

在DAG有向无环图上 做dp

代码

待补

D

题目HERE

题目大意

交互题

1<= t,c,(t+c)<=1000

有一条链表，这个链表上有一个环，其中环的部分长度为c，非环的部分长度为t

从非环的部分开始走，目的地是 环和非环的交界处，也就是环的入口(环上)

不知道t和c

一共有10个单位可以用来走

交互次数应当<=3(t+c)

交互:

每次提供 需要移动的单位列表，比如2 4 5，那么意味着 2号 4号 5号 沿着链表跳向下一个节点

每次操作返回 哪些单位在同一个点上,如129 3745 680 表示，1号2号9号在一个点上，3.7.4.5在一个点上..

当你认为所有点都走到入口上的时候，输出done

解法

分成 甲 乙 丙

甲1步
乙2步

甲t步，乙2*t步在环上，变成环上追击问题，距离为 (c-(2t-t)%c)%c = (c-t%c)%c

然后，甲乙丙，都走1步

当丙进入环时，步数为t

甲和乙相遇后一起走，所以位置相同，甲的步数这时候为 (t+ (c-t%c)%c)+t

注意到(t+ (c-t%c)%c)是c的倍数，也就是，丙刚进入时，甲和乙也同时走到了环的入口

总耗时2(t+(c-t%c)%c)+t = 3t + 2(c-t%c)%c < 3t+3c = 3(t+c)

解了