A 辞树的QAQ水题 时间限制 1s            内存限制 512Mb            蒟蒻的辞树又被吊打了嘤嘤嘤。留下了属于弱者的眼泪QAQAQAQAQAAQAAQA······ 现在我 们定义辞树的悲伤值 F 。F的值为主串中子序列为”QAQ”的个数。注意字母“QAQ”不一定是 连续的，但是字母的顺序应该是准确的。 输入 输入一个整数T（0 ≤ T ≤ 20）,代表有T组数据。每组数据会给出一个字符串S,长度为len，0 < len ≤ 1000000 输出 根据每组的字符串，输出辞树的悲伤值F，每组数据换行。 输入样例 2 QAQAQYSYIOIWIN QAQQ 输...

算数基本定理 定义：任何一个大于1的自然数，如果N不为质数，那么N可以分解成有限个质数的乘积，并且在不计次序的情况下，这种分解方式是唯一的。 例如：60可以分解为 2^2 * 3 * 5 数学公式描述 N=P1^r1 * P2^r2 *P3^r3*...*Pn^rn  （P1<P2<P3<...<PN & Pi 是质数 & ri>=0）   质因子分解计算方法 算法复杂度  ( O(√n)  )  map<int,int> prime_factor(int n){      map<int,int>ans;     for(...

呃...心态崩了。 A 又是斐波那契数列？？ 时间限制 1s      内存限制 128Mb 大家都知道斐波那契数列吧？斐波那契数列的定义是这样的： f0 = 0, f1 = 1, fi = fi−1 + fi−2 现在给你一个数x，聪明的你一定知道这是斐波那契数列中的第几项。 (数据保证x一定有对应的项y，且 2 ≤ y < 1e4) 输入 第一行一个整数T，表示测试组数。 之后的T行，每行一个数x 输出 对于每个测试数据，输出一行表示数x是第几项。 输入样例 2 2 5 输出样例 3 5   思路：题意很明显，就是求斐波那契的前1e4项。但是斐波那契的增长速度很快，即使用double...

BFS(宽度优先搜索) 宽度优先搜索算法（又称广度优先搜索算法）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。 他并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。 举例： 由橙色位置出发，进行BFS：                             灰色位置表示已经走过，橙色标示当前位置 首先进行第一步：                            已经走过的位置，不需要再走了 进行第二步：                       同上，状态继承，进行第三步：                                    进行第四步...

A Math Problem 时间限制   1s        内存限制     128Mb  求:  ps:[x]表示x向下取整 输入 第一行一个整数T表示测试组数。(0<=T<=10) 第二行一个n和k，n表示序列a的长度。(1<=n,k<=1e6) 第三行n个整数表示ai (0<=ai<=1e6) 输出 每组数据输出题目描述的求和值。  输入样例 2 2 1 3 5 3 2 1 2 3 输出样例 8 2 2 思路：签到题，我们直接暴力求解就行了。 代码如下： #include<stdio.h> #include<math.h> ...

先放一个题目： 小明今年上大学，在大学里发现有很多同学都女朋友，两人整天都在一起腻歪，小明看到后感 觉很孤单，现在，给你一行括号序列，你来判断一下其中的括号是否配对。 第一行输入一个数N（0<n<=100),表示有N组测试数据。后面的N行输入多组输入数据，每组 输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保 证S中只含有”[”, ”]”, ”(”, ”)” 四种字符 ,输入以“EOF”结束。 输出 每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则 输出No。 输入样例 3 [(]) (]) ([[...

素数，是指因子只包含1和其本身的数，那么，我们怎么判断素数呢？ （以下代码均基于打表（1~1e6）的基础上完成） 1.按照定义计算 素数的定义就是一个数的因子只包含1和其本身，那么我们直接就按照定义写： #include<stdio.h> #include<string.h> #define maxn 1000000+10 int pri[maxn]; int isprime(int n) { for(int i=2;i<n;i++) if(n%i==0) return 0; return 1; } int main() { pri[1]=0; for(int i...

A题：从左往后找到第一个b[i]-a[i]非零的位置，从右往左一样，然后查这个区间内是否b[i]-a[i]完全一致并且大于等于0.   B题：dp[i][j]表示将棍子i切割成j份的信息簇（结构体），里面存储切成j份后所有棍子的最大值和最小值，要保证最大值尽可能小，最小值尽可能大，同时初始化一个切割次数cost=j。然后n^2循环，对于第i根棍，我们要在第i-1根棍的所有方案中找到满足dp[i-1][j].maxx<=dp[i][j].minn的所有cost,然后去最小值加到dp[i][j].cost中。这个可以用两个指针来求，因为可以知道对于第i根棍，j递增，则maxx,minn递减。...

题目大意： 给你两棵树，在这两棵树上分别找一个点，将其连接，使得\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}dis(i,j) 最小，其中dis(i,j)表示从节点 i 到节点 j 的边数。 Part1 首先我们需要判断我们找的这两个点应该是哪个点，对于两棵树，他们的 dis 和是固定的,因此我们需要讨论将两个点连接起来所增加的花费。 假设需要连接的两棵树A,B,两棵树上进行连接的点为 u,v ， 点 u,v 到其所在子树其他点的距离之和为Dis_u,Dis_v ，A,B 上点的个数为 P_A,P_B, 那么将其连接后增加的 dis 值为： Dis_u*P_B+Dis_v*P...

题目传送门 题目大意为： 给你一个1~n的数组,然后有m个操作，0操作为在数组最后添加一个新元素，1操作为查询区间 [l,r] 子集异或最大值。 其中输入经过加密操作，需要经过解密才能获取正确数据（强制在线） 看到了子集异或值就应该知道是使用线性基的知识。 如果按照暴力的解法一定会超时，但是我们可以通过一定贪心策略找到当前的最优解。 （下面就需要对线性基有清晰的认识了） 添加元素 对于区间[1,x](1 \leq x \leq n)，我们可以通过继承的方式找到每个区间的线性基： for(int j=30;j>=0;j--){ f[i][j]=f[i-1][j];//将上一个区间[1,i-...

线性基是用来求解数组子集最大异或和的一种方法。其思想与线性代数中的最大线性无关组相似。  线性基的性质   线性基有以下几种性质：     数组中的所有元素都能够用线性基中的元素相互异或计算出来   线性基中不存在异或值为0的子集   满足性质1的前提下，线性基中的元素个数是最少的。   线性基中每个元素二进制位数均不相同     线性基的计算   对于当前所求出来的线性基，我们在插入一个新的元素时（即使得其表示范围多一个数 x      ），要保证插入的元素与其他元素异或不为零。   根据性质4，我们能够通过位运算对插入的元素进行异或计算：   x=p1⨁p2⨁…⨁pi⨁px       p...

状压dp   状态压缩dp，是一种将复杂的状态压缩成二进制数字的算法。   旅行商问题   我们来看一个经典的旅行商问题：    给定一个n个顶点组成的带权有向图的距离矩阵d(i,j)(INF表示没有边)。要求从顶点0出发，经过每个顶点恰好一次后再回到顶点0。问所经过的边的总权重的最小值是多少？（来源于《挑战程序设计竞赛》）。   限制条件：   2<=n<=15   0<=d(i,j)<=1000    所有可能的路线会有 (n-1)! 种结果，因此我们不能够使用暴力的方法求解，那么我们需要用高效的方法来求解。   假如我们对每个顶点编号。我们可以用一个数的二进制来表...