emu in blogjava

<script>
var m=1000000000;//000;

function choices(decree)
{
    var i,j,n=1;
    var arrSum=new Array(26);//最后一個字母在每個位置的總合
    for(j=0;j<arrSum.length;++j)arrSum[j]=0;
    for(i=1;i<=decree.length;++i)
    {
        var tmpSum=new Array(26);
        for(j=0;j<26;++j)tmpSum[j]=0;

        if('A'==decree.charAt(i-1))
        {
            if(1==i)
            {
                arrSum[0]=1;
            }
            else
            {
                n=0;
                for(j=i-1;j>=0;--j)//向前分散，如123->6530
                {
                    n+=arrSum[j];
                    tmpSum[j]=n;
                }
                n = 0
                for(j=0;j<=i;++j)
                {//保存到arrSum
                    arrSum[j]=tmpSum[j];
                    n+=arrSum[j];
                }

            }
        }
        else
        {
            if(1==i)
            {
                arrSum[1]=1;
            }
            else
            {
                n=0;
                for(j=0;j<i;++j)//向后分散，如123->0136
                {
                    n+=arrSum[j];
                    tmpSum[j+1]=n;
                }
                n = 0
                for(j=0;j<=i;++j)
                {//保存到arrSum
                    arrSum[j]=tmpSum[j];
                    n+=arrSum[j];
                }
            }
        }
        document.write(decree.substr(0,i),"=",n,"<br>");
        //if(n>m)return -1;
    }

    return n;
}
document.write("BAA","=",choices("BAA"),"<br>");
document.write("AAAA","=",choices("AAAA"),"<br>");
document.write("BABABABABABABABABABABABAB","=",choices("BABABABABABABABABABABABAB"),"<br>");
</script>

這道比較難，emu寫了程序窮舉了各種可能性輸出后，手工分析了一番數據才終于找到規律。嘔血中……


public class Alphabet {
public static void main(String[] args) {
Alphabet a = new Alphabet();
String[] data = new String[]{"BAABABBAABBBAAB:-1","AABBABABABABBA:520259727",
"BAABABAAABBBAAB:969740563","AAABABABABABBA:294939658"};
for (int i = 0; i < data.length; i++) {
String[] sample = data[ i ].split(":");
String decree = sample[0];
int choices = Integer.parseInt(sample[1]);
assertEquals(a.choices(decree), choices);
}
System.out.println("all passed!");
}

private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public int choices(String decree) {
int[] oldPosList = new int[3];
int timesCount = 1;
oldPosList[decree.startsWith("A")?1:2]=1;
for (int i = 2; i <= decree.length(); i++) {
timesCount = 0;
int[] newPosList = new int[i + 2];
char ch = decree.charAt(i - 1);
if (ch == 'A') {
for (int j = 1; j <= i; j++) {
int times = oldPosList[j];
if (i < decree.length())
for (int k = 1; k <= j; k++) newPosList[k] += times;
timesCount += j*times;
}
} else {
for (int j = 1; j <= i; j++) {
int times = oldPosList[j];
if (i < decree.length())
for (int k = j + 1; k <= i + 1; k++) newPosList[k] += times;
timesCount += (i-j+1)*times;
}
}
oldPosList = newPosList;
if (timesCount > 1000000000) return -1;
}
return timesCount;
}
}

用了一些高深的數學原理，不過對“th+=e/n;”能否把閘值修正到曲線線的定點，我有一點懷疑。

<SCRIPT LANGUAGE="JavaScript">
<!--
function minErr(s,c)
{
for(var th=2;th<50;++th)
{
var e = 0,n=0;
for(var i=0;i<s.length;++i)
{
if(c.charAt(i )!=(s[i]>=th?"C":"N"))
{
++n;
e+=(s[i]-th);
}
}
if(e<=0)
{
th+=e/n;
break;
}
}
e = 0;
for(var i=0;i<s.length;++i)
{
if(c.charAt(i )!=(s[i]>=th?"C":"N"))
{
e+=(s[i]-th)*(s[i]-th);
}
}
return e/s.length;
}

