總述:
這次的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 閱讀(279)
評論(1) 編輯 收藏 引用 所屬分類:
算法題解