题意：给你n个数，m个运算符，初始值为k 让你选择m个数进行计算，输出计算后的最大数，需要注意的是，计算选择必须按照顺序，不可乱序选择 本题是一个很显然的dp问题，枚举数和运算符进行计算即可。 需要注意的点1：因为计算中可能存在负数，所以我们需要同时维护一个最大值和最小值，当当前值为负数，且之后计算中存在负数时，我们就可以负负得正得到正数。 需要注意的点2：注意当我们枚举数和运算符时，当枚举的数的数量不大于运算符的数量   代码如下： #include<cstdio> #include<algorithm> using namespace std; ...

给一个数n（n <= 1000），问将这个n分解成n1，n2，n3...nk的解法有多少（k >= 1 且 n1 >= n2 >= n3 ...>= nk >= 1） 由于答案可能过大， 因此答案对1e9+7取模 1. 背包问题解决，这里可看作，结果恰好为n的，小于n的正整数有无数个的背包问题 f[i][j]表示在1~i中选择，结果恰好是j的方案数 ☆已知在j中选i最多选k个 总结果为j，在1~i中选择，1.不选i：f[i-1][j] 2.选k个i：f[i-1][k]; f[i][j] = f[i - 1][j] + f[i - 1][j - ...

给你一个区间[a, b]  (0 < a, b < )，让你求出区间内[0~9]每个数字出现的总次数 思想： 实现一个count(n, x)代表1~n中x出现的次数 然后用前缀和解决[a,b]中x出现的次数即 ans = count(b, x) - count(a, x); 对于一个数n，形式为abcdefg 找1~abcdefg中，1在d位上出现的次数即有两种情况待讨论 设我们讨论的数为x = 1 1.首数为000~abc-1， 那么efg可取000~999，共abc*999种 2.首数为abc， 2.1若x > d，共0种 2.2若x == d，那么...

刚开始看错题，一通乱搞发现了按输入顺序遍历。 参考了下大佬的博客，发现了如果区间有交集那么就不断取他们共同的区间，如果没有交集那么就计算区间到区间之间的最小距离。乱搞一通会发现要么全走2，要么n-1次2加一次1，所以我们需要纠结的就是这最后一次到底怎么走。 首先如果我们到这个区间的最短距离是奇数且这个区间长度大于1，那么说明可以走个1，但是我们还得为之后的区间考虑。   比如我们从点1 走到A区间[4,5]。 A区间[4,5]之后的下一个区间是B区间[7,8] 从1走2+1到4，从4到7得走2+1两次，共4次 但是从1走2+2到5，从5到7只要走一个，共3次 因此我们确定下端点的...

这题刚开始着重看到了g和f函数上去了，后来看到了1e18知道了应该是个分解质因数的问题 对g和f函数的参数简单理解下，f(x,y) 、g(y,p)只需要预处理出x的质因子即可，然后求解1~n中质因子的各幂次倍数有多少个即可   不过有个玄学问题，先预处理出每个质因子及其幂次的倍数的总数再跑快速幂会T，但是对于每次循环中跑就可以过。。很玄学 #include<cstdio> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const...

先占坑，日后来补 贴个代码 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 1e5 + 10; int a[N]; int val[N], cnt[N], num[N], le[N], ri[N]; int d[N][20]; int n, q, now; void RMQ_init(){ for(int i = 1; i <= now; i++) d[i][...

需要预先知道的： sa数组，其中按照数组的顺序存放着按照字符串后缀排好序的该后缀的首字符位置 rank数组，其中rank[i] = i在sa中的排名 因此sa和rank是两个互逆的数组，即sa[rank[i]] = i; 此外也可以直观表示为sa[排名] = 首字符位置，rank[位置] = 排序后的排名 height数组，height[i] = suffix(sa[i-1], sa[i]);   定理1：对于rank[j] < rank[k]，则后缀Sj...n 和Sk...n的LCP可以表示为min{height[rank[j] + 1], height[rank[j] ...

不得不说cf锻炼思维，基础题考思维，实现都很简单 本题题意如下： 给个数n，问你将1~这个数平均分布在n个组中，有两组比较，A组和B组，A组中的每个数和B组中的每个数比较，共有次，若A中某数大于B中某数，则sumAB++，否则sumBA++。然后组比较中min{sum} 现在问你所有分组情况中，最小值最大的分组是什么，可能有多组，只需输出一组即可   分析所有分组情况可知，要使最小值越大，则分布要越均匀，保证每组之间比较时都差不多，同时因为每两组之间有个比较，因此最大的min可为。为了使分布更均匀，方法则是居中分布，即我们定义一个答案数组为q[N][N] 这里定义答案数组为q[1...

本题是道阅读理解题，读懂题意了就可破。 题意： 就是h个平台，初始在h高度上，事先已经使n个平台已开，当你需要下降时，事先必须有now-1的状态为开 且每次最多下降2格，当你无法满足条件来下降时，可花费一块水晶来调整平台状态，问你最少要多少水晶来到达地面 注意下h <= 1e9 用数组存储即可，刚开始弄错题意错用unordered_set TLE了。   题解： 本题的思路是，我们一定从h高度开始下降 当我们从下降时，判断下当前所处位置now的下两个位置的平台状态，即now-1和now-2的状态 1.若两者皆开，可直接到now-2处， 2.若now-1开，now-2...

kmp是一个模式匹配串，主要作用即给出一个串t，一个串s，问s中是否有子串和串t相等的解法。 暴力时间复杂度则是O(len(t) * len(s)) 那么kmp则是在暴力匹配的情况下记录了串的已匹配特征来减少回溯的范围。 1.首先求next数组. 这里预先知道s[1~n], t[1~m]为存储的字符串 next[j]即当s[i]与t[j + 1]不相等时，我们应该回溯到 next[j] 处进行继续匹配。 因为s[i]和t[j + 1]不相等，那么可知s[1 ~ i - 1]和t[1 ~ j]是两者一一对应相等的地方 如果在t[1~j]中存在某前缀等于后缀，（前缀和后缀必须...

题意： 给一个字符串及其长度，问你该字符串的每个前缀在该字符串***有多少个 题解： kmp的next数组含义：next[i]表示在1~i中前缀和后缀的最大长度。 举例：ababab s : ababab next : 001234 a: 2 + 1 ab: 2 + 1 aba: 1 + 1 abab: 1 + 1 ababa: 0 + 1 ababab: 0 + 1 其中每个+1表示他们前缀自身， 而2 2 1 1 0 0即除了自身以外在s中出现的次数。 (这里解释下因为是自身，因此不可能有前后缀相等的情况，故单独考虑) 那么有 i:1 2 3 4 5 6 n...

赛时不停的找环以及用并查集把自己卡sb了。赛后一发入魂。 题意： 给一个序列，问你从某个位置开始传书后，要传几次才能回到自己手上 q次询问，总共有n(n <= 2e5)个序列   题解： 模拟下样例会发现是个环，所以从某个位置开始传导后，它所到达的所有位置，从这所有位置开始后，再回到自己手上都需要相同的次数，因此可以在O(n)的情况下处理出所有存在于一个集合的数，输出即可。   代码： #include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int p[N], anc[N...

数学太差自闭了。 题意： 给一个数n，问你大于等于n的数中，可以拆分成3的幂之和的最小的数，其中每个幂最多出现一次 题解： 先将n分解成三进制，然后观察，当某位出现2的时候，我们需要从大于这位的幂开始寻找一位出现0次的幂，将其改成1，同时将小于这个幂出现次数被改成1的幂的出现次数全部改成0 如：  ，3^0这个幂出现次数为2，那么从该幂开始寻找一个幂出现次数为0，那么就是3^3将其换成1，同时3^0,3^1,3^2出现次数全部换成0，即答案为 证明： 考虑极端情况： 那么对于任意的三位三进制数，如果每一位都不小于1，同时如果某位为2，那么不可能大于等于 因此得证.   ...

原题链接：https://www.acwing.com/problem/content/description/93/   题意：求从点0到点n-1的最短哈密顿路径，即0~n-1这n个点每个点必须且只能经过一次。 起点为0，终点为n-1，问你最短路径长度   题解： 设f[i][j]表示从0开始，途中经过了i这个二进制表示的数中位为1的所有点后，到达了j这个点的最短路径 举个例子i为111001110，那么这时候第1，2，3和6,7,8这6个点就经历过了。这时候到达了j这个点，其中j可能是123678中任意一个   那么我们需要考虑：在到达j这个点之前，到达的点是k，即到达f[...