首页 > 专题系列 > Java解POJ > POJ 3274 Gold Balanced Lineup [解题报告] Java
2013
11-12

POJ 3274 Gold Balanced Lineup [解题报告] Java

Gold Balanced Lineup

问题描述 :

Farmer John’s N cows (1 ≤ N ≤ 100,000) share many similarities. In fact, FJ has been able to narrow down the list of features shared by his cows to a list of only K different features (1 ≤ K ≤ 30). For example, cows exhibiting feature #1 might have spots, cows exhibiting feature #2 might prefer C to Pascal, and so on.

FJ has even devised a concise way to describe each cow in terms of its "feature ID", a single K-bit integer whose binary representation tells us the set of features exhibited by the cow. As an example, suppose a cow has feature ID = 13. Since 13 written in binary is 1101, this means our cow exhibits features 1, 3, and 4 (reading right to left), but not feature 2. More generally, we find a 1 in the 2^(i-1) place if a cow exhibits feature i.

Always the sensitive fellow, FJ lined up cows 1..N in a long row and noticed that certain ranges of cows are somewhat "balanced" in terms of the features the exhibit. A contiguous range of cows i..j is balanced if each of the K possible features is exhibited by the same number of cows in the range. FJ is curious as to the size of the largest balanced range of cows. See if you can determine it.

输入:

Line 1: Two space-separated integers, N and K.

Lines 2..N+1: Line i+1 contains a single K-bit integer specifying the features present in cow i. The least-significant bit of this integer is 1 if the cow exhibits feature #1, and the most-significant bit is 1 if the cow exhibits feature #K.

输出:

Line 1: A single integer giving the size of the largest contiguous balanced group of cows.

样例输入:

7 3
7
6
7
2
1
4
2

样例输出:

4

温馨提示:

In the range from cow #3 to cow #6 (of size 4), each feature appears in exactly 2 cows in this range

解题代码:

import java.util.HashMap;  
    import java.util.Scanner;  
      
    public class Main{  
      
        public static final int size = 100001;  
        static int max_dis ;  
          
        public static void main(String[] args) {  
              
            Scanner scan = new Scanner(System.in);  
            while(scan.hasNext()){  
            max_dis = 0;  
            int N = Integer.parseInt(scan.next());  
            int K = Integer.parseInt(scan.next());  
            HashMap< String,Integer> hm = new HashMap< String,Integer>();  
            StringBuffer sb = new StringBuffer();  
            for(int i=0;i< K;i++)  
                sb.append(0);  
            hm.put(sb.toString(),0);  
            int sum[][] = new int[N+1][K];  
            int c[][]= new int[N+1][K];  
              
            for(int i=1;i<=N;i++){  
                int p = Integer.parseInt(scan.next());  
                int feature  ;  
                for(int j=0;j< K;j++){  
                    feature = p%2;  
                    sum[i][j] = sum[i-1][j] + feature;  
                    c[i][j] = sum[i][j]-sum[i][0];  
                    p /= 2;  
                }  
                add(c[i],i,hm);  
            }  
            System.out.println(max_dis);  
              
            }  
        }  
      
        public static void add(int[] a, int i,HashMap< String,Integer> hm) {  
            String data = null;  
            StringBuffer sb = new StringBuffer();  
            for(int k=0;k< a.length;k++)  
                sb.append(a[k]);  
            data = sb.toString();  
            if(hm.get(data)==null){  
                hm.put(data, i);  
            }else{  
                if(max_dis< i-(hm.get(data)))  
                    max_dis = i-hm.get(data);  
            }  
              
        }  
      
    }

  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。