「Solution Set」06/14

P9329 [JOISC 2023 Day1] Two Currencies

简单题。因为每次尽量花银币，而且尽可能在银币花销比较小的花银币，所以整一棵主席树，二分。

P7984 [USACO21DEC] Tickets P

原来这道题当时只有我没写啊 /hsh

假如我们只从一个点进入，我们可以直接线段树优化建图。

然后我们发现一个性质：只要能从一个点走到 \(1\)，那么 \(1\sim i\) 所有点都是能走到的。到 \(n\) 同理。

于是我们可以先建反图，预处理 \(i\) 到 \(1\) 的最短路，\(i\) 到 \(n\) 的最短路。然后加起来会发现可能有重复的边，就是在 \(i\) 到 \(1\) 的时候走到了 \(i\sim n\) 里的点。

那么我们可以考虑以所有点为起点跑多源最短路，这样就像 dij 这样，消掉了可能的重复的边。

Submission

P9331 [JOISC 2023 Day1] Passport

跟上面那题双倍经验 /qd

P9333 [JOISC 2023 Day2] Council

我们考虑把问题转化为去掉一个二进制数，再给一个二进制数 \(tmp\)，求剩下的二进制数里和 \(tmp\) 与的最多的 \(1\) 的数量。

我们考虑先预处理 \(f_{S}\) 表示是否存在 \(S \subset a_i\)，这个好像随便处理一下。

我们考虑再预处理 \(g_{i,S}\) 表示是否存在 \(s'\subset S,popcount(s')=i,s'\subset a_{k}\)

然后能直接求了。但是我们好像没有排除掉自己。我们可以转移的时候记录一下由谁可以转移，记录两个不同的就行。

洛谷评测机垃圾/fn/fn/fn

Submission

你懂三天只写三道题的含金量吗？