20230921 做题记录
目录
总结
总计完成 \(3+4\) 题
上午校内练习赛，下午改了上午的题，晚上继续复习连通性问题，还写了 \(1\) 道数学题。
1 P2863 [USACO06JAN] The Cow Prom S
裸题。
点数大于 \(1\) 的强连通分量个数。
直接 Tarjan 求，最后判断点数是否大于 \(1\) 即可。
2 P2746 [USACO5.3] 校园网Network of Schools
强连通+性质
如果学校之间构成环，给任意一个发送软件是等效的，先用 Tarjan 缩点后，我们要发送先软件副本的一定是新图中入度为 \(0\) 的点，子任务A的答案就是新图上入度为 \(0\) 的点的个数
子任务B是要在缩点后得到的DAG中加入若干条边使其成为一个SCC，显然对于一个SCC，其中每一个点的入度和出度均不为 \(0\)，所以最优的情况是一条边使得一个点的入度，和另一个点的出度均加 \(1\) ，多出来的点随便连边即可，所以答案就是 \(\max\left(\left|S\right|,\left|T\right|\right)\)，其中 \(\left|S\right|\) 为入度为 \(0\) 的点，\(\left|T\right|\) 为出度为 \(0\) 的点。
P.S. 这题还有双倍经验，但要注意数据范围
3 P1407 [国家集训队] 稳定婚姻
图论建模+强连通
对于现在的夫妻，我们从女孩向男孩连一条有向边，对于曾经的情侣，我们从男孩向女孩连一条有向边，如果这对夫妻在一个SCC中，则其婚姻是 Unsafe 的，如果这对夫妻不在一个SCC中，则其婚姻是 safe 的
4 P1072 [NOIP2009 提高组] Hankson 的趣味题
数学题
根据题目分析性质即可
得到
\[\begin{cases}
&\gcd(x/a_1,a_0/a_1)=1\\
&\gcd(b_1/b_0,b_1/x)=1\\
\end{cases}
\]
可以发现 \(x\) 是 \(a_1\) 的整数倍而且是 \(b_1\) 的因子
于是可以枚举 \(b_1\)的因子，如果其同时是 \(a_1\) 的整数倍，并且满足上述两式，即答案加 \(1\)。