字符串哈希学习笔记
字符串哈希学习笔记 板子：传入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)...
trie字典树
维护一个字符串集合，支持两种操作： I x 向集合中插入一个字符串 xxx； Q x 询问一个字符串在集合中出现了多少次。 所有输入的字符串总长度不超过 10510^5105（ 也就是节点数） 123456789101112131415161718192021222324252627282930313233const int N=100010;int n;char s[N];int ch[N][26],cnt[N],idx;void insert(char *s){ int p=0; for(int i=0; s[i]; i ++){ int j=s[i]-'a';//字母映射 if(!ch[p][j])ch[p][j]=++idx; p=ch[p][j]; } cnt[p]++;//插入次数}int query(char *s){ int p=0; for(int i=0; s[i]; i ++){ int j=s[i]-'a'; ...
5156
https://www.acwing.com/problem/content/5156/ 对于能够被某个数整除的数的特征的一些总结 当我们要枚举一个数的后三位来判断这个数是不是能被8整除，可能会遇到这个数不足三位的情况，可以积累一个技巧，在数前面加两个前导零，这样枚举各位百位十位的时候，就可以枚举到个位数和两位数的情况。 下面两种写法等价，第一种是第二种代数变形后的结果。 12int x = s[i] * 100 + s[j] * 10 + s[k] - 111 * '0';int x=(s[i]-'0')*100+(s[j]-'0')*10+(s[k]-'0');
矩阵乘法
123456789101112131415161718192021222324252627282930313233343536373839int n, m;int k;struct matrix{ int c[101][101]; matrix(){memset(c,0,sizeof c);} };matrix operator*(matrix &a,matrix &b){ matrix t; for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ for(int g=1;g<=m;g++){ t.c[i][j]+=a.c[i][g]*b.c[g][j]; } } } return t;}void solve(){ cin>>n>>m>>k; matrix a,b; for(int...
容斥原理应用Acwing890借鉴题解
参考文献 简单的容斥原理介绍请看下图： C++ 代码 简单的容斥原理介绍请看下图： 本题思路： 将题目所给出的m个数可以看成是m位的二进制数，例如 当p[N]={2,3}时，此时会有01,10,11三种情况 而二进制的第零位表示的是p[0]上面的数字2,第1位表示p[1]上面的数字3 所以当i=1时表示只选择2的情况，当i=2（10）时,表示只选择3的情况,当i=3时,表示2和3相乘的情况 在过程中可以用标记变量t记录,可以按照t的值来选择是”+”还是“-” 代码如下： 12345678910111213141516171819202122232425262728293031323334353637383940#include#includeusing namespace std;typedef long long LL;const int N=20;int p[N];int main(){ int n,m; cin>>n>>m; for(int i=0;i>p[i]; int res=0; ...
质因数分解
acwing的最基础模板 https://www.acwing.com/blog/content/406/ 知乎大佬给的各种数据范围模板大全：https://zhuanlan.zhihu.com/p/591377294 对于其中的一部分进行提炼形成自己的模板 1.使用场景：假设有n个数需要分解，每个数最大可能是N,下面给出的这种代码的时间复杂度是O(nlogN)O(nlogN)O(nlogN) 思想：通过O(n)O(n)O(n)线性筛预处理过程中记录范围内每个数的最小质因数，分解时每个数的最多被计算O(logN)O(logN)O(logN)次。 1234567891011121314151617181920//预处理：for (int i = 2; i < N; i++)minp[i] = i;//通过这个初始化省下bool数组空间int cnt = 0;for (int i = 2; i < N; i++) { if (minp[i] == i) prime[cnt++] = i; for (int j = 0; j < cnt...
2023牛客周赛 Round 6
https://ac.nowcoder.com/acm/contest/62622/C c题 从x!作为切入点，阶乘增长的非常快，我们可以枚举x，从而达到固定x，只剩y一个变量，问题转变为一次函数绝对值求最小值的数学问题，显然可以o（1）。 13!=6227020800=6.2270208×10913!=6227020800 =6.2270208 × 10^9 13!=6227020800=6.2270208×109 12!=479001600=4.790016×10812!=479001600=4.790016 × 10^8 12!=479001600=4.790016×108 对于13的阶乘不超过int...
Codeforces Round 784 (Div. 4)
Codeforces Round 784 (Div. 4) 感觉是所有cf里简单的一场了 D:题意：给一排白砖染色，每次可以选择两个相邻的数染成红蓝或蓝红，可以覆盖。多次询问，每次给出一个终态（红蓝白），问这个状态有没有可能作为终态？ Solution：快速猜猜题.首先发现white直接将状态分割成若干段，也就是染色操作显然不能跨过W，所以考虑单独考察某一段，发现无论怎么操作只要出现两种颜色怎么样都能成功，所以对每个段维护颜色种类数，每段的种类数都为2才合法。 1234567891011121314151617181920212223242526void solve(){ cin>>n; string str;cin>>str;str=" "+str; bool flag=true; set<char>s; bool end=0; bool st=0; for(int...
Codeforces Round 859 (Div. 4)
Codeforces Round 859 (Div. 4) 评价：比较简单的一集，简单考察思维和最基础算法 E:交互题。看了oiwiki和codeforces的文章，之前看的abc文章忘了，打算写一篇总结特点和一些典型例题，还了解了其他题型。 Solution：回到本题：只需要利用前缀和优化每次二分答案，从输入里得到我们想要的信息 123456789101112131415161718192021//cout.flush()；void solve(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){ a[i]+=a[i-1]; } int l=1,r=n; while(l<r){ cout<<"?"<<" "; int mid=(l+r)>>1; cout<<mid-l+1<<"...
最新文章