一開始用土法煉鋼直接算的方法，喜提三題TLE，後來我改用只記下每一次輸入的端點（都紀錄在一個boolean的一維陣列中）並把土法煉鋼的O(n×m)時間複雜度改成O(n)，空間複雜度依然是O(n) 結果記憶體爆了

import java.util.*;

public class Main {

 public static void main(String[] args) {

    Scanner sc=new Scanner(System.in);

    int pe=sc.nextInt()+1;

    boolean [] line=new boolean[pe];

    boolean li;

       int n=sc.nextInt();

    sc.nextLine();

    for(int i=1;i<=n;i++){

     String [] s=sc.nextLine().split(" ");

     line[Integer.parseInt(s[0])-1]=!line[Integer.parseInt(s[0])-1];  

           line[Integer.parseInt(s[1])]=!line[Integer.parseInt(s[1])];

    }

    li=true;

    int time=0;

    for(int i=1;i<line.length;i++){

    li=line[i-1]==true?!li:li;

    time+=li?1:0;

    }

    System.out.println(time);

    sc.close();

 }

}

一開始用土法煉鋼直接算的方法，喜提三題TLE，後來我改用只記下每一次輸入的端點（都紀錄在一個boolean的一維陣列中）並把土法煉鋼的O(n×m)時間複雜度改成O(n)，空間複雜度依然是O(n) 結果記憶體爆了

import java.util.*;

public class Main {

 public static void main(String[] args) {

    Scanner sc=new Scanner(System.in);

    int pe=sc.nextInt()+1;

    boolean [] line=new boolean[pe];

    boolean li;

       int n=sc.nextInt();

    sc.nextLine();

    for(int i=1;i<=n;i++){

     String [] s=sc.nextLine().split(" ");

     line[Integer.parseInt(s[0])-1]=!line[Integer.parseInt(s[0])-1];  

           line[Integer.parseInt(s[1])]=!line[Integer.parseInt(s[1])];

    }

    li=true;

    int time=0;

    for(int i=1;i

    li=line[i-1]==true?!li:li;

    time+=li?1:0;

    }

    System.out.println(time);

    sc.close();

 }

}

 

這題 $N$ 太大，即使時間/空間複雜度 $O(N)$ 都還是會爆炸，要想想有沒有更好的方法，像是這題的 $M$ 看起來就比較合理，有沒有辦法做到 $O(M)$ 或 $O(MlogM)$ 之類的的複雜度呢？

如果使用20億個bit，相當於238MB，何況boolean的儲存空間不只一個bit(大約1byte)，所以這樣寫一定爆。

一開始用土法煉鋼直接算的方法，喜提三題TLE，後來我改用只記下每一次輸入的端點（都紀錄在一個boolean的一維陣列中）並把土法煉鋼的O(n×m)時間複雜度改成O(n)，空間複雜度依然是O(n) 結果記憶體爆了

import java.util.*;

public class Main {

 public static void main(String[] args) {

    Scanner sc=new Scanner(System.in);

    int pe=sc.nextInt()+1;

    boolean [] line=new boolean[pe];

    boolean li;

       int n=sc.nextInt();

    sc.nextLine();

    for(int i=1;i<=n;i++){

     String [] s=sc.nextLine().split(" ");

     line[Integer.parseInt(s[0])-1]=!line[Integer.parseInt(s[0])-1];  

           line[Integer.parseInt(s[1])]=!line[Integer.parseInt(s[1])];

    }

    li=true;

    int time=0;

    for(int i=1;i

    li=line[i-1]==true?!li:li;

    time+=li?1:0;

    }

    System.out.println(time);

    sc.close();

 }

}

 

這題 $N$ 太大，即使時間/空間複雜度 $O(N)$ 都還是會爆炸，要想想有沒有更好的方法，像是這題的 $M$ 看起來就比較合理，有沒有辦法做到 $O(M)$ 或 $O(MlogM)$ 之類的的複雜度呢？

