http://codeforces.com/group/xrTA2IaQje/contest/249069/problem/A   题目描述：给你k个n*m个矩阵 里面有不同的字母，每个图形可以用前面已有的矩阵变化过来（起初没有），花费是相同点不同字母的个数*w，或者全部赋值花费n*m*w;   问生成全部矩阵最少花费多少。   分析：把它构造成一个完全图，点是矩阵，边即两个举证之间的花费，所以问题转化为求最小生成树，注意dfs遍历树的时候只需要不走到父节点就行了，并不用标记所有点。   ac代码：  #include<bits/stdc++.h> using namespace ...

http://codeforces.com/contest/432/problem/D   题目大意 ：给你一个串问前缀和后缀相同的情况下子串出现了多少次  ，输出相同的串数，并且输出出现个数   题目分析： kmp 的next就是匹配与前缀相同多长，所以用最后的next[len]可以知道最长后缀匹配前缀的长度，又最后一个next包含了前一个短的匹配串  所以总共匹配的串数可以用next一直递归下去直到next[i]==0;                       而每一个的个数为d[i]+=d[k] ，k>i . d[i]表示 长度为i的子串出现个数 因为每一个长度至少出现一次所以...

http://codeforces.com/group/xrTA2IaQje/contest/249302/problem/D   题目描述： 对于一个图  给定你一些边表示火车能走的边，没给的就是巴士能走的边，现在要求巴士和火车不能在除终点外的点同时相遇（每走一次火车和巴士都用一小时）                       问两种交通工具最短时间中的最长时间   分析：以前做过这个题。。。。。。。。。。。 这次还是没有考虑到巴士和火车肯定有一种可以直接到达终点。   所以可以转化为求另外一种交通工具的最短路（无权） 即bfs（bfs注意也要标记走过的点，并且可以记录父节点来跟踪）   ...

题目描述  给你一个棋盘 n*n 并且让你放两个教主攻击棋盘中的位置x,y  a[x][y] 代表攻击后将得到的值  每个教主能攻击对角线上的位置，现在求两个教主不会同时攻击某个位置时获得的最大价值；   分析  ：  首先对角线 的处理用到了八皇后的处理方法   即副x+y,  和主x-y ；而两个点不会同时攻击  同一个位置  则(y=x+c)x1+y1!=x2-y2 (副 副  和主主重合容易去掉)   显然当x1+y1和x2-y2奇偶性不一样时肯定不等   ...

http://codeforces.com/group/xrTA2IaQje/contest/249302/problem/A   题目描述：有一个n*m的方格，给定起始位置，‘#’表示不可走‘ .’表示可走   超出范围的按x%n,y%m 判定是‘#’  还是‘.'  判断是否可走 ， 问是否可以走到无穷远处   分析：如果出了范围后走到了没出范围的点（x%n,y%m 相等）那么  肯定可以循环下去  也就是无穷远，因为dfs要标记走过的点 防止下次走，所以不能用是否走过来判断，                 最好设置一个记录看看该点两次走分别对应哪个点（这么简单竟然想了这么。。。。。。。...

http://codeforces.com/contest/722/problem/C   题目描述  给你一串正整数数列 a1,a2,a3......an   每次删除一个元素 并且输出此时最大连续子串和   首先从前向后删可能比较麻烦些 （每个区间肯定要遍历） ，所以考虑从后向前添元素 ，每次记录最大和 与下一次比较  ，添元素的过程中只需考虑两点   1左边是否添加   2右边是否添加   所以麻烦主要是要去遍历左右两边找和，这里解决的方法是用并差集，记录一个区间的和，  并且更新（好好理解下并差集搜索和更新与线段树，st表，树状数组的区别）   wa了一次  其实意识到了会爆int ，...