//-->
</SCRIPT>

我估計均方差是一條類似拋物線的曲線（有一個頂點或者一個平的頂部），用二分法收斂到曲線的頂點上。但是由于計算機二進制計算精度限制的原因，實際收斂到的地方可能和頂點有微小的偏差（比如0.1,0.2,0.3,0.4用二進制表示都是循環小數，因此用二分法如果不做特別處理就收斂不到這些點上）。

---

public class MSQErr {
public static void main(String[] args) {
MSQErr err = new MSQErr();
assertEquals(err.minErr(new int[] {3, 3, 1, 8}, "NNNC"), 0);
assertEquals(err.minErr(new int[] {5, 2, 3, 6}, "CCNC"), 0.125);
assertEquals(err.minErr(new int[] {5, 2, 3, 6, 2}, "CCNCN"), 0.1);
assertEquals(err.minErr(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
12, 13, 14, 15, 16, 17, 18, 19, 20},
"NNNCNNNCNNNCNCCCCCCC"), 2.34);
System.out.println("all pass");
}

private static void assertEquals(double a, double b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public double minErr(int[] score, String cancerous) {
double max = 0, min = 1000;
for (int i = 0; i < score.length; i++) {
int s = score[ i ];
if (s > max)
max = s;
if (s < min)
min = s;
}
double mid = (max + min) / 2;
double d1 = 1, d2 = 2;
while (d1 != d2) {
d1 = getErr(score, cancerous, mid);
d2 = getErr(score, cancerous, mid + (max - min) / 1000000000);
if (d1 > d2)
min = mid;
else
max = mid;
mid = (max + min) / 2;
}
return Math.floor(d1 * 1000000000) / 1000000000;
}

public double getErr(int[] score, String cancerous, double threshold) {
double result = 0;
for (int i = 0; i < score.length; i++) {
double d = score[ i ] - threshold;
char c = cancerous.charAt(i);
if (d > 0 && c == 'N' || d < 0 && c == 'C') {
result += d * d;
}
}
return result / score.length;
}
}

---

對它的正確性沒有充分驗證過，因為
d2 = getErr(score, cancerous, mid + (max - min) / 1000000000);
我只是想知道向x軸正方向走一小步看看拋物線的走向是向上還是向下。如果這一小步恰好跨過了拋物線頂點的話對方向的判斷有可能就是錯的，不過這樣的事件發生的概率實在是太小了。
參數驗證沒有做，如果給錯誤參數的話，有可能拋異常（cancerous串太短的話），也有可能忽略錯誤的數據（cancerous太長或者不完全由N和C構成）。題目中沒有明確的提出應該怎么處理這樣的數據，由它去吧。

趕上秋水無恨第一次的解法了，時間復雜度o(1)。

