posts - 33,  comments - 33,  trackbacks - 0
总述:
这次的SRM题目四平八稳,可惜在比赛期间发挥不好,成绩也就一般了。主要失误是看错题目。。。

250 Point BadVocabulary
题意:在String[] vocabulary中查找符合条件的字符串的数目,条件如下:
1. 前缀含有badPrefix
2.或后缀含有badSuffix
3.或子串含有badSubstring,并且子串不是该字符串的前缀和后缀

题解:题意已经很清楚了,直接按照要求做即可。直接放代码:
class BadVocabulary
{
    
public boolean IsPrefix(String _pre,String _src)
    
{
        
if(_src.length() >= _pre.length())
        
{
            
if(_src.substring(0, _pre.length()).compareTo(_pre) == 0)
                
return true;
            
else
                
return false;
        }

        
return false;
    }


    
public boolean IsSuffix(String _suf,String _src)
    
{
        
if(_src.length() >= _suf.length())
        
{
            
int len = _src.length();
            
if(_src.substring(len - _suf.length(), len).compareTo(_suf) == 0)
                
return true;
            
else
                
return false;
        }

        
return false;
    }


    
public boolean IsSub(String _sub,String _src)
    
{
        
for(int k = 1; k < _src.length()-_sub.length(); ++k)
        
{
            String su 
= _src.substring(k, k+_sub.length());
            
if(su.compareTo(_sub) == 0)
            
{
                
return true;
            }

        }

        
return false;
    }


    
public int count(String badPrefix, String badSuffix, String badSubstring, String[] vocabulary)
    
{
        
int cnt =0;
        
for(int i = 0;i < vocabulary.length; ++i)
        
{
            
int len = vocabulary[i].length();
            
if(IsPrefix(badPrefix,vocabulary[i]))
                
++cnt;
            
else if(IsSuffix(badSuffix,vocabulary[i]))
                
++cnt;
            
else
            
{

                
if(IsSub(badSubstring,vocabulary[i]))
                    
++cnt;

            }

        }

        
return cnt;
    }

}

500 Points BuyingFlowers
题意:给出int[] roses, int[] lilies,分别代表rose和lilie花束的花的支数,要求选择任意roses和lilies的组合,注意两者必须同时选取,如选了roses[1],lilies[1]也要
选,然后将这些花布成R*C的矩阵,要求任意相邻的两块都要有不同的花,最后求在这些可行解中,abs(R-C)的最小值。
题解:按要求暴力,可以按位暴力或者DFS枚举组合暴力。
那么怎么符合矩阵的要求呢?
观察例子,不难发现当abs(sumOfRoses-sumOfLilies)小于等于1时,必可符合题目要求。
代码:
class BuyingFlowers
{
    
private int GetRCD(int _sum)
    
{
        
int ret = 1<<30;
        
for(int i = 1; i * i <= _sum; ++i)
        
{
            
if(_sum%== 0)
                ret 
= Math.min(ret, Math.abs((_sum/i) - i));
        }

        
return ret;
    }


    
public int buy(int[] roses, int[] lilies)
    
{
        
int len = roses.length;
        
int limit = 1 << len;
        
int sumR = 0;
        
int sumL = 0;
        
int minC = 1 << 30;
        
for(int i = 1; i < limit; ++i)
        
{
            sumR 
= 0;
            sumL 
= 0;
            
for(int j = 0; j < len; ++j)
            
{
                
int k = i&(1<<j);
                
if(k == 1)
                
{
                    sumR 
+= roses[j];
                    sumL 
+= lilies[j];
                }

            }

            
if(Math.abs(sumR-sumL) <= 1)
            
{
                minC 
= Math.min(minC, GetRCD(sumR+sumL));
            }

        }

        
if(minC == 1 << 30)
            
return -1;
        
else
            
return minC;
    }

}

1000 Points - SolitaireChess
题意:8*8棋盘,有两种棋子,N(马)和P(兵),马行日,兵只能向前走,但兵到对面最顶后能升马。
给出初始棋盘状态和最终棋盘状态,计算最小的移动步数。
题解:典型的状态DP。首先用BFS计算初始棋子i到结束棋子j的花费cost[i][j]
设状态S,i为S二进制中位数为1的个数,S表示i个初始棋子放到S对应的结束状态的最小花费,那么dp[1<<n-1]即为答案
状态转移方程:
dp[S] = min{dp[pre]+cost[i][j]},pre为可以推出S的状态
代码:
import java.math.*;
import java.util.*;
import java.util.Queue;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;  