首先理一理快速幂  之前总结过但没记录下来   首先对于 将n看成二进制的形式比如 那么 以此类推 每一位都会判断一遍是否是1 是就乘起来   现在在来讲矩阵快速幂：   首先现代知识矩阵乘法 （直接上代码）：  void multi(int a[][MAX],int b[][MAX]){     int temp[3][3];     memset(temp,0,sizeof(temp));     for(int i=0;i<2;i++)         for(int j=0;j<2;j++)             for(int k=0;k<2;k++)      ...

http://codeforces.com/problemset/problem/369/C   题目描述：   给你一棵树，每条边有2,1两种情况 每次可以选择一个点走到1点（根节点） 问最少选择几个点可以把边是2的点走完   分析：加入有一个条边是2 那么只需要找有没有子节点有2的边  有的话走子节点  没有的话走这个点   这个题比较特殊的是dfs遍历树   可以学习下存储方法;   ac代码：  #include<bits/stdc++.h> using namespace std; const int MAX=1...

http://codeforces.com/group/xrTA2IaQje/contest/249069/problem/B   首先描述一下 单调栈的作用  如5 2 1 4 3  从左到右入以递减的方式入栈， 遇到大的就出栈，直到栈为空或者出现比它大的数那它就入栈   在这个过程中有一个现象，每个数都会从左到右找第一个比它大的数   那么下面题目来了：   有一串数字 a[1],a[2].....a[n]  问你这里面任意一个区间的最大值和第二大的值的异或值最大是多少；   分析：   显然每个区间枚举太耗费时间了，而且时间上也过不去，那我们可以从值入手（因为值的个数有限），回想上面的单...

与01不同的点只有一个，就是允许物品多次放入   首先分析这个问题得到状态转移方程 dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+v[i]*k);   这是最朴素的方法   实现代码：  for(i=1;i<=n;i++)     {         for(j=1;j<=V;j++)         {             for(k=0;k <= j/w[i-1];k++)             {                 dp[i][j] = max_2(dp[i][j], dp[i-1][ j-k*w[i-1] ] ...

欧拉函数 表示小于等于x的素数有多少个 如   几个性质：   1、euler(1)=1（唯一和1互质的数就是1本身）。 2、若n是质数p的k次幂，φ(n) = p^k - p^(k-1) = (p - 1)*p^(k - 1)， 因为p为质数，所以与n不互质的数只有p的倍数，一共有p^(k-1)个。 3、若m, n互质，φ(m*n) = φ(m) * φ(n) 4、一个数与其互质的数(<n)的总和是euler(n)*n/2 5、欧拉定理：如果n为正整数且a是一个与n互质的数，那么：a ^ φ(n) ≡ 1 (mod n)

经典问题： 有n个物品，分别价值为value，重为volume，  放入一个m的背包 （保证放满） 问如何使得价值最大   分析：  首先从最后那个状态来看   dp[i][j]=max(dp[i-1],dp[i-1][ j-vo[i] ]+va[i])，起始状态显然是dp[0][j]=0，有了起始状态 我们便可以一次一次的转移到最后的最大值   对于一些细节上的解释：枚举j（重量）时有些j 并不会用到，也不会产生影响（遇到两个重复出现时，会取最大的），因为各个情况都要考虑到所以每个j都考虑，也有可能数据太大了此时就需要离散化 ，只枚举必须的部分。   因为状态转移是根据i转（j两两之间没有关...

题目描述 ：给你n个单词，  并且有m行每行有一个数字两个单词 数字代表之间的关系，2表示意思相反 ，1表示同义   之后有q行询问 每行两个单词 输出它两的关系   2 ≤ n ≤ 10^5, 1 ≤ m, q ≤ 10^5   分析：典型的带权并差集问题， 带1权值表示反义，0权值表示同义，在更新时用异或和维护他们之间的关系，  当合并时因为两个个方向走到尾 其异或和相等，而两者异或和为0 所以一个点的权值等去另外三个的异或和    ac代码  #include<bits/stdc++.h> using namespace std; co...

题意描述 给你 m段区间和 表示1->n  问有多少段是不满足条件的？   (1 <= N <= 200000, 1 <= M <= 40000)   题目分析： 具有很明显的并查集气息（多种情况矛盾），可以把[1 , 2] 变为(0 , 2] 因为我们要表示他的权值，然后把各个段按并查集放到一起：   带权并查集注意事项：节点更新时如何更新权值，引生出两种情况 是否在同一颗树上   学习链接：https://blog.csdn.net/yjr3426619/article/details/82315133   ac代码：  #include<bi...