20260525

A - P3172 [CQOI2015] 选数题意从区间[L,H][L,H][L,H]中可重复地选取NNN个整数求最大公约数恰好为KKK的方案数结果对109710^971097取模。1≤N,K≤1091\le N,K\le 10^91≤N,K≤1091≤L≤H≤1091\le L\le H\le 10^91≤L≤H≤109H−L≤105H-L\le 10^5H−L≤105。容易想到O(Llog⁡n)O(L \log n)O(Llogn)的莫比乌斯反演的做法整除分块优化一下O(LH−Llog⁡n)O(L\sqrt{H-L} \log n)O(LH−L​logn)会 T。主要是求莫比乌斯函数太慢了这个O(LH−Llog⁡n)O(L\sqrt{H-L} \log n)O(LH−L​logn)的做法其实只用到几段相当于如果能在10610^6106级别求出∑i1xμ(i)\sum_{i1}^x \mu(i)∑i1x​μ(i)就好了。这个好像能用杜教筛在O(x23)O(x^{\frac{2}{3}})O(x32​)次方求出总时间复杂度O(H−L(log⁡nL23))O(\sqrt{H-L} (\log n L^{\frac{2}{3}}))O(H−L​(lognL32​))但是由于什么神秘记忆化跑出来才 300ms 左右。B - P3872 [TJOI2010] 电影迷题意有NNN部电影每部有一个价值vXv_XvX​可正可负。另有MMM个依赖关系(X,Y,dX,Y)(X,Y,d_{X,Y})(X,Y,dX,Y​)若选了XXX但未选YYY则总收益减少dX,Yd_{X,Y}dX,Y​。求选择若干电影使得总收益所有选中电影的价值之和减去所有违反的依赖惩罚最大若最大值为负则输出000。N≤100N \le 100N≤100。最小割。构建网络流用sss点到iii表示选该点iii到ttt表示不选该点。对于负数而言直接让sss到iii连∣ai∣|a_i|∣ai​∣。而正数则是让iii与ttt连aia_iai​令tot为正数之和。剩余两条边权为000。接下来加上依赖关系限制直接让yyy向xxx连dx,yd_{x,y}dx,y​就行了。最后用tot减去最大流最小割就可以了。C - P5038 [SCOI2012] 奇怪的游戏题意有一个N×MN \times MN×M的棋盘每个格子有一个正整数。每次操作可以选择两个相邻四连通的格子将它们同时加111。问最少需要多少次操作才能使所有格子的数值相等。如果无法做到则输出−1-1−1。TTT组数据N,M≤40N,M \le 40N,M≤40数值≤109\le 10^9≤109。根据数据范围大概猜测是O(n2m2)O(n^2m^2)O(n2m2)的 dp。设fx0,y0,x1,y1f_{x0,y0,x1,y1}fx0,y0,x1,y1​表示将[x0,x1],[y0,y1][x0,x1],[y0,y1][x0,x1],[y0,y1]这个矩阵变成同一个数所需要的最小代价这里记录了最小代价就可以用这个最小代价原本总和/总点数 算出都变成了什么数。对于一个x×yx \times yx×y的矩阵原本是相同的它变多少次又会相同呢首先假如x×yx\times yx×y为偶数那么一次必然可以为奇数时以上均为考场思路发现一开始方向就错了。可以发现给相邻的两个点同时加111我们可以染色可以构造出二分图使得任意两个相邻的点颜色不相同。记被染成黑的点的个数和aaa之和分别为cnta,tota白点同理。首先对黑点和白点的操作次数必然是相等的所以可以知道cnta×x−totacntb×x−totbcnta \times x-totacntb \times x -totbcnta×x−totacntb×x−totb移项可得(cnta−cntb)×xtota−totb(cnta-cntb) \times xtota -totb(cnta−cntb)×xtota−totb对于cntacntbcntacntbcntacntb若tota−totbtota -totbtota−totb为000则有解否则无解。解必然存在单调性可以二分。否则可以得到xxx的取值去check若合法则输出否则-1。对于check这个就是一个经典的二分图最大匹配了。