全國模擬賽 2021

Created2021-12-05Updated2021-12-05

最後一次的全國賽要下來了
最近因為外務有點多，事實上沒有花到高二那麼多的時間準備
總之還是蠻感謝學長們提供優質的比賽給我們打> <

賽前策略

測機

練打模板:

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
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define X first
#define Y second
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
    cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
    for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
#ifndef EVAL
#define test(x...) abc("[" + string(#x) + "]", x);
#else
#define test(x...) void(0);
#endif
const int N = 200000;

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
}

測本機 & judge 速度

(0) 模運算、加法、乘法
(1) vector、array 常數

設定codeblock (字體consolas、編譯快捷鍵)

__int128

正賽

  1. 花約半小時打模板 + 看完所有題目，後面題目記得看部分分，然後稍微想一下第一直覺的想法，並把水題(馬上有好實作解的題目)挑出來

  2. 先把水題寫完，剩下題目每次留三題最可做 or 部分分少的題目輪流想，一題想20分鐘，時間到就要跳，不能一直停在某題

  3. 前三小時思考盡量以滿分解為主，最後兩小時以難題的部分分為主

比賽可能的狀況

滿分解WA

  1. 去趟廁所，花5分鐘先看過一遍code，看看有沒有刻爆
  2. 重新想自己的想法有沒有爛，構構看反例
  3. 寫對拍
  4. 除蟲時間最多20分鐘，一到就要跳

TLE

  1. 花5分鐘先看過一遍code，看看有沒有刻爆
  2. 本機生大測資，看是想法爛還是卡常
  3. 卡常：線段樹 -> BIT or 靜置、vector -> array

RE / MLE

  1. 戳到陣列外面
  2. assert

judge爛了

不確定的題目先寫對拍簡單驗一下

其他事項

  1. 遇到大實作 or 大資節題先想清楚脈絡再寫

  2. 記得上廁所

  3. 檔名存好，之後對拍較方便

  4. 吃飯deadline：12:30

模擬賽

題本

比賽過程

首先開賽前20分鐘就一樣打模板 + 讀題目，看完的一些想法：

pA 看四個方向 map / set 維護
pB DAG DP
pC 四個方向stack單調隊列
pD 一臉bitset背包 想起了三模的陰影
pE 沒想法
pF 看完發現有點像這題CF 但我之前想很久都不會那題欸 慘
pG snell’s law 滿分解一臉會卡精度的樣子
pH greedy/dp 但感覺subtask不難
pI 鍊22可以拿

可能有人會問說為什麼可以看得那麼快
因為我讀題第一遍真的只是把題目 + 難題部分分看完
然後把直覺的方向寫下來而已=w=
這也是為啥pE看完第一遍沒啥想法

首先先從簡單的pA開始，寫完丟

[00:29:33] pA TLE 65

看到TLE愣了一下 仔細想想n≤106n \leq 10^6好像真的會被卡map/set常數
改成set又丟一次還是不行就果斷跳了

之後順順的寫完pB

[00:38:02] pB AC 100

然後pC被數學卡了一下，WA了幾次後去了廁所，回來改一下就過了

[00:55:37] pC AC 100

之後到了pD，想了一下開2e8的bool會不會爆空間，確定不會就直接開寫

[01:20:26] pD AC 100

寫完這裡之後回去看了pA，忽然想到sort常數小可能有機會過

[01:23:30] pA AC 100

當下看到AC其實蠻氣的，到底在卡三小常數= =
不過師大確實很容易卡常，就算了吧= =

接下來看了一下部分分，決定從pE開始想
不到兩分鐘就想到觀察：

  1. 當刪除kk個人時，群組人數≥k\geq k的人都會rotate kk次
  2. 每一群人的相對位置是不變的

這也導出一個簡單的BIT + 二分搜做法，但我二分搜實作有點燒雞，寫了一陣子才過範測

[01:51:26] pE WA 0

看到0分愣了一下 不過運氣不錯去趟廁所回來馬上想到邊界會爛

[01:54:01] pE AC 100

接著考慮部分分太少，繼續想pF

pF直覺是greedy，想了一陣子想到了重要的觀察：

若存在至少一組合法解，則必存在一組合法解使的他是某個dfs序

有了這個，合理會想要去做樹dp，然後結論就出來了：

dpvdp_v代表將vv的子樹葉子全部跳完後，最後所能停留的最小深度

之後回朔答案就順著做一遍就好

[02:17:21] pF WA 0

又去了一次廁所，發現回朔寫爛

[02:24:55] pF TLE 23

看到這種怪結果愣了一下，仔細看一下題目忽然不確定題目的意思到底484樹，就決定寫個dsu assert看看

[02:28:57] pF AC 100

然後就過了???

後來又多丟了一次原本TLE 23的那份，結果就變AC= =

不過就算了吧，沒管那麼多

到這裡半場600算是很不錯，總之偷偷休息了大概五分鐘繼續想pG

直覺就是snell’s law砸下去，但因為我物理不好所以還是寫了n=2n = 2的case驗了一下

[02:54:57] pG 23

確定沒問題就直接開寫二分搜

[03:10:45] pG WA 61

不意外被卡精度，亂改一下砸不過就先放著了，畢竟感覺61也夠多了

之後開始回去想pH的subtask 1 + 2，一開始以為單調隊列可以直接做完，結果寫到一半才發現不對

燒雞的同時想起還有pI的水分可以喇，就先去喇了

先把暴力dfs和暴力dfs寫掉

[03:39:56] pI 7

[03:50:59] pI 12

然後想到pH subtask1的greedy

[03:55:24] pH WA 0

改了一下先丟著，這裡剩一小時了，因為知道自己greedy不好，決定先去寫自己有把握的pI 22

[04:25:18] pI 22

然後回來一眼就看到pH哪裡爛了= =

[04:33:00] pH 12

接著剩下大概半小時就是全力想pH subtask2或subtask3
後面感覺subtask3比較簡單是對的，但就是燒雞只會亂砸解= =
傳了幾筆WA後比賽就結束了

成績

Score 714 / 900
rk 1

總之是莫名拿了一個第一名 開心> <

這場算是少數打的不錯的場了吧，策略也都實施的蠻好的

整場除了pH 24以外沒有少拿什麼分數，雖然賽後聽解真的會覺得自己是笨蛋= =

希望全國賽也能保持這場的節奏> <