总述:
这次的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;
}
}
题意：给出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%i == 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(0, 0, '\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 阅读(273)
评论(1) 编辑 收藏 引用 所属分类:
算法题解