做国外网站用国内服务器,荆州网站建设,网站建设的关键点,中国最好的网站制作目录
POJ1988 思路#xff1a;
POJ1182 思路#xff1a; POJ1988
有n个栈每个栈中有一个方块#xff0c;现要执行n次操作。一种是移数#xff0c;一种是计数 移数M#xff1a;把包含x的栈整体移动到y栈顶 计数C#xff1a;统计X方块下面的方块数
输入#xff1a; 6 …目录
POJ1988 思路
POJ1182 思路 POJ1988
有n个栈每个栈中有一个方块现要执行n次操作。一种是移数一种是计数 移数M把包含x的栈整体移动到y栈顶 计数C统计X方块下面的方块数
输入 6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4 思路
我们不需要模拟我们只需要等价即可每次操作无非是把一个链表接到了另一个链表上这完全可以用并查集实现。 设置fa数组表示集合号cnt表示x号栈中的数量d为x下方的数量 移数就等价与并查集的合并建树的过程。我们设置祖宗是栈底的方块然后一边维护facntd数组即可。 值得注意的是这三个数组我们都只需要在祖宗那里标记一下就行然后查找的时候再去更新类似分块和线段树中懒标思想。 然后查找祖宗的时候也就是回溯时候既要更新fa(根据祖宗更新)也要更新每个点的d值(根据亲爹更新)不用更新cnt都一样更新啥呀 #include bits/stdc.h
using namespace std;
const int N30005;
int n,fa[N],d[N],cnt[N];//d[x]是x下方的数量cnt[x]是x号栈中的数量void init(){for(int i1;iN;i){fa[i]i; d[i]0; cnt[i]1;}
}
//很多时候每个点都要设置d值的来代表深度
int find(int x)
//我们设置祖先是栈底方块在查找的时候更新fa和dfa[x]find(fa[x]) d[x]d[x的亲爹]
{int fxfa[x];//保存亲爹if(x!fa[x]) {//x自己不是祖宗就要让fa[x]更新成祖宗的集合号fa[x]find(fa[x]);d[x]d[fx];//必须让亲爹先是正确的所以放在dfs之后}return fa[x];//返回祖先
}void unity(int x, int y)//我们要让祖宗能代表整个栈所以就为祖宗设置cnt
{int f1find(x);int f2find(y);fa[f1]f2;//走到栈底了进行合并x栈放在y栈上面d[f1]cnt[f2]; //更新x栈祖宗f1的d因为只需要把根更新正确即可cnt[f2]cnt[f1];//更新y的祖宗f2的cnt
}int main(){char ch;int i,j;cinn;init();while(n--){getchar();//cin,scanf的除了字符型都不怕空格和回车死不掉但是只管过滤前面的后面不管scanf(%c,ch);if(chC){scanf(%d,i);int fifind(i);//必须先查一边fi没用的printf(%d\n,d[i]);}else{scanf(%d%d,i,j);unity(i,j);}}
}POJ1182
有三类动物ABCA吃BB吃CC吃A。现有n只动物(1~n编号)每个动物都是ABC的一种但是我们并不知道它具体是哪一种。 有两种说法对这n个动物构成的食物链关系进行描述 第一种说法1 x y 表示x和y是同类 第二种说法2 x y 表示x吃y 每句话满足以下三条之一就是假话否则是真话。 1当前话与前面的某些话冲突此句话是假话 2当前话x或y比n大就是假话 3当前话x吃x就是假话 请输出假话的数量
输入 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 思路
第2个最好判断。主要是第13个话。 并查集的优势是能快速帮你找到关系的祖宗fa和关系的层数d(深度)。而这道题就是利用关系层级解题的。 我们发现直接节点如果构成一条链的话一定会3种动物进行循环。那么也就是说会形成大量的环。所以如果两种动物本来就在同一个集合的话就不需要合并了。 首先判断吃
如果x和y在同一个集合中且x吃y的话
(d[x]-d[y]3)%31即可说明是正确的因为可能有负值所以要多加3。参考循环队列嘛
如果不在同一个集合中
那就fa[x]y;(d[y]-d[x]3)%31也说明正确。 然后判断同类
如果x和y在同一个集合中的话
(d[x]-d[y]3)%30即可说明是正确的因为可能有负值所以要多加3。
如果不在同一个集合中
那就fa[x]y;(d[y]-d[x]3)%30也说明正确。 分析样例
首先2 1 22 2 3 那么构成的并查集为
fa[1]2 , d[1]1 查询后变成- fa[1]2 , d[1]2
fa[2]3 , d[2]1 fa[2]3 , d[2]1
fa[3]3 , d[3]0 fa[3]3 , d[3]0
然后2 3 3 直接错误。
然后1 1 3 明显不是同类 (d[x]-d[y]3)%32 错误
然后2 3 1 (d[x]-d[y]3)%31 正确
然后1 5 5 (d[x]-d[y]3)%30 正确 然后我们再优化一下: 如果是在不同集合的话无论是查还是吃都需要合并建边不用判断。 但是如果在同一个集合中无论是吃和是查只需要判断就行。还合并什么呀 那么在同一个集合中判断公式为(d[x]-d[y]3)%3 c - 1
明显x和y是吃时c为2时应该和1比较c为1时应该和0比较。
在不同集合中合并公式为fa[a]b , d[a](d[y]-d[x]3c - 1)%3 #include bits/stdc.h
using namespace std;
const int N50010;
int n,fa[N],d[N];void init(){for(int i1;in;i){fa[i]i;d[i]0;}
}int find(int x){int fxfa[x];if(x!fa[x]){fa[x]find(fa[x]);d[x](d[x]d[fx])%3;}return fa[x];
}int main(){int k,c,x,y,tot0,a,b;scanf(%d%d,n,k);//n个动物k个描述init();while(k--){scanf(%d%d%d,c,x,y);if(xn||yn||(c2xy)) tot;else {afind(x),bfind(y);if(ab){if((d[x]-d[y]3)%3!c-1) tot;}else{fa[a]b;d[a](d[y]-d[x]3c-1)%3;}}}couttot\n;
}
