487做的不錯(cuò)……
第一題是這么一個(gè)題，給出一個(gè)序列N（N<=50），你可以選擇距離恰好為L(zhǎng)的兩個(gè)數(shù)，取出來(lái)求和（每個(gè)數(shù)只能用一次），求取法讓和最大
乍一看有點(diǎn)蒙，實(shí)際上，這N個(gè)數(shù)可以按照對(duì)L＋1同余分類，這樣就分出了若干類，然后每類里數(shù)肯定<=25，在2S的時(shí)間內(nèi)用2^25的方法搜索即可……
1 public class BunnyComputer
2 {
3 int dfs(int[] arr,int now,int k)
4 {
5 if (now+k>=arr.length) return 0;
6 int notTake=dfs(arr,now+k,k);
7 int take=arr[now]+arr[now+k]+dfs(arr,now+k+k,k);
8 return take>notTake?take:notTake;
9 }
10 public int getMaximum(int[] preference, int k)
11 {
12 k++;
13 int ans=0;
14 for (int i=0;i<k;i++)
15 ans+=dfs(preference,i,k);
16 return ans;
17 }
18 }
水了這么一道，rating->1535，黃了……
489的300是這么個(gè)問(wèn)題：給你N類球（N<=50），和一張N＊N的轉(zhuǎn)移表，某臺(tái)機(jī)器的功能就是：扔進(jìn)若干球（數(shù)量不定，每個(gè)球都屬于這N類），隨機(jī)取兩個(gè)出來(lái)，根據(jù)轉(zhuǎn)移表合成出一個(gè)……直到只有一個(gè)球，問(wèn)對(duì)于給定的輸入，輸出能否確定……
聽(tīng)起來(lái)很玄的題…我當(dāng)時(shí)猜測(cè)的結(jié)論是：由少許幾個(gè)球的情況可以產(chǎn)生所有情況，于是就枚舉＋驗(yàn)證，剛開(kāi)始猜測(cè)的是3～4個(gè)，結(jié)果4個(gè)TLE，3個(gè)大概過(guò)了……水了下，對(duì)了……
public class BallsConverter{
int[][] arr;
int n;
int work(int[] now,int n){
if (n==1) return now[0];
int[] next=new int[n-1];
int[] ans=new int[n-1];
for (int i=0;i<n-1;i++){
for (int j=0;j<n-1;j++)
next[j]=now[j];
next[i]=arr[now[i]][now[n-1]];
ans[i]=work(next,n-1);
}
for (int i=1;i<n-1;i++){
if (ans[i]!=ans[0]) return -2;
}
return ans[0];
}
public String theGood(String[] convent){
n=convent.length;
arr=new int[n][n];
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
char tmp=convent[i].charAt(j);
if (tmp>='A' && tmp<='Z')
arr[i][j]=tmp-'A';
else
arr[i][j]=tmp-'a'+26;
}
}
for (int t1=0;t1<n;t1++)
for (int t2=0;t2<n;t2++)
for (int t3=0;t3<n;t3++)
{
int[] tmp=new int[3];
tmp[0]=t1; tmp[1]=t2; tmp[2]=t3;
int ans=work(tmp,3);
if (ans==-2) return "Bad";
}
return "Good";
}
}
經(jīng)刁哥教育，我明白了，這個(gè)東西實(shí)際上是這個(gè)意思，如果這個(gè)東西滿足結(jié)合律，則順序無(wú)關(guān)緊要了，可以直接從頭到尾合并算出……也就確定了……于是檢驗(yàn)結(jié)合律相當(dāng)于檢驗(yàn)arr[i][arr[j][k]]==arr[arr[i][j]][k]……
500是個(gè)規(guī)律題……但是我沒(méi)找到規(guī)律……悲劇了……
rating-=13，1522……