honer规则/大数相乘/快速幂
杂项
秦久韶算法/honer规则
123456789101112ll sum(int n, vector<int> &a, int x){ ll ans = 0; ll mid = 1; for (int i = 0; i <= n; i++) { ans = (ans + (a[i] % MOD * mid % MOD) % MOD) % MOD; mid = (mid * x) % MOD; } return ans;}//带入x求f(x);f(x)=a0*x0+a1*x1...
大数相乘
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include<iostream>#include<string>using namespace std;//移位进位法string Mul(stri ...
堆和单调栈
数据结构
堆
注意：这些函数中num为形参。(懒得写指针了)
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include<stdio.h>void heapUp(int *heap,int index){ while(index>0) { int parent=(index-1)/2; if(heap[parent]<heap[index]) { int mid=heap[index]; heap[index]=heap[parent]; heap[parent]=mid; index=parent; } els ...
E6-B
E6-B KMP
题目描述
这是一道 KMP 的模板题，尽管有多种方法可以通过此题，但还是建议大家利用此题测试自己的模板。
给定两个字符串 s,t(1≤∣s∣,∣t∣≤105)s,t(1≤|s|,|t|≤10^5)s,t(1≤∣s∣,∣t∣≤105) ，请求出$ t 在在在 s $中的出现次数，及每次出现开始位置（下标从 0 开始）。
输入
第一行一个正整数 T(1≤T≤5)T(1≤T≤5)T(1≤T≤5) 代表数据组数；
每组第一行一个字符串 s(1≤∣s∣≤105)s(1≤|s|≤10^5)s(1≤∣s∣≤105) ，第二行一个字符串$ t(1≤|t|≤10^5)$ ；
输出
对于每组数据输出一行：
先输出$ t 在在在 s$ 中的出现次数 nnn ，接下来输出 nnn 个数，代表$ t$ 在$ s $中的出现开始位置（若未出现则不输出）。
输入保证$ Σ|s|,Σ|t|≤2×10^5 $。
输入样例
123452aaabaabaababababbaaba
输出样例
122 2 52 1 3
示例代码
1234567891011121314151617181920212223242 ...
C7-E
C7-E 复习安排
题目描述
猫猫即将开始紧张刺激的考期！
考期总共有 nnn 天，猫猫有$ k$ 门课需要考试。对于第 i 门课，如果想顺利通过考试，必须在考期的第 lil_ili 天到第 rir_iri 天全身心投入这门课的复习，不能复习其他课程，否则就会挂科。
猫猫最多能通过多少门课的考试呢？
输入
本题测试点包含多组数据。
第一行，一个正整数 T（1≤T≤5）T（1≤T≤5）T（1≤T≤5），表示数据组数。
对于每组数据：
第一行，两个正整数 n,k（1≤n≤105，1≤k≤n）n,k（1≤n≤10^5，1≤k≤n）n,k（1≤n≤105，1≤k≤n），分别表示考期天数和课程数。
接下来 $k $行，每行两个正整数 li,ri（1≤li≤ri≤n）l_i,r_i（1≤l_i≤r_i≤n）li,ri（1≤li≤ri≤n），表示通过第 i 门课的考试所需的复习起讫天数。
输出
对于每组数据：
输出一行，一个整数，表示最多能通过的考试数量。
输入样例
1234567891028 41 12 44 56 85 31 32 43 5
输出样例
1231
提示
对于样例中第一 ...
排序
排序
插入排序
1234567891011121314151617void InsertSort(int a[],int l)//从小到大{ int temp; int j; for(int i=1;i<l;i++) { if(a[i]<a[i-1]) { temp=a[i]; for(j=i-1;j>=0&&temp<a[j];j--) { a[j+1]=a[j]; } a[j+1]=temp; } }}
计数排序
123456789101112131415161718192021222324252627282930313233343536373839//通常用于元素大小不是特别大时vector<int> countSort(vector< ...
字符串匹配
字符串匹配
前缀函数(π\piπ函数)
定义
给定一个长为nnn字符串SSS，其前缀函数被定义为一个长度为nnn的数组π\piπ。其中π\piπ的定义是：如果子串s[0...i]s[0...i]s[0...i]有一对或多对相等的真前缀与后前缀，π[i]\pi[i]π[i]等于他们相等的最长长度，没有则为0.
具体实现
遍历字符串，每次都从最大的π\piπ开始比较。
1234567891011121314151617vector<int> piFunction(string s){ int n = s.length(); vector<int> pi(n); for(int i=0;i<n;i++) { for(int j=i;j>=0;j--) { if(s.substr(0,j)==s.substr(i-j+1,i)) { pi[i]=j; break; } ...
