建设银行网站登录首页,企业网盘收费标准,seo下拉优化,静态网页模板生成工具4.1-4.5算法刷题笔记 1. 区间和2. 区间合并3. 用队列实现栈#xff08;queueMain queueTemp;#xff09;4. 最小栈 1. 单链表模板5. 单链表 2. 双链表模板6. 双链表 3. 模拟栈7. 模拟栈(一个数组即可)8. 表达式求值 4. 队列 tt -1,hh 0;9. 模拟队列 5. 单调栈10. 单调栈 6… 4.1-4.5算法刷题笔记 1. 区间和2. 区间合并3. 用队列实现栈queueMain queueTemp;4. 最小栈 1. 单链表模板5. 单链表 2. 双链表模板6. 双链表 3. 模拟栈7. 模拟栈(一个数组即可)8. 表达式求值 4. 队列 tt -1,hh 0;9. 模拟队列 5. 单调栈10. 单调栈 6. 单调队列11. 滑动窗口最大值 7. KMP12. KMP字符串 8. Trie树13. Trie字符串统计14. 最大异或对 9. 并查集 find merge15. 合并集合16. 连通块中点的数量每个集合有多少个元素17. 食物链 1. 区间和
原题链接 import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();pair[] add new pair[n2];pair[] query new pair[m];ListInteger arrayMap new ArrayList(nm*2);int[] sum new int[nm*2];for (int i 0; i n; i) {add[i] new pair();add[i].l scanner.nextInt();add[i].r scanner.nextInt();arrayMap.add(add[i].l);}for (int i 0; i m; i) {query[i] new pair();query[i].l scanner.nextInt();query[i].r scanner.nextInt();arrayMap.add(query[i].l);arrayMap.add(query[i].r);}arrayMap new ArrayList(new HashSet(arrayMap));Collections.sort(arrayMap);for (int i 0; i n; i) {sum[arrayMapIndexOf(add[i].l,arrayMap)] add[i].r;}for (int i 0; i arrayMap.size(); i) {if(i ! 0) {sum[i] sum[i-1];}}for (int i 0; i query.length; i) {int l arrayMapIndexOf(query[i].l,arrayMap);int r arrayMapIndexOf(query[i].r,arrayMap);if (l 0) {System.out.print(sum[r] \n);} else {System.out.print(sum[r]-sum[l-1] \n);}}}static class pair {int l;int r;}private static int arrayMapIndexOf(int k,ListInteger arrayMap) {int l 0,r arrayMap.size()-1;while (l r) {int mid (lr1) 1;if (arrayMap.get(mid) k) {l mid;} else {r mid - 1;}}return r;}
}2. 区间合并
原题链接
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();pair[] range new pair[n];for (int i 0; i n; i) {range[i] new pair();range[i].l scanner.nextInt();range[i].r scanner.nextInt();}Arrays.sort(range,new Comparatorpair(){Overridepublic int compare(pair o1,pair o2) {if (o1.l o2.l) {return o1.r - o2.r;} else {return o1.l - o2.l;}}});int st (int)-2e9-1;int ed (int)-2e9-1;int cnt 0;for (int i 0; i n; i) {if (ed range[i].l) {st range[i].l;ed range[i].r;cnt;} else {ed Math.max(ed,range[i].r);}}System.out.print(cnt);}static class pair {int l;int r;}}3. 用队列实现栈queueMain queueTemp;
原题链接
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;class MyStack {public QueueInteger queueMain;public QueueInteger queueTemp;public MyStack() {queueMain new LinkedList();queueTemp new LinkedList();}public void push(int x) {queueMain.add(x);}public int pop() {int x 0;while (!queueMain.isEmpty()) {x queueMain.poll();if (!queueMain.isEmpty()) {queueTemp.add(x);}}queueMain queueTemp;queueTemp new LinkedList();return x;}public int top() {int x 0;while (!queueMain.isEmpty()) {x queueMain.poll();queueTemp.add(x);}queueMain queueTemp;queueTemp new LinkedList();return x;}public boolean empty() {return queueMain.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj new MyStack();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.top();* boolean param_4 obj.empty();*/4. 最小栈
原题链接
class MinStack {StackInteger A, B;public MinStack() {A new Stack();B new Stack();}public void push(int x) {A.add(x);if(B.empty() || B.peek() x)B.add(x);}public void pop() {if(A.pop().equals(B.peek()))B.pop();}public int top() {return A.peek();}public int getMin() {return B.peek();}
}1. 单链表模板
5. 单链表
acwing链接 力扣
class MyLinkedList {int size;ListNode head;public MyLinkedList() {size 0;head new ListNode(0);}public int get(int index) {if (index 0 || index size) {return -1;}ListNode cur head;for (int i 0; i index; i) {cur cur.next;}return cur.val;}public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(size, val);}public void addAtIndex(int index, int val) {if (index size) {return;}index Math.max(0, index);size;ListNode pred head;for (int i 0; i index; i) {pred pred.next;}ListNode toAdd new ListNode(val);toAdd.next pred.next;pred.next toAdd;}public void deleteAtIndex(int index) {if (index 0 || index size) {return;}size--;ListNode pred head;for (int i 0; i index; i) {pred pred.next;}pred.next pred.next.next;}
}class ListNode {int val;ListNode next;public ListNode(int val) {this.val val;}
}
import java.util.*;public class Main {static int[] e new int[100010];static int[] ne new int[100010];static int idx,head;public static void init() {idx 0;head -1;}public static void add_head(int x) {e[idx] x;ne[idx] head;head idx;} public static void add(int k,int x) {e[idx] x;ne[idx] ne[k];ne[k] idx;}public static void remove(int k) {ne[k] ne[ne[k]];}public static void main(String[] args) {Scanner scan new Scanner(System.in);int m scan.nextInt();init();while(m -- 0){String s scan.next();char op s.charAt(0);if(op H){int x scan.nextInt();add_head(x);}else if(op D){int k scan.nextInt();if(k 0) head ne[head];else remove(k-1);}else {int k scan.nextInt();int x scan.nextInt();add(k-1,x);}}for(int i head;i ! -1;i ne[i] ){System.out.print(e[i] );}}
}2. 双链表模板
void init()
{r[0] 1;l[1] 0;idx 2;
}6. 双链表
原题链接
import java.util.Scanner;
public class Main{static int N 100010;static int[] e new int[N];static int[] r new int[N];static int[] l new int[N];static int idx;//删除第k位插入的数public static void remove(int k){r[l[k]] r[k];l[r[k]] l[k];}//这是在第k位数后面插入一个数xpublic static void add_all(int k,int x){e[idx] x;r[idx] r[k];l[idx] k;l[r[k]] idx;r[k] idx;}public static void main(String[] args){Scanner scan new Scanner(System.in);int m scan.nextInt();r[0] 1;l[1] 0;idx 2;while(m -- 0){String s scan.next();char op s.charAt(0);if(op L){int x scan.nextInt();add_all(0,x);}else if(op R){int x scan.nextInt();add_all(l[1],x);}else if(op D){int k scan.nextInt();remove(k 1);}else if(s.equals(IR)){int k scan.nextInt();int x scan.nextInt();add_all(k 1,x);}else {int k scan.nextInt();int x scan.nextInt();add_all(l[k1],x);}}for(int i r[0];i ! 1; i r[i]){System.out.print(e[i] );}}
}3. 模拟栈
7. 模拟栈(一个数组即可)
原题链接
import java.util.Scanner;
public class Main{public static void main(String[] args){Scanner scan new Scanner(System.in);int m scan.nextInt();int[] stl new int[100010];int tt 0;while(m -- 0){String s scan.next();if(s.equals(push)){int x scan.nextInt();stl[tt] x;}else if(s.equals(pop)){tt--;}else if(s.equals(empty)){if(tt 0){System.out.println(NO);}else System.out.println(YES);}else{System.out.println(stl[tt]);}}}
} 8. 表达式求值
原题链接
import java.util.*;
public class Main{public static void main(String[] args){Scanner scan new Scanner(System.in);//以字符串形式输入表达式String s scan.next();//map来添加运算符号进去定义优先级MapCharacter,Integer map new HashMap();map.put(,1);map.put(-,1);map.put(*,2);map.put(/,2);StackCharacter op new Stack();//存运算符号StackInteger num new Stack();//存数字for(int i 0 ; i s.length(); i ){char c s.charAt(i);//判断c字符是不是数字if(Character.isDigit(c)){int x 0,j i;//数字可能会是多位数while(j s.length() Character.isDigit(s.charAt(j))){x x * 10 s.charAt(j) - 0;j;}num.push(x);//将数字x存入数字栈栈顶i j - 1;//重新赋值i}else if(c (){op.push(c); // 将左括号存入字符栈栈顶}else if(c )){//如果栈顶不等于左括号一直计算下去while(op.peek() ! (){eval(op,num);}op.pop(); // 将左括号弹出栈顶}else { //如果是正常字符while(!op.empty() op.peek() ! ( map.get(op.peek()) map.get(c)){eval(op,num);}op.push(c);}}while(!op.empty()) eval(op,num);System.out.println(num.peek());}public static void eval(StackCharacter op,StackInteger num){int b num.pop();int a num.pop();char c op.pop();if(c ){num.push(ab);}else if(c -){num.push(a-b);}else if(c *){num.push(a*b);}else {num.push(a/b);}}
}4. 队列 tt -1,hh 0;
9. 模拟队列
原题链接
import java.util.Scanner;
public class Main{public static void main(String[] args){Scanner scan new Scanner(System.in);int m scan.nextInt();//队列是在tt队尾插入元素队头hh弹出元素int[] dl new int[100010];int hh 0;int tt -1;while(m -- 0){String s scan.next();if(s.equals(push)){int x scan.nextInt();dl[tt] x;}else if(s.equals(pop)){hh;}else if(s.equals(empty)){if(hh tt) System.out.println(NO);else System.out.println(YES);}else {System.out.println(dl[hh]);}}}
}5. 单调栈
常见模型找出每个数左边离它最近的比它大/小的数
int tt 0;
for (int i 1; i n; i )
{while (tt check(stk[tt], i)) tt -- ;stk[ tt] i;
}10. 单调栈
力扣链接 原题链接
原题链接
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int[] nums new int[n2];int[] st new int[n2];int tt 0;for (int i 0; i n; i) nums[i] scanner.nextInt();for (int i 0; i n; i) {while (tt ! 0 st[tt-1] nums[i]) {tt--;}if (tt 0) {System.out.print(-1 );} else {System.out.print(st[tt-1] );}st[tt] nums[i];}}
}6. 单调队列
11. 滑动窗口最大值
力扣链接 原题链接 原题链接
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] q new int[nums.length];int hh 0, tt -1;int[] ans new int[nums.length-k1];for (int i 0; i nums.length; i) {int x nums[i];if (hh tt q[hh] k i) {hh;}while (hh tt x nums[q[tt]]) {tt--;}q[tt] i;if (i1 k) {ans[i-k1] nums[q[hh]];}}return ans;}
}7. KMP
12. KMP字符串
力扣链接 acwing链接
class Solution {public int strStr(String haystack, String needle) {int[] ne new int[haystack.length()2];ne[0] -1;for (int i 1,j -1; i needle.length(); i) {while (j ! -1 needle.charAt(j1) ! needle.charAt(i)) {j ne[j];}if (needle.charAt(j1) needle.charAt(i)) {j;}ne[i] j;}int ans 0;for (int i 0,j -1; i haystack.length(); i) {while (j ! -1 haystack.charAt(i) ! needle.charAt(j1)) {j ne[j];}if (haystack.charAt(i) needle.charAt(j1)) {j;}if (j needle.length()-1) {return i-needle.length()1;}}return -1;}
}8. Trie树
13. Trie字符串统计
力扣链接 acwing链接
class Trie {public int N,idx;public int[][] song;public int[] cnt;public char[] str;public Trie() {N 100010;idx 0;song new int[N][26];cnt new int[N];str new char[N];}public void insert(String word) {char[] str word.toCharArray();int p 0; //下标0表示头结点根节点for(int i 0 ; i str.length; i ){// 将字符串每个字符都转化成数字0-25int u str[i] - a; //如果这个的儿子分支没有字符说明这条分支还没有这个字符插入过//就新建一个然后赋值为然后把【idx】下标赋值上去作为每个分支的专属坐标if(song[p][u] 0) song[p][u] idx;//然后将p往下前进一层p song[p][u];}//最后停在那一层的那个数字就做标记说明这是一个字符串的结束。cnt[p];}public boolean search(String word) {char[] str word.toCharArray();int p 0;//从根节点开始下标是0表示根节点头结点for(int i 0 ; i str.length; i ){int u str[i] - a; // 将字符串每个字符都转化成数字0-25//如果这个点上面没有标记就说明没有存入过这个字符所以返回0if(song[p][u] 0) return false;//如果这个点上面能寻找到这个字符就让他往下一层继续寻找p song[p][u];}//最后查找完之后输出最后一个做标记的点为下标的cnt数组的值。return cnt[p] ! 0;}public boolean startsWith(String prefix) {char[] str prefix.toCharArray();int p 0;//从根节点开始下标是0表示根节点头结点for(int i 0 ; i str.length; i ){int u str[i] - a; // 将字符串每个字符都转化成数字0-25//如果这个点上面没有标记就说明没有存入过这个字符所以返回0if(song[p][u] 0) return false;//如果这个点上面能寻找到这个字符就让他往下一层继续寻找if (i str.length-1) {return song[p][u] ! 0;}p song[p][u];}//最后查找完之后输出最后一个做标记的点为下标的cnt数组的值。return false;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj new Trie();* obj.insert(word);* boolean param_2 obj.search(word);* boolean param_3 obj.startsWith(prefix);*/import java.util.Scanner;
public class Main{static int N 100010,idx 0;static int[][] song new int[N][26];static int[] cnt new int[N];static char[] str new char[N];public static void insert(char[] str){int p 0; //下标0表示头结点根节点for(int i 0 ; i str.length; i ){// 将字符串每个字符都转化成数字0-25int u str[i] - a; //如果这个的儿子分支没有字符说明这条分支还没有这个字符插入过//就新建一个然后赋值为然后把【idx】下标赋值上去作为每个分支的专属坐标if(song[p][u] 0) song[p][u] idx;//然后将p往下前进一层p song[p][u];}//最后停在那一层的那个数字就做标记说明这是一个字符串的结束。cnt[p];}public static int query(char[] str){int p 0;//从根节点开始下标是0表示根节点头结点for(int i 0 ; i str.length; i ){int u str[i] - a; // 将字符串每个字符都转化成数字0-25//如果这个点上面没有标记就说明没有存入过这个字符所以返回0if(song[p][u] 0) return 0;//如果这个点上面能寻找到这个字符就让他往下一层继续寻找p song[p][u];}//最后查找完之后输出最后一个做标记的点为下标的cnt数组的值。return cnt[p];}public static void main(String[] args){Scanner scan new Scanner(System.in);int n scan.nextInt();String sss scan.nextLine();while(n -- 0){String s scan.nextLine();String[] st s.split( );String s1 st[0];String s2 st[1];if(s1.equals(I)){insert(s2.toCharArray());}else{System.out.println(query(s2.toCharArray()));}}}
}14. 最大异或对
力扣链接 acwing链接
class Solution {public static int N,idx;public static int[][] song;public static void add(int x){int p 0;//从头结点开始for(int i 30 ; i 0 ; i -- ){ //因为每一个数的二进制是有31位组成所以需要从大开始遍历int u x i 1;//每一个数的二进制31个二进制每一位看0还是1if(song[p][u] 0) song[p][u] idx;//判断这一层是空的就创建然后赋值下标p song[p][u];//然后让往下前进一层}}//查询public static int query(int x){int p 0,res 0;//从根节点0开始。res进就算异或后的最大值for(int i 30; i 0 ; i --){int u x i 1;if(song[p][1-u] ! 0){ //如果该节点的u是0则判断一下在这一层有没有跟他相反的0-11-0如果相反对应位置有数res (1 i);//res就将该二进制位对应异或之后的最优解1每一位顺次加起来。因为是异或相反数就是1这是最优解p song[p][1-u];//然后往最优解那边前进一层。}else{//否则就不是最优解的0匹配1,1匹配0所以就异或之后的值是0//res (0 i);因为是0所以可以省略,p song[p][u];//然后让他往不优解那边前进一层。}}return res;//最后返回异或之后的最大值res}public int findMaximumXOR(int[] nums) {N 3100010;idx 0;song new int[N][2];int n nums.length;for(int i 0 ; i n ; i ){add(nums[i]);}int res 0;for(int i 0 ; i n ; i ){//因为输入的是字符串所以需要转成整形。然后每一次比较res的值谁大然后将最大值重新赋值给resres Math.max(res,query(nums[i]));}return res;}
}import java.io.*;
public class Main{static int N 3100010,idx 0;static int[][] song new int[N][2];//插入public static void add(int x){int p 0;//从头结点开始for(int i 30 ; i 0 ; i -- ){ //因为每一个数的二进制是有31位组成所以需要从大开始遍历int u x i 1;//每一个数的二进制31个二进制每一位看0还是1if(song[p][u] 0) song[p][u] idx;//判断这一层是空的就创建然后赋值下标p song[p][u];//然后让往下前进一层}}//查询public static int query(int x){int p 0,res 0;//从根节点0开始。res进就算异或后的最大值for(int i 30; i 0 ; i --){int u x i 1;if(song[p][1-u] ! 0){ //如果该节点的u是0则判断一下在这一层有没有跟他相反的0-11-0如果相反对应位置有数res (1 i);//res就将该二进制位对应异或之后的最优解1每一位顺次加起来。因为是异或相反数就是1这是最优解p song[p][1-u];//然后往最优解那边前进一层。}else{//否则就不是最优解的0匹配1,1匹配0所以就异或之后的值是0//res (0 i);因为是0所以可以省略,p song[p][u];//然后让他往不优解那边前进一层。}}return res;//最后返回异或之后的最大值res}public static void main(String[] args)throws IOException{BufferedReader re new BufferedReader(new InputStreamReader(System.in));BufferedWriter wt new BufferedWriter(new OutputStreamWriter(System.out));int n Integer.parseInt(re.readLine());String[] s re.readLine().split( );for(int i 0 ; i n ; i ){add(Integer.parseInt(s[i]));}int res 0;for(int i 0 ; i n ; i ){//因为输入的是字符串所以需要转成整形。然后每一次比较res的值谁大然后将最大值重新赋值给resres Math.max(res,query(Integer.parseInt(s[i])));}wt.write(res );//最后输出res因为快输出输出的是字符串所以需要在后面加上“ ”wt.close();}
}9. 并查集 find merge
15. 合并集合 原题链接 原题链接 import java.util.Scanner;
public class Main{static int N 100010;static int[] p new int[N];public static void main(String[] args){Scanner scan new Scanner(System.in);int n scan.nextInt(); // 全部有n个数int m scan.nextInt(); // 读入m个操作//将n个数每个数各自都在一个集合里面。都指向自己说明现在有多少个集合for(int i 1 ; i n ; i ) p[i] i; while(m -- 0){String s scan.next();int a scan.nextInt();int b scan.nextInt();//合并集合if(s.equals(M)) p[find(a)] find(b); //将a集合的根节点即祖先指向b集合的祖先 else{ //是否同个集合if(find(a) find(b))System.out.println(Yes); //如果两个集合的祖先相同说明两个集合在同个集合中。else System.out.println(No); //否则相反}}}//并查集的核心操作寻找根节点祖先 路径压缩public static int find(int x){// 如果这个集合的父节点指向的不是自己说明不是根节点递归寻找//最后找到根节点之后把路径上的所有集合都指向根节点、if(p[x] ! x) p[x] find(p[x]); return p[x]; // 最后返回根节点}
}16. 连通块中点的数量每个集合有多少个元素 原题链接
import java.util.Scanner;
public class Main{static int N 100010;static int[] p new int[N];static int[] size new int[N];//size用来存每个集合中数的个数public static void main(String[] args){Scanner scan new Scanner(System.in);int n scan.nextInt();int m scan.nextInt();for(int i 1 ; i n ;i ){p[i] i;size[i] 1;// 一开始每个数是一个集合各自都是个数为1}while(m -- 0){String s scan.next();if(s.equals(C)){int a scan.nextInt();int b scan.nextInt();if(find(a) find(b)) continue; // 这里需要特判一下如果两个数是同个集合中的数就结束else{ size[find(b)] size[find(a)]; // 只有两个数的根节点也就是祖先的size值才是有用的//两个集合中的赋值给另一个祖先的即赋值给另一个祖先的这个祖先就是合并之后的两个集合的祖先// b的size[] a的size[] 因为b是合并之后的新祖先所以要让b加上被合并的ap[find(a)] find(b); //合并操作p[a]的祖先指向b说明b是合并之后的祖先}}else if(s.equals(Q1)){int a scan.nextInt();int b scan.nextInt();if(find(a) find(b))System.out.println(Yes);else System.out.println(No);}else{int a scan.nextInt();//只有根节点的size才是有用的,则通过find(a)找到他的根节点然后输出根节点的size;System.out.println(size[find(a)]);}}}public static int find(int x){if(p[x] ! x) p[x] find(p[x]);return p[x];}
}17. 食物链
原题链接
法一 xxnxnn merge(f[xn],f[x]) 思路
因为有三种物种A吃BB吃CC吃A如果我们用一个数组存储那么比如1吃2那么我们让2的角标处的值标记成1如果3吃2那怎么标记一个数组指定标记不过来。那么我们想用三个数组存储其实也存储不过来因为角标就那么几个最好的方法就是用xxnxnn来表示 比如1吃2那么就可能有三种情况 A类中的1吃B类的2 : fa[1] fa[2nn] B类中的1吃C类的2 : fa[1n] fa[2] C类中的1中A类的2 : fa[1nn] fa[2n]; 这样的话就会有3*n个角标就可以充分表达 A中的1吃B中的2B中的2用2n表示 这样的话就不会出现数字冲突
A吃B 则让f[A] B
/**/#include bits/stdc.h
using namespace std;
int fa[200000];
int n,m,k,x,y,ans;
int get(int x)
{if(xfa[x]) return x;return fa[x]get(fa[x]);
}
void merge(int x,int y)
{fa[get(x)]get(y);
}
int main()
{cinnm;for(int i1;i3*n;i) fa[i]i;for(int i1;im;i){scanf(%d%d%d,k,x,y);if(xn || yn) ans;else if(k1){if(get(x)get(yn) || get(x)get(ynn)) //如果x,y是同类,但是x是y的捕食中的动物,或者x是y天敌中的动物,那么错误.ans;else{merge(x,y);merge(xn,yn);merge(xnn,ynn);}}else{if(xy || get(x)get(y) || get(x)get(yn)) //x就是y,或者他们是同类,再或者是y的同类中有xans;//都是假话else{merge(x,ynn);//y的捕食域加入xmerge(xn,y);//x的天敌域加入ymerge(xnn,yn);//x的捕食域是y的同类域.}}}coutansendl;
}法二将有关系的都存储在一个部落用到根节点的距离表示关系 二刷总结
X吃Y 让x的祖宗等于y的祖宗 或者 y的祖宗等于x的祖宗都可以find查找函数中具有压缩路径的作用所以在写的时候先找到此根节点然后依次压缩如下代码 find中 d[x] d[p[x]];
int find(int x)
{if (p[x] ! x){int t find(p[x]);d[x] d[p[x]];p[x] t;}return p[x];
}不可以如下代码
int find(int x)
{if (p[x] ! x){d[x] d[p[x]];return p[x] find(p[x]);}return p[x];
}
在查询合并过程中比如查询x的父节点应该用一个变量记录下来不能多次find不然找不到x的原来父节点了初始化 p[i] i; d[i] 0;合并的时候画图即可明白彼此的距离
具体过程如下
#include iostreamusing namespace std;const int N 50010;int n, m;
int p[N], d[N];int find(int x)
{if (p[x] ! x){int t find(p[x]);d[x] d[p[x]];p[x] t;}return p[x];
}int main()
{scanf(%d%d, n, m);for (int i 1; i n; i ) p[i] i;int res 0;while (m -- ){int t, x, y;scanf(%d%d%d, t, x, y);if (x n || y n) res ;else{int px find(x), py find(y);if (t 1){if (px py (d[x] - d[y]) % 3) res ;else if (px ! py){p[px] py;d[px] d[y] - d[x];}}else{if (px py (d[x] - d[y] - 1) % 3) res ;else if (px ! py){p[px] py;d[px] d[y] 1 - d[x];}}}}printf(%d\n, res);return 0;
}
