爱飞鱼的blog

子序列自动机 判断s是不是t的子序列 123456789101112131415161718192021bool isSubsequence(string s, string t) { int m = t.size(); vector<array<int, 26>> next(m + 2); t = " " + t; for (int i = m; i >= 1; i--) { for (int j = 0; j < 26; j++) { if (j == t[i] - 'a') next[i][j] = i + 1; else { next[i][j] = next[i + 1][j]; } } } int p = 1; for...

给定 n×n 的矩阵 A，求 A^k。 12345678910111213141516171819202122232425262728293031323334353637typedef long long LL;const int mod=1000000007;struct matrix{ LL c[101][101]; matrix(){memset(c, 0, sizeof c);}} A, res;LL n, k;matrix operator*(matrix &x, matrix &y){ //矩阵乘法 matrix t; //临时矩阵 for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) for(int k=1; k<=n; k++) t.c[i][j]=(t.c[i][j]+x.c[i][k]*y.c[k][j])%mod; return...

线段树 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125template <class Info, class Tag>struct LazySegmentTree { int n; vector<Info> info; vector<Tag> tag; LazySegmentTree() : n(0) {} LazySegmentTree(int n_, Info v_ = Info()) {...

N≤400，所有 0≤aij<1e9+7 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647const int N=405,P=1e9+7;int n;LL a[N][N<<1];LL quickpow(LL a, LL b){ LL ans = 1; while(b){ if(b & 1) ans = ans*a%P; a = a*a%P; b >>= 1; } return ans;}bool Gauss_Jordan(){ for(int i=1;i<=n;++i){ //枚举主元的行列 int r = i; for(int k=i; k<=n; ++k) //找非0行 if(a[k][i]) {r=k; break;} if(r!=i)...

高斯消元 1.高斯消元解线性方程组。这个模板只处理n方程n个未知数的，分别处理无解，无穷多解，以及唯一解的情况。结果存在最后一列中（一开始的常数项）， 无解返回0 唯一解返回1 无穷多解返回2 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657int gauss(vector<vector<db>>& a, int n) { int r = 1; // 当前行 for (int c = 1; c <= n; c++) { // 消元进行到第c列 // 1.找到c列的最大行t int t = r; for (int i = r; i <= n; i++) if (fabs(a[i][c]) > fabs(a[t][c])) ...

字符串哈希学习笔记 板子：传入0base即可 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394struct Hash { static int findprime() { random_device rd; mt19937 gen(rd()); int n = gen() % 900000000 + 100000000; if (n % 2 == 0) n++; while (true) { bool ok = 1; for (int i = 3; i * i <= n; i += 2)...

https://www.acwing.com/problem/content/5367/ 题目如果只需要输出最大值，我都没有问题。每次需要输出方案的时候,我似乎都需要先统计最大值，再重新扫描一遍找所有能够取得最大值的方案，然后在这些方案中找到最大值。最好的做法应该是在找最大值的过程中就维护题目要求方案的排序关键字，有时候这个关键字不是我们枚举顺序能决定的，我们就需要单独处理。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071// Problem: 奶牛报数// Contest: AcWing// URL: https://www.acwing.com/problem/content/5367/// Memory Limit: 256 MB// Time Limit: 1000 ms// // Powered by CP Editor...

Codeforces Round 294 (Div. 2) C题：有n个老师，m个学生，a方案是1老师和2学生，b方案是2老师和1学生，求最多可以成功达成多少套方案？ Sol：wa了一发贪心，样例怎么全过了？从纯数学的角度去看，就是线性规划，只不过由于参数不确定需要分类讨论，我们只需要设x套a，y套b，求x+y的最大值（在两个总人数的约束条件下。 1234567void solve(){ cin>>n>>m; if(m<n)swap(n,m); if(m>2*n)cout<<n<<endl; else cout<<(n+m)/3<<endl; //cout<<ad+tmp<<endl;} 考虑到数据范围很小，官方正解是直接暴力枚举 12345678910111213141516171819202122int main() {#ifndef ONLINE_JUDGE freopen("in",...

https://zhuanlan.zhihu.com/p/646586178 待补

找到最小的数满足里面有n个不被x整除的整数，m个不被y整除的数，且这n个数和m个数完全不重合。x和y都是质数 1234567891011121314151617181920212223int n, m,a,b;//int a[N];bool check(int x){ int n1=x/a; int m1=x/b; int c=x/(a*b); int p=n1-c,q=m1-c; int lf=x-n1-m1+c; int p1=max(m-p,0LL); int q1=max(n-q,0LL); if(p1+q1<=lf)return true; return false;}void solve(){ cin>>n>>m>>a>>b; int l=0,r=2e9; while(l<r){ int mid=(l+r)>>1; if(check(mid))r=mid; else...