WORIA

https://ac.nowcoder.com/acm/contest/5668 A - Clam and Fish   题意：有 n 天，每天可能 有/无🐟，有/无蚯蚓。在有🐟的时候可以直接拿一条🐟，有鱼饵时可以拿一个鱼饵。如果有鱼儿可以钓一条鱼。每天只能进行一个操作，问最终最多有几条鱼。 显然有鱼直接拿🐟，什么都没有可以用存的鱼饵钓鱼，其它时候可能拿鱼饵也可能钓鱼。 但是鱼饵不能拿太多，否则就没有时间钓鱼了。 先在所有有鱼饵的日子里拿鱼饵，看多出几个，这里的一半日子可以用来钓鱼。 1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const ll mod = 998244353;const int N = 2e6 + 10;int T; ...

https://ac.nowcoder.com/acm/contest/5667 F - Fake Maxpooling   题意：nm的矩阵，a[i][j]=lcm(i,j)a[i][j]=lcm(i,j)a[i][j]=lcm(i,j)，经过k*k的最大池化，求最终矩阵的元素和。 求出 lcm 之后观察发现当 k>1 时，最终的矩阵是递增的，所以可以滑动窗口一直滑，也不需要删除已经划过的了，因为后面必定大于前面。 至于求lcm，直接求也不会T，但是题解里用了类似二维埃氏筛的方法，还挺秀的。 不过这样多一个数组，内存会超。。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3 ...

https://ac.nowcoder.com/acm/contest/5675 J - Identical Trees   题意：给定两棵树，要求修改最少的第一棵树上的节点编号，使得两棵树同构。 树上dp+费用流 dp[u][r]dp[u][r]dp[u][r] 表示 第一棵树上点 u 对应第二棵树上点 r，最少需要修改的节点数。 从两个根开始向下递归，对于所有子节点的两两对应情况都需要求，假设现在已经求出来所有子节点两两对应的结果，需要得到点 u 的结果。 需要把树1上的子节点重新排列，与树2上的子节点一一对应，结果就是各个子节点求和+根是否需要修改。 重新排列对应，使得总和最小，那么就是二分图上求费用流。 有些博客树哈希先判断两棵子树是否能对应，只连能对应的情况，其实不需要判断两棵子树是否能对应，如果不能对应，一定是在某个子节点儿子数量不同，或者两棵树儿子数量没法一一对应，只要把儿子数量不同的情况的dp值设为INF即可。费用流是在保证最大流的基础上求最小费用，所以如果没法只要合法的情况一一对应，求出的结果一定包含INF的情况，也就是无解。这也是必须用INF的原因，如果不用INF， ...

https://ac.nowcoder.com/acm/contest/5666#question F. Infinite String Comparision   题意：给定两个字符串，且可以无限循环，问两个无限的字符串的字典序大小。 如果两个长度不是倍数关系，那么第二次比较一定是每一位向后移动一位，所以如果第一次比不出大小，第二次还是比不出，则一定是两个串都只有一个字符，否则两次内一定有结果。 如果成倍数，比一次长度最大的即可。 12345678910111213141516171819202122232425262728#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const ll mod = 998244353;const int N = 2e6 + 10;char a[N], b[N];int ck() { int n = max((int)strl ...

http://acm.hdu.edu.cn/contests/contest_show.php?cid=887 1003 - Slime and Stones   题意：两个人，两堆石子，每次操作可以从某一堆拿任意多个，或者从两堆分别拿 x，y 个，要求 ∣x−y∣≤k|x-y|\le k∣x−y∣≤k。先拿完的胜，问先手能否必胜。 扩展威佐夫博弈 扩展威佐夫博弈裸题，设 ∣x−y∣<d|x-y|<d∣x−y∣<d，则第 kkk 个奇异局势为 (⌊2−d+d2+42k⌋,⌊2+d+d2+42k⌋)\left ( \left \lfloor \frac{2-d+\sqrt{d^2+4}}{2} k \right \rfloor,\left \lfloor \frac{2+d+\sqrt{d^2+4}}{2}k \right \rfloor \right )(⌊22−d+d2+4​​k⌋,⌊22+d+d2+4​​k⌋)，面对奇异局势的必败。 证明什么的咱也不会 就贴个大佬链接吧 https://www.cnblogs.com/Khada-Jhin/p/9609561.ht ...

