题意 给你一个数字nnn，问你有多少段连续的素数之和等于nnn 题解 通过欧拉筛线性时间得到所有的素数，并且求出他们的前缀和，接着通过双指针来求解方案数 超时思路 本来是用unordered_map来做，但是好像常数太大了，导致超时，后面改成双指针就过了 代码 #include<bits/stdc++.h> using namespace std; #define de(x) cerr << #x << " = " << x << endl #define dd(x) cerr << #x << " = " &...

题意 有两只青蛙，在一个首位相接的路上，路的长度为LLL, 它们的起点不同，一个在xxx,一个在yyy，它们的弹跳力也不同，一个青蛙一次可以跳mmm米，一个青蛙一次可以跳nnn米，问你他们同时起跳的话，多久可以相遇（也可能这辈子都遇不到了） 思路 假设跳了aaa次他们相遇了，那么我们可以得到如下方程 x+am=y+an+bLx + am = y + an + bLx+am=y+an+bL 经过移项，我们可以得到 x−y=a(n−m)+bLx - y = a(n - m) + bLx−y=a(n−m)+bL 因为x−y=cx - y = cx−y=c和n−m=dn -***th>n−m=d都是常...

题意 让你求一个子矩阵，这个子矩阵无限拓展之后，可以让原来的矩阵变成这个无限矩阵的子矩阵，并且要使得cost最小， cost是这个子矩阵的最大值 * (子矩阵宽 + 1) * (子矩阵高 + 1) 思路 很显然，我们要求的矩阵尽量小，因为横向和纵向不相互影响， 那么我们可以横向纵向求最小周期，这样就可以保证矩阵最小 求完最小矩阵的长宽后，我们就要求这个矩阵位于哪里，可以使得矩阵里面的最大值最小，这个就可以出动我们的单调队列的，首先，维护一个单调递减的队列，这样队首就是最大值，然后的话，还得主要超过(宽或者高的）我们就抛弃掉了 代码 /** * author: andif * created: ...

题意 给你两个字符串SSS和TTT，让你求SSS中有多少个子串和TTT是kkk匹配的，kkk匹配的概念就是两个字符串存在长度为kkk的子串是相同的 思路 我们计算以第iii开头有多少个子串是和TTT为kkk匹配的，然后求个和就是最终答案了 那么假设要以某位开头的话，我们可能要找到第一次匹配的地方，然后这个位置后面的字母任意取就好 比如n=5n = 5n=5， k=3k = 3k=3 S=ababaS = ababaS=ababa，T=abaT = abaT=aba 那么我们可以用kmp求出SSS中所有和TTT匹配的位置 ababa vxvxx v表示匹配，x表示不匹配 那么可以计算出每一位到它...

题意 定义函数f(s,t)f(s, t)f(s,t)表示sss在ttt中出现的次数，然后让你对每个字符串iii， 求解∏0≤j≤nf(si,sj)\prod_{0 \leq j \leq n} f(s_i, s_j)∏0≤j≤n​f(si​,sj​) 思路 长度超过最短长度的肯定为000，或者如果最短长度的字符串不全部相等的话也为000 根据这个发现，我们就可以只求最短那个串的答案即可 易错点 一开始看错题目了，累乘以为是累加 代码 /** * author: andif * created: 22.06.2023 18:16:51 **/ #include<bits/stdc++.h&...

题意 给你两个数组, AAA和BBB，长度分别为nnn和mmm，然你求AAA中长度为mmm的子数组，这个子数组A1A_1A1​，满足 (A1[1]+B[1])%k==…(A1[m]+B[m])%k(A_1[1] + B[1]) \% k == \dots (A_1[m] + B[m]) \% k(A1​[1]+B[1])%k==…(A1​[m]+B[m])%k 问你有多少个这样的子数组 思路 我们可以把上面的等式拆解下 (A1[1]+B[1])%k==(A1[2]+B[2])%k (A_1[1] + B[1]) \% k == (A_1[2] + B[2]) \% k(A1​[1]+B[1])...

题目描述 求一个最长的子串，满足下面三个性质  子串是原串的前缀 子串是原串的后缀 除了前缀和后缀，还在其他地方出现过一次  思路 首先，这个答案子串肯定是原串的border，那么我们就把nxt[n]…nxt[nxt[n]]…nxt[…nxt[n]]nxt[n] \dots nxt[nxt[n]] \dots nxt[\dots nxt[n]]nxt[n]…nxt[nxt[n]]…nxt[…nxt[n]] 都计算出来，这样就知道原串的所有border 知道这个后，我们就可以从大到小贪心的来求，首先判断nxt[n]nxt[n]nxt[n]行不行，判断可行的方法，就是2≤i<n2 \leq ...