我剛發了文我就想到去掉arrays的方法，就是只弄個List儲存端點，再計算端點之間是站著的距離，這樣時間是O(mlogm) ，空間是O(m)了

算下來第三個測資可以過，但第45個測資還是會MLE(約85mb)，下面是我改的代碼

一開始用土法煉鋼直接算的方法，喜提三題TLE，後來我改用只記下每一次輸入的端點（都紀錄在一個boolean的一維陣列中）並把土法煉鋼的O(n×m)時間複雜度改成O(n)，空間複雜度依然是O(n) 結果記憶體爆了

import java.util.*;

public class Main {

 public static void main(String[] args) {

    Scanner sc=new Scanner(System.in);

    int pe=sc.nextInt()+1;

    boolean [] line=new boolean[pe];

    boolean li;

       int n=sc.nextInt();

    sc.nextLine();

    for(int i=1;i<=n;i++){

     String [] s=sc.nextLine().split(" ");

     line[Integer.parseInt(s[0])-1]=!line[Integer.parseInt(s[0])-1];  

           line[Integer.parseInt(s[1])]=!line[Integer.parseInt(s[1])];

    }

    li=true;

    int time=0;

    for(int i=1;i

    li=line[i-1]==true?!li:li;

    time+=li?1:0;

    }

    System.out.println(time);

    sc.close();

 }

}

 

這題 $N$ 太大，即使時間/空間複雜度 $O(N)$ 都還是會爆炸，要想想有沒有更好的方法，像是這題的 $M$ 看起來就比較合理，有沒有辦法做到 $O(M)$ 或 $O(MlogM)$ 之類的的複雜度呢？

我剛發了文我就想到去掉arrays的方法，就是只弄個List儲存端點，再計算端點之間是站著的距離，這樣時間是O(mlogm) ，空間是O(m)了

算下來第三個測資可以過，但第45個測資還是會MLE(約85mb)，下面是我改的代碼

package apcs;

import java.util.*;

public class b526 {//time cost O(w log(w)),space O(w)

public static void main(String [] args) {

Scanner sc=new Scanner(System.in);

int p=sc.nextInt();

int w=sc.nextInt();

Listpoint=new ArrayList<>();

sc.nextLine();

for(int i=1;i<=w;i++) {

String[]s=sc.nextLine().split(" ");

point.add(Integer.parseInt(s[0])-1);

point.add(Integer.parseInt(s[1]));

}

Collections.sort(point);

for(int i=1;i<point.size();i++)

if(point.get(i)==point.get(i-1)) {

point.remove(i);

point.remove(i-1);

i--;

}

int time=point.get(0)+p-point.get(point.size()-1);

for(int i=2;i<point.size()-1;i+=2)

time+=point.get(i)-point.get(i-1);

System.out.println(time);

sc.close();

}

}

然後奇怪的是 我就算把代碼閹割成只剩輸入

package apcs;
import java.util.Scanner;
public class b526 {
public static void main(String [] args) {
    Scanner sc=new Scanner(System.in);
    sc.nextInt();
    int w=sc.nextInt();
        for(int i=1;i<=w;i++)
        sc.nextLine();
System.out.println(w);
}
}

第45測資還是MLE(ˊ._.)

 

Scanner面對大的測資很容易爆

可以嘗試使用BufferReader和BufferWriter，StreamTokenizer也是不錯的選擇。

其實還有一個io寫法更快，如果上述三種io物件都超時的話，可以試試看這種寫法 https://zerojudge.tw/ShowThread?postid=36365  ，可以把Writer物件拿掉，單獨寫需要的程式碼就好。

一開始用土法煉鋼直接算的方法，喜提三題TLE，後來我改用只記下每一次輸入的端點（都紀錄在一個boolean的一維陣列中）並把土法煉鋼的O(n×m)時間複雜度改成O(n)，空間複雜度依然是O(n) 結果記憶體爆了