class SolitaireChess
{
    
private int dsx[] = {2,1,-1,-2,-2,-1,1,2};
    
private int dsy[] = {1,2,2,1,-1,-2,-2,-1};
    
private class State
    
{
        
public int x;
        
public int y;
        
public char s;

        
public State(int _x,int _y,char _s)
        
{
            x 
= _x;
            y 
= _y;
            s 
= _s;
        }


        
public void ReValue(State _state)
        
{
            x 
= _state.x;
            y 
= _state.y;
            s 
= _state.s;
        }


        
public boolean isEqual(State _state)
        
{
            
return (x == _state.x&&
                    y 
== _state.y&&
                    s 
== _state.s);
        }

    }


    
private List<State> listInit;
    
private List<State> listTarget;
    
private int [][]cost;

    
private List<State> getState(String[] board)
    
{
        List
<State> reList = new ArrayList<State>();
        
for(int i = 0; i < board.length; ++i)
        
{
            
for(int j = 0; j < board[i].length(); ++j)
            
{
                
if(board[i].charAt(j) != '.')
                
{
                    reList.add(
new State(i,j,board[i].charAt(j)));
                }

            }

        }

        
return reList;
    }


    
private int minCost(State _s1,State _s2)
    
{
        
if(_s1.s == 'P' && _s2.s == 'P')
        
{
            
if(_s1.y != _s2.y)
                
return Integer.MAX_VALUE;
            
if(_s1.x < _s2.x)
                
return Integer.MAX_VALUE;
            
else
                
return _s1.x - _s2.x;
        }

        
if(_s1.s == 'P' && _s2.s == 'N')
        
{
            
return BFS(new State(0,_s1.y,'P'),_s2) + _s1.x;
        }

        
if(_s1.s == 'N' && _s2.s == 'P')
            
return Integer.MAX_VALUE;
        
if(_s1.s == 'N' && _s2.s == 'N')
            
return BFS(_s1,_s2);
        
return Integer.MAX_VALUE;
    }


    
private int BFS(State _s1, State _s2)
    
{
        Queue
<State> que = new LinkedList<State>();
        
int[][] dist = new int[10][10];
        
for(int i = 0; i < 8++i)
            
for(int j = 0; j < 8++j)
            
{
                dist[i][j] 
= Integer.MAX_VALUE;
            }

        dist[_s1.x][_s1.y] 
= 0;
        que.add(_s1);
        State nextState 
= new State(00'\0');
        
while (!que.isEmpty()) 
        
{
            State curState 
= que.poll();
            
if ((curState.x == _s2.x) && (curState.y == _s2.y ))
                
break;

            
for (int i = 0; i < 8++i) 
            
{
                nextState.x 
= curState.x + dsx[i];
                nextState.y 
= curState.y + dsy[i];
                
if (nextState.x >= 0 && nextState.x < 8 && nextState.y >= 0
                        
&& nextState.y < 8
                
{
                    
if (dist[nextState.x][nextState.y] > dist[curState.x][curState.y] + 1
                    
{
                        
                        dist[nextState.x][nextState.y] 
= dist[curState.x][curState.y] + 1;
                        que.add(
new State(nextState.x,nextState.y,'N'));
                    }

                }

            }

        }

        
return dist[_s2.x][_s2.y];
    }


    
private int StateDP(int _size)
    
{
        
int limit = 1 << _size;
        
int dp[] = new int[limit];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[
0= 0;
        
for(int state = 0; state < limit; ++state)
        
{
            
if(dp[state] != Integer.MAX_VALUE)
            
{
                
int i = Integer.bitCount(state);
                
for(int j = 0; j < _size; ++j)
                
{
                    
if(((state >> j)&1== 0)
                    
{
                        
if(cost[i][j] != Integer.MAX_VALUE)
                        
{
                            
int newState = (state | (1 << j));
                            dp[newState] 
= Math.min(dp[newState], dp[state] + cost[i][j]);
                        }

                    }

                }

            }

        }

        
if(dp[limit-1== Integer.MAX_VALUE)
            
return -1;
        
else
            
return dp[limit-1];
    }

    
public int transform(String[] board1, String[] board2)
    
{
        listInit 
= getState(board1);
        listTarget 
= getState(board2);
        
if(listInit.size() != listTarget.size())
            
return -1;
        
int size = listInit.size();
        cost 
= new int[size][size];
        
for(int i = 0; i < size; ++i)
        
{
            
for(int j = 0; j < size; ++j)
            
{
                cost[i][j] 
= minCost(listInit.get(i),listTarget.get(j));
            }

        }

        
return StateDP(size);
    }

}
posted on 2010-12-01 23:56 bennycen 阅读(257) 评论(1)  编辑 收藏 引用 所属分类: 算法题解

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理