Alex0319

题解

PAT(11) poj(16) 算法(1)

/ 注册

全部文章 / 题解（共27篇）

poj1182 266ms 并查集

没有大佬那么厉害的可以直接得出结论，只能把情况都列出来，其实一共只有18种情况，所以不妨头脑风暴一次，然后稍加整理(先根据d的值分类，再根据rank[a]的值进行分类)规律就显然了。详细阐述下整理部分吧。首先把d=1，2，这是两种情况，然后细分，例如，当d=1，把rank[a],rank[b],ra...

Union_Find poj

2019-08-29

0 735

poj1988 266ms 并查集

#include<cstdio> using namespace std; //说难不难，说简单不简单，就是并查集的处理，额外的两个数组是关键 //解决并查集有关问题时，如何利用辅助数组记录节点与根节点的关系是解题的关键 const int N = 3e4; int father[N+5...

Union_Find poj

2019-08-28

0 553

poj1703 带权并查集344ms

include using namespace std;//带权并查集难点就是关系更新，其他的与普通并查集无异const int Maxn = 1e5;int rel[Maxn+5],father[Maxn+5];//0同1异void init(int n){ for(int i = 1; i...

Union_Find poj

2019-08-27

0 580

poj2492 750ms 解法二：带权并查集

#include<cstdio> using namespace std; const int Maxn = 2019; int rel[Maxn],father[Maxn]; //0表示同性，1表示异性 //参考网上的第二种解法，也就是带权(种类)并查集 void init(int n...

Union_Find poj

2019-08-27

0 574

poj2492 766ms 带权并查集

#include<cstdio> #include<cstring> using namespace std; //带权并查集其一解法 //敌人的敌人就是朋友 const int Maxn = 2000; int father[Maxn<<1]; void ini...

Union_Find poj

2019-08-26

0 451

pooj2524 313ms 并查集

规整一点，将各个步骤写成函数，所以函数调用浪费了时间 #include using namespace std; //union_find //水题，先把每人看成一个社团，然后合并一个，减一就好 int father[50005]; int ans; void init(int n) { f...

Union_Find poj

2019-08-25

1 590

poj2244 16ms Joseph

#include<cstdio> using namespace std; //Joseph变形，最后一个是第二个，也就是编号应该为代码中的0 //过几天要开始好好学学了，最近追了部剧，小欢喜，挺好看的 int Joseph(int n,int m) { int t = 0; ...

Joseph poj MATH

2019-08-24

0 640

poj1012 235ms Joseph

#include<cstdio> using namespace std; //Joseph问题 //大概思路可以理解了，要整理一下 int main() { int k; int ans[15] = {0}; ans[1] = 2; while(scan...

Joseph poj MATH

2019-08-23

0 574

poj1083 0ms

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; //因为是同时搬运，记录每段走廊使用的次数，找出最大的*10就好 int main() { int t,...

poj GREEDY

2019-08-22

0 539

poj1118 469ms 0(n^3)飘过

#include<cstdio> using namespace std; struct point { int x; int y; } points[705]; int main() { int n; while(scanf("%d",&n),n...

poj WATER

2019-08-21

0 461