import java.util.*;

public class Main {

 public static void main(String[] args) {

    Scanner sc=new Scanner(System.in);

    int pe=sc.nextInt()+1;

    boolean [] line=new boolean[pe];

    boolean li;

       int n=sc.nextInt();

    sc.nextLine();

    for(int i=1;i<=n;i++){

     String [] s=sc.nextLine().split(" ");

     line[Integer.parseInt(s[0])-1]=!line[Integer.parseInt(s[0])-1];  

           line[Integer.parseInt(s[1])]=!line[Integer.parseInt(s[1])];

    }

    li=true;

    int time=0;

    for(int i=1;i

    li=line[i-1]==true?!li:li;

    time+=li?1:0;

    }

    System.out.println(time);

    sc.close();

 }

}

 

這題 $N$ 太大，即使時間/空間複雜度 $O(N)$ 都還是會爆炸，要想想有沒有更好的方法，像是這題的 $M$ 看起來就比較合理，有沒有辦法做到 $O(M)$ 或 $O(MlogM)$ 之類的的複雜度呢？

我剛發了文我就想到去掉arrays的方法，就是只弄個List儲存端點，再計算端點之間是站著的距離，這樣時間是O(mlogm) ，空間是O(m)了

算下來第三個測資可以過，但第45個測資還是會MLE(約85mb)，下面是我改的代碼

package apcs;

import java.util.*;

public class b526 {//time cost O(w log(w)),space O(w)

public static void main(String [] args) {

Scanner sc=new Scanner(System.in);

int p=sc.nextInt();

int w=sc.nextInt();

Listpoint=new ArrayList<>();

sc.nextLine();

for(int i=1;i<=w;i++) {

String[]s=sc.nextLine().split(" ");

point.add(Integer.parseInt(s[0])-1);

point.add(Integer.parseInt(s[1]));

}

Collections.sort(point);

for(int i=1;i<point.size();i++)

if(point.get(i)==point.get(i-1)) {

point.remove(i);

point.remove(i-1);

i--;

}

int time=point.get(0)+p-point.get(point.size()-1);

for(int i=2;i<point.size()-1;i+=2)

time+=point.get(i)-point.get(i-1);

System.out.println(time);

sc.close();

}

}

然後奇怪的是 我就算把代碼閹割成只剩輸入

package apcs;
import java.util.Scanner;
public class b526 {
public static void main(String [] args) {
    Scanner sc=new Scanner(System.in);
    sc.nextInt();
    int w=sc.nextInt();
        for(int i=1;i<=w;i++)
        sc.nextLine();
System.out.println(w);
}
}

第45測資還是MLE(ˊ._.)

 

Scanner面對大的測資很容易爆

可以嘗試使用BufferReader和BufferWriter，StreamTokenizer也是不錯的選擇。

其實還有一個io寫法更快，如果上述三種io物件都超時的話，可以試試看這種寫法 https://zerojudge.tw/ShowThread?postid=36365  ，可以把Writer物件拿掉，單獨寫需要的程式碼就好。

我把scanner換成buffer就AC了 干超有用，謝啦：D

 

Scanner面對大的測資很容易爆

可以嘗試使用BufferReader和BufferWriter，StreamTokenizer也是不錯的選擇。

其實還有一個io寫法更快，如果上述三種io物件都超時的話，可以試試看這種寫法 https://zerojudge.tw/ShowThread?postid=36365  ，可以把Writer物件拿掉，單獨寫需要的程式碼就好。

我把scanner換成buffer就AC了 干超有用，謝啦：D

Buffer確實是cp值很高的作法，寫起來還算快，而且幾乎不會遇到TLE，記憶體使用上也還算有效率，但是如果你還會繼續寫Java超過一年的話，可以把上述網址記下來，這個做法未來一定會用到(ZeroJudge有很多很刁鑽的題目)