public class HouseParty {
public static void main(String[] args) {
HouseParty hp = new HouseParty();
//hp.maxArea(3,0,0);
long startBy = System.currentTimeMillis();
System.out.println("(8, 0, 0):"+hp.maxArea(8, 0, 0));
System.out.println("(7, 0, 1):"+hp.maxArea(7, 0, 1));
System.out.println("(9, 8, 2):"+hp.maxArea(9, 8, 2));
System.out.println("(6, 23, 13):"+hp.maxArea(6, 23, 13));
System.out.println("(16, 0, 4):"+hp.maxArea(16, 0, 4));
System.out.println("(16, 2, 1):"+hp.maxArea(16, 2, 1));
System.out.println("(16, 4, 4):"+hp.maxArea(16, 4, 4));
System.out.println("(1024, 324, 4):"+hp.maxArea(1024, 324, 4));
System.out.println("(9, 0, 3):"+hp.maxArea(9, 0, 3));
System.out.println("time used:" + (System.currentTimeMillis() - startBy));
}
public int maxArea(int numReg, int numWin, int numDoor) {
int width = 0;
int length = 0;
if (numDoor>4) numDoor =4;
if (numReg<6) return 0;
if (numDoor<1) return 0;
if (numReg+numWin+numDoor<8) return 0;
if (numDoor>1) {
width = 1;
length = 3;
numReg -= 6;
numDoor -= 2;
}else if (numWin>1){
width = 1;
length = 3;
numReg -= 6;
numDoor -= 1;
numWin -= 1;
}else{
width = 1;
length = 3;
numReg -= 7;
numDoor -= 1;
}
if (numDoor >=2 && numReg>=2){
if (width<length) width += 2; else length += 2;
numDoor -= 2;
numReg -= 2;
}

if (numWin >=2 && numReg>=2){
int n = Math.min(numWin,numReg)/2;
int m = n/2; n -= m;
if (width<length) {
width += n*2;
length += m*2;
} else{
width += m*2;
length += n*2;
}
numWin -= 2*(n+m);
numReg -= 2*(n+m);
}

if (numDoor >=1 && numWin >=1 && numReg>=2){
if (width<length) width += 2; else length += 2;
numWin -= 1;
numDoor -= 1;
numReg -= 2;
}
if ((numDoor >=1 || numWin >=1) && numReg>=3){
if (width<length) width += 2; else length += 2;
numReg -= 3;
}
if (numReg>=2){
int n = numReg/2;
int m = n/2; n -= m;
if (width<length) {
width += n;
length += m;
} else{
width += m;
length += n;
}
}
return width*length*16;
}
}

這次時間復雜度降到了o〔n)，結果也正確了，從代碼可以看得清思路。


public class HouseParty {
    public static void main(String[] args) {
        HouseParty hp = new HouseParty();
        long startBy = System.currentTimeMillis();
        System.out.println("(50,50,50):" + hp.maxArea(50, 50, 50));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(8, 0, 0):" + hp.maxArea(8, 0, 0));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(8, 1, 1):" + hp.maxArea(8, 1, 1));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(7, 0, 1):" + hp.maxArea(7, 0, 1));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(9, 8, 2):" + hp.maxArea(9, 8, 2));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(6, 23, 13):" + hp.maxArea(6, 23, 13));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(16, 0, 4):" + hp.maxArea(16, 0, 4));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(16, 2, 1):" + hp.maxArea(16, 2, 1));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(16, 4, 4):" + hp.maxArea(16, 4, 4));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(9, 0, 3):" + hp.maxArea(9, 0, 3));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(8, 0, 4):" + hp.maxArea(8, 0, 4));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(9, 1, 2):" + hp.maxArea(9, 1, 2));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(9, 2, 1):" + hp.maxArea(9, 2, 1));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("time used:" + (System.currentTimeMillis() - startBy));

    }

    public Room biggestRoom;
    public int maxArea(int numReg, int numWin, int numDoor) {
        biggestRoom = null;
        if (numReg < 6)
            return 0;
        if (numDoor < 1)
            return 0;
        if (numReg + numWin + numDoor < 8)
            return 0;
        Room initialRoom = null;
        if (numDoor > 1) {
            initialRoom = new Room("RDR", "R", "RDR", "R");
            numReg -= 6;
            numDoor -= 2;
        } else if (numWin > 0) {
            initialRoom = new Room("RDR", "R", "RWR", "R");
            numReg -= 6;
            numDoor -= 1;
            numWin -= 1;
        } else {
            initialRoom = new Room("RDR", "R", "RRR", "R");
            numReg -= 7;
            numDoor -= 1;
        }

        if (numDoor >= 2 && numReg >= 2) {
            initialRoom.appendWalls("DR", "DR");
            numDoor -= 2;
            numReg -= 2;
        } else if (numDoor >= 1) {
            if (numWin >= 1 && numReg >= 2) {
                initialRoom.appendWalls("DR", "WR");
                numWin -= 1;
                numDoor -= 1;
                numReg -= 2;
            } else if (numReg >= 3) {
                initialRoom.appendWalls("DR", "RR");
                numDoor -= 1;
                numReg -= 3;
            }
        }

        while (numWin >= 2 && numReg >= 2) {
            initialRoom.appendWalls("WR", "WR");
            numWin -= 2;
            numReg -= 2;
        }
        if (numWin >= 1 && numReg >= 3) {
            initialRoom.appendWalls("WR", "RR");
            numWin -= 1;
            numReg -= 3;
        } while (numReg >= 2) {
            initialRoom.appendWalls("R", "R");
            numReg -= 2;
        }
        biggestRoom = initialRoom;
        return initialRoom.getArea() * 16;
    }


    private class Room {
        StringBuffer east, south, west, north;
        public Room(String east, String south, String west, String north) {
            this.east = new StringBuffer(east);
            this.south = new StringBuffer(south);
            this.west = new StringBuffer(west);
            this.north = new StringBuffer(north);
        }

        public int getArea() {
            return east.length() * south.length();
        }

        public String toString() {
            return "east:" + east + "\tsouth:" + south + "\twest:" + west +
                    "\tnorth:" + north;
        }

        public void appendWalls(String w1, String w2) {
            if (east.length() < south.length()) {
                east.append(w1);
                west.append(w2);
            } else {
                south.append(w1);
                north.append(w2);
            }
        }
    }
}

