2023 Zerojudge 愚人節大賽 題解

2023 Zerojudge 愚人節大賽結束了，不知道大家打得如何。

若有意見反饋，可進入此連結填表單。

因為有些題目會進入其他練習題，但是沒有權限就進不去，因此大多數題目都設成不公開了。

p1：

$\text{April Fool}$ 的字串題

出題：becaido
首殺：[e-mail]

對題目中的

$s$ 點右鍵，查看 TeX Commands，會發現這個東西：

進入隱藏的連結，會發現題目敘述，接下來就可以 dp 了。

從題目標題有 $$ 也可以想到做法跟

$LATEX$ 有關。

code

#include <bits/stdc++.h>
using namespace std;

const int MOD = 10007;

string s;
int dp[5];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> s;
    dp[0] = 1;
    for (char c : s) {
        if (c == 'f') (dp[1] += dp[0]) %= MOD;
        if (c == 'o') (dp[3] += dp[2]) %= MOD, (dp[2] += dp[1]) %= MOD;
        if (c == 'l') (dp[4] += dp[3]) %= MOD;
    }
    cout << dp[4] << '\n';
}

p2：杰哥不要

出題：Ststone
首殺：bitset

這題不是互動題，因為在Zerojudge上目前是不可能做出互動程式的。換句話說，不管你選擇杰哥或阿偉，每一筆測資的輸入都會長一樣。

如果你選擇當杰哥的話，因為測資的輸入是固定的，所以理論上阿偉一定跑不掉，這當然存在很多種解法可以處理，但這裡就只提供其中一種做法。你可以事先讀入阿偉會走的路徑，並且先去阿偉第

$100$ 個會走到的點，就停在那邊等阿偉就會贏了。

如果選擇當阿偉的話，你當然也可以試著乖乖逃離杰哥，這樣也是有機會得到分數的，評分程式並沒有邪惡到會把你的輸出（阿偉要走的路徑）事先讀取起來，而是與阿偉一同移動。但是杰哥會想辦法縮短與阿偉的距離，但是在以下情況，杰哥也不一定能抓到阿偉：

阿偉
	杰哥

而這裡還開了一個小玩笑，如果你選擇當阿偉，且照著選擇當杰哥時，輸入給定的路徑移動阿偉的話，評分程式會讓杰哥自動避開阿偉而讓你拿到AC。

code (杰哥 version)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int xa,ya,xb,yb;
    cin >> xa >> ya >> xb >> yb;
    int xg,yg;
    for(int i=0;i<100;i++) cin >> xg >> yg;
    cout << 1 << '\n';
    for(int i=0;i<100;i++){
        if(xb>xg) xb--;
        else if(xb<xg) xb++;
        else if(yb>yg) yb--;
        else if(yb<yg) yb++;
        cout << xb << ' ' << yb << '\n';
    }
}

code (阿偉 version)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int xa,ya,xb,yb,x,y;
    cin >> xa >> ya >> xb >> yb;
    cout << 0 << '\n';
    for(int i=0;i<100;i++){
        cin >> x >> y;
        cout << x << ' ' << y << '\n';
    }
}

p3：ZJ 房地產

出題：becaido
首殺：LittleOrange666

如果把每個題目當成一個節點，每個通道當成節點間的邊，那這些題目就會組成一棵樹。

在遍歷完之後可以發現樹長這樣：

那就可以輸出每個

$t$ 的答案了。

$t=0$，請輸出這棵樹有幾個連通塊。
顯然是

$1$。

$t=1$，請輸出這棵樹的節點數。
共有

$13$ 個節點。

$t=2$，請輸出這棵樹的邊數。
共有

$12$ 條邊。

$t=3$，請輸出這棵樹的最大獨立集。
暴力枚舉或是 dp 後可以發現最大獨立集為

$8$。

$t=4$，請輸出這棵樹的最小點覆蓋。
暴力枚舉或是 dp 後可以發現最小點覆蓋為

$5$，或是可以發現樹其實是二分圖，最大獨立集

$+$ 最小點覆蓋

$=n$。

$t=5$，請輸出這棵樹的最大匹配數。
暴力枚舉或是 dp 後可以發現最大匹配數為

$5$，或是利用二分圖的最大匹配數

$=$ 最小點覆蓋。

$t=6$，請輸出這棵樹的直徑。
dfs 或 dp 後可以發現為

$8$。

$t=7$，請輸出這棵樹的嚴格次長直徑(端點不一定要是葉節點)。

$8-1=7$。

$t=8$，請輸出這棵樹有幾種對節點塗黑色 or 白色的方法，使得這棵樹上剛好有一個皆為黑色節點的極大連通塊。
定根在隨便一點，令

${\text{dp}}_v$ 代表考慮

$v$ 這個子樹，

$v$ 塗成黑色且剛好有一個黑色連通塊的方法數，若

$v$ 沒有子節點，

${\text{dp}}_v=1$，否則

${\text{dp}}_v=\prod _{\text{son}}({\text{dp}}_{\text{son}}+1)$。
最終答案為

$\sum _{i=1}^n{\text{dp}}_i=296$。

$t=9$，請輸出砍掉樹上的其中一條邊，再另外加上一條邊回去使其保持連通，透過這個操作減少樹的直徑，可以使樹直徑最小為何？
可以自己接接看、暴力枚舉，或是換根 dp，發現答案是

$5$。
dp 的做法是假設這條邊連接

$u,v$，

$u,v$ 兩棵樹的直徑分別是

$\text{d}(u),\text{d}(v)$，那答案會是

$max(\text{d}(u),\text{d}(v),\lceil \frac{\text{d}(u)}{2}\rceil +\lceil \frac{\text{d}(v)}{2}\rceil +1)$，維護一大堆東西就可以做到 O(n) 了。

然後這一題除了

$t=8$ 答案有點大之外，其他都很小，所以你如果一個一個試也有可能 AC。

code

#include <bits/stdc++.h>
using namespace std;

const int ans[] = {1, 13, 12, 8, 5, 5, 8, 7, 296, 5};

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    cout << ans[n] << '\n';
}

p4：ZJ 抄人

出題：becaido
首殺：lw310659

這題的標籤有 2-step，但是 ZJ 根本沒有這個功能，讓人不禁懷疑是不是根本可以唬爛。

另一個線索是題目叫你 include 的函式庫還有實作的函式名稱寫正常題都會用到，所以這題會不會只是一個正常題？

題目輸入

$0s$ 的時候，你只要輸出一個長度為

$16$ 的任意 01 字串

$s^{\prime }$，系統會給你

$1f(s^{\prime })$，輸入檔都是固定的，所以

$f(s^{\prime })$ 是固定的而且不重要，你只要再輸出

$s$ 就能 AC 了。

code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    string s;
    cin >> s >> s;
    cout << string(16, '0') << '\n';
    cout << s << '\n';
}

p5：ZJ 的禁忌祕術

出題：becaido
首殺：lw310659

此題會叫「禁忌祕術」是因為用到了 Zerojudge 使用者在競賽中可以看得到隱藏題的特性 (p3, p6 也有用到)，你會發現題目給你的字串都是 ZJ 的題目名稱，編號分別是

$\text{a172, b173, c174, d175, e176, f177, g178, h179, i180, k182}$，唯獨少了

$\text{j181}$。

進入「j181 - 消失的帕斯卡」後可以看到一些敘述，其中一個很奇怪的東西是裡面有一個圖片寫 2841，點進去這個圖片後會看到它的網址是 https://zerojudge.tw/ShowImage?id=3117 ，把 3117 改成 2841 後會看到這張圖片：

輸出維基百科裡的程式碼就能 AC 了。

此題還用到了 ZJ 的另一個特性，在 ZJ 輸入圖片編號可以看到已刪除的圖片或是隱藏題的圖片。

這題會叫消失的帕斯卡是因為 Zerojudge 曾經可以寫 Pascal，現在不能寫了。而且去 Pascal 的墓 (解題動態) 真的要花很多時間，還會讓 judge 卡住。

code

#include <bits/stdc++.h>
using namespace std;

const string s = R"(Program HelloWorld(output);
begin
  writeln('Hello, world!')
 {程序块的最后一条语句后不需要";" - 
   如果添加一个";"会在程序中增加一个“空语句”}
end.
)";

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cout << s;
}

p6：孤獨搖滾

出題：Ststone
首殺：Fysty

在Zerojudge的題目中插入圖片，其實用的是<img src="">，而我們其實可以偷偷塞入不是圖片的連結，這樣看起來就會是破圖。然而Zerojudge可以在題目中手動修改html程式碼，於是如果在外面又包了一層<a href="">，就可以誘導人去點擊圖片然後被Rick Roll了。

如果你是直接點開三扇門的話，你會去到 https://reurl.cc/rL07YE ，而若你是點擊右鍵開啟圖片的話，三扇門分別會對應到第一扇門 第二扇門 第三扇門 ，其中的第三扇門才是這題的題目。

而我們可以發現其實這是一個不能經過相同點的一筆畫問題，其中點是數字，邊是倍數關係。

而若要能一筆畫走完且不能經過相同的點， 與

$1$ 這個點連接的邊最多只會有

$2$ 條被走到（入邊和出邊），也就是說，如果把點

$1$ 拔掉後，聯通塊數量

$\ge 3$ 就無解。而觀察之後就可以發現其實case數很少，答案如下表：

N	Ans
$1$	$1$
$2$	$1,2$
$3$	$2,3,1$
$4$	$2,4,1,3$
$5$	$-1$
$6$	$3,6,2,4,1,5$
$\ge 7$	$-1$

然後由於

$N$ 可能很大，所以你可能要用字串輸入

$N$ 會比較好。

code

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    string s;
    cin >> s;
    if (s == "1") cout << "1\n";
    else if (s == "2") cout << "1 2\n";
    else if (s == "3") cout << "2 1 3\n";
    else if (s == "4") cout << "2 4 1 3\n";
    else if (s == "6") cout << "3 6 2 4 1 5\n";
    else cout << "-1\n";
}

p7：ㄆㄧㄑㄧ

出題：becaido
首殺：lw310659

題目內容那麼一大串，可以看到強調的是 "Mountains and valleys"，標籤有 "dmoj"，題目名稱又叫 "p7"，那在網路上就能查到這一題。

題目給了

$a,b$，而且

$1\le a\le 41$，如果你很會通靈，那你會發現截至 4/1 AC 的 submission 有

$41$ 筆，看了範測之後可以推論出

$b=0$ 時，你要輸出第

$a$ 筆 AC submission 的執行時間，

$b=1$ 時，要輸出第

$a$ 筆 AC submission 的記憶體用量。

code

#include <bits/stdc++.h>
using namespace std;

const double ans[] = {17.77,169.1,
                      17.32,168.0,
                      57.88,355.6,
                      71.63,382.4,
                      17.58,169.1,
                      74.75,142.1,
                      63.69,342.5,
                      61.46,342.6,
                      17.27,167.1,
                      17.25,167.1,
                      49.27,298.3,
                      45.27,140.1,
                      54.19,355.6,
                      68.63,304.6,
                      68.99,375.3,
                      67.46,382.8,
                      67.33,382.9,
                      66.97,305.2,
                      64.83,304.6,
                      67.45,327.1,
                      64.58,327.3,
                      29.75,231.7,
                      24.60,197.9,
                      32.27,176.0,
                      33.20,176.1,
                      45.07,486.1,
                      44.12,488.9,
                      44.06,488.9,
                      70.10,328.2,
                      71.88,357.6,
                      71.08,357.6,
                      69.91,356.7,
                      64.51,356.6,
                      61.77,196.4,
                      28.95,197.3,
                      57.11,195.6,
                      28.15,300.1,
                      25.59,203.0,
                      20.27,161.9,
                      39.59,352.9,
                      63.48,335.6};

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int tt;
    cin >> tt;
    while (tt--) {
        int a, b;
        cin >> a >> b;
        cout << fixed << setprecision(b == 0 ? 2 : 1) << ans[2 * (a - 1) + b] << '\n';
    }
}

p8：一起來寫詩

出題：Ststone
首殺：baluteshih

我知道這題很煩很搞人，但這是故意的。

希望答題者可以在有限的線索下找到這題的評分系統其實存在著某些特性。

「每個字的美麗度以及淒涼度是固定的。」

這句話想表達的是，可以透過測試單個字元，來獲得該字元的美麗度及淒涼度的得分區間。而其實也可以測試看看傳送同樣的字元但是不同的數量，會獲得完全一樣的結果。

「如果一首詩裡面有些部分過於美麗，那在單單評論美麗度時，不夠美麗的部分會被蓋掉。」
「如果一首詩裡面有些部分過於淒涼，那在單單評論淒涼度時，不夠淒涼的部分會被蓋掉。」

這兩句話想表達的是，你如果找到了某個字元在「美麗度」的表現特別好，而某個字元在「淒涼度」的表現特別好，你可以將這兩個字元混和輸出，你的詩就會同時有好的「美麗度」以及好的「淒涼度」。

詞語的契合度與任意兩個相鄰的字之間有關係。

根據這個條件，要提高這一項的分數，其實有很多種方法可以來突破，你可以測試單一字元在該項目的評分（契合度是相同的單一字元之間的關係）或是任意兩個字元在該項目的評分（契合度是該兩字元之間的關係），然後找到一組得分高的之後，不需要管他們的「美麗」以及「淒涼」程度，混和上面找到的詩一起輸出，如果得分太低就調整一下比例。

如果一首詩的美麗與淒涼程度差異越大或越小，那臨末就會越喜歡它。

這個條件其實只是為了讓一首隨機生成的詩分數不會太慘而設計的，然後又不希望這個項目的評分會成為無法讓人 AC 的最後一根稻草，於是就變成了這樣。當你找到一首「美麗度」與「淒涼度」都很高分的詩的時候，這項分數自然也會很高。

這裡最後再來講一下評分程式的詳細評分方式。

美麗/淒涼度：評分程式會根據答題者輸出的詩的每個字元，轉成ASCII Code之後代入某個函數計算出該字的美麗/淒涼度，並且取前

$100$ 個美麗/淒涼的字，取平均四捨五入後成為該首詩的美麗/淒涼度。

契合度：評分程式會根據答題者輸出的詩的每組相鄰字元，轉成ASCII Code之後代入某個函數計算出該組字的契合度，並且將所有得到的契合度取平均四捨五入後成為該首詩的契合度。

喜愛程度：計算公式為

$2\times |50-$

$|$該首詩的美麗度

$-$ 該首詩的淒涼度

$||$。

code

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    for(int i=0;i<100;i++) cout << '*';
    for(int i=0;i<100;i++) cout << '7';
    for(int i=0;i<800;i++) cout << 'b';
}

p9：字串壓縮

出題：becaido
首殺：Fysty

輸出說明只有一個 0123456789，那會什麼要「字串壓縮」呢？實際把這個字串複製下來後，你會發現它其實有很多零寬空格，你如果直接輸出會超過 ZJ 程式碼的長度限制。

分析這個字串後能知道兩個數字分別間有

$4,8,7,6,3,10000,1,1,1$ 個零寬空格，得到這個資訊後就能順利在程式碼長度限制下 AC 了！

在 ZJ 上輸出零寬空格的方法有很多種，可以輸出 "\u200B" 或直接輸出 "​"(零寬空格)。

code

#include <bits/stdc++.h>
using namespace std;

const int len[] = {4, 8, 7, 6, 3, 10000, 1, 1, 1, 0};

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    for (int i = 0; i <= 9; i++) {
        cout << i;
        for (int j = 1; j <= len[i]; j++) cout << "​";
    }
}

p10：lIll III lIll ll

出題：Ststone
首殺：lw310659

題目標籤裡面有ㄌㄌ，提示裡還放了一張智乃的圖片，於是可以先猜題目應該跟ㄌㄌ有關。而題目名稱是lIll III lIll ll，看起來像是4個字，有什麼東西跟ㄌㄌ有關又是4個字的呢？那就是包含4個字母的LOLI。

這其實是把英文用摩斯密碼加密後的結果，其中l代表.，I代表-，解密後你會得到
The/input/contains/two/integers/A/and/B/,/please/output/two/numbers/C/and/D/,/so/that/A/times/B/times/C/times/D/is/a/prime/number/not/exceeding/48763/./
但是要怎麼輸出數字之後還可以讓

$a\times b\times c\times d$還是一個質數呢？我們可以考慮使用浮點數。

你可以輸出類似

$\frac{1}{a}$

$\frac{2}{b}$之類的結果。但考慮到就算答題者輸出的精度非常精確，但評測程式對於使用者輸出的精度會有所削減，但是沒錯！這題就是要利用這個特性。你只要有辦法「騙過」評測程式，使最後乘起來的結果使用比較運算子==時與整數相等，那你就會獲得AC。

但以結論上來說，卡精度似乎有點太過頭了，於是只要程式判定後發現誤差在

${10}^{-15}$ 以內就會獲得 AC 。

code

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long double a,b;
    cin >> a >> b;
    cout << setprecision(30) << fixed << 2/a << ' ' << 1/b << '\n';
}

p11：公開的 Special Judge

出題：becaido
首殺：lw310659

從給你的圖片可以知道

$\text{result}$ 必須等於 $JUDGE_RESULT=AC (或是你有在 ZJ 出過 special judge 也可以知道)。

在 ZJ 上的 RAND_MAX 是

$2^{31}-1$，rand() >> 16 最大會到

$30000$ 多，可是限制 pos 只能

$<10000$，所以你要找出一個

$\text{seed}$ (

$0\le \text{seed}\le {10}^8$) 使得前

$16$ 次的 rand() >> 16 都

$<10000$。

如果你的電腦的 RAND_MAX 不是

$2^{31}-1$，那就不能在本機跑，在 ZJ 上跑有一些缺點，像是執行時間最多只有

$3$ 秒，輸出

$24$ 個字元之後就會 …略，每隔

$30$ 才能傳一次 submission。

那要怎麼辦呢？我的做法是在

$\text{atcoder}$ 上跑，因為

$\text{atcoder}$ 的 RAND_MAX 是

$2^{31}-1$，在 Custom Test 最多可以輸出

$2048$ 個字元，而且可以跑大約

$10$ 秒，而且沒有間隔限制。在其他 RAND_MAX 是

$2^{31}-1$ 的 OJ 或 IDE 上跑應該也會有相同的結果。

暴搜之後就會發現前滿足條件的

$\text{seed}$ 有

$7029175,33867693$。

code

#include <bits/stdc++.h>
using namespace std;

const int seed = 7029175;
const string code = "$JUDGE_RESULT=AC";

string s;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    srand(seed);
    s = string(10000, 'a');
    for (int i = 0; i < code.size(); i++) s[rand() >> 16] = code[i];
    cout << s << ' ' << seed << ' ' << code.size() << '\n';
}

p12：小排序

出題：becaido
首殺：lw310659

這題可能是這場比賽最正常，但做法最奇怪的一題。

對於

$25\mathrm{\%}$ 的測資，只要宣告一個大小為

${10}^5$ 的陣列，輸入進來

$\text{sort}$ 它就好了。

對於

$75\mathrm{\%}$ 的測資，大小

${10}^6$ 的陣列會超過記憶體限制，那要怎麼做呢？

如果可以掃這個陣列很多次，或許就會有一點想法了，那在 ZJ 上有很多種方法可以重製 stdin，出題者的做法是用 rewind(stdin)。

每次掃過陣列後輸出還沒輸出過的前

$k$ 小的數字，那掃

$\frac{n}{k}$ 次陣列就能輸出完整個陣列了。

至於要如何找前

$k$ 小，方法可能有很多種，出題者的做法是利用

$\text{heap}$。

如果直接宣告一個

$\text{priority\_queue}$ 會直接 RE，可以用陣列代替，C++ 在 <algorithm> 裡有 push_heap, pop_heap 兩個函式，當 size 超過

$k$ 的時候就 pop_heap，最後

$\text{sort}$ 完這個陣列就可以輸出此輪最小的

$k$ 個數字了。

時間複雜度

$O(\frac{n^2}{k}\times \log (k))$，這裡

$k$ 可以取

${10}^5$，有一點要注意，就是輸入的量級到了

$O(\frac{n^2}{k})$，所以可能要用一些輸入輸出優化。

此題的靈感來源是這一題，既然可以輸出第

$k$ 大，那為何不能排序呢？

code

#include <cstdio>
#include <unistd.h>
#include <algorithm>

const int B = 1 << 15;

char input[B], output[B];
char *p1 = input, *p2 = input;
int p3;

inline char readchar() {
    return p1 == p2 && (p2 = (p1 = input) + read(0, input, B), p1 == p2) ? -1 : *p1++;
}
inline void writechar(char c) {
    output[p3++] = c;
    if (p3 > B - 10) {
        write(1, output, p3);
        p3 = 0;
    }
}
inline int in() {
    int val = 0;
    char c = readchar();
    while (c == ' ' || c == '\n') c = readchar();
    while (c >= '0' && c <= '9') {
        val = 10 * val + c - '0';
        c = readchar();
    }
    return val;
}
inline void out(int x) {
    char s[10];
    int p = 0;
    do {
        s[p++] = '0' + x % 10;
        x /= 10;
    } while (x);
    for (--p; p >= 0; p--) writechar(s[p]);
    writechar(' ');
}

const int K = 1e5;

int n, sz, cur;
int mx = -1, a[K + 5];

int main() {
    n = in();
    while (cur < n) {
        rewind(stdin);
        p1 = p2 = input;
        n = in();
        sz = 0;
        for (int i = 1; i <= n; i++) {
            int x = in();
            if (x <= mx) continue;
            a[++sz] = x;
            std::push_heap(a + 1, a + sz + 1);
            if (sz > K) {
                std::pop_heap(a + 1, a + sz + 1);
                sz--;
            }
        }
        std::sort(a + 1, a + sz + 1);
        cur += sz;
        mx = a[sz];
        for (int i = 1; i <= sz; i++) out(a[i]);
    }
    write(1, output, p3);
}