跳转至

題型概述

在算法競賽中，有多種多樣的問題類型。

傳統題

傳統題 是目前算法競賽中較為常見的題型。

選手需要提交源代碼，評測系統會使用事先準備好一些輸入數據和相應的輸出數據作為測試點1，將選手提交的源代碼編譯後2，讓選手程序讀入輸入數據，通過將選手輸出與事先準備好的輸出比較，來判斷選手程序是否正確。這種評測方式被稱之為 黑盒評測3。

對於一個測試點，往往還會設置時間限制和空間限制。

時間限制，指的是程序運行時間的限制4。選手程序在一個測試點上的運行時間不能超過給定的時間限制。

空間限制，指的是程序使用的內存量的限制。選手程序在運行時佔用的最大空間不能超過給定的空間限制。

在程序正常運行結束後，選手的輸出會和測試點輸出進行比對。這種比對一般採用過濾文末換行和行末空格之後，進行全文比對的方式。對於某些特殊的題目，會使用 Special Judge 來進行比對。

這一過程結束後，評測系統會根據程序的運行狀態，給出不同的 評測結果5：

  • Accepted（AC）：選手程序被接受。
  • Compile Error（CE）：選手程序無法正常編譯。
  • Wrong Answer（WA）：選手程序正常結束，但是選手程序的輸出與測試點輸出不符。
  • Presentation Error（PE）：選手程序正常結束，但是格式不符合要求6。
  • Runtime Error（RE）：選手程序非正常結束（選手程序結束時的返回值不為零）。
  • Time Limit Exceeded（TLE）：選手程序運行的時間超過了給定的時間限制。
  • Memory Limit Exceeded（MLE）：選手程序佔用的最大空間超過了給定的空間限制。
  • Output Limit Exceeded（OLE）：選手程序輸出的內容的量超過了最大限制。

在 ICPC 賽事中，你的程序需要在一道題目的所有測試點上都取得 AC 狀態，才能視為通過相應的題目。在 OI 賽事中，在一個測試點中取得 AC 狀態，即可拿到該測試點的分數7。

提交答案題

提交答案題 是直接提交答案的題目。該種題目一般會給出輸入文件，要求提交包含有 XXX1.out、XXX2.out、XXX3.out…XXXn.out 的壓縮包、文件夾或純文件。

提交答案後，評測系統會比較答案文件與標準答案，根據選手答案的優劣情況和任務完成度，給予一定的分數。

因為提交答案題不需要運行源程序，故提交答案題不存在時間和空間限制。

做這種題目一般有兩種方法：

  • 手玩。這種方法簡單粗暴，但是遇到較大的數據就沒轍了。
  • 編寫一個程序來獲得答案文件。

交互題

交互題 是需要選手程序與測評程序交互來完成任務的題目。一類常見的情形是，選手程序向測評程序發出詢問，並得到其反饋。測評程序可能對選手的詢問作出限制，或調整應答策略來儘可能增加詢問次數，這也給題目帶來了更多變化。

更詳細的交互題講解可以看 交互題。

交互方式主要有如下兩種。雖然技術上有不小的差異，但在考察算法的本質上它們並沒有實際區別。

STDIO 交互

STDIO 交互（標準 I/O 交互）是 Codeforces、AtCoder 等在線平台的交互手段，也是 ICPC 系列賽事中的標準。Codeforces 提供了一個更加簡要的 説明（英文）。

ZQC 的迷宮

LOJ #559.「LibreOJ Round #9」ZQC 的迷宮

請注意最下方添加內容。

本題是一道交互題。

位於 \(n \times m\) 個方格組成的黑暗迷宮的你，需要走到這個迷宮的終點，以完成迷宮挑戰。

最開始，你位於迷宮的起點即 \((1,1)\) 處，且面向右側，終點位於 \((n,m)\) 處。迷宮中任意兩個方格之間均連通，且僅有唯一的一條路徑，兩個相鄰（即上、下、左、右四連通）方格間長度為一個單位長度。兩個相鄰方格之間可能會有牆壁，牆壁厚度相對於方格而言非常小，粗略不計。迷宮的邊界均有牆壁，且每一堵牆壁均與邊界連通。迷宮是完全黑暗的，這意味着，你無法得到除 \((n,m)\) 以外的任何信息。

為了在黑暗條件下儘量不迷路，每次前進時你只能從當前格子出發，沿着左側或右側牆壁，左手或右手扶着牆壁前進，並且使扶着牆壁的手移動距離恰好為一個單位長度。需要注意的是，若左側或右側牆壁不存在，則沿該側方向無法前進。

在黑暗中過久的你會感到恐懼，因此你需要在你儘早走出迷宮。如果你沒有在限定步數內走出迷宮，挑戰將會失敗。

對於這類題目，選手只需像往常一樣將詢問寫到標準輸出，刷新輸出緩衝 後從標準輸入讀取結果。選手程序刷新輸出緩衝後，通過管道連接它的測評程序（稱為交互器）才能立刻接收到這些數據。在 C/C++ 中，fflush(stdout) 和 std::cout << std::flush 可以實現這個操作（使用 std::cout << std::endl 換行時也會自動刷新緩衝區，但是 std::cout << '\n' 不會）；Pascal 則是 flush(output)。