http://acm.hdu.edu.cn/contests/contest_show.php?cid=886 1004 - Discovery of Cycles   题意：给定一张无向图，边集中的每条边给了编号，多次询问，问只保留编号在 [l,r][l,r][l,r] 的边，是否有环。 只要判断环，可以考虑并查集。但是这里有多次询问，说明需要动态修改加边删边，所以要考虑 LCT。 由于询问的端点可能抖动，所以即使离线后按照一维排序，另一维仍可能抖动，不能保证复杂度。 但是可以发现在一张已经有环的图上再加边并不会使得它没环，所以只要预处理出 i 作为左端点，第一次出现环时的右端点，再对于每个以 i 为左端点的询问，判断询问的右端点是否在预处理得到的右端点更右即可。 动态删边加边要用到 LCT，这里只需要一些基础操作，link 加边，cut 删边，findroot 用来找根判断是否已在同一棵树。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525 ...

http://acm.hdu.edu.cn/contests/contest_show.php?cid=885 1007 - Game   题意：二维平面上给定 n 个点，要求从第一个点开始移动到任意一个没有到过的点，并且移动的距离要比上一次远。两个人轮流操作，不能移动的输，问先手能否赢。 博弈 做法一：直接dfs记忆化搜，其实不需要记录vis过的点，也就是说“不能走到走过的点”这个限制是假的。 假设之前 A 走到过 j，现在 B 由 i 又走到 j，下一步由 A 来操作。 如果此时 A 没法移动了，那么当 A 第一次在 j 点时，A 就可以移动到 i，也就限制了 B 不能再走到 j 了，也就相当于这样的困境不会出现。 而如果此时 A 可以移动，假设 A 走到了 k，那么 A 完全可以在第一次到 j 时直接走到 k。 如果是由 A 从 i 走到 j，那么是否进行这个操作的决定权还是在于 A。 也就是说，能否走重复点并不会增大或减小每个人对局面的主动性。 1234567891011121314151617181920212223242526272829303132333435363738 ...

http://acm.hdu.edu.cn/contests/contest_show.php?cid=884 1010 - Expectation   题意：给定一张无向图，AND生成树的权值为生成树上所有边的AND和，问这张图的生成树权值的数学期望。 遇到按位与的显然可以遍历每一位操作，由于最终要求总的权值和，所以遍历每一位，得到各自的权值和，再按照位加起来，就是总和。 求无向图的生成树个数用矩阵树定理，对于每一位重新建图，得到这一位的生成树个数。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 5e5 + 10;const ll mod = ...

http://acm.hdu.edu.cn/contests/contest_show.php?cid=883 1012 - Set1   题意：给定奇数 n，从包含 1 到 n 的集合中每次先删去最小值，再随即删去一个数，对每个 i 问最终剩下 i 的概率。 显然如果 i<n−12i<\frac{n-1}{2}i<2n−1​ 则必定为 000. 后面 n−in-in−i 个数要在前面某几轮手动删去，所以要对应前 i−1i-1i−1 个中的 n−in-in−i 个，被对应到的表示是被作为最小值删去的。则有 Pi−1n−iP_{i-1}^{n-i}Pi−1n−i​. 前面还剩下 i−1−(n−i)i-1-(n-i)i−1−(n−i) 个，这些两两配对，每一对中小的那个作为最小值删去，大的手动删去。也就是不断从 i−1−n+ii-1-n+ii−1−n+i 中选 222 个删去，就是 C2i−n−12⋅C2i−n−32⋯C22/P2i−n−122i−n−12C_{2i-n-1}^2\cdot C_{2i-n-3}^2\cdots C_2^2/P_{\frac{2i-n-1} ...

http://acm.hdu.edu.cn/contests/contest_show.php?cid=882 1007 - Go Running   题意：每个人可以选择任意的时间开始，任意时间结束，从任意位置出发，向左或右跑步，给出了 n 个报告，每次告诉你在第 t[i]t[i]t[i] 秒时坐标 x[i]x[i]x[i] 处至少有一个人。问最少有几个人跑过步了。 最小点覆盖/二分图匹配 如果 x[i]−t[i]=x[j]−t[j]x[i]-t[i]=x[j]-t[j]x[i]−t[i]=x[j]−t[j] 则 i，j 可以视为同一个人向右跑。 如果 x[i]+t[i]=x[j]+t[j]x[i]+t[i]=x[j]+t[j]x[i]+t[i]=x[j]+t[j] 则 i，j 可以视为同一个人向左跑。 所以问题变为平面上 n 个点 (xi,ti)(x_i,t_i)(xi​,ti​)，要用最少的斜率为正负 1 的直线穿过所有点。 本来也想过网络流，但是想着网络流复杂度太大了，但是其实 Dinic 在二分图上的复杂度是 O(mn)O(m\sqrt n)O(mn​) 的。 每个点可以被两 ...