WORIA

https://codeforces.com/gym/102452 J. Junior Mathematician   题意：定义 f(x)=∑i=1k−1∑j=i+1kd(x,i)⋅d(x,j)f(x)=\sum_{i=1}^{k-1}\sum_{j=i+1}^{k} d(x,i) \cdot d(x,j)f(x)=∑i=1k−1​∑j=i+1k​d(x,i)⋅d(x,j)，其中 d(x,i)d(x,i)d(x,i) 为数 xxx 第 iii 为上的数字。给定 L,R,m,(10≤L≤R<105 000,2≤m≤60)L,R,m,(10 \le L \le R < 10^{5\,000},2\le m\le 60)L,R,m,(10≤L≤R<105000,2≤m≤60) ，问 [L,R][L,R][L,R] 中有几个数 xxx 满足 x≡f(x)(modm)x \equiv f(x) \pmod{m}x≡f(x)(modm)。 数位dp 套路，要判断两个数是否相等，不需要分别记录这两个数，而只需要记录两数之差。 dp[pos][ans][pre][lim]dp[po ...

https://vjudge.net/contest/411103 K - Largest Common Submatrix   题意：给定两个矩阵，求最大相同子矩阵。 单调栈 先预处理出每个位置最长的竖向相同的长度，再遍历每行，单调栈求这一行最大的矩阵大小。 注意每次新加入单调栈中时不能存当前位置，而应该存最早的大于当前长度的位置，因为这之间虽然在栈里被删掉了但是仍然是能取到的。 细节比较多。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace std;#define ll long longconst int N = 2e6 + 10;cons ...

http://codeforces.com/gym/102428 G – Gluing Pictures   题意：给定一个字符串 S，多次询问，每次给定一个字符串 T，要用最少数量的 S 中的子串拼出串 T。问最少数量。 后缀自动机 后缀自动机是在压缩后缀。同一点上的字符串为后缀关系且出现位置最右点的集合相同，父节点是子节点的后缀，且子节点的出现位置集合是父节点的真子集。 首先要看出贪心，尽量长地匹配。 le 用于记录当前维护的连续的 S 中子串的长度。则每次 dp[i]=dp[i−le]+1dp[i]=dp[i-le]+1dp[i]=dp[i−le]+1。 如果当前节点有字符 c 的边，则直接在后缀自动机上跳这条边，同时 le+1，表明这个子串仍在延长。 否则压缩后缀，即跳parent树的 fa 边，直到有字符 c 的边。同时 le 变为这一点代表的endpos等价类中最长串长度+1，再跳 字符 c 的边。要注意不能先跳，因为跳完之后的点上的最长串可能不是 T 以当前位置为右端点的子串，而眺之前所在的点上的最长串一定是 T 以当前位置为右端点的子串。 123456789101112 ...

https://nanti.jisuanke.com/t/42391 题意：给出两个n* m矩阵，两个矩阵都为1到n* m的一种排列，求两个矩阵的最大相同子矩阵。 对于第二个矩阵的每一个位置，仅当相邻点在第一个矩阵中也相邻，才能拓展，处理出该点向由拓展出的最远长度。 则变为如下图，有一些线段，求最大矩形。 我们可以一列一列地枚举，但对于每一列，只能线性地求最大矩阵。 可以建立一个单调栈，由上到下地放入线段，初始时把第一个线段放进栈中。仅当下一条线段的长度比栈顶长或一样长时，栈顶线段可以继续向下拓展。否则对栈顶线段进行结算并弹出。 还有一种不合法的情况，由于预处理只判断了横向拓展，所以第二个矩阵中同一列的可能在第一个矩阵中并不是同一列，或者第二个矩阵中两行相邻的在第一个矩阵中不相邻，这时要把栈整个清空结算。 注意当弹出栈顶时，预留的空间仍是存在的，因此实际压入栈中的位置也要改变。 最后还要再结算一次。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 ...

https://vjudge.net/contest/413133 A - 9102   题意：有 n 个家庭，初始时每个家庭独自成为一个部落，m 个事件，5种事件：a 和 b 所在的部落合并；a 家庭被消灭；a 家庭从原本部落中离开并加入 b 所在部落；查询 a，b 是否在同一个部落；查询 a 所在部落的家庭数。每个事件还给出了这个事件所在的时间线，事件中的 kkk 表示该事件发生在第 kkk 个事件后。 dfs+离线+可撤销并查集 可持久化的结构可以尝试离线。 根据事件的依赖关系建出一棵树，dfs，当进入节点时让事件生效，当离开子树时撤销事件。 可撤销并查集通过给每个点建立一个马甲，并每次都对马甲操作，当某点的合并操作被撤销时，只要再新建一个马甲并舍弃旧的即可。 可撤销并查集不能路径压缩，例如，a 合并到 b 上，a 的子树中某个节点 c 又路径压缩直接连到了 b，这时撤销 a 的合并操作，但是 c 却仍然连在 b 上。 123456789101112131415161718192021222324252627282930313233343536373839404142434445 ...

https://vjudge.net/contest/413140 J - Spy   题意：a[i]a[i]a[i] 表示对手的每个队伍战斗力，p[i]p[i]p[i] 表示打败对手后获得的分数，b[i]b[i]b[i] 表示我方第一种人的战斗力，c[i]c[i]c[i] 表示我方第二种人的战斗力。定义我方一组选手的战斗力为 b[i]+c[j]b[i]+c[j]b[i]+c[j] ，第一种选手与第二种选手某种顺序两两组队后，与对方进行pk，共有 n!n!n! 种pk顺序，求 最大期望×n×n×n。 KM最大权完备匹配 对于两种个人，即两种点集之间连边，关键在于边权的设定。 两个人结成一队，则该队的能力值确定了，可以算出以这个队面对对面的队伍的贡献的数学期望，即若他与对面所有队伍交手，它的胜负情况可以确定，且可以贡献的值也可以 O(nlog⁡n)O(n\log n)O(nlogn) 确定，把对面所有队伍按照能力值排序，由小到大求前缀和即可，再每次二分找到位置。 若一个队伍能战胜的所有队伍的和为 sumsumsum，则总的贡献为 sum⋅Pn−1n−1sum\cdot P^{n-1}_{ ...

http://codeforces.com/gym/102460 L - Largest Quadrilateral   题意：二维平面上给定 n 个点，求最大的四边形的面积。 旋转卡壳 四边形的对角线必定在凸包上，枚举对角线。对于一条对角线，两边各找出面积最大的三角形。 旋转卡壳求最大三角形。 当对角线旋转时，三角形的最大高度也同样方向旋转，所以可以旋转卡壳。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107#include <bits/stdc++.h>using namespace std;#define ll long long#define debug(x) cout << #x ...

https://vjudge.net/contest/399466#overview E - Colorful Balloons   题意：给定一个数列和 kkk，每个数为 111 到 nnn，一个区间的权值等于 ∑i=1ncntik\sum_{i=1}^ncnt^k_i∑i=1n​cntik​，其中 cnticnt_icnti​ 为区间中数 iii 的个数，求所有区间的权值之和。 FFT 对于数 A，包含一个A的区间数为 a1⋅a2+a2⋅a3+a3⋅a4a1\cdot a2+a2\cdot a3+a3\cdot a4a1⋅a2+a2⋅a3+a3⋅a4，包含两个A的区间数为 a1⋅a3+a2⋅a4a1\cdot a3+a2\cdot a4a1⋅a3+a2⋅a4，包含三个区间A的区间数为 a1⋅a4a1\cdot a4a1⋅a4。 则A的贡献为 (a1∗a2+a2∗a3+a3∗a4)∗1K+(a1∗a3+a2∗a4)∗2K+(a1∗a4)∗3K(a1*a2+a2*a3+a3*a4)*1^K+\\ (a1*a3+a2*a4)*2^K+\\ (a1*a4)*3^K\\ (a1∗a2+a ...

statement https://acm.ecnu.edu.cn/contest/332/ E. Consistent Trading   题意：给定一张无向图，u 指向 v，边权为 w，表示 用 1 个 u 可以换 w 个 v，且 w 个 v也可以换 1 个 u。问是否可能换出无限多物品。 连接 (u,v,w)(u,v,w)(u,v,w) 以及 (v,u,1w)(v,u,\frac{1}{w})(v,u,w1​) 从任意一点出发，如果转了一圈回来时该点权值变了，则说明产生了差价，也就说明可以换出无限多物品。 由于精度问题，不能用分数算，需要用逆元哈希判断相等。要找个好的模数。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << ...

https://ac.nowcoder.com/acm/contest/3732#question A. City   题意：给定一个 (n+1)* (m+1) 的网格，找到有几条线段满足：长度大于0，两端点都是格点，中点也是格点。 找规律。 如果条直线x坐标和为偶数，则中点x为整数，y同理。则枚举出有几对这样的x，y。相乘后减去长度为0的情况，再除2去重。 123456789101112131415161718192021#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int maxn = 1e5 + 10;ll n, m;ll cnt1, cnt2;int main() { cin >> n >> m; for (ll i = 0; i <= n; i++) { for (ll j = 0; j <= n; j++)if (!((i + j) &a ...