Grader 交互

Grader 交互方式常見於 IOI、APIO 等國際 OI 賽事（特別是 CMS 平台的競賽）。

Gap

UOJ #206.【APIO2016】Gap

有 \(N\) 個嚴格遞增的非負整數 \(a_1,a_2,\cdots,a_N (0\leq a_1<a2<\cdots<a_N\leq 10^{18})\)。你需要找出 \(a_{i+1}−a_i (0\leq i\leq N−1)\) 裏的最大的值。

你的程序不能直接讀入這個整數序列，但是你可以通過給定的函數來查詢該序列的信息。關於查詢函數的細節，請根據你所使用的語言，參考下面的實現細節部分。

你需要實現一個函數，該函數返回 \(a_{i+1}−a_i (0\leq i\leq N−1)\) 中的最大值。

對於這類題目，選手只需編寫一個特定的函數完成某項任務，它通過調用給定的若干輔助函數來進行交互。為了便於選手在本地測試，題目會下發一個頭文件與一個參考測評程序 grader.cpp（對於 Pascal 語言是一個庫 graderlib），選手將自己的程序與 grader.cpp 一同編譯方可得到可執行文件。

1
2
g++ grader.cpp my_solution.cpp -o my_solution -Wall -O2
./my_solution   # 執行程序

編譯得到的程序表現與傳統題程序類似。它會打開固定的文件，以固定的格式讀取數據，調用選手編寫的函數，並將結果和若干信息（例如詢問的次數、答案正確性）顯示在標準輸出上。

實際測評時，選手的程序會與一個不同的 grader.cpp 編譯。這個 grader.cpp 將以類似的方式調用選手編寫的函數，並記錄其得分。一般來説，這個版本的 grader.cpp 所有全局符號都會設為 static，也即不能通過沖突命名的方式破解它，但是任何嘗試突破 grader 限制的行為都會被判失格 (disqualification)。

差別

STDIO 交互的一個明顯優勢在於它可以支持任何編程語言，但是輸入輸出的耗時容易成為問題設計的瓶頸，導致有時無法區分程序的時間效率差別；Grader 交互則恰好相反，由於函數調用的開銷不大，常常可以允許 \(10^6\) 數量級的詢問次數，但是語言的限制是其短板。

如果自己設計題目或舉辦比賽，需要對二者認真權衡和比較。

通信題

通信題 是需要兩個選手程序進行通信，合作完成某項任務的題目。第一個程序接收問題的輸入，併產生某些輸出；第二個程序的輸入會與第一個的輸出相關（有時是原封不動地作為一個參數，有時會由評測端處理得到），它需要產生問題的解。

通信題的例子有：UOJ #178. 新年的賀電，#454.【UER #8】打雪仗 等。

本地測試的方法由於題目設定的不同而多種多樣，常用的形式如：

  • 手工輸入
  • 編寫一個輔助程序，轉換第一個程序的輸出到第二個程序的輸入
  • 用雙向管道將兩個程序的標準輸入/輸出連接起來

由於評測平台對於通信題的支持有限，因而目前為止，通信題只常見於 IOI 系列賽和 UOJ 等少數在線平台舉辦的比賽。它仍是一個有待探索的領域。

函數補全題

函數補全題 是需要選手補全程序的題目。可以理解為在一道交互題中，題目給定了選手代碼，要求編寫輔助函數。

通常有以下幾種形式：

  • 給定一個程序，並告知要求補全的代碼塊將被嵌入在哪裏。
  • 不給出程序，而將輸入信息作為待提交函數的參數。

這種題在 LeetCode 和 PTA - 拼題 A 上比較多見。

其他類型

Quine

Quine

寫一個程序，使其能輸出自己的源代碼。

代碼中必須至少包含十個可見字符。

題目很經典，但是在絕大多數 OJ 上都很難實現。

參考代碼

注意：源代碼不包含下方第一行（即 // clang-format off）。

1
2
3
4
5
6
// clang-format off
#include<cstdio>

char *s={"#include<cstdio>%cchar *s={%c%s%c};%cint main(){printf(s,10,34,s,34,10);return 0;}"};

int main(){printf(s,10,34,s,34,10);return 0;}

參考資料與註釋

  1. 因為技術上和資源上的限制，一道題目的測試點大多數情況下不能覆蓋滿足數據範圍的全部數據。 ↩

  2. 對於 Python 這樣的解釋性語言則直接由解釋器解釋運行程序。 ↩

  3. 事實上評測系統的實現遠比這個複雜，這裏只是大概介紹了評測系統的評測過程。 ↩

  4. 準確來説，一般是程序的用户態時間。 ↩

  5. 這裏的評測結果大多也適用於其他類型題目。 ↩

  6. 大多數評測系統會將 PE 狀態歸到 WA 狀態當中。 ↩

  7. 一些測試點可能會有部分分，選手在完成一個測試點的部分任務，或者選手的輸出正確但不夠優的情況下，可以獲得一定比例的分數。 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：StudyingFather, NachtgeistW, countercurrent-time, Ir1d, H-J-Granger, Chrogeek, sshwy, Suyun514, hsfzLZH1, CBW2007, Xeonacid, kawa-yoiko, Konano
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用