BZOJ2154 整除分块, 容斥原理, 线性筛

巧妙地利用了μ函数容斥

我们首先观察原题式子,一个显然的套路是枚举gcd,那么:

我们不妨假设几个辅助函数:

分块计算即可

Read more

BZOJ1934 & SHOI2007 最小割

最小割建模简单题

发现了有两个贡献冲突以后我们可以考虑使用最小割来解决这个问题

我们考虑将利益的两种分别放置在图的两侧,如果,那么从源点向连边,否则从到汇点连边,如果为朋友,那么连接,边的容量均为1,求出最小割即可

Read more

BZOJ1433 & ZJOI2009 二分图最大匹配

最近碰到的都是网络流啊...

我们发现这道题只需要判定可行性,而且方案可以自由安排,那么我们考虑用网络流来解决

令二分图的点集分别表示人和床的集合,如果认识,那么直接两边判定是否满流即可

Read more