[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks
487做的不错……
第一题是这么一个题,给出一个序列N(N<=50),你可以选择距离恰好为L的两个数,取出来求和(每个数只能用一次),求取法让和最大
乍一看有点蒙,实际上,这N个数可以按照对L+1同余分类,这样就分出了若干类,然后每类里数肯定<=25,在2S的时间内用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是这么个问题:给你N类球(N<=50),和一张N*N的转移表,某台机器的功能就是:扔进若干球(数量不定,每个球都属于这N类),随机取两个出来,根据转移表合成出一个……直到只有一个球,问对于给定的输入,输出能否确定……
听起来很玄的题…我当时猜测的结论是:由少许几个球的情况可以产生所有情况,于是就枚举+验证,刚开始猜测的是3~4个,结果4个TLE,3个大概过了……水了下,对了……
public class BallsConverter{
  
int[][] arr;
  
int n;
 
  
int work(int[] now,int n){
    
if (n==1return 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==-2return "Bad";
    }
    
return "Good";
  }
}
经刁哥教育,我明白了,这个东西实际上是这个意思,如果这个东西满足结合律,则顺序无关紧要了,可以直接从头到尾合并算出……也就确定了……于是检验结合律相当于检验arr[i][arr[j][k]]==arr[arr[i][j]][k]……

500是个规律题……但是我没找到规律……悲剧了……
rating-=13,1522……

posted on 2010-11-30 23:28 sweetsc 阅读(142) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: