TOI 2021 初選心得

Created2021-03-08Updated2021-03-08

成績：rk 10 Score 241/500

進了是進了，但還是覺得打得有點糟@@

題目的話可以看金刀這裡有Po
就不再重複講ㄌ

早上

早上搭火車去，在車上把一些模版稍微再看一下
中午在摩斯度過，然後等時間差不多就一群人(7個)走到師大
然後迷路了一下總算找到了
我還是覺得我很厲害，連續兩年走到同一個錯的地方= =

開場策略

  1. 先把題目讀完，看到簽到題直接寫掉，順便打模版
  2. 讀完之後挑幾題較有想法的想，前兩小時以滿分解為主，之後再喇部分分

(會這樣配是因為我對我喇分能力還算有把握 + 入營考部分分不會到太刁鑽，覺得一個小時夠)
然後就開始唄

比賽過程

開場讀了A，發現A就是簽到，調了一下設定打完模版後AC
然後繼續讀題目

pB 沒想法
pC 沒想法
pD 沒想法
pE 一臉flow樣，然後炮打皮皮輸出解有60分?_?

考量到pB的部分分真的很少，所以我決定先想pB
結果想了10分鐘還是沒想法，有夠可撥
於是決定轉換心情去看pC
再看一次發現pC只是要找最大字典序的lis而已，直接開刻滿分解

寫完大概40分鐘吧，直接丟

WA Score: 0

因為扣很短，2分鐘就又檢查了一遍，還是沒看到錯
現在就回到一個大問題
「我到底要繼續de pC還是跳過」
我賽前有預想過這種情況，當時我決定要跳題
所以理所當然比賽當下也跳了，去想了pD
pD想了不到3分鐘就精神掉了，還好樹剖這個想法在我腦袋只停留不到30秒= =
但是實作好煩躁，簡單來說就是一題狗幹實作題
但我當下因為沒其他題可做，又不想繼續陷在pC裡，就只好直接硬上了

然而再刻pD的時候，我的腦袋卻一直在想pC
「de個bug就有100分了，真的不拿嗎？」
這個想法一直出現在我的腦袋
所以事實上，我寫pD沒多久就會回去看一下pC，也因為這樣實作速度減慢不少
結果最後時間過快一半了，pC還是掛蛋，pD才刻完lca下往上的部分，而且還沒有把握正確性
之後心態就有點小炸，pC和pD都不想管了，決定去寫pE的炮打皮皮

因為流之前校內賽已經背下來了，也刻的蠻快的，所以就直接刻流，沒有考慮匈牙利
(現在想一想我真滴好毒，匹配用流解)
寫一寫之後發現自己不會輸出解
(我到賽後才知道沒輸出解也會有分= =)
想了一下IOIC上的構法，但跑範測發現都有問題

然後就瀕臨崩潰邊緣
90分鐘過去了，只有簽到題的100分
我TM484沒救了？
剛好看到有人提早交，當下真的有股衝動要直接交出去不考了
還好沒做(?

為了平復心情，我去了趟廁所
思緒真的很亂，不過回來之後感覺心情有好些
雖然覺得自己一定不會進，但還是決定開始喇分模式
先把pB的pq暴力模擬30分寫一寫，丟

TLE Score: 0

看到TLE愣了一下
想了很久沒想法，丟著

然後寫了一個n≤10n \leq 10的pC，拿到22分，然後還是太執著於那個滿分解
寫完22分直接瘋狂拿那份code對拍，對一對都沒對出來

然後跑去看pD，發現pD subtask2好肥，也很水
寫完之後丟

WA Score: 0

第二度感到絕望
現在大概剩50分鐘吧，我只有122，超可撥

休息一下調一下心態，決定回去看pB
發現是一個while寫爛
改掉之後順利拿回30分

然後就pC pD輪流看，pC還是一樣對不到拍，反而發現自己的暴力解好像寫爛了(?
所以當下直接認定那題有問題，直接繼續看pD
然後pD怎麼看都找不到錯，重看題目發現我subtask2看錯了，pi=1p_i = 1我以為是星狀圖的case
想了一下，發現lca找路徑長就好，還好之前的扣還沒刪，修一修之後直接丟，就拿到該拿的分數ㄌ

到這裡大概剩下10幾分鐘吧，我回去看之前寫的E
我看到我寫了Dinic
裡面有一個函式叫做bfsans，會從源點開始bfs，跑過還有流的邊，看有哪些點有被跑過

讀完之後我盯著想了五秒

阿這樣不就做完了？

快速打了輸出解，就拿到了該拿的分數(很肥的60分)

然後傳完剩兩分鐘，也不能做甚麼就結束了

最後分數 100/30/22/31/60

賽後

我比完估線會落在300上下，所以其實還蠻難過的
跟同學會和之後發現他們也都考爆了，一個200一個250
不過他們都AC2題，跟我這種純唬分的完全不同等級
然後想說一定不會進，就沒看板直接走人
在走到捷運站的路上還在跟同學說我要學測了之類的話
然後走到捷運站想說還是要面對就開了版看，意外發現線異常的低，只有200
集體燒雞(?

總之一個打得跌跌撞撞的、只AC簽到題的人還是成功進了選訓

再賽後

我打這篇的時候回想了一下賽中大概的情形
沒有到完全一樣，但應該很接近了
然後發現自己真的好抖
尤其看場外直播發現自己最後兩分鐘傳那60分才衝破線
該說還好我沒放棄嗎(?
然後我這場的精神分理論上應該是100/30/100/100/60的
只是因為pC的關係，pD也刻不下去，就這樣直接燒掉好多分
可能還要再多調整一下比賽的策略和心態吧~

最後

最後因為我到現在還是沒有找到我pC的反例
在這裡附上我的code
因為賽中看很久，所以應該沒有記錯
若有人能幫我找到錯哪的話我會非常感謝> <

UPD: Hacked by syl123456 \好電/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector <int> a(n), b(n);
    map <int, int> m1;
    for (int i = 0; i < n; ++i) cin >> a[i], m1[a[i]] = i;
    for (int i = 0; i < n; ++i) cin >> b[i], b[i] = m1[b[i]];
    vector <int> lis(n), v;
    for (int i = n - 1; ~i; --i) {
        if (v.empty() || b[i] < v.back()) v.push_back(b[i]), lis[i] = v.size();
        else {
            auto it = lower_bound(v.begin(), v.end(), b[i], greater<int>());
            lis[i] = it - v.begin() + 1;
            *it = b[i];
        }
    }
    int m = v.size();
    deque <int> dq[m + 1];
    for (int i = 0; i < n; ++i) {
        int j = lis[i];
        while (!dq[j].empty() && a[b[dq[j].back()]] < a[b[i]]) dq[j].pop_back();
        dq[j].push_back(i);
    }
    vector <int> ans;
    int lst = 0;
    for (int i = m; i > 0; --i) {
        while (dq[i].front() < lst) dq[i].pop_front();
        ans.push_back(a[b[dq[i].front()]]);
        lst = dq[i].front();
    }
    for (int i = 0; i < m; ++i) cout << ans[i] << " \n"[i == m - 1];
}