GreenHatHGのBlog

洛谷P2819图的m着色问题, POJ 1129 Channel Allocation 模板题—洛谷P2819图的m着色问题 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354/*代码 C++11，0.77KB提交时间 2019-04-04 15:54:31耗时/内存277ms, 888KB*/#include <cstdio>using namespace std;const int MAXN = 1E3;bool gra[MAXN][MAXN] = {false}; //判断两个点是否连通int color[MAXN] = {0}; //存每个点已经涂成的颜色,值为0则是没有被涂色int n, k, m, e1, e2, ans = 0;bool check(int num){ for(int i = 1; i <= num; i++) {...

L2-016 愿天下有情人都是失散多年的兄妹 L2-016 愿天下有情人都是失散多年的兄妹 思路找到并标记两人的5代以内祖先，如果发现已标记过的祖先，就说明两人有共同祖先 存储和查找输入的数据包含一个人的ID、性别和父母的ID，为了方便可以就用一个结构体来存储数据，声明一个结构体数组， 其数组下标代表这个人的id，结构体属性有父母id。另外开辟一个数组空间来保存性别，一个数组空间保存标记信息。 坑点测试数据里面可能会判断某个人的父亲，或者母亲和某个人是否能结婚，所以也要标记父母的性别 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include <cstdio>#include <cstring>using namespace std;const int MAXN = 100005;//sex[i]:编号为i的人的性别，vis[i]：编号为i的人是否已经标...

FZU-1649-PrimeNumberOrNot-大素数判断 题目FZU-1649 思路普通素数筛法不能用于大数。此时只能用别的算法——米勒-拉宾素数测试 我们知道对于某个素数P,由费马定理得 a^p \ mod \ p \equiv a于是就有了希望使用这个来判断某个p是否是素数 但$a^p \ mod \ p \equiv a$不是p是素数的充分条件 存在有名但是极端稀少的Carmichael数，它们不是素数但是满足费马小定理，比如561, 1105, 1729, 2465, 2821,6601, 8911, 10585, 15841, 29341…。 所以如果我们只是随机的从1和p-1之间（这里p是一个待判断的正整数）取一个数a计算$a^p \ mod \ p \equiv a$的值，如果该值不是a，那么我们100%肯定p不是素数。但如果$a^p \ mod \ p \equiv a$的值是a，p可能是素数也可能不是。 费马小定理的一个特殊情况，如果n是一个素数，那么phi(n)=n-1，而任意不大于n的数a都与n互质，于是费马小定理的推论为： a^{n-1}=1...

CodeForces-236B-求因子个数 题目CodeForces-236B 题目大意先算出q=i*j*k，然后算q的因子的个数，最后把这个因子和加起来mod上一个数 记录下求解因子个数的办法 123456789101112131415161718192021222324252627282930313233343536373839404142434445/*2019-03-15 15:00:3592ms*/#include <cstdio>using namespace std;const int MAXN = 1e6 + 10;const int MOD = 1073741824;int arr[MAXN];void init(){ arr[1] = 1; for(int i = 2; i < MAXN; i++) //初始化，每一个数最少有两个因子，１和它本身 arr[i] = 2; //i*j得到一个数，代表这个数有因i和j，如果i,j相等,因子个数+1,否则+2 for(int i = 2; i*i < MAXN; i...

L2-025-分而治之 题目链接：L2-025 解析图问题！！ 刚开始是想存储在vector里面，然后如果摧毁i的话，就把对应的vector<i>清空，还有查询别的vector，如果有i的话，则去掉，然后提交了一发，过了两个test，TLE了两个（很明显暴力超时，而且暴力不对） 附上TLE代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172/*2019/3/6 20:42:45 */#include <iostream>#include <vector>#include <cstring>#include <algorithm>using namespace std;int vis[11000];int main(){ ios::sync_with_stdio(false); ...

L2-028 秀恩爱分得快 题目链接：L2-028 解析分别求出a，b与编号为i(i>0)的人的亲密度va[i]，vb[i]，还有va，vb的最大值MAXA，MAXB然后进行判断 如果MAXA对应的人是b而且MAXB对应的人是a，那么输出a，b即可 否则，分别按要求输出MAXA对应的人的编号，MAXB对应的人的编号 对于va，vb我们可以用个double数组存储，因为编号有正有负，所以得进行绝对值处理，所以得有另外一个数组g进行标记性别，同时需要注意到0这个点，因为会有+0，-0出现，所以得以字符串的形式输入 存储输入的数据，因为每行的个数都不一样，所以可以开辟一个较大的二维数组，或者用vector，这里选用vector 参考：https://blog.csdn.net/qq1013459920/article/details/86772096 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596...

利用Live CD的另外一个方法解决grub rescue方法 开机缺引导日常进grub rescue，除了set set prefix的办法外，还可以利用Live CD进行update-grub命令 从Linux LIve CD启动后，能够通过update-grub chroot到grub分区来解决这个问题 步骤参考：https://askubuntu.com/questions/254491/failed-to-get-canonical-path-of-cow 评论区还有个更好的解决方案，如果这个不行，可以试试那一个 （/dev/sda1用你在grub上安装的任何分区替换下面。所有命令都是root。） 12345678910mkdir /mnt/chrootdirmount /dev/sda1 /mnt/chrootdir#分别用proc dev sys etc bin sbin var usr lib lib64 tmp替代$dir后执行命令mkdir /mnt/chrootdir/$dirmount --bind /$dir /mnt/chrootdir/$dirc...

L2-001紧急救援 题目L2-001紧急救援 解析123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112/*2019/2/22 17:08:1056ms*/#include <bits/stdc++.h>using namespace std;const int MAXN = 1e3;const int INF = 0X3F3F3F3F;int edge[MAXN][MAXN]; int vis[MAXN] = {0}; int dis[MAXN];int num[MAXN]; //存每个点救援人员数量int path[MAXN]; //存储路径，...

prim算法，kruskal算法，POJ1251入门题目 参考：https://blog.csdn.net/qq_40306845/article/details/81540626 模板题目poj1251—Jungle Roads 题意：给你n个点，右n-1条边，每个边都有一个权值，让你求出最小生成树 题目说明不含重复边 prime 先任意选择一条边（一般直接选择第一条），连接与其相连权值最小的点，然后两个点成为一个集合体。 找这个不在这个集合体里 但是与集合体相连的权值最小的点 与集合体相连，并把该点归入集合体。 重复上一条操作，直到集合体归入了所有的点 时间复杂度 记顶点数v，边数e 邻接矩阵:O(v2) 邻接表:O(elog2v) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include <iost...

Floyd，Dijkstra， Spfa Dijkstra：适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度O(E+VlgV) BellmanFord：适用于权值有负值的图的单源最短路径，并且能够检测负圈，复杂度O(VE) SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，SPFA的最坏情况应该是O(VE). Floyd：每对节点之间的最短路径 （E为边个数，V为顶点个数） 其中N表示点数，M表示边数 Floyd 算法虽然总体上时间复杂度较高，但可以处理带负权边的图（但不能有负权回路），并且均摊到每一点对上，在所有的算法中还是属于比较优秀的算法。另外，floyd算法较小的编码复杂度也是一大优势，所以，如果要求的是所有点对间的最短路径，或者如果数据范围较小，则floyd算法比较合适。 Dijkstra算法最大的弊端就是他无法处理带有负权边以及负权回路的图，但是Dijkstra算法具有良好的可扩展性，扩展后可以适应很多问题。另外用堆优化的Dijkstra算法的时间复杂度可以达到O（M log N）。当边有负权，甚至存在负权回路时，需要使用Bellman-...