編程競賽的快速I

編程競賽的快速I/O

在競爭性編程中,儘快讀取輸入很重要,這樣可以節省寶貴的時間。

您肯定已經看到各種問題陳述:“警告:大型I/O數據,請謹慎使用某些語言(儘管如果算法設計得當,大多數應該可以)”。解決此類問題的關鍵是使用更快的I/O技術。

通常建議使用scanf / printf代替cin / cout以獲得快速的輸入和輸出。 但是,您仍然可以使用cin / cout並通過在main()函數中包含以下兩行來達到與scanf / printf相同的速度:

<code>ios_base::sync_with_stdio(false);/<code>

如果在程序執行其第一個輸入或輸出操作之前調用它,則將打開或關閉所有C++標準流與其對應的標準C流的同步。添加ios_base :: sync_with_stdio(false); (默認情況下為true)(在任何I / O操作中避免此同步之前)。它是std :: ios_base函數的靜態成員。

<code>cin.tie(NULL);/<code>

tie()是一種僅在std :: cin接受輸入之前保證刷新std :: cout的方法。這對於交互式控制檯程序很有用,因為交互式控制檯程序需要不斷更新控制檯,但同時也會降低大型I / O的速度。NULL部分僅返回NULL指針。

此外,您可以將標準模板庫(STL)包含在單個include中:

<code>#include <bits>/<code>

因此,用於競爭性編程的模板可能如下所示:

<code>#include <bits>using namespace std;int main(){    ios_base::sync_with_stdio(false);    cin.tie(NULL);    return 0;}/<bits>/<code>

建議使用cout <

我們可以在問題INTEST – SPOJ(http://www.spoj.com/problems/INTEST/)上的巨大輸入測試中測試我們的輸入和輸出方法。在繼續閱讀之前,建議您先解決該問題。

C ++ 4.9.2中的解決方案

普通I/O:下面的代碼使用cin和cout。 該解決方案的運行時間為2.17秒。

<code>// A normal IO example code #include <bits> using namespace std; int main() {     int n, k, t;     int cnt = 0;     cin >> n >> k;     for (int i=0; i> t;         if (t % k == 0)             cnt++;     }     cout << cnt << "\\n";     return 0; } /<bits>/<code>

快速的I/O,我們可以通過添加兩行來做得更好,並大大減少運行時間。 下面的程序運行時間為0.41秒。

<code>// A fast IO program #include <bits> using namespace std;   int main() {     // added the two lines below     ios_base::sync_with_stdio(false);     cin.tie(NULL);              int n, k, t;     int cnt = 0;     cin >> n >> k;     for (int i=0; i> t;         if (t % k == 0)             cnt++;     }     cout << cnt << "\\n";     return 0; } /<bits>/<code>

現在談論諸如ACM ICPC,Google CodeJam,TopCoder Open之類的競賽,這是一種以最快的方式讀取整數的專有代碼。

<code>void fastscan(int &number) {     //variable to indicate sign of input number     bool negative = false;     register int c;       number = 0;       // extract current character from buffer     c = getchar();     if (c=='-')     {         // number is negative         negative = true;           // extract the next character from the buffer         c = getchar();     }       // Keep on extracting characters if they are integers     // i.e ASCII Value lies from '0'(48) to '9' (57)     for (; (c>47 && c<58); c=getchar())         number = number *10 + c - 48;       // if scanned input has a negative sign, negate the     // value of the input number     if (negative)         number *= -1; }   // Function Call int main() {     int number;     fastscan(number);     cout << number << "\\n";     return 0; } /<code> 

getchar_unlocked()用於在C語言中更快地輸入以進行競爭性編程。


分享到:


相關文章: