Java教程

【记录】妙妙题

本文主要是介绍【记录】妙妙题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

新坑。

arc136 e

\(1\) 到 \(n\) 的数，如果两个数不互质则从小到大连有向边，点带权，求一个权最大点集使没有互相可达的点。

sol 首先把 $1$ 选掉，考虑两个数 $x,y$ 互相可达的条件：
  • \(x\equiv 0,y\equiv 0\) 一定可达。
  • \(x\equiv 1,y\equiv 0\) 则 \(x+minprime_x \leq y\)。
  • \(x\equiv 0,y\equiv 1\) 则 \(x \leq y-minprime_y\)。
  • \(x\equiv 1,y\equiv 1\) 则 \(x+minprime_x \leq y-minprime_y\)。

于是对于每个点表示出一个区间，如果 \(x\equiv 0\) 则为 \([x,x]\)，否则为 \([x-minprime_x+1,x+minprime_x-1]\)。

然后两个点有可达关系等价于它们弄出的区间不交，也就是说无可达关系等价于它们弄出的区间有交。

于是把点权加到对应区间然后取最大值即可。

record

为什么感觉自己就是把官方题解抄了一遍（）

这篇关于【记录】妙妙题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航