<script>
function Int(n){return Math.floor(n)};
function min(n,m){return Math.min(n,m)};
function maxArea(numReg,numWin,numDoor){
 if(numDoor<1 || numReg<4 )
  return 0;
 var l,x=1,y=1;//x,y表示長和寬
 if(numDoor>4)numDoor=4;numReg-=4;
 var nUsed=min(numReg,numDoor+numWin);//用的門窗的總合
 
 if(nUsed%2)//如果是1或3，則補足2的倍數
 if(numReg-1>nUsed){//如果墻夠用來代替門窗
  if((0==(numReg%2))&&(1==(nUsed%4))&&(nUsed>1))--nUsed;else//(12,4,1)bug
  {numReg-=1;++nUsed;}//則多用一個門窗
 }else --nUsed;//若不夠,則少用一個門窗

 if(nUsed==0)return 0;//(5,5,5)bug

 if(l=Int(nUsed/4))//先添加到四面
 {
  x+=l*2;y+=l*2;//2=一個門窗加一個墻
  numReg-=l*4;nUsed%=4;//每面都要用墻,故*4
 }
 if(nUsed==2)
 {
  numReg-=2;//減去和門窗對應的墻
  x+=2;//先添加給一邊,因為目前兩邊還一樣長
  if(numReg>=2){numReg-=2;y+=1;}//如果墻有多余的,先給另一邊加1,盡量相同
 }

 if(l=Int(numReg/4))//先添加到四面
 {
  x+=l;y+=l;//這時只加了一個墻
  numReg-=l*4;//但一樣每面都要用墻,故*4
 }
 if(numReg>1)//多出來的分兩邊
 {
  numReg-=2;//只有一面加墻
  if(x>y)y+=1;else x+=1;
 }
 return x*y*16;
}

document.write("8,0,0=",maxArea(8,0,0), "<br>");
document.write("8,0,1=",maxArea(8,0,1), "<br>");
document.write("9,8,2=",maxArea(9,8,2), "<br>");
document.write("6,23,13=",maxArea(6,23,13), "<br>");
</script>

窮舉法。其中用了3進制代替多重循環遍歷。時間復雜度超過題目要求，失敗！


import java.util.*;

