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; } ...
E5-D
E5-D 中位数
题目描述
Bellalabella 学到了中位数的知识，Bellalabella 想知道对于一个长度为 nnn 的序列 a1,a2,…,ana_1,a_2,…,a_na1,a2,…,an，所有前缀的中位数是多少。
由于 Bellalabella 学艺不精，不知道长度为偶数的序列的中位数的定义，因此她只需要你求出长度为奇数的所有前缀的中位数。
一个长度为 2n−12n−12n−1 的序列的中位数是将这个序列从小到大排序后第 n 个位置的数，例如$ [1,3,2]$ 中位数为 2，[2,3,2]2，[2,3,2]2，[2,3,2] 中位数为 222。
输入格式
第一行一个正整数 t（1≤t≤10）t（1≤t≤10）t（1≤t≤10），表示数据组数。
对于每组数据，第一行一个正奇数 n（1≤n≤105）n（1≤n≤10^5）n（1≤n≤105），含义同题目描述。
第二行 nnn 个整数 a1,a2,…,an（0≤ai≤105）a_1,a_2,…,a_n（0≤a_i≤10^5）a1,a2,…,an（0≤ai≤105），含义同题目描述。
对于得分占比 50%50\ ...
拓展欧几里得-求解线性同余方程
拓展欧几里得
欧几里得算法
原理
辗转相除法：用aaa除以bbb，得到余数rrr和结果qqq，再用除数bbb除以余数rrr得到新余数r2r2r2，再用除数rrr除以r2...r2...r2...直至余数为0此时的除数即为最大公因数。
辗转相除法的依据：
gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a\%b)
gcd(a,b)=gcd(b,a%b)
应用
求两个数的最大公约数。
拓展欧几里得
裴属定理
1 1cpp
a0x0+b0y0=gcd(a0,b0)a_0x_0+b_0y_0=gcd(a_0,b_0)
a0x0+b0y0=gcd(a0,b0)
即如果ax+by=max+by=max+by=m有解，那么mmm一定是gcd(a,b)gcd(a,b)gcd(a,b)的整数倍。
解释
联系辗转相除法的依据，我们可以得到：
b0x1+(a0%b0)y1=gcd(a0,b0)=gcd(b0,b0%a0)b_0x_1+(a_0\%b_0)y_1=gcd(a_0,b_0)=gcd(b_0,b_0\%a_0)
b0x1+(a0%b0)y1=gcd(a0 ...
