【题解】CodeForces-1876/1877-526互联

CodeForces-1877A Goals of Victory

答案是 \(-\sum_{i=1}^{n-1} a_i\)。

按 \(b_i\) 排序，贪心取 \(b_i\) 小的，如果比 \(p\) 大就取 \(p\)。注意初始是要花费 \(p\) 的。

\(k>3\) 一定无解。

\(k=1\) 时只能取 \(0\)。

\(k=2\) 时一定是只在某个位置变为 \(0\)，那么要求是 \([1,n]\) 的数或是 \(n\) 的倍数。

剩下的情况 \(k=3\)。

从大到小枚举 \(a_i\)，设有 \(cnt\) 个位置是 \(i\) 的因数且未被删去，\(tot\) 个位置未被删去，那么 \(a_i\) 的贡献次数是 \((2^{cnt}-1)2^{tot-cnt}\)，之后将这个 \(cnt\) 个位置都删去。

考虑 \(i\to a_i\) 连边，题目变成如果 \(u\to v\)，那么 \(u\) 没有删去则 \(v\) 一定删去。

变成黑白染色，白点后必须连黑点，黑点至少被一个白点连接。

形成内向基环树森林，树的部分正常黑白染色即可。环的部分如果存在一个已经被染黑的节点 \(u\)，那么 \(u\) 连出的这条边没有意义，直接断成链处理；如果不存在则偶环可以任选位置开始黑白染色，奇环无解。

后面的以后再补。