public class HouseParty {
public static void main(String[] args) {
HouseParty hp = new HouseParty();
//hp.maxArea(3,0,0);
long startBy = System.currentTimeMillis();
/*
System.out.println(hp.maxArea(7, 0, 1));
System.out.println("biggest room:" + hp.biggestRoom);
System.out.println(hp.maxArea(9, 8, 2));
System.out.println("biggest room:" + hp.biggestRoom);
System.out.println(hp.maxArea(6, 23, 13));
System.out.println("biggest room:" + hp.biggestRoom);
*/
System.out.println("(16, 0, 4):"+hp.maxArea(16, 0, 4));
System.out.println("biggest room:" + hp.biggestRoom);
System.out.println("(16, 2, 1):"+hp.maxArea(16, 2, 1));
System.out.println("biggest room:" + hp.biggestRoom);
System.out.println("(16, 4, 4):"+hp.maxArea(16, 4, 4));
System.out.println("biggest room:" + hp.biggestRoom);
System.out.println("time used:" + (System.currentTimeMillis() - startBy));
}

private int numReg, numWin, numDoor;
private int REG = 0, WIN = 1, DOOR = 2;
private Room biggestRoom = null;
public int maxArea(int numReg, int numWin, int numDoor) {
if (numDoor == 0)
return 0;
if (numReg < 4)
return 0;
if (numDoor > 4)
numDoor = 4;
if (numWin > numReg / 2)
numWin = numReg / 2;
this.numReg = numReg;
this.numWin = numWin;
this.numDoor = numDoor;
ArrayList possibleWalls = getPossibleWals(numReg / 2 , numWin,1);
int result = getMaxArea(possibleWalls);
return result * 16;
}

private ArrayList getPossibleWals(int numReg, int numWin, int numDoor) {
ArrayList result = new ArrayList();
if (numWin > numReg / 2 - 1)
numWin = numReg / 2 - 1;
if (numDoor > 1)
numDoor = 1;
int wallMaxLength = numReg + numWin + numDoor;
for (int wallLength = 1; wallLength < wallMaxLength; wallLength++) {
for (int i = 0, n = new Double(Math.pow(3, wallLength)).intValue();
i < n; i++) { //這樣窮舉的效率很低，應用遞歸檢查
Wall wall = new Wall();
wall.wall = new int[wallLength];
int tmp = i;
for (int j = 0; j < wallLength; j++) {
wall.wall[j] = tmp % 3;
tmp = tmp / 3;
}
if (wall.checkRule()) {
result.add(wall);
}
}
}
return result;
}

private int getMaxArea(ArrayList possibleWalls) {
int wallCount = possibleWalls.size();
int result = 0;
for (int iWallEast = 0; iWallEast < wallCount; iWallEast++) {
Wall east = (Wall) possibleWalls.get(iWallEast);
for (int iWallWest = 0; iWallWest < wallCount; iWallWest++) {
Wall west = (Wall) possibleWalls.get(iWallWest);
if (east.wall.length != west.wall.length)
continue;
if (east.wall.length != west.wall.length)
continue;
if (east.getRegCount() + west.getRegCount() > numReg)
continue;
if (east.getWinCount() + west.getWinCount() > numWin)
continue;
if (east.getDoorCount() + west.getDoorCount() > numDoor)
continue;
for (int iWallSouth = 0; iWallSouth < wallCount; iWallSouth++) {
Wall south = (Wall) possibleWalls.get(iWallSouth);
if (east.getRegCount() + west.getRegCount() +
south.getRegCount() > numReg)
continue;
if (east.getWinCount() + west.getWinCount() +
south.getWinCount() > numWin)
continue;
if (east.getDoorCount() + west.getDoorCount() +
south.getDoorCount() > numDoor)
continue;
for (int iWallNorth = 0; iWallNorth < wallCount; iWallNorth++) {
Wall north = (Wall) possibleWalls.get(iWallNorth);
if (south.wall.length != north.wall.length)
continue;
if (east.getRegCount() + west.getRegCount() +
south.getRegCount() + north.getRegCount() > numReg)
continue;
if (east.getWinCount() + west.getWinCount() +
south.getWinCount() + north.getWinCount() > numWin)
continue;
if (east.getDoorCount() + west.getDoorCount() +
south.getDoorCount() + north.getDoorCount() >
numDoor)
continue;
if (east.getDoorCount() + west.getDoorCount() +
south.getDoorCount() + north.getDoorCount() < 1)
continue;
Room room = new Room(east, south, west, north);
if (room.getArea() > result) {
result = room.getArea();
biggestRoom = room;
}
}
}
}
}
return result;
}

private class Wall {
public int[] wall;
public int[] combinationCount;
public int getRegCount() {
return combinationCount[REG];
}

public int getWinCount() {
return combinationCount[WIN];
}

public int getDoorCount() {
return combinationCount[DOOR];
}

public String toString() {
char[] tmp = new char[] {'R', 'W', 'D'};
String result = "";
for (int i = 0; i < wall.length; i++)
result += tmp[wall[ i ]];
return result;

}

public boolean checkRule(){
this.combinationCount = new int[3];
if (wall[0] == DOOR)
return false;
if (wall[wall.length - 1] == DOOR)
return false;
if (wall[0] == WIN)
return false;
if (wall[wall.length - 1] == WIN)
return false;
for (int i = 0, n = wall.length; i < n; i++)
if (wall[ i ] == WIN && (wall[i - 1] != REG || wall[i + 1] != REG))
return false;
else
combinationCount[wall[ i ]]++;
if (getRegCount() < 1)
return false;
if (getRegCount() > numReg)
return false;
if (getWinCount() > numWin)
return false;
if (getDoorCount() > numDoor)
return false;
if (getDoorCount() > 1)
return false;
return true;
}
}


private class Room {
Wall east, south, west, north;
public Room(Wall east, Wall south, Wall west, Wall north) {
this.east = east;
this.south = south;
this.west = west;
this.north = north;
}

public int getArea() {
if (east.wall.length != west.wall.length)
return 0;
if (south.wall.length != north.wall.length)
return 0;
if (east.getRegCount() + west.getRegCount() + south.getRegCount() +
north.getRegCount() > numReg)
return 0;
if (east.getWinCount() + west.getWinCount() + south.getWinCount() +
north.getWinCount() > numWin)
return 0;
if (east.getDoorCount() + west.getDoorCount() + south.getDoorCount() +
north.getDoorCount() > numDoor)
return 0;
if (east.getDoorCount() + west.getDoorCount() + south.getDoorCount() +
north.getDoorCount() < 1)
return 0;
return east.wall.length * south.wall.length;

}

public String toString() {
return "east:" + east + "\tsouth:" + south + "\twest:" + west +
"\tnorth:" + north;
}
}
}

>>import Java.util.Hashtable;

Java這個包是樓主自己寫的吧？我只知道有個java.util.Hashtable

>>Map allDrivers =; 這也能編譯通過？

不只jboss和eclipse是免費的，java也是免費的，但是我們都還在靠java混飯吃呢，這倒沒什么不妥。

從來沒有人證明過不可能有銀彈，這也不是問題。目標過于遠大？這更不成其為問題了。

剩下的問題我認為才是真正的問題。普元再強，你能強得過微軟去？windows上面的軟件大半不是微軟出品的，用java開發的軟件也大半不是sun出品的，可是普元上面的構件卻基本上是普元出品的。雖然我們自己也可以開發構建，但是這不是一個開放的標準，我們如果這樣做了自己的利益得不到保障，誰會去這樣做呢？所以普元這個封閉的標準造成了他只能閉門造車，想幫他忙豐富他的構件庫的人都無從下手。普元開發能力再強能開發出來多少種構件呢？

我覺得普元想做大，唯一的出路就是吧開發和應用環境都免費開放，最好干脆開源，并免費開放目前的大多數可以通用化的構件，在他的主導下創建并維護一個社群，讓每個人都可以用EOS獲取自己的利益，然后他可以以定制構件和生產出售在EOS平臺上的軟件來盈利。

如果他不這樣做，我相信他的競爭對手遲早也會這么做。事實上，如果我是個沒有生存壓力的自由程序員，我現在也許已經在這么做了。

在他轉向開放之前，我沒有辦法再看好他。

題目真夠難的，一個鐘頭完成3道題的，都是些什么人?。。?/div>