链接：http://acm.hdu.edu.cn/showproblem.php?pid=5015思路：我们可以考虑将每个列向量组看成由前一个列向量组通过线性变换得到的。矩阵快速幂的核心思想就是构造关系矩阵，即考虑当前列向量组如何由之前向量组左乘一个矩阵得到。那么考察某一列与之前一列的关系，我们发现，首先233到2333的关系是23310+3，即a0i=a0i-110+3,能够显然发现我们通过10和a01,a02,a03,a04...a0n是构造不出来这个关系的，那么我们就把这个n*n矩阵给拓展一下，多一个维度，最后加个3。然后列向量最后加个1，然后为了使得这一变换的初始能够变换过来，应该对第...

思路：很容易知道所有的情况共有2^n个，然后我们思考不可能存在的情况有多少种。我们知道每次都可以从前m+1个种取一个。当我们左边减少0个，那么右边m+1到n中任意数字减少都不行，因此答案有2^(n-m-1)-1种(真子集都是不存在的情况，-1是因为自己一个不去)当我们左边m+1个中减少1个，那么答案为C(m+1, 1)（2^(n-m-2)-1）若从左边m+1个中减少2个，那么答案为C(m+2, 2)（2^(n-m-3)-1）。。。以此类推直到最后情况即n-m-i-1==0即可代码： #include<bits/stdc++.h> using namespace std; typed...

思路：看到K这么大，我们知道这种题一般要先从找规律的角度尝试一下。f(x)=x+Mu(x)，那么跟据Mu(x)，我们知道如果x的Mu(x)为0，不管经过多少次迭代，其结果都是0如果Mu(x)不为0呢，通过对Mu(x)打表我们可以大胆猜测，在k很大的时候，要么x通过迭代到了Mu(x)=0的点，会产生-1，1的死循环。代码： #include<bits/stdc++.h> using namespace std; #define int long long const int MAXN = 1e7+10; int prime[MAXN], prime_tot; bool prime_...

思路：可以从度的角度来考虑来考虑相连如果是两个D>1的结点相连，我们知道这一定是两颗树合并了，那么树++，如果其中一个D=1，那就是一个点和并到了一颗树上，树的个数不变，如果两个D=0的点相连，树的个数++接下来考虑断开如果是两个D>1的结点断开，我们知道肯定是1棵树变成了2颗树。如果其中一个D=1，那么就是把一个叶子结点分出去了，树的个数不变。如果两个点的度都为1，那么分成的两个东西都是单个结点，树的数目--代码： #include<bits/stdc++.h> using namespace std; const int maxn = 1e8+7; int n; i...

链接：https://ac.nowcoder.com/acm/contest/7079/A思路：让求在这个区间的最小未出现的最小自然数，那么可以反向思维来求不在这个区间出现的最小自然数。那么维护一个前缀和后缀最小值即可。代码： #include<bits/stdc++.h> using namespace std; const int maxn = 1e5+7; int a[maxn]; int sm[maxn], bm[maxn]; int main() { int n, q; cin >> n >> q; sm[0] = n; b...

题目链接：https://loj.ac/problem/165拉格朗日插值重心优化 #include<bits/stdc++.h> using namespace std; #define int long long const int mod = 998244353; const int maxn = 3010; int num, x[maxn], y[maxn], w[maxn]; int q_pow(int a, int b){ int ans = 1; while(b > 0){ if(b & 1){ ...

如何判断两个数互质： 来源：https://blog.csdn.net/HelloZEX/article/details/82667263 bool isrp(int a, int b) { if(a==1||b==1) // 两个正整数中，只有其中一个数值为1，两个正整数为互质数 return true; while(1) { // 求出两个正整数的最大公约数 int t = a%b; if(t == 0) { break; } else ...

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 ———————————————— 版权声明：本文为CSDN博主「brandong」的原创文章，遵循 CC 4.0 BY-...

种子填充(连通块）紫皮书p162 要实现bfs算法需要标记数组 需要使用回溯法 #include <cstdio> #include <cstring> const int maxn = 100 + 5; char pic[maxn][maxn]; int m, n, idx[maxn][maxn];//idx是记录连通分量编号（避免一个格子访问多次） void dfs(int r,int c,int id) { if(r < 0 || r >= m || c < 0 || c >= n) return;//边界判断回溯 ...

题目地址：3rd_Practice_A:Illusive Chase 题目大意：先给你一幅图，0表示可以走，1表示障碍物。在第1s的时候，向R（右）走12步，第2s的时候，向D(下)方向走12步，第3s的时候向右走一步。问有多少个起始点满足要求。 tag：对每个点来遍DFS note：二维数组中的xy容易搞混，，， up和down的加减容易搞混 前几次提交中忽略了i=1~a的过程中碰到障碍的情况 通过此题更加理解DFS、回溯法、边界 此题的核心语句：if(dfs(cx,cy,step+1)) return 1 AC代码： #include <iostream> #inclu...

题目地址 题意：给你一个有m条权值为1的无向边的完全图，问你得到的最小生成树的权值为多少 tag:最小生成树，贪心思想 题解：能用权值为0的边就用。 那么对那m条边的端点，将能用0边到达的点都缩在一起 形成一个个连通块 在对缩完的点进行用1边连接，所以答案为缩完后的点数减一 dfs求连通块 u[x] ：与vis[x]一样的作用 set g[maxn] 每个点都记录自己与哪些点距离为1 set vis 每个点通过g[maxn]结合着vis便可知自己还与哪些点距离为0 vector ret 对dfs中的的点暂时记录与其距离为0的点 #include<bits/stdc++.h>...

内容来源 紫皮书p356 kruskal算法的思想在于合并 Kruskal算法的第一步是给所有边按照从小到大的顺序排列。这一步可以直接使用sort。接下来从小到大依次考察每条边(u,v)。 u,v如果在同一个连通分量中，那么加入(u,v)后会成环 伪代码： 把所有边排序，记第i小的边为e[i]; 初始化MST为空 初始化连通分量，让每个点自成一个独立的连通分量 for(int i = 0; i < m; i++) if(e[i].u和e[i].v不在同一个连通分量) { 把边e[i]加入MST 合并e[i].u和e[i].v所在的连通分量 } 最关键...

1.Dijkstra算法 Dijkstra算法适用于边权为正的情况。它可用于计算正权图上的单源最短路，即从单个源点出发，到所有节点的最短路。该算法同时适用于有向图和无向图。 伪代码如下： 清除所有点的标号 设d[0]=0, 其他d[i]=INF 循环n次 { 在所有未标号结点中，选出d值最小的结点x 给结点x标记 对于从x出发的所有边(x,y)，更新d[y] = min{ d[y], d[x]+w(x,y)} } 模拟Dijkstra算法:https://www.bilibili.com/video/av36886088 完整算法 memset(v, 0, si...

题目地址:https://vjudge.net/contest/354354#problem/F 参考博客：https://blog.csdn.net/qq_28954601/article/details/60969313 主要参考博客： 差分约束算法总结：https://www.cnblogs.com/wjhstudy/p/9757046.html 题意：假设当前有这样一个序列S=a1,a2,a3…an ，现在给出一些不等式，使得 ai+ai+1+ai+2+…+ai+n<ki 或 ai+ai+1+ai+2+…+ai+n>ki ，问这样的一个序列是否存在。 tag：差...