20251126

· · 个人记录

T1

思路比较简单。到达之后根据洋流的方向直接流就行了。修改了边权就为1，没改边权就为0。跑任意一个最短路算法即可（spfa不行）。我使用了01-bfs。

注意：字符串题仔细分辨大小写。

T2

很神奇的题目，把位运算和加法结合起来了。看到异或先拆位。

由于异或不会进位，加法会进位。所以考虑计算

然后做容斥即可得到答案。

有一个关键观察是如果进位，会影响这一位的答案，且影响的方式是翻转这一位。

T3

隐隐约约能感觉到这是个dp。和上次一样的输出 ans_1 \sim ans_n。

然后我没有设计出来dp状态。我没有跳出“记录上一个11的位置”这个坎。而正解的dp又很绕，很多步。所以在中途就断掉了。

T4

最容易想到的是 $O(kn\sqrt n \log n)$。但是很难做到。 然后是 $O(\frac{kn^2}{w})$。接着是 $O(2^kn \log n)$。（这是对的） 但是从复杂度入手还是太不够直接了。没想出来。只能从做法入手。