C小红的子串 直接考虑每一个位置作为左端点时对于答案的贡献，比如第对于从第位开始来说，在第L位置开始有了l个字母，第R+1位置时有了R+1个字母，则第个位置的贡献为 R-L+1。 那么我们只要知道每一个位置后面的每一种字母最早在哪里出现即可。可以使用序列自动机进行维护。 for (int i = len - 1; i >= 0; i--) { for (int j = 0; j < 26; j++) { nxt[i][j] = nxt[i + 1][j]; } nxt[i][s[i] - 'a'] = i; }  完整代码 #include <bits/stdc++.h&gt...

从横向和纵向分别扫描，每一行或列记录1的长度，Y横向有两张长度，纵向有三种长度，E和S横纵不同长度都是2，但E的四个角上有1，而S没有，通过这个分辨出来E还是S即可   #include <bits/stdc++.h> #define int long long #define endl '\n' #define sz(x) x.size() #define lbt(x) (x)&(-x) #define all(x) x.begin(),x.end() ...

用埃氏筛O(nlog(logn))求得1~5e6每个数的质因数个数,用并查集来维护连通块的大小，合并时判断两个数的最大公约数是否含有两个以上的质因数，如果是则合并，最后遍历所有位置，输出最大连通块大小即可。维护连通块不难，建图用dfs搜索也可以实现。困难的是想到可以用gcd的约数个数判断是否优雅，和在nlogn时间内处理出每个数的质因数个数。（我最开始是对每个数分解质因数，结果是超时了），考验的是对gcd和素数筛的理解。   #include <iostream> #include<cstring> #include<algorithm> #inc...