UVA 10324ゼロとワン

Question

私はUVA（10324）から質問をしていましたが、常に時間制限を取得し続けています。私はかなりコードが正しいと確信していますが、まだコードは無限ループに入ります。私はこの質問を6回試みましたが、それを渡すことはできません。

誰かが間違っている可能性がどのようにいくつかの光を当てることができます：

import java.util.*; 
import java.lang.*; 
import java.io.*; 

/* Name of the class has to be "Main" only if the class is public. */ 
public class Main { 
    public static void main(String[] args) { 
     Scanner sc = new Scanner(System.in); 
     int ii=1; 
     boolean flag = false; 
     while(sc.hasNextLine()){ 
      String str = sc.nextLine(); 
      if(str.trim().isEmpty()) 
       break; 
      int TC = sc.nextInt(); 
      System.out.println("Case " +ii+++":"); 
      while(TC-->0){ 
       flag = false; 
       int a = sc.nextInt(); 
       int b = sc.nextInt(); 
       int c=0; 
       if(a>b){ 
        c=a; 
        a=b; 
        b=c; 
       } 
       c = str.charAt(a)-'0'; 
       for(int i=a+1;i<=b;i++){ 
        if(str.charAt(i)-'0' != c){ 
         flag = true; 
         break; 
        } 
       } 
       System.out.println(flag?"No":"Yes"); 
      } 
      try{ 
       sc.nextLine(); 
      } 
      catch(Exception ex){ 
       break; 
      } 
     } 
} 
} 

Answer 1

それは非効率的ですwhileループ内のfor(int i=a+1;i<=b;i++)ループの実行です。これは毎回ほとんどの文字列をスキャンする必要があります。

各入力文字列に複数のテストケースがあるため、クエリの方が効率的な別のデータ構造を作成できます。

whileループの前に、各位置のための文字列の開始以降に変更された回数を格納するアレイ、作成：次に

int total = 0; 
int changes[] = new int[str.length()]; 
for(int i = 1; i < changes.length; i++) { 
    if(str.charAt(i) != str.charAt(i - 1)) { 
     total++; 
    } 
    changes[i] = total; 
} 

にフラグを設定することができるとして得た：

boolean flag = (changes[a] != changes[b]);