problem1

遍历未被删除的叶子结点即可。

problem2

首先，将所有的蛋白质原子编号，设为$[0,m-1]$，每个原子可能对应多个长度为3的$ACGT$。设$n$为DNA串的长度。用$g[i][j]$表示从$i$开始匹配数字$j$后的最小位置,$0\leq i \leq n-1,0\leq j \leq m-1$。

然后就是动态规划.设$dp[i][j]$表示位置$i$之前最后匹配的数字为$j$的方案数。对所有的$0\leq t < m$有$dp[g[i][t]][t]+=dp[i][j] $

problem3

首先将所有节点分成若干个$group$，每个$group$里的节点可以互相到达。然后一个一个$group$进行处理。

对于某个$group$，建一个新的二分图$G$。对于其中的一个点$x$，若存在不在该$group$中的一点$y$使得存在边$y$到$x$那么在新图$G$中连一条$x$到$y$的边。那么该$group$中需要作为新的$division$的根结点的个数为$|group|-maxMatch(G)$。

 

code for problem1

import java.util.*;import java.math.*;import static java.lang.Math.*;public class CellRemoval {	List
     
      
       > lists=null;	public int cellsLeft(int[] parent, int deletedCell) {		final int n=parent.length;		lists=new ArrayList<>();		for(int i=0;i
       
        ());		}		int root=-1;		for(int i=0;i
       
      
     

　　

code for problem2

import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;/** * Created by mcl on 2017/9/27. */public class DNADeletion {	final static int MOD=1000000007;	public int differentProteins(String[] DNASequence, String[] codonTable) {		StringBuilder sb=new StringBuilder();		for(int i=0;i
     
      =0;--i) {			for(int j=0;j<4;++j) {				nxt[i][j]=nxt[i+1][j];			}			nxt[i][getIndex(S.charAt(i))]=i;		}		List
      
       
        > lists=init(codonTable);		final int m=lists.size();		int[][] g=new int[n][m];		for(int i=0;i
        
         cur)) {						g[i][j]=cur;					}				}			}		}		int[][] dp=new int[n+1][m];		for(int i=0;i
         
          > init(String[] codonTable) {		Map
          
            map=new HashMap<>(); int id=0; List
           
            
             > lists=new ArrayList<>(); for(int i=0;i
             
              ()); } lists.get(map.get(value)).add(key); } return lists; } int getIndex(char c) { if(c=='A') { return 0; } else if(c=='C') { return 1; } else if(c=='T') { return 2; } return 3; }}
             
            
           
          
         
        
       
      
     

　　

code for problem3

import java.util.*;import java.math.*;import static java.lang.Math.*;public class CompanyRestructuring {		public int fewestDivisions(String[] hasManaged) {		final int n=hasManaged.length;		boolean[][] g=new boolean[n][n];		for(int i=0;i
     
       left=new ArrayList<>();			List
      
        right=new ArrayList<>();			for(int j=0;j