Educational Codeforces Round #105 A-Z Graph - 图论 + 构造

题意

有$n$个点,$m$次操作。操作有三种:

  1. + u v c。建立uv的有向边,边上的字母为c。保证不会重边。
  2. - u v。删除uv的有向边。保证有边可删。
  3. ? k。问你是否存在这样的k个点,使v1->v2->v3->...->vk的边构成的字符串和vk->vk-1->vk-2->...->v1的边构成的字符串相同。(点可以重复

题解

点可以重复那就很显然了。

假设有解,那么必然存在v1->v2v2->v1两条边。

如果k是奇数,那我们可以不假思索的得出这样的路线:v1->v2->v1->v2->v1。其返回的路线也是v1->v2->v1->v2->v1。那不管v1->v2v2->v1的字母是啥,只要k是奇数,就一定是一样的。

如果k是偶数就稍微麻烦一点点。以k=4为例,假设有解,解为:v1->v2->v3->v4。其反过来是v4->v3->v2->v1。且这两个的字符串相同。
于是我们可以发现v2->v3v3->v2的字母一定是一样的。那就很简单了。
我们其实可以构造v2->v3->v2->v3,其反面是v3->v2->v3->v2

综上,对于k是奇数,我们找能直接互联的两个点。如果k是偶数,找能直接互联且字母一样的两个点。

代码

Submission #